RTS: Unit sight in fog of war

Question

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.

Problems are:

• 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:

// pseudocode
func calculate_visibility:
   vector<Bitfield> visible;

   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?

Answer 1

You should have a visibility map with at least one bit per cell per team.

Don't brute force a full map update each frame. Only when a unit's location and/or sight range changes. Before and after movement, check his visibility against each teams bit. If he was not visible to a team and becomes visible. Send an event.

Answer 2

Well the way I was taught in university was to first store your units in memory based on their cell location. So you have a square-grid of cells (you might need to play around with the cell size to find which is most efficient), and whenever a unit moves, you update its cell (if it changes, remove it from its old cell and add it to the new one). Note, you're only moving pointers to units, not the objects themselves, so this is very efficient.

I normally use a TreeMap structure, whose key is a Point (x, y) and the value is a list of units within that point. Note that you want to store your units as a straight array as well for when it comes to iterating through their update steps (or rendering). You could further segment this structure by 'team'. You don't need to check your own units against each other when it comes to visibility, only the units on other teams.

Using this method, when it comes to the actual checking, you take each unit's viewing radius and work out all possible cells that they might be able to see based on which cell they're in (rounded up). You then look at the other teams' units in those cells and check if the distance between them is within the viewing radius. Once an enemy is spotted, you store it in a list so that you don't need to check it again. (The list could also be segmented by cell in the same fashion to shorten the list and the number of checks required to find the unit in there).

I used this method to detect collisions between firework particles in a little firework simulator I made. It shrunk the number of checks I needed to perform from 500,000 to 500 on average.

Pros: Extremely efficient.

Cons: Small increase in RAM, due to secondary pointers storage.
Bugs in the code can cause units to be invincible/invisible.

If you need an example project with this all working, I can fix something up for you. It's a lot easier than you think.