Efficient fog-of-war visibility searching

Question

Every game I look into that uses fog of war tends to have the AI ignore fog of war completely. I'm starting to see why.

I have a RTS game I'm working on, with lots of units moving around. All units are on a grid, and I use a predefined search pattern to scan the grid points around the unit to find the nearest target. So far so good.

However, I have another unit type who's job it is to run around the map and collect scrap from destroyed units. As with combat units, I want it to look around and select the closest scrap it can find. However, unlike combat units, this search isn't limited to it's own vision radius. It should be able to take advantage of the player's entire fog of war. If another unit or building has revealed some scrap, it should be available for the unit to go pick up.

While scanning the vision radius of a unit is simple, I'm having trouble thinking of an efficient way to determine which grid points to scan in this much larger case. Any grid points within view of a building will be fairly static, but things other units see will change every frame, as they are constantly moving.

The two options I see are to record per-player visibility flags within the grid points themselves, and then (somehow) update those flags each frame, or to just loop through all units and buildings and perform individual searches to build a list of visible scrap. The first would be difficult to keep updated without re-scanning the entire map, and the second would be very redundant if there were many units or buildings in a small area.

Is there another method I could use to build a list of visible scrap within a player's entire fog of war view, given that that view is constantly changing?

Answer 1

I think, that's work for influence maps. It's almost your first option but in more common interpretation for AI in games. Influence maps presents all your map with grid in some specific structure. For each cell you save some value and periodically update it. In your case, you can save last_seen_time as value. So, when you'll iterate scrap to find new target, you easily can check that someone from units saw it (last_seen_time > scrap_spawn_time). In updating phase you should iterate units and set current time as last_seen_time at each visible cell from this unit.

How to implement good influence map structure depends in your purposes. Easiest way: divide the map to small cells. You don't need to update it each frame, few times per second should be enough in your purposes. And you don't need to clear it each frame, only update new visible cells.

Answer 2

The two options I see are to record per-player visibility flags within the grid points themselves, and then (somehow) update those flags each frame...

This seems like the right answer to me. Store whether or not each player can see each grid point. Updating the map can actually be very simple and efficient. You presumably already update each unit. When you do this, check the grid cells within the view radius (this is easy to do using rasterization). Mark them as "seen" if a unit has seen them. Just clear the visibility map every frame.

If that's too slow, you can store the visibility map the other way around: a spatial hash map of all the nodes currently seen. Create a hash map where the value is the node, and the key is

hash(x, y) = x * p1 ^ y * p2

Where p1, p2 are large primes and ^ is the xor operator. You can iterate over the hash map to see which nodes to check (don't need to iterate over nodes that aren't seen). You can also add to the hash map easily using the hash function.