Dijkstra maps for roguelike AI in Godot

What a Dijkstra map is

A Dijkstra map is a grid where every cell holds its cheapest distance to a goal, computed with Dijkstra's algorithm over non-negative step costs. Seed the goal cells at 0, flood the distances outward, and you have a field any number of actors can read at once - no per-actor pathfinding.

It turns up in roguelikes, grid AI, and procedural systems because it makes smart movement a lookup instead of a search. Godot 4 ships none of it natively, so this page builds it from scratch. The everyday shapes:

• Chase: an actor steps toward the lowest neighboring value.
• Avoid: it steps the other way - though the naive highest value rule hugs corners, which this page fixes later.
• Fire, smell, or sound spread: distance values can be transformed into intensity.
• Safe-spot AI: pick a high value on a danger map.

The direct answer

A Dijkstra map is a distance field for grid AI. Build one field from the player, a goal, gold, exits, hazards, or any set of sources; then each actor looks at neighboring cells and steps toward the lowest value.

That flips the usual pathfinding question. A* answers what path should this one actor take to this one target? A Dijkstra map answers what is the best direction from every reachable cell? For roguelike AI, that means one solve can guide pursuit, flee behavior, autoexplore, hazard escape, and source-biased desire maps.

A useful Godot rule is this: store the field as a dense PackedFloat32Array, mark unreachable cells as INF, seed one or more cells with starting scores, then rescan the finite cells through Dijkstra relaxation.

1. Build the walkable grid from your TileMapLayer or board data.
2. Seed the field: player = 0, exits = 0, gold = negative bias, hazards = safe cells, or any mix that fits the behavior.
3. Relax the field through walkable neighbors with terrain costs.
4. For each actor, inspect four neighboring cells and step to the lowest score.
5. Recompute only when sources, terrain, blockers, or revealed cells change.

Why roguelikes use maps, not only paths

Roguelike AI is usually grid-native. Actors move one cell at a time, turns advance in discrete steps, and the same map facts are read by many systems: pursuit, fleeing, exploration, sound, hazards, tactical safety, and item desire.

If ten actors all chase the same player, ten A* queries are wasteful. A single Dijkstra map from the player gives every actor a downhill direction. When the player moves, rebuild the field. Until then, every actor can read the same array.

This is also why Dijkstra maps compose well with flow fields and influence maps. They are all grid-wide fields. The difference is what the cell values mean and how actors interpret them.

The Pac-Man-style ghost AI pattern

A Pac-Man-style maze chase is the textbook shared-field case: several ghosts pursue one player on the same grid. Instead of running a separate A* search for every ghost, build one player-centered Dijkstra map and let each chaser choose a valid neighboring cell with a lower score.

Different personalities do not require separate pathfinders. A direct hunter can read the shared player field, an ambusher can reseed the same solver ahead of the player's direction, and other policies can blend or switch fields. Occupancy and target reservations remain a separate movement rule applied when each ghost chooses its next cell.

To build the complete small loop around that field, use the Pac-Man-style maze-chase starter. You can see the larger pattern running in Dijkstra's Ghost, a playable Godot maze chase where four hunters use one Dijkstra-map system and the live overlay exposes the field behind each decision.

The field representation

The proof scene uses one flat PackedFloat32Array. A cell at (x, y) maps to y * width + x. That keeps the field compact, easy to serialize, and easy to scan in a headless verification run.

INF is the sentinel for blocked or unreachable. Do not use null for every unreachable cell in a hot grid loop; keep the array dense and reserve dictionaries for sparse facts such as blockers or terrain overrides.

const INF := 1_000_000.0
const ORTHOGONAL := [
    Vector2i.RIGHT,
    Vector2i.LEFT,
    Vector2i.DOWN,
    Vector2i.UP,
]

static func make_field(width: int, height: int, value: float = INF) -> PackedFloat32Array:
    var field := PackedFloat32Array()
    field.resize(width * height)
    field.fill(value)
    return field

static func in_bounds(cell: Vector2i, width: int, height: int) -> bool:
    return cell.x >= 0 and cell.y >= 0 and cell.x < width and cell.y < height

static func index_of(cell: Vector2i, width: int) -> int:
    return cell.y * width + cell.x

Rescan seeded fields

The important implementation detail is the rescan. A basic solver can wipe the field, seed a goal at zero, and expand from there. But source bias and flee behavior need something stronger: a function that starts from every finite value already in the field.

That is what rescan_field() does. It accepts a pre-filled field, pushes every finite non-blocked cell into the frontier, and relaxes outward with terrain costs. Positive edge costs keep the Dijkstra loop valid even when some source cells start at negative values.

static func rescan_field(
    field: PackedFloat32Array,
    width: int,
    height: int,
    terrain_cost: Dictionary,
    blocked: Dictionary
) -> PackedFloat32Array:
    var frontier: Array[Vector2i] = []

    for y in range(height):
        for x in range(width):
            var cell := Vector2i(x, y)
            var index := index_of(cell, width)
            if blocked.has(cell):
                field[index] = INF
                continue
            if field[index] < INF:
                frontier.append(cell)

    while not frontier.is_empty():
        frontier.sort_custom(func(a: Vector2i, b: Vector2i) -> bool:
            return field[index_of(a, width)] < field[index_of(b, width)]
        )

        var current: Vector2i = frontier.pop_front()
        var current_cost: float = field[index_of(current, width)]

        for direction_variant in ORTHOGONAL:
            var direction: Vector2i = direction_variant
            var next: Vector2i = current + direction
            if not in_bounds(next, width, height):
                continue
            if blocked.has(next):
                continue

            var step_cost: float = maxf(1.0, float(terrain_cost.get(next, 1.0)))
            var next_cost: float = current_cost + step_cost
            var next_index: int = index_of(next, width)

            if next_cost < field[next_index]:
                field[next_index] = next_cost
                if not frontier.has(next):
                    frontier.append(next)

    return field

Build the standard pursuit map

A pursuit map is the simplest case. Seed the player cell at zero, rescan, then every actor walks downhill. Terrain costs make slower cells more expensive, so the field naturally bends around mud, doors, or hazard tiles if you model them as higher entry cost.

This version uses a sorted array frontier for readability. For large maps or frequent rebuilds, swap it for a real priority queue. The algorithmic contract stays the same; only the frontier implementation changes.

static func build_dijkstra_map(
    sources: Array[Vector2i],
    width: int,
    height: int,
    terrain_cost: Dictionary,
    blocked: Dictionary
) -> PackedFloat32Array:
    var field := make_field(width, height)

    for source in sources:
        if in_bounds(source, width, height) and not blocked.has(source):
            field[index_of(source, width)] = 0.0

    return rescan_field(field, width, height, terrain_cost, blocked)

Actors read downhill

Once the field exists, movement is cheap. The actor checks each walkable neighbor and picks the cell with the lowest value. This is the shareable part: the expensive search happened once; each actor's turn is just a local read.

Keep occupancy separate from the field. The field describes terrain and goals. Runtime blockers, other actors, and reserved target cells are a second layer applied during step selection.

static func choose_downhill_step(
    cell: Vector2i,
    field: PackedFloat32Array,
    width: int,
    height: int,
    blocked: Dictionary,
    occupied: Dictionary = {}
) -> Vector2i:
    var best_cell := cell
    var best_cost := field[index_of(cell, width)]

    for direction_variant in ORTHOGONAL:
        var direction: Vector2i = direction_variant
        var next: Vector2i = cell + direction
        if not in_bounds(next, width, height):
            continue
        if blocked.has(next):
            continue
        if occupied.has(next):
            continue

        var cost: float = field[index_of(next, width)]
        if cost < best_cost:
            best_cost = cost
            best_cell = next

    return best_cell

Why several actors choose the same cell

The field describes terrain and goals. It doesn't know that another actor picked the same destination a few microseconds earlier. If two actors read the same field and see the same lowest neighbor, both choices are individually correct.

Equal-cost choices also need a policy. The downloadable solver iterates right, left, down, then up, and replaces the current choice only when it finds a strictly lower value. Equal values therefore keep the first authored direction. If you want variation, shuffle with a seeded RNG or rotate the authored direction order by actor ID; don't let incidental container iteration decide replays.

For real-time grid ticks, clear an ephemeral reserved_targets table at the start of the tick and claim every accepted destination until the batch commits. This conservative policy blocks moves into cells another actor intends to vacate later in the same tick. If actors must swap, push chains, or move through each other's starting cells, use the turn-order and movement-planning resolver instead of making the field own a batch-resolution problem.

static func choose_reserved_downhill_step(
	actor_id: int,
	cell: Vector2i,
	field: PackedFloat32Array,
	width: int,
	height: int,
	blocked: Dictionary,
	occupied: Dictionary,
	reserved_targets: Dictionary
) -> Vector2i:
	var unavailable := occupied.duplicate()
	for reserved_cell in reserved_targets:
		unavailable[reserved_cell] = true

	var next := choose_downhill_step(cell, field, width, height, blocked, unavailable)
	if next != cell:
		reserved_targets[next] = actor_id
	return next

Turn the field into a complete route

Most actors need only one downhill step. A movement preview, debug overlay, or ‘show route to the stairs’ command often needs the whole path. You don't need to run A* again: follow strictly lower field values until no lower neighbor exists.

On a valid field with positive entry costs, every accepted step is lower than the last and the trace ends at one of the seeds. An empty return means the start was invalid, unreachable, or the safety guard found inconsistent data. A one-cell path means the start was already at a local seed.

This route is a view over the field, not a new source of truth. If terrain, blockers, or seeds change, rebuild the field before drawing or confirming it. The action-points and terrain-cost guide owns the separate rule that previewed cost and confirmed cost must use the same board revision.

static func trace_downhill_path(
	start: Vector2i,
	field: PackedFloat32Array,
	width: int,
	height: int,
	blocked: Dictionary
) -> Array[Vector2i]:
	if not in_bounds(start, width, height):
		return []
	if field[index_of(start, width)] >= INF:
		return []

	var path: Array[Vector2i] = [start]
	var visited := {start: true}
	var current := start

	for _step in range(width * height):
		var next := choose_downhill_step(current, field, width, height, blocked)
		if next == current:
			return path
		if visited.has(next):
			return []

		path.append(next)
		visited[next] = true
		current = next

	return []

Multiple sources and source bias

Multiple sources are where Dijkstra maps start to feel like AI instead of only pathfinding. Seed the player at zero and treasure at a negative value, then rescan. Cells near the treasure become more attractive without writing a separate target-switching system.

The negative number is not magic. It is an explicit preference. A source at -4 says this source is four cost units more attractive than a neutral source at 0. The rescan propagates that preference through the map.

static func build_seeded_map(
    source_costs: Dictionary,
    width: int,
    height: int,
    terrain_cost: Dictionary,
    blocked: Dictionary
) -> PackedFloat32Array:
    var field := make_field(width, height)

    for source in source_costs.keys():
        if source is Vector2i and in_bounds(source, width, height) and not blocked.has(source):
            field[index_of(source, width)] = float(source_costs[source])

    return rescan_field(field, width, height, terrain_cost, blocked)

func build_greed_map(player: Vector2i, gold_cells: Array[Vector2i]) -> PackedFloat32Array:
    var source_costs := {}
    source_costs[player] = 0.0

    for gold_cell in gold_cells:
        source_costs[gold_cell] = -4.0

    return DijkstraMapField.build_seeded_map(source_costs, width, height, terrain_cost, blocked)

Flee maps need the second pass

Naive flee behavior often gets stuck in local corners: multiply the approach map by -1, then step downhill away from the player. The actor runs toward the locally highest distance, which may be a dead end.

The useful roguelike trick is to multiply the approach field by a stronger negative coefficient, usually around -1.2, then rescan. That creates a new safety field. The rescan rewards cells that are far from the player but still connected through useful exits, so the actor can head toward a doorway instead of hugging the nearest corner.

static func make_flee_seed(approach: PackedFloat32Array, coefficient: float = -1.2) -> PackedFloat32Array:
    var seed := PackedFloat32Array()
    seed.resize(approach.size())

    for i in range(approach.size()):
        seed[i] = INF if approach[i] >= INF else approach[i] * coefficient

    return seed

static func build_flee_map(
    approach: PackedFloat32Array,
    width: int,
    height: int,
    terrain_cost: Dictionary,
    blocked: Dictionary,
    coefficient: float = -1.2
) -> PackedFloat32Array:
    return rescan_field(make_flee_seed(approach, coefficient), width, height, terrain_cost, blocked)

Compose desires without INF poisoning

A richer actor can score a cell against several maps: approach the player, prefer treasure, avoid hazard, seek unexplored cells. The pitfall is INF. If one optional map is unreachable at a cell, you do not want that one value to poison an otherwise valid score.

The proof scene handles this by skipping INF maps during composition. If no finite map contributes at all, the score is INF and the cell is not attractive.

static func score_cell(cell: Vector2i, width: int, maps: Dictionary, desires: Dictionary) -> float:
    var index := index_of(cell, width)
    var score := 0.0
    var used_any_map := false

    for key in desires.keys():
        if not maps.has(key):
            continue

        var field: PackedFloat32Array = maps[key]
        var value := field[index]
        if value >= INF:
            continue

        score += float(desires[key]) * value
        used_any_map = true

    return score if used_any_map else INF

Behavior recipes

The same solver covers several common roguelike behaviors. What changes is the seed set and how the actor interprets the result.

Update policy matters more than the first demo

The Dijkstra map should not rebuild just because an actor takes a step. Rebuild when the facts that define the field change: the player source moves, treasure is collected, a door opens, a wall appears, a cell is revealed, or the selected behavior changes.

For small roguelike maps, a full field rebuild is often fine. For larger maps, split the work: keep terrain and blocker data explicit, use dirty regions where possible, and move repeated field builds into a scheduled budget. The related frame-spike scheduling guide covers the production side of that decision.

Measurement-gap: the attached artifact is a correctness proof, not a throughput benchmark. Its verification JSON confirms ten behavior contracts on Godot 4.7.1: the original field, bias, flee, scoring, and hazard fixtures plus deterministic ties, target reservations, strictly descending route traces, and unreachable starts.

Try the proof scene

The browser demo attached above is there because this concept is easier to trust when it moves. Drag the player and the field bends immediately; switch to greed or flee and the same grid starts answering a different AI question.

The downloadable Godot mini project includes the shared solver and headless verification runner. The current receipt is dijkstra-maps-for-roguelike-ai-verification.json, generated from a Godot 4.7.1-stable run with all ten behavioral checks passing plus a clean extracted-package rerun bound to the exact ZIP.

Where this fits in the Godot navigation stack

AStarGrid2D is still the right built-in when one actor needs one path to one target. A Dijkstra map is the better shape when many actors share a goal, when every cell needs a score, or when AI should read a tactical field instead of constantly asking for fresh paths.

For adjacent pieces, keep the tactical movement range article, the shared-goal flow field guide, the influence maps article, and the grid vs navmesh decision guide nearby.

PathForge is being built around that family of production grid systems: movement ranges, flow fields, Dijkstra and influence maps, dynamic blockers, scheduled queries, and editor-visible navigation state.