GDnD Wiki

GDnD Wiki

This site is for Ulster University students and staff. Enter the class access password to continue.

Influence Maps

11 min read

Summary

An influence map is a spatial data structure — typically a 2D grid — in which each cell stores a numerical value representing how strongly some agent or group of agents influences that region. Influence may represent threat, control, safety, or any other game-relevant property. The map is a superposition of all agent influences and can be queried cheaply at runtime to guide AI decisions about positioning, target selection, and tactical behaviour.

Influence maps are a classic game AI technique (Paul Tozour, Game Programming Gems 2, 2001) that have been used in strategy games for decades. The Paragon bot AI (Zieliński, Game AI Pro 360, Ch. 8, see source-game-ai-pro-360-character-behavior) applied a modified version specifically designed for MOBA gameplay under severe time constraints.

Key ideas

  • Grid representation: The world is divided into cells of fixed size. Each cell stores one or more floating-point influence values (enemy influence, friendly influence, tower danger, etc.).
  • Influence sources: Agents, structures, and persistent effects each contribute to the map. The strength of contribution may be proportional to health, combat readiness, or ability range.
  • Influence propagation vs. radius application: Classic influence maps propagate outward from each source to neighbouring cells iteratively. A cheaper approximation is to apply influence to all cells within a fixed radius directly — equivalent to a flat “stamp” rather than a gradient falloff.
  • Superposition: Multiple sources are summed, producing a composite map from which net threat or net safety can be read at any location.
  • Query layer: The map feeds into spatial query systems to score candidate positions for movement, cover, or attack.

In practice — Paragon bots (Epic Games / UE4)

Described by Zieliński (Game AI Pro 360, Ch. 8, see source-game-ai-pro-360-character-behavior).

Representation

Paragon used a 2D cell grid at 5×5 m resolution. Total map memory: ~320 KB. Each cell stored:

  • Enemy influence (hero + minion)
  • Friendly influence
  • Auxiliary counters (list of agents influencing each cell; per-cell target density by type)

One-step influence (no propagation)

Full iterative propagation was too expensive for Paragon’s server budget. Instead, each hero applied influence to all cells within its primary ability range, rather than just its current cell. This is semantically equivalent to one step of propagation with a flat kernel.

Effect: minions contribute influence only at their cell (radius 0); heroes contribute within their attack radius. The result approximates how far each agent is dangerous without the full propagation cost.

// Pseudocode — building influence map from scratch each tick
for each agent in world:
    influenceRadius = (agent.isHero) ? agent.primaryAbilityRange : 0
    for each cell in GridCellsWithinRadius(agent.position, influenceRadius):
        cell.enemyInfluence += agent.strength  // or friendlyInfluence

Tower influence (cached)

Towers are static, so affected cells are computed once at match start and cached. The tower’s influence is conditionally included only when no minions are within the tower’s attack range (minions serve as cover; the bot should not fear the tower if minions are present).

AoE attack influence

Persistent AoE attacks (those that last long enough for the AI to react) are injected into the map. Short-duration AoE is ignored — there is no time to respond anyway.

Target density

A per-cell counter of enemy units of each type (minion vs. hero). Used by the ability picker to determine whether an AoE ability would hit multiple targets or be wasted on a single target.

Integration with UE4’s Environment Query System (EQS)

The influence map exposed a custom EQS test that reads influence values at query locations. This allowed bot positioning queries to filter out cells above a threat threshold (e.g., do not advance into tower fire) and score candidate positions by net safety/threat.

// EQS test concept in UE4 C++ (illustrative)
float UEnvQueryTest_InfluenceMap::CalculateScore(
    const FEnvQueryInstance& QueryInstance, 
    const FVector& TestPoint) const
{
    float enemyInfluence = InfluenceMapManager->GetEnemyInfluence(TestPoint);
    return FMath::Clamp(1.0f - enemyInfluence / MaxExpectedInfluence, 0.0f, 1.0f);
}

Lane Space

For MOBA positioning, Zieliński introduced Lane Space: projecting any 3D world position onto the axis between the two team bases (AB). This gives a single scalar (lane progress, normalised 0–1) representing how far along the lane a position is.

The Front-Line Manager uses minion positions and tower states to compute the current combat front-line on each lane. Bots use this to avoid chasing enemies too deep into enemy territory and to prefer positions behind the minion wave (ranged heroes) or at the front (melee heroes).

Unity implementation sketch

A simple 2D influence map in Unity:

public class InfluenceMap : MonoBehaviour
{
    public int width = 100;
    public int height = 100;
    public float cellSize = 2f;
    
    private float[,] enemyInfluence;
    private float[,] friendlyInfluence;
 
    void Awake()
    {
        enemyInfluence  = new float[width, height];
        friendlyInfluence = new float[width, height];
    }
 
    public void Rebuild(List<AIAgent> agents)
    {
        // Clear map
        System.Array.Clear(enemyInfluence, 0, enemyInfluence.Length);
        System.Array.Clear(friendlyInfluence, 0, friendlyInfluence.Length);
 
        foreach (var agent in agents)
        {
            Vector2Int cell = WorldToCell(agent.transform.position);
            int radius = Mathf.RoundToInt(agent.InfluenceRadius / cellSize);
            
            for (int dx = -radius; dx <= radius; dx++)
            for (int dy = -radius; dy <= radius; dy++)
            {
                int cx = cell.x + dx;
                int cy = cell.y + dy;
                if (!InBounds(cx, cy)) continue;
                if (agent.IsEnemy)
                    enemyInfluence[cx, cy] += agent.Strength;
                else
                    friendlyInfluence[cx, cy] += agent.Strength;
            }
        }
    }
 
    public float GetEnemyInfluence(Vector3 worldPos)
    {
        Vector2Int cell = WorldToCell(worldPos);
        return InBounds(cell) ? enemyInfluence[cell.x, cell.y] : 0f;
    }
 
    private Vector2Int WorldToCell(Vector3 pos) =>
        new Vector2Int(
            Mathf.FloorToInt(pos.x / cellSize),
            Mathf.FloorToInt(pos.z / cellSize));
 
    private bool InBounds(int x, int y) => 
        x >= 0 && x < width && y >= 0 && y < height;
    private bool InBounds(Vector2Int c) => InBounds(c.x, c.y);
}

Rebuild the map on a timer or whenever agents move significantly rather than every frame.

Modular tactical influence maps

Described by Mark (Chapter 5, see source-game-ai-pro-360-tactics-strategy).

Rather than maintaining one monolithic influence map updated globally each frame, a modular architecture separates concerns:

Base map types

Map typeWhat it representsUpdate rate
Proximity mapWhere an agent (or group) can currently reachPer agent move
Threat mapWhat an agent can currently threaten (attack range)Per agent move
Ownership mapWhich faction controls each regionLow frequency
Static hazard mapEnvironmental hazards (traps, terrain damage)Rarely

Proximity and threat maps are distinct: an agent may be able to reach a cell (proximity) without being able to threaten it (if its weapon has a minimum range, for example).

Stamped templates

Recalculating influence for every agent every frame is wasteful when agents are stationary. A stamped template is a pre-computed falloff pattern (disc, ring, directed cone, etc.) stored in a reusable buffer:

  1. Pre-compute the template at initialisation for each agent type.
  2. On each update, stamp the template at the agent’s current cell — a single array copy.
  3. Accumulate all stamps into the working map.

This eliminates repeated distance calculations. The template for a ranged unit with range r is computed once; stamping it is O(r²) rather than O(r²) per-frame-per-query.

Personal interest template

An agent’s own decision-making queries a personal interest map — a combination of the global working map and a per-agent priority gradient that scores nearby cells more highly. This ensures agents focus on tactically relevant nearby information rather than the entire map.

Working maps

A working map assembles combinations of base maps for a specific query:

# Pseudocode: working map for "safe attack position"
working_map = (
    friendly_proximity    × 0.4   # can I reach it?
  + enemy_threat          × -0.6  # how dangerous is it?
  + cover_quality         × 0.3   # can I take cover there?
)

Because base maps are maintained separately, working maps are constructed cheaply (element-wise addition/multiplication over a grid) and can be assembled on demand for different query types.

Infinite-resolution influence mapping

Described by Lewis (ArenaNet, Chapter 6, see source-game-ai-pro-360-tactics-strategy).

The problem with fixed grids

A 100×100 grid at 2 m resolution covers a 200×200 m area. Finer detail requires exponentially more memory. Grids waste memory on empty space and have hard-coded maximum resolution.

Point-based falloff model

Instead of a grid, each influence source is stored as a point with a falloff function:

I(p) = strength × falloff(distance(p, source))

Where falloff can be linear, exponential, Gaussian, or any smooth function. The total influence at any point is the sum over all sources:

I(p) = Σᵢ strengthᵢ × falloff(|p - sourceᵢ|)

This gives infinite resolution — any point in space can be queried to arbitrary precision.

k-d tree for efficient queries

Brute-force evaluation is O(n) per query (n sources). A k-d tree partitioned on source positions reduces this to approximately O(√n) with a range-limited query — only sources within falloff_radius are evaluated:

// Unity-compatible: use Physics.OverlapSphere to find nearby sources
// (production code would use a purpose-built k-d tree for non-physics objects)
Collider[] nearbySources = Physics.OverlapSphere(queryPoint, maxFalloffRadius, influenceLayer);
float total = 0f;
foreach (var col in nearbySources)
{
    var src = col.GetComponent<InfluenceSource>();
    float dist = Vector3.Distance(queryPoint, col.transform.position);
    total += src.Strength * src.Falloff.Evaluate(dist / maxFalloffRadius);
}

Temporal propagation

Influence from moving sources is updated by:

  1. Splitting: A source that moves spawns a new source at its new position and marks the old one to decay.
  2. Decay: Old points reduce their strength over time and are removed when strength falls below a threshold.
  3. Simplification: Points close together in space and value are merged to control source count.

This gives temporal continuity (influence “lingers” where an agent recently was) at bounded memory cost.

Obstacle-aware flow

Standard point-based influence ignores walls. Obstacle-aware propagation uses conditional placement: when a new point would spawn inside or immediately behind a wall, it is redirected to the nearest walkable cell. This approximates diffraction without full ray-marching.

Region-level influence propagation

See Region-level influence propagation for the full treatment. In brief: for strategic-scale AI (RTS, grand strategy), a region graph (tens to hundreds of nodes) replaces the fine grid entirely. Influence propagates between connected regions using Dijkstra, respecting chokepoints and topology. Much cheaper than any grid approach at strategic scale.

Trade-offs

ApproachProsCons
Full propagationGradient falloff; respects distanceExpensive, especially with many sources
Radius stamp (Paragon)Fast; O(agents × radius²)No falloff gradient; ignores obstacle occlusion
Modular / template approachCheap stamping; flexible compositionTemplate setup cost; grid resolution still fixed
Infinite-resolution (point-based)Arbitrary resolution; linear memoryk-d tree overhead; merge/split complexity
Region graph propagationVery fast; topology-awareCoarse; misses sub-region detail
Pre-computed static mapNear-zero runtime costCannot model dynamic agents

When to use influence maps

  • Strategy/MOBA games with meaningful spatial control.
  • Any AI needing to reason about “where is dangerous?” or “where are my allies?” without expensive per-frame raycasts.
  • As an input to spatial query systems (UE4 EQS, custom Unity query runners).

Limitations

  • Ignores obstacles by default — a cell inside a building could register high influence even if separated by walls.
  • Coarse resolution loses fine spatial details; fine resolution is expensive.
  • Dynamic rebuild at 5×5 m resolution was ~320 KB in Paragon — still significant for mobile platforms.

Evidence

  • Zieliński (Game AI Pro 360, Ch. 8, see source-game-ai-pro-360-character-behavior) describes the Paragon one-step influence map in production detail, including the 5×5 m cell size decision and the EQS integration.
  • The technique originates with Tozour, “Influence Mapping,” Game Programming Gems 2 (2001).
  • Shroff (Ch. 4, same source) describes a complementary technique — action ranking and on-screen realization — that achieves similar “who is the most relevant NPC” decisions without a spatial grid.
  • Mark (Ch. 5, see source-game-ai-pro-360-tactics-strategy) describes the modular influence map architecture — proximity/threat separation, stamped templates, and working map assembly — as a scalable production approach.
  • Lewis (Ch. 6, same source) describes the infinite-resolution point-based model with k-d tree queries, temporal propagation via point splitting/simplification, and obstacle-aware conditional placement (ArenaNet).

Implications

  • Influence maps are a cheap way to give AI agents spatial awareness that would otherwise require expensive per-agent raycasts.
  • The radius-stamp approximation is sufficient for most action games. Reserve full propagation for turn-based or strategy games where the gradient detail matters.
  • Combining influence maps with a query system (EQS or custom) creates a clean separation: the map produces data, the query system consumes it, and neither needs to know how the other works.

Open questions

  • How can obstacle occlusion be efficiently incorporated into a real-time influence map without full ray-casting? (Flood-fill from sources respecting navmesh connectivity is one option.)
  • Is there a clean way to implement an EQS-equivalent query runner in Unity that can consume influence map data? Unity’s NavMesh sampling API might serve as the spatial query layer.
  • How do influence maps interact with steering-behaviours context steering — can the map values directly modulate the context steering danger array?

game-ai-agent-design · utility-ai · steering-behaviours · npc-perception-systems · combat-coordinator-pattern · tactical-position-selection · squad-ai-patterns · strategic-ai-rts · source-game-ai-pro-360-character-behavior · source-game-ai-pro-360-tactics-strategy

Graph View

Backlinks