Possibility Maps

Summary

A possibility map represents which hidden states of the world are still possible, given what the player has observed so far. Instead of simulating every unseen event explicitly, the AI tracks a set of still-valid options and only commits to one when the player would be able to detect the result. This makes it possible to create opportunistic AI that appears more prepared or more cunning than it really is, while still staying consistent with the player’s observations. (Manslow, Game AI Pro 2, see source-game-ai-pro-2)

Key ideas

• Observed vs unobserved state: The technique is about parts of the world the player cannot currently verify.
• Possible, not probable: A possibility map stores whether a state is still valid, not how likely it is.
• Propagation rules: The map expands according to what the hidden entity could reasonably have done since it left observation.
• Forced resolution: When the player looks somewhere that would reveal the hidden entity, the AI must decide whether to instantiate it there or rule that location out.
• Forking: If a hidden actor could have taken a resource or changed the world, the map can split into alternate valid futures until one becomes necessary.

In practice

Classic use case: a stealth or combat NPC disappears behind cover.

1. The player loses sight of the NPC.
2. The possibility map expands to all positions the NPC could plausibly have reached.
3. If the player exposes one of those positions, the AI either commits to that state or removes it from the set.
4. The longer the player leaves the NPC unobserved, the more tactical options the AI may have available.

This is useful for:

• stealth enemies
• ambush design
• search behaviours
• hidden item pickup or switch activation

Unity/C# sketch:

public class PossibilityMap
{
    private HashSet<int> possibleCells = new();
 
    public void Propagate(IEnumerable<int> reachableCells)
    {
        possibleCells.UnionWith(reachableCells);
    }
 
    public bool ResolveObservedCell(int cell, bool instantiateHere)
    {
        if (!possibleCells.Contains(cell)) return false;
 
        if (instantiateHere)
            possibleCells = new HashSet<int> { cell };
        else
            possibleCells.Remove(cell);
 
        return true;
    }
}

Trade-offs

• Strength: gives the illusion of foresight or planning without actually computing a complex long-range plan
• Strength: stays observation-consistent if used carefully
• Weakness: forking hidden state can grow combinatorially if the world offers too many invisible choices
• Weakness: if the AI resolves in ways that feel too convenient, players will perceive cheating rather than intelligence

Examples

• Hidden NPC movement in stealth games
• Ambush setup where the exact enemy position is deferred until the player exposes a lane
• Off-screen item or resource pickup decisions

Related

npc-perception-systems · stealth · game-ai-agent-design · smart-zones · source-game-ai-pro-2