I am making an RTS game, and like most RTSs, you can see what's going on in a part of a map only if you have a unit over there.
I have few ideas how to accomplish this, but there are problems with them.
- Algorithm must be efficient.
- I need to notify players (over network), when an enemy comes into sight.
- How do I account for obstacles obstructing sight (such as cliffs).
Naïve approach would be like this:
for all units on map:
let unit = enumerated unit
for all human players:
let player = enumerated player
for all units of player:
let player_unit = enumerated unit
if player_unit sees unit
visible[unit.id][player.id] = true
process next player
And then run this calculation each frame, compare results with previous frame and send out events, like “enemy unit detected”.
I did some benchmarking, and using approach like this may take up to 2/3 of a frame, which is unacceptable.
I figured out a better way to calculate which units are visible. This approach is to use a visibility map.
- Subdivide the map into N×M cells.
- Each cell is marked by IDs of players that can see the cell.
- To determine which players can see an unit, I need only to check cells that contain given unit.
However, I don't know how to fill the map in the first place. I could iterate through all units and use a circle-drawing algorithm.
But I'll have to redraw the visibility map every frame, so this doesn't look much more efficient than the first approach. Unless I update it at a lower rate, but then there's a problem with fast-moving units.
And how do I detect when unit comes in player's sight, except than iterating through every unit and comparing with previous frame?
How is this done in modern RTS, such as StarCraft 2?