• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

RTS fog of war with huge maps

 
Greenhorn
Posts: 24
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I am making an RTS, with huge maps, 500000*500000, and I am looking to work on the fog of war aspect now.

I am also hoping to hundreds of ships, that will all have radar (circular), which will be their sight. What method for creating fog of war would be the best for simplicity, accuracy and efficiency? I am thinking that a tile-based method would require huge arrays, or be very innacurate, with 100*100 squares (which would still require 25 million cells)... not what I would be hoping for.

Also, it might be helpful to know the view size. The view size is always 1366*768 pixels, but the amount of x and y coordinates within the view varies on the zoom factor, which varies from 2000% to fitting the whole map on the screen (approximately 0.27% by 0.15%). So it might be best - if it was a tile-based method - to have a dynamic tile size, according to the zoom factor.

Any suggestions on how to go about this? Is there any more information you need?
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Alfie Noakes wrote:I am making an RTS, with huge maps, 500000*500000, and I am looking to work on the fog of war aspect now.


1. I assume, by RTS, you are referring to this, and not to one of the umpteen other things it could be.

2. 500,000*500,000 = 25,000,000,000, which is BIG, even by modern computer standards - almost a gig of space even if every piece of information can be stored in a single bit (which I doubt), so unless you come up with some sort of compression, I fear you'll be spending a lot of time "spinning your wheels".

I am also hoping to hundreds of ships, that will all have radar (circular), which will be their sight.


3. And now you've added hundreds of ships and "radar"...

I am thinking that a tile-based method would require huge arrays, or be very innacurate, with 100*100 squares (which would still require 25 million cells)...


4. I'm not sure how you get 25 million out of 100*100, but I guess you know what you want.

The view size is always 1366*768 pixels...


5. Which isn't square. Not necessarily a problem in itself, but it might be worth having your "board" conform to the same basic dimensions (ie, 16:9).

Do you see a theme here?

You're taking on waay too much at once: Astronomic sizes; hundreds of complex objects; involved capabilities... I have no doubt that you'll be adding sophisticated weapons at some point too.

Back up and lower your sights a bit: What do you want to do?

My suggestion would be to try a "proof of concept" first: Much smaller spaces (and I'd make them the same proportion as your screen); 3 ships (or maybe even just one to start with); maybe a grid of 4 viewing areas, or possibly 5, with the fifth one being the "centre", so that every area except the outside edge is covered by at least two "views".

Once you get that working, then start adding or expanding stuff; but while you're thinking in terms of billions you're likely to get stuck in "development paralysis".

HIH

Winston
 
Alfie Noakes
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Oh, no, I have all that implemented already. The ships do have weapons and do shoot each other, and all that sort of stuff. The map size is about what I want, it is meant to be very large scale, but I can alter that later anyway, whether it be bigger or smaller.

The 25 million cells was from the area of the map divided by the area of a single grid cell: (500000*500000)/(100*100)

Even with grid cells of 1000*1000, it seems to drastically reduce performance when I tried to implement a very crude method of fog of war: drawing black rectangles on spots where no ships could see. The frame rate dropped from 100+ to about 5-6.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Alfie Noakes wrote:Even with grid cells of 1000*1000, it seems to drastically reduce performance when I tried to implement a very crude method of fog of war: drawing black rectangles on spots where no ships could see. The frame rate dropped from 100+ to about 5-6.


Which is why I mentioned compression.

I suspect very strongly that for any "grid" of that size, 99.99% of your "cells" will be empty, so there doesn't seem much point in forcing a program to go through them all. I suspect that if I was designing something like this, I'd probably use a LinkedHashMap, eg:
LinkedHashMap<Coordinate, Cell>
to store my "grid". However, if the number of "not empty" cells exceeds a billion you might run into performance issues; but you're far more likely to run into space issues first.

Then again, I could be totally out to lunch on this; I'm not a "gamer".

Winston

PS: Even with a LinkedHashMap, working out which cells are part of you current "view" could be quite lengthy, so you might need to be more creative. A TreeMap might offer better performance for something like that. You might also want to look at BitSet if the only thing you're worried about is "empty" or not.
 
Marshal
Posts: 28193
95
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The 1970's term for what Winston describes is "sparse matrix". It's still a technology in use today and you could do a web search to find other ways to implement it.
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
How many total objects are we talking about anyway?

Bill
 
Alfie Noakes
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The total amount of ships at the moment is limited to 400, 100 for each team, but will hopefully increase to probably 1000 in total. Also, there would be structures, many without radar, which are also limited to 100 per team.
So a maximum of 800 objects with radar.

I had a quick look at sparse matrix on wikipedia, and it gave me an interesting idea. Because of the way I draw stuff in my game, I might be better off drawing a black rectangle to cover the view, and then subtract polygons from that depending on if it is in range of the ships that I draw.
What I normally do is, since I can zoom in quite far in a huge map, I only draw objects that will be visible in the view. So I could then only check the radar range of those visible objects, and from there I could subtract their view from the fog (big black rectangle).

If you have any suggestions on how to better that idea, or just a better idea, please feel free to suggest it.
 
Winston Gutkowski
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Alfie Noakes wrote:I had a quick look at sparse matrix on wikipedia, and it gave me an interesting idea. Because of the way I draw stuff in my game, I might be better off drawing a black rectangle to cover the view, and then subtract polygons from that depending on if it is in range of the ships that I draw.
What I normally do is, since I can zoom in quite far in a huge map, I only draw objects that will be visible in the view. So I could then only check the radar range of those visible objects, and from there I could subtract their view from the fog (big black rectangle).
If you have any suggestions on how to better that idea, or just a better idea, please feel free to suggest it.


As I say, I'm no expert, but could you not simply specify a black background, and then add objects to be displayed on top of that? I don't know, but if you can, I suspect it might be quicker than explicitly drawing a black rectangle. Also: I believe that Java now supports transparency, but whether you can make any use of it or not I don't know.

However, I'd definitely suggest you tackle one thing at a time. Work out how you're going to store your grid/"board" information first, then deal with the display.

HIH

Winston
 
William Brogden
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
With less than 1000 objects why bother with cells at all. Some simple sorting of references to objects in X, Y and Z will give you quick information on who is close to who. Presentation can be at any scale you want.

Bill
 
Alfie Noakes
Greenhorn
Posts: 24
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Ok, by referring to X, Y and Z, do you mean finding the distance between different objects' coordinates? If so, I only need X and Y - it's 2D. I think I could store a ArrayLists in each team that contains all of the visible ships and structures, by checking distances between enemy and friendly ships and structures.

Then, I when drawing friendly ships and structures, I normally determine if they're in view, and if so, then I draw them. At this stage, I could also create a circle Shape out of their radarRange, and then subtract that from the black rectangle that would cover the view. After all that has been done, after all of the subtractions, I can then draw that black (used to be a rectangle) to represent the fog.

The reason why I don't simply use a black background is because I already have a background that looks like space, so the method I have above would still allow the space background to be seen in the visible areas.

Although, I'm not sure how processor-intensive this will be with lots of ships and structures, so I should probably put it on a timer.

The transperancy idea could be good for areas that have been explored before, but I'll have to look up how to use it.

Thankyou for your suggestions, and keep them coming if you've got some.
 
William Brogden
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Ok, by referring to X, Y and Z, do you mean finding the distance between different objects' coordinates? If so, I only need X and Y - it's 2D. I think I could store a ArrayLists in each team that contains all of the visible ships and structures, by checking distances between enemy and friendly ships and structures.



By X and Y I mean coordinates in your space - perhaps long integers. IF you keep a sorted array of references to your objects for X coordinate and one for Y coordinate then locating possible visible objects simply means finding the N nearest neighbors in X and combining with the N nearest neighbors in Y - all other objects can't possibly be seen. Keep in mind that in Java it is relatively cheap to keep a variety of collections - multiple ways of looking at the same objects.

Working with that much smaller collection you can then do distance calculations - the time saving principle being don't do expensive calculations before you have the smallest possible list of objects.

Bill
 
reply
    Bookmark Topic Watch Topic
  • New Topic