skip to content

What is an influence map in game AI, and how do propagation, decay and layered maps help NPCs reason about territory and danger?

level: middleimportance: should knowfreq 45%

answer

  1. values on a grid or graph
  2. units stamp, values spread
  3. falloff with distance, fade with time
  4. one layer per side or concern
  5. combine layers into questions

basics

~20 s

An influence map is a grid or graph storing, per cell, how strongly each side controls or threatens it; units stamp values that spread with falloff and fade over time, and layers combine to locate front lines, safety and danger.

solid answer

~50 s

An **influence map** stores a number per cell of a grid, or per node of a waypoint or navmesh graph. Units **stamp** strength at their position; **propagation** spreads it to neighbours with a falloff such as `exp(-decay * distance)`, taking the **maximum** decayed neighbour value so values stay bounded by the strongest source; each cell then **blends** towards that target, `value = (1 - alpha) * value + alpha * target`, so old influence fades when units move away. Keep separate **layers**, friendly and enemy influence plus things like recent deaths or gunfire, and combine them: `F - E` is control and crosses zero at the front line, `F + E` is tension, and `(F + E) - |F - E|`, which equals `2 * min(F, E)`, picks out contested ground. Propagate only through walkable connections so influence does not leak through walls, and update at a low rate on a coarse grid.

code

pseudocode · 11 lines
pseudocode
function propagate(layer, decay, alpha):
    for each cell c in layer:
        if not walkable(c):
            layer.next[c] = 0
            continue
        target = layer.stamp[c]                 // this update's sources
        for each neighbour n of c:
            if walkable(n) and connected(c, n):   // no spreading through walls
                target = max(target, layer.value[n] * exp(-decay * dist(c, n)))
        layer.next[c] = (1 - alpha) * layer.value[c] + alpha * target
    swap(layer.value, layer.next)

go deeper

for a junior

Recall that an influence map stores per-cell values that units stamp, that spread with falloff and fade over time, with separate layers per side.

for a middle

Explain a propagation pass, why the maximum keeps values bounded, what the blend factor does, and how control, tension and contested ground are combined.

for a senior

Diagnose leaking through walls, blow-up, flicker and stale danger, and choose grid or graph representation, resolution and update rate for a level.

for a principal

Decide which layers the whole AI shares as common infrastructure and whether they are fed by perceived or true positions, since that sets how honest every consumer is.

## The idea An **influence map** is a spatial summary that lets AI ask area questions cheaply: which part of the arena does each team hold, where is it dangerous right now, where is the front line, where is a safe place to fall back to. Instead of reasoning about every unit, the AI reads numbers stored over space. The space is a **grid** of cells or a graph of **waypoints** or **navmesh** polygons. Each cell holds one value per **layer**. Picture a team-based arena where bots must know which zones each side controls and where teammates recently died. ## Building one: stamping and propagation One common scheme, updated a few times a second: 1. **Clear the stamps** and let each unit write its strength into the cell it stands in, one layer per side. 2. **Propagate**: for each walkable cell, the target is the larger of its own stamp and the strongest neighbour value after falloff, `value[n] * exp(-decay * dist(c, n))`. 3. **Blend** each cell towards its target: `value = (1 - alpha) * value + alpha * target`, with `alpha` between 0 and 1. 4. **Swap** buffers so every cell in one pass reads the previous values. Taking the **maximum** rather than the **sum** matters. Summing eight decayed neighbours each pass multiplies values whenever eight times the falloff exceeds 1, and the map blows up. The maximum is never larger than the strongest stamp, and blending two values in that range stays in range. One pass spreads influence one ring of cells, so repeated updates let it flow outwards. An alternative is to flood each source outward over walkable cells to a cut-off radius, which is a bounded shortest-path expansion. ## Decay over time The blend factor controls memory. If a unit leaves, its old cell's target drops, and while that target holds still the gap between the cell and it shrinks by a factor of `(1 - alpha)` per update. With `alpha = 0.2`, `0.8^10` is about 0.11, so roughly a tenth of the stale excess remains after ten updates. High `alpha` reacts quickly but flickers; low `alpha` is smooth but lags behind the fight. ## Layers and combining them | Layer | Written by | Fades | Used for | |---|---|---|---| | Friendly influence | Allied units | Quickly | Control, support | | Enemy influence | Perceived enemies | Quickly | Threat, front line | | Danger | Deaths, explosions, gunfire stimuli | Slowly | Avoiding killing zones | | Visibility | Precomputed sight lines | Static | Exposure of a position | Combinations answer the questions directly, with `F` friendly and `E` enemy influence: - **Control** `F - E`: positive is ours, negative is theirs, and the zero crossing is the **front line**. - **Tension** `F + E`: how much force is present at all. - **Contested ground** `(F + E) - |F - E|`, which equals `2 * min(F, E)`: high only where both sides are strong. Control alone cannot tell contested ground from empty ground, since both give values near zero. The enemy layer should be written from what the team has actually perceived, so the map does not quietly hand bots knowledge they never sensed. Decision code then reads the map to choose where to attack or retreat, and a pathfinder can add a layer as extra traversal cost. ## Representation and cost A 256 by 256 grid is 65,536 cells; one pass reading eight neighbours is about 524,000 reads, and four updates a second is about two million reads a second per layer. That is affordable as a background job, which is why maps run at coarse resolution and low rate rather than every frame. Navmesh or waypoint graphs need far fewer nodes and follow the level's real connectivity. ## Failure modes - **Leaking through walls**: neighbours on a raw grid are connected across a thick wall, so a firefight next door paints a quiet room as dangerous. Propagate only between cells joined by walkable space. - **Blow-up**: summing neighbours, or adding stamps every update without fading. - **Flicker or lag**: `alpha` set too high or too low. - **Resolution mismatch**: cells larger than corridors merge spaces that have nothing to do with each other. - **Omniscient enemy layer**: stamping enemy positions the team never perceived.

  • Why take the maximum decayed neighbour value instead of the sum when propagating?
    Summing makes each cell the total of up to eight neighbours, so whenever eight times the falloff exceeds one, values grow every pass without limit. The maximum is bounded by the strongest stamp and spreads a smooth falloff from each source. If you want strength to add up, for example two squads near one point, stamp each unit's falloff directly once per update instead of summing during propagation.
  • How do you stop influence leaking through walls?
    Only propagate between cells that are walkable and connected, so influence travels the way units do: round corners and through doorways. On a grid that means skipping blocked cells and diagonal moves that cut corners; on a waypoint or navmesh graph the edges already encode connectivity, which is one reason teams prefer graphs for indoor levels.
  • What does the blend factor alpha trade off?
    With `value = (1 - alpha) * value + alpha * target`, a high alpha follows the current situation almost at once, which reacts fast but flickers as units move. A low alpha keeps a fading memory of recent influence, which is smoother and remembers where the fight was, but lags. Separate layers can use different values: fast for unit control, slow for a danger layer of recent deaths.

  • Influence can spread by straight-line distance, ignoring walls.
  • Summing neighbour values each pass stays bounded on its own.
  • A control value near zero means nobody is near that area.
  • One combined map is enough; separate layers add nothing.
  • Influence maps must be fully recomputed every frame at fine resolution.
  • Stamp every enemy's true position whether or not anyone perceived it.