Dev Diary #9: Fog of war and vision in a strategy engine

In short: Fog of war depends on what a side sees on the map now and what it has explored before. In MKA Engine the engine keeps these facts, and the game chooses the range, sharing, detection and fog rules. In an unattended measurement, one vision step took 1,216 microseconds with range measured by neighbouring places, 3,642 microseconds with a cost of 1 on every place, and 5,251 microseconds with varied place costs.

In strategy games the map is usually closed at the start. The player sees only what their units see; the rest stays under fog (Wikipedia, Fog of war (opens in a new tab); Game Developer, Adding strategy to your tactics (opens in a new tab)). For a simulation this raises a question: which places each side sees and has explored must be the same every day, on every machine. In a multiplayer game every machine runs the same simulation and only commands travel over the network (Game Developer, Building a Multiplayer RTS in Unreal Engine (opens in a new tab); Deterministic Lockstep in Networked Games, academic thesis (opens in a new tab)). If vision were only something drawn on the screen, machines could drift apart. This lockstep design, which we described in Multiplayer and consistency, makes vision part of the simulation too.

What the engine keeps, what the game chooses#

The engine does not impose one model of vision. The built-in system keeps two facts: the places this side sees today, and the places it has explored before. Each fact is a single yes-or-no bit. In a 30,000-place world the bits are packed into groups of 64: 469 groups and two columns per side, about 7.5 KB. For 250 sides the measured total of these bits was about 1.9 MB. How the bits sit in memory is described in The world in memory.

Everything else is the game's decision:

We split it this way on purpose. Two games can see the same sides and still have different fog rules. One ties vision only to range; another ties it to terrain and weather costs. The engine supports both with the same family of bits, and the game writes its rule. How game rules are written is described in How strategy game rules are written.

Range: neighbour count or cost?#

By default, range is the number of neighbouring places: a unit sees as far as that many steps. It is fast and easy to follow. If the game wants, it can give each place a cost, expensive in a forest or on a mountain and cheap on open plains. Range then becomes a budget, and vision spreads until the budget runs out. A place whose cost uses up the budget hides the places behind it.

What we measured is the time of one update step. The runner used a 30,000-place world, 8 sides, range 3 and 5,000 sources. It ran on a shared machine with load 20–30, as one run.

With a cost of 1 on every place, the result matched the neighbour count: 9,855 places were seen in both cases. The route is correct, but about three times slower. With varied place costs the update took 5,251 microseconds and 9,039 places were seen; the seen area shrank a little.

Sharing and detection#

Sharing is set up with a relation table. If the game writes a row between two sides, that row gives one side's current view to the other; if the row is removed, the sharing stops. The engine does not know what an alliance is. The game may also share exploration. Shared exploration only grows: a place once explored stays explored even if the row is later removed.

Detection is a separate rule. Each unit has a concealment value: how hard it is to spot. A hidden unit is seen at a place we can see only if the viewer's detection reaches its concealment. Shared vision carries no detection: an ally's view opens the place, but a hidden unit there stays hidden. Detection does not come with an alliance.

There is a story behind this part. In the first version, detection stored one value per side per place: 240,000 bytes per side, 60 MB for 250 sides (calculated). We changed it. Each slot of the hidden table (the space reserved for one row of a table) now holds one bit and the slot's entity. For the same 250 sides this is 4.16 MB; the measured value matched the formula.

Last known copy and estimates#

The last known strength of an army we cannot see is the copy taken the last time the side saw it. The army may move on, but the copy stays. If a slot is reused, the old copy is not shown.

An estimate works with an intelligence value from 0 to 1. At full intelligence the true value is read. Otherwise the true value is shifted by a daily draw of at most (1 − intelligence) × spread. The draw is deterministic: the same day gives the same answer.

What does the AI know?#

When the vision rules are on, the AI reads only what its side sees. Values it cannot see are unknown, and a condition that depends on them is not met. The reading mode chooses between unknown, last known and estimate.

We checked this with a capability test. With the rules on, the AI does not choose a target it cannot see or detect, does not draw a route into a closed unexplored area, and acts on the shared sight of its ally. The test checks behaviour; we did not add a setting for the AI's win rate. Which difficulty sees which information is the game's decision.

Fog for the player#

The rows shown on the player's screen are set by a rule per table. For example, a game can write: units are shown only when they are seen and the viewer's detection reaches their concealment; orders and plans are read only by their owner; places stay visible once explored. Which fog model the game uses is also the game's choice.

What does it cost?#

• Memory: about 7.5 KB per side for vision and exploration (calculated); about 16.6 KB per side for each hidden table of 2,048 slots, which was measured and matches the formula.
• Speed: a costly range makes an update step about three times slower (unit costs) to 4.3 times slower (varied costs) than the neighbour count; this was measured. The daily total cost of open vision was not measured, because our scale world does not use vision keys. We will measure it in the game's own world.
• Concealment query: "Is this concealment detected at this place?" is not answered from stored state today. If a game needs it, it is added as a computed query.
• Not measured: the time of the unexplored and estimate paths, and the speed of the end-of-day bit calculation while detection is on. These paths were checked with scenario tests.

Frequently asked questions#

Sources and records#

External sources:

• Wikipedia, Fog of war (opens in a new tab)
• Game Developer, Adding strategy to your tactics (opens in a new tab)
• Game Developer, Building a Multiplayer RTS in Unreal Engine (opens in a new tab)
• Deterministic Lockstep in Networked Games, academic thesis (opens in a new tab)

Our internal records:

• Vision decision: range, sharing, detection and knowledge are the game's choice; the engine keeps only the bits and the building blocks.
• Vision measurement: unattended runner, one run, shared machine.

If you have questions or suggestions about this diary, write to us through the contact page. For an overview of the engine, see the MKA Engine page; for all diaries, see the Developer Diaries list.