Influence maps in Godot: giving a grid a sense of danger

Shortest is not safest

A familiar moment in any tactical game: you order a unit to move, it takes the mathematically perfect route, and it walks straight into a crossfire and dies. The pathfinder did its job flawlessly. Its job just did not include the concept of danger.

This is not a bug in A*. A* optimizes for distance because distance is the only thing it was taught to care about. A cell is walkable or it is not, and among the walkable ones it prefers the cheap, short route. Nothing in that model knows that a particular corridor is overlooked by three enemies, or that the open field is a kill zone, or that the long way around is the way a competent human would actually go.

The question this post answers: how do you give a grid a cheap, reusable sense of where danger and opportunity are, so that pathfinding produces routes a tactician would not be embarrassed by.

What an influence map actually stores

An influence map is a scalar field laid over the same grid the pathfinder already uses. Every source of tactical meaning — an enemy, an ally, an objective, a piece of cover — stamps a value onto its cell and lets that value spread outward, falling off with distance. Enemies contribute negative influence, allies positive, and the sum at any cell is a single number that answers a useful question: how contested is this spot, and by whom.

The point is that this collapses a messy spatial question into one value per cell. Instead of asking, at search time, which enemies can see this tile and how far away are they, you ask the map: what is the influence here. The expensive reasoning about who affects what was already folded into the field.

Different combinations of the same sources answer different questions. Enemy influence alone is a threat map. Friendly minus enemy is a tension or frontline map. The gradient of the field points toward safety or toward contact, depending on which way you read it. One structure, several tactical opinions.

Propagation: spread the values, cheaply

Building the map is two steps. First, stamp each source onto its cell. Then spread the values outward with a few decay passes, so a strong enemy presence bleeds into the cells around it instead of staying a single hot point. The number of passes controls how far influence reaches; the decay factor controls how fast it fades.

This is the same principle that runs through production navigation: pay the expensive work where it is paid least often. The spread is computed once per update, not re-derived for every agent that reads it.

# Stamp each source, then blur outward so influence falls off with
# distance. Enemies push negative, allies positive. Run on update,
# not per agent and not every frame.
func build_influence(sources: Array, w: int, h: int, decay: float) -> PackedFloat32Array:
    var inf := PackedFloat32Array()
    inf.resize(w * h)
    for s in sources:
        inf[s.cell.y * w + s.cell.x] += s.strength  # enemy < 0, ally > 0
    for _pass in range(PROPAGATION_PASSES):
        inf = blur_step(inf, w, h, decay)  # average neighbours, scale by decay
    return inf

Feeding danger back into the search

With the field built, the pathfinder barely changes. Wherever A* computes the cost of entering a cell, it adds a danger term read straight from the map. Danger raises the cost of stepping into a contested cell without forbidding it outright, so a unit will cut through a mildly risky tile if the safe detour is absurdly long, but will go around real danger when the detour is reasonable.

A single tuning value decides how cautious the agent is. A high caution makes a unit hug cover and take the long way; a low one makes it behave like the old distance-only pathfinder. The same map can drive a nervous scout and a reckless berserker by changing one number per agent.

# Danger raises entry cost without making the cell impassable.
# caution scales how far the agent will detour to stay safe.
func enter_cost(inf: PackedFloat32Array, w: int, cell: Vector2i, caution: float) -> float:
    var danger := maxf(-inf[cell.y * w + cell.x], 0.0)  # only enemy influence hurts
    return 1.0 + caution * danger

# Inside A*, relax neighbours with terrain + danger instead of terrain alone:
for n in neighbours(current):
    var tentative := g[current] + enter_cost(inf, w, n, agent_caution)
    if tentative < g[n]:
        g[n] = tentative
        came_from[n] = current

Influence maps, Dijkstra maps, and flow fields

Influence maps are one member of a small family of grid-wide fields, and the family is more useful than any single member. An influence map answers where is danger and opportunity. A Dijkstra map answers how far is every cell from a goal, and which way leads there. A flow field bakes a direction into every cell so a crowd heading to one destination reads a vector instead of running a search.

They compose. An agent can follow a Dijkstra map toward an objective while an influence map biases it away from contested ground, so it advances toward the goal by the safer of two equally short routes. The frame-spike discipline from why your Godot pathfinding causes frame spikes still applies: these fields are shared structures, computed once and read by many agents, which is exactly why they scale where per-agent reasoning does not.

The rule is to pick the field by the question. Many agents, one destination: flow field. Distance and direction to a goal: Dijkstra map. Where it is safe to be: influence map. A production navigation layer usually carries all three and chooses per situation rather than per dogma.

Updating without rebuilding the world

An influence map would be a liability if every frame demanded a full rebuild, because the sources move constantly. They do not need one. The map is an approximation of a situation that itself changes on a human timescale, so recomputing it every few frames is almost always enough, and the cost is a fixed budget you can schedule rather than a spike you suffer.

When only a few sources move, you can do better than a full rebuild: clear and re-stamp the affected region and re-blur a window around it, the same localized-update idea that keeps clearance maps cheap when a door opens. The map is allowed to be slightly stale, because a unit reacting to where the enemy was a third of a second ago is still behaving more intelligently than one that cannot perceive danger at all.

The tradeoffs

Influence maps cost memory — one value per cell, per field you keep — and a periodic compute pass. Both are cheap, but neither is free, and the propagation passes and decay factor are tuning knobs that need a real game to tune against. Set the spread too wide and everywhere looks dangerous; too narrow and units only react when they are already in trouble.

The map is also an opinion, not a fact. It encodes a heuristic about where danger probably is, derived from sources you chose to stamp and weights you picked. It will occasionally be wrong in ways a full line-of-sight or simulation check would not be, and that is the trade: a cheap, grid-wide sense of the situation in exchange for giving up exactness.

The deeper point is the one that runs through all of this. Tactical movement is not a smarter search algorithm bolted onto A*. It is the data you let the search read. Encode the situation into a field the pathfinder can consult in constant time, and ordinary A* starts producing routes that look like judgement instead of arithmetic.