"fog of war" algorithm

Newbie & Debugging Questions
#1

I have a simulation of shipping traffic around the world, which is displayed on a 3d globe via java opengl (my question has nothing to do with java opengl though). I would like to be able to evaluate which units can be “seen” by another team of units. The end effect is pretty much a fog of war. The unit’s positions are stored in spherical coordinates and I will probably just assess distances between units to determine if one can see the other. If a unit not owned by the user is seen by a unit “owned” by the user, this non-user unit will be rendered on the globe (along with all the user’s units). The problem is I would like there to be many units and for the evaluations to be carried out quite often. I have asked this question on another site and the only advice I got was to not model that many objects, which isn’t helpful. What I really want to know is what is the best way to make these evaluations given that I have a very large number of units that can be detected and units that are capable of detecting.

I am currently planning to take a list of all non-user units and iteratively consider whether or not each one can be seen. This involves taking one of the non-user units and then iterating through the user’s units to evaluate if one of them sees it. If none of the user units see it, the non-user unit is not flagged for rendering and I move on to evaluating the next non-user unit. If a user unit did see that non-user unit, I stop the evaluation, flag the unit, and move on to evaluating the next non-user unit.

I would appreciate any advice on how to make this better. Perhaps some heuristic tricks could be of use here.

#2

You could use something like a Binary Space Partition(BSP). You basically divide your entire game area into grids(cubes for 3D) and only check units that are in a grid that would be close enough to the user units.

#3

I had thought about using a technique like that to reduce making comparisons of units on opposite sides of the world, but I was concerned about how far the “line of sight” could be for some of the units. The users of the simulation will decide the parameters of the units (such as line of sight radius) and if possible I wouldn’t want there to be a maximum light of sight range just for flexibility’s sake. The performance benefits would probably be worth it though so maybe I will implement it in the end. Thanks for the suggestion.

Are there other improvements that anyone can think of?

#4

Just to a get the idea… how many units are we talking about?

Hundreds?
Thousands?
Millions?

Anyway, a 3D space partitioning system will do this for you easily.
Octtrees as easiest, but slightly less efficient than BSP-trees.

#5

The number of units (n) is really up to the end user. I really can’t conceive of n ever being less than 100 or more than a million. It depends on how complex the simulation needs to be. I would guess the “average” user would opt for around 1,000 to 10,000 units. An important point is that I am planning to have some units grouped together moving as one “super-unit” which would reduce the burden of the fog of war calculation. If I had to guess, I would say that in the limit as n goes to infinity I could probably expect a 10 fold drop in the number of units I have to run calculations on. It is possible that I may not have performance issues, but I would like to have a fairly efficient algorithm to start with.

I don’t need cube partitions since all the units are positioned on the surface of a sphere. Would it be best to divide up the units into lists representing portions of the earth’s surface area? It is easy to divide up the sphere surface into rectangles (like this: http://upload.wikimedia.org/wikipedia/commons/3/38/Sphere-wireframe.png) , but it might be best to just lump all of the polar regions into two lists because the rectangles get small at the poles and there will probably be little activity there. For a unit in a given rectangle, I would then see if any units in the adjacent rectangles can see it. I’m new to this, so perhaps you can think of a more efficient way to divide up the units.

#6

Well, you can indeed chop your surface into non-uniform areas (Object per area) only based on their spherical angles. You’d then store all neighbour areas in each area in an array (for example) along with the distance between the center-points. Using a simple floodfill-algorithm you’d easily rougly find all areas within a distance of X. Each area would ofcourse also have a list of units.

If you make your areas small enough, you can just have the user see all units in a certain set of areas. Otherwise you’ll have to start figuring out distances between units that probably see eachother. Not that hard.

But well, an octtree will solve this all for you, although it’s probably a bit harder to implement, yet it is probably more effictient… even though it’s overhead will be quite a bit larger due to the cube-hierarchy.

#7

I don’t know details about your application, but think about few points:

  1. Do the visibility evaluation once per some time - probably once per second is just ok. You can distribute the work per certain area over time - so instead of doing one global check, you can spread multiple subchecks during this time

  2. You will probably like to also give some different kind of indication about fog of war - some kind of shading. In this case, it is not about enemy units, but terrain. Maybe think about solving this part first and you will get unit visibility for free (if it is on revealed terrain, it is visible)

  3. It seems to be some kind of multiplayer game? In such case, think very seriously about doing at least basic checks on server side (area-wide at least). You can leave the edge cases for client, but by doing at least preliminary checks on server side, you will be able to save some traffic (by not sending invisible movement) and make it bit more hack-proof (compromised client can display only what you send to it)