Pathfinding was the part of the roguelike I was dreading. A* for every monster every turn, with a priority queue, in JavaScript, on a level with forty monsters. I had the Wikipedia tab open for a week.
Then I read Brian Walker's article on Dijkstra maps, from 2010, and closed the tab. Walker is the author of Brogue, and Brogue's monsters are the reason I wanted good pathfinding in the first place.
What it is
A Dijkstra map is a grid, the same size as the level, where every cell holds its walking distance to the nearest goal. The player's tile is the goal, so the player's cell is zero, the cells next to it are one, and so on outwards, around walls, until every reachable floor tile has a number.
You compute it once per turn. Then every monster that wants to reach the player looks at the eight cells around it and steps onto the lowest number. No search, no queue per monster, one array lookup and eight comparisons.
So the monsters never path to the player. The player's position spreads outward through the map and the monsters roll downhill.
The code
Every step costs one, so the fill is a plain breadth first search. If you add terrain costs later, swap the queue for a priority queue and it's Dijkstra proper, hence the name.
// src/ai/dijkstra.ts
export const UNREACHABLE = Infinity;
type Passable = (x: number, y: number) => boolean;
export function dijkstraMap(width: number, height: number, goals: Array<[number, number]>, passable: Passable): Float64Array {
const map = new Float64Array(width * height).fill(UNREACHABLE);
for (const [x, y] of goals) map[y * width + x] = 0;
relax(map, width, height, passable);
return map;
}
// Spread every known value to its neighbours until nothing improves.
// A plain queue is enough because a step always costs one.
export function relax(map: Float64Array, width: number, height: number, passable: Passable): void {
const queue: number[] = [];
for (let i = 0; i < map.length; i++) if (map[i] !== UNREACHABLE) queue.push(i);
let head = 0;
while (head < queue.length) {
const i = queue[head++];
const x = i % width;
const y = (i - x) / width;
const next = map[i] + 1;
for (let dy = -1; dy <= 1; dy++) {
for (let dx = -1; dx <= 1; dx++) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || ny < 0 || nx >= width || ny >= height || !passable(nx, ny)) continue;
const j = ny * width + nx;
if (map[j] <= next) continue;
map[j] = next;
queue.push(j);
}
}
}
}
// The neighbour with the lowest value, or null when the actor is already at the bottom
export function downhill(map: Float64Array, width: number, height: number, x: number, y: number): [number, number] | null {
let best: [number, number] | null = null;
let lowest = map[y * width + x];
for (let dy = -1; dy <= 1; dy++) {
for (let dx = -1; dx <= 1; dx++) {
const nx = x + dx;
const ny = y + dy;
if (nx < 0 || ny < 0 || nx >= width || ny >= height) continue;
const value = map[ny * width + nx];
if (value < lowest) {
lowest = value;
best = [nx, ny];
}
}
}
return best;
}relax is the loop that does the work, and it's separate from the seeding for a reason that comes next. The map is a Float64Array so that Infinity can mean unreachable and the maths in the next section works without a special case.
Flee maps
This is the part of Walker's article that made me sit up. A frightened monster should run away from the player. The naive version is to step onto the highest number instead of the lowest, and it's wrong: the monster runs into the nearest dead end and stops there, because the corner of a dead end is a local maximum.
Walker's fix: take the chase map, multiply every value by a negative number a bit past one, say -1.2, and run the relaxation again.
// src/ai/flee.ts
import { relax, UNREACHABLE } from './dijkstra';
export function fleeMap(chase: Float64Array, width: number, height: number, passable: (x: number, y: number) => boolean): Float64Array {
// Far away becomes very attractive, then the rescan smooths the valleys out
const map = Float64Array.from(chase, (value) => (value === UNREACHABLE ? value : value * -1.2));
relax(map, width, height, passable);
return map;
}The multiplication turns the far away cells into deep valleys. The rescan smooths it out, so a dead end next to the player is no longer attractive and a long corridor leading away is. Rolling downhill on this map takes the monster around the player and out of the room, not into a corner. The 1.2 is a knob: higher and monsters prefer the far corners of the level, lower and they settle for keeping a bit of distance.
Everything else
Once the map is a value you can add and scale, it stops being pathfinding and becomes a way to describe what a monster wants.
- Autoexplore: the goals are every unexplored floor tile. Roll downhill and you walk to the nearest one, then the next. Brogue and DCSS both have this on a key, and it's one map.
- Several goals at once: seed the map with the player and all the stairs, and a monster that rolls downhill goes to whichever is closest. Seed it with every item on the floor and you get a looting map.
- Combined wants: add a chase map to a flee map from the lava and the monster chases you but won't cross it. Weight each map before adding and you can tune a personality without writing an if.
- Packs: a map seeded with the pack leader keeps the pack together, a map seeded with the pack's own members, scaled negative, spreads them out.
Cost
One map is a pass over the level. On an 80 by 25 level that's two thousand cells, and even a dozen maps a turn is nothing in a turn based game that spends most of its time waiting for a key press. I compute the player map every turn and the others on demand, cached until the goals change.
The one thing a Dijkstra map doesn't do is a path for a single thing to a single target, a thrown item's arc or a bolt. A line does that.
Walker's article, The Incredible Power of Dijkstra Maps on RogueBasin, has more tricks than I've listed here, and it's still the best thing I've read on the subject.