Pathfinding Deep Dive
This tutorial was written in February 2026, for v2 of the engine.
The click-to-move tutorial built a navigation system powered by 4-direction BFS. It works, but BFS is one tool in the box. It can't do diagonals, it treats every tile the same, and it has no sense of direction — it floods outward until it stumbles into the goal. Depending on what your game needs, there are better options.
We're gonna compare four pathfinding algorithms on the same grid: 4-direction BFS, 8-direction BFS, Dijkstra's algorithm with weighted terrain, and A* search with a heuristic. Same sprites, same walls, same click-to-move setup. The only thing that changes is how the path gets found.
Setup
This is the same grid, sprites, and free movement system from the click-to-move tutorial. If any of it looks unfamiliar, go read that one first — we're picking up right where it left off:
const sprites = {
floor: [[
3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 11, 3,
3, 3, 3, 3, 3, 3, 3, 3,
3, 11, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 11, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3,
3, 3, 3, 3, 3, 3, 3, 3,
], null],
wall: [[
5, 5, 5, 5, 5, 5, 5, 5,
5, 6, 5, 5, 5, 6, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 6, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 6, 5, 5, 5, 5, 6,
5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 6, 5, 5,
], null],
player: [[
-1, -1, 12, 12, 12, 12, -1, -1,
-1, 12, 12, 12, 12, 12, 12, -1,
-1, 12, 7, 12, 12, 7, 12, -1,
-1, 12, 12, 12, 12, 12, 12, -1,
-1, -1, 12, 12, 12, 12, -1, -1,
-1, -1, 12, 12, 12, 12, -1, -1,
-1, -1, 12, -1, -1, 12, -1, -1,
-1, -1, 12, -1, -1, 12, -1, -1,
], null],
};
// prettier-ignore
const grid = [
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,1,0,0,1,1,1,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,0,1,1,1,1,1,0,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1],
[1,0,0,0,1,0,0,0,0,0,0,1,0,0,0,1],
[1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,0,0,0,0,0,0,1,1,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1],
];
let playerPx = 12, playerPy = 12;
let targetX = -1, targetY = -1;
let path = [];
const speed = 1.5;
function findPath(sx, sy, gx, gy) {
if (mget(gx, gy, 0) === 'wall') return null;
const key = (x, y) => x + ',' + y;
const queue = [{ x: sx, y: sy }];
const visited = new Set([key(sx, sy)]);
const parent = {};
while (queue.length > 0) {
const { x, y } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
for (const [dx, dy] of [[0, -1], [1, 0], [0, 1], [-1, 0]]) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
if (visited.has(key(nx, ny))) continue;
if (mget(nx, ny, 0) === 'wall') continue;
visited.add(key(nx, ny));
parent[key(nx, ny)] = { x, y };
queue.push({ x: nx, y: ny });
}
}
return null;
}
function init() {
cursor('crosshair');
for (let y = 0; y < 16; y++)
for (let x = 0; x < 16; x++)
mset(x, y, grid[y][x] === 1 ? 'wall' : 'floor');
}
function update() {
if (click()) {
const pos = mouse();
const gx = Math.max(0, Math.min(15, Math.floor(pos.x / 8)));
const gy = Math.max(0, Math.min(15, Math.floor(pos.y / 8)));
const sx = Math.floor(playerPx / 8);
const sy = Math.floor(playerPy / 8);
const result = findPath(sx, sy, gx, gy);
if (result) {
path = result;
targetX = gx;
targetY = gy;
}
}
if (path.length > 0) {
const tx = path[0].x * 8 + 4;
const ty = path[0].y * 8 + 4;
const dx = tx - playerPx;
const dy = ty - playerPy;
const dist = Math.sqrt(dx * dx + dy * dy);
if (dist < 1) {
playerPx = tx;
playerPy = ty;
path.shift();
} else {
playerPx += (dx / dist) * speed;
playerPy += (dy / dist) * speed;
}
}
}
function draw(time, frame) {
cls(0);
map(0);
for (const step of path)
circfill(step.x * 8 + 4, step.y * 8 + 4, 1, 9);
if (targetX >= 0) {
if (frame % 30 < 15)
rectfill(targetX * 8 + 2, targetY * 8 + 2, targetX * 8 + 5, targetY * 8 + 5, 10);
else
rect(targetX * 8, targetY * 8, targetX * 8 + 8, targetY * 8 + 8, 10);
}
spr('player', Math.floor(playerPx) - 4, Math.floor(playerPy) - 4);
}The player starts at (1, 1) and glides toward each waypoint at 1.5 pixels per frame. findPath() returns an array of {x, y} steps — the movement code doesn't care how the path was found. That's the key insight here: every algorithm we build returns the same shape, so the movement system never changes. Only the pathfinding does.
4-Direction BFS
Here's the findPath() function from the setup, pulled out on its own. This is our baseline — every improvement builds on it:
function findPath(sx, sy, gx, gy) {
if (mget(gx, gy, 0) === 'wall') return null;
const key = (x, y) => x + ',' + y;
const queue = [{ x: sx, y: sy }];
const visited = new Set([key(sx, sy)]);
const parent = {};
while (queue.length > 0) {
const { x, y } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
for (const [dx, dy] of [[0, -1], [1, 0], [0, 1], [-1, 0]]) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
if (visited.has(key(nx, ny))) continue;
if (mget(nx, ny, 0) === 'wall') continue;
visited.add(key(nx, ny));
parent[key(nx, ny)] = { x, y };
queue.push({ x: nx, y: ny });
}
}
return null;
}BFS explores outward from the start, one ring at a time. Every cell remembers which cell it came from. Once we reach the goal, we trace those parents backward to build the shortest path. The [[0,-1],[1,0],[0,1],[-1,0]] array defines four cardinal directions — up, right, down, left. Paths always run along grid axes, so every route ends up as a staircase of horizontal and vertical segments.
The limitation is pretty clear once you see it: the player can't cut corners. A destination one tile northeast takes two steps (one right, one up) instead of one diagonal. Let's fix that.
8-Direction BFS
Expanding to eight directions means adding the four diagonals — NE, SE, SW, NW — to the neighbor list. But there's a catch. Without a safety check, the player can squeeze through diagonal gaps between two walls that share a corner. The fix: before allowing a diagonal move, we check that both adjacent cardinal cells are open:
function findPath(sx, sy, gx, gy) {
if (mget(gx, gy, 0) === 'wall') return null;
const key = (x, y) => x + ',' + y;
const queue = [{ x: sx, y: sy }];
const visited = new Set([key(sx, sy)]);
const parent = {};
const dirs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]];
while (queue.length > 0) {
const { x, y } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
if (visited.has(key(nx, ny))) continue;
if (mget(nx, ny, 0) === 'wall') continue;
if (dx !== 0 && dy !== 0) {
if (mget(x + dx, y, 0) === 'wall') continue;
if (mget(x, y + dy, 0) === 'wall') continue;
}
visited.add(key(nx, ny));
parent[key(nx, ny)] = { x, y };
queue.push({ x: nx, y: ny });
}
}
return null;
}The corner-cutting check is the if (dx !== 0 && dy !== 0) block. If we're trying to move northeast, both the north cell and the east cell must be open. Otherwise we'd clip through a wall corner — think of an L-shaped wall where the player slides through the bend.
BFS treats all steps as equal cost. A diagonal step actually covers more ground (about 1.41 tiles) than a cardinal step (1 tile), but BFS counts them the same. For unweighted grids this produces correct shortest paths in terms of step count, but not true distance. The next two sections address this.
Dijkstra's Algorithm
BFS treats every step the same. Dijkstra's algorithm doesn't — it tracks the total cost to reach each cell and always expands the cheapest one first. That means we can give different terrain types different costs. Mud is expensive, floor is cheap, and the path routes around the mud when going the long way is actually faster.
We add a brown mud sprite and scatter some mud patches across the grid. Floor costs 1, mud costs 3. Diagonal steps multiply the terrain cost by 1.41 (the square root of 2) to account for the extra distance. The queue is a sorted array — we insert each new entry at the right position by cost. On a 16x16 grid this is fast enough. For larger maps you'd want a binary heap:
function findPath(sx, sy, gx, gy) {
const tile = mget(gx, gy, 0);
if (tile === 'wall') return null;
const key = (x, y) => x + ',' + y;
const dirs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]];
const cost = { floor: 1, mud: 3 };
const dist = {};
dist[key(sx, sy)] = 0;
const parent = {};
const queue = [{ x: sx, y: sy, d: 0 }];
while (queue.length > 0) {
const { x, y, d } = queue.shift();
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return result.reverse();
}
if (d > (dist[key(x, y)] ?? Infinity)) continue;
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
const nt = mget(nx, ny, 0);
if (nt === 'wall') continue;
if (dx !== 0 && dy !== 0) {
if (mget(x + dx, y, 0) === 'wall') continue;
if (mget(x, y + dy, 0) === 'wall') continue;
}
const moveCost = (dx !== 0 && dy !== 0) ? cost[nt] * 1.41 : cost[nt];
const nd = d + moveCost;
const nk = key(nx, ny);
if (nd < (dist[nk] ?? Infinity)) {
dist[nk] = nd;
parent[nk] = { x, y };
let i = 0;
while (i < queue.length && queue[i].d <= nd) i++;
queue.splice(i, 0, { x: nx, y: ny, d: nd });
}
}
}
return null;
}The priority queue is the big change. BFS uses a plain FIFO queue — first in, first out. Dijkstra sorts by accumulated cost, so cheap paths get explored first. The if (d > (dist[key(x, y)] ?? Infinity)) continue line skips stale entries — if we already found a cheaper route to this cell, there's no point expanding it again.
A* Search
Dijkstra always expands the cheapest cell, but it has no sense of direction. It searches outward like ripples in a pond. A* adds a heuristic — an estimate of how far each cell is from the goal. Cells that look closer get explored first. We end up with the same optimal path, but A* looks at far fewer cells along the way.
For 8-direction movement, the right heuristic is octile distance: max(dx, dy) + (sqrt(2) - 1) * min(dx, dy). It accounts for diagonal steps costing more than cardinal ones. The priority queue sorts by f = g + h, where g is the cost so far and h is the heuristic estimate:
function findPath(sx, sy, gx, gy) {
const tile = mget(gx, gy, 0);
if (tile === 'wall') return null;
const key = (x, y) => x + ',' + y;
const dirs = [[0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1]];
const cost = { floor: 1, mud: 3 };
function heuristic(x, y) {
const dx = Math.abs(x - gx), dy = Math.abs(y - gy);
return Math.max(dx, dy) + (Math.SQRT2 - 1) * Math.min(dx, dy);
}
const g = {};
g[key(sx, sy)] = 0;
const parent = {};
const explored = new Set();
const queue = [{ x: sx, y: sy, f: heuristic(sx, sy) }];
while (queue.length > 0) {
const { x, y } = queue.shift();
const k = key(x, y);
if (explored.has(k)) continue;
explored.add(k);
if (x === gx && y === gy) {
const result = [];
let cx = gx, cy = gy;
while (cx !== sx || cy !== sy) {
result.push({ x: cx, y: cy });
const p = parent[key(cx, cy)];
cx = p.x; cy = p.y;
}
return { path: result.reverse(), explored };
}
for (const [dx, dy] of dirs) {
const nx = x + dx, ny = y + dy;
if (nx < 0 || nx > 15 || ny < 0 || ny > 15) continue;
const nt = mget(nx, ny, 0);
if (nt === 'wall') continue;
if (dx !== 0 && dy !== 0) {
if (mget(x + dx, y, 0) === 'wall') continue;
if (mget(x, y + dy, 0) === 'wall') continue;
}
const moveCost = (dx !== 0 && dy !== 0) ? cost[nt] * 1.41 : cost[nt];
const ng = (g[k] ?? Infinity) + moveCost;
const nk = key(nx, ny);
if (ng < (g[nk] ?? Infinity)) {
g[nk] = ng;
parent[nk] = { x, y };
const f = ng + heuristic(nx, ny);
let i = 0;
while (i < queue.length && queue[i].f <= f) i++;
queue.splice(i, 0, { x: nx, y: ny, f });
}
}
}
return null;
}The red dots are explored cells — every cell the algorithm had to look at before finding the path. Compare this to Dijkstra on the same route and you'll see A* typically explores a fraction of the cells. The savings get more dramatic on larger maps.
This version returns { path, explored } instead of just the path. The explored set is only for visualization — in a real game you'd drop it and return the path directly.
A* only finds the optimal path when the heuristic is optimistic — it should guess equal to or less than the real cost, never more. If the heuristic overestimates, A* might skip cheaper routes and return a suboptimal path. Octile distance works here because our cheapest terrain (floor) costs 1 per step, matching the heuristic's assumption. If your cheapest terrain cost less than 1, you'd need to scale the heuristic down so it never guesses too high.
Putting It All Together
Here's all four algorithms in one demo. Press 1 through 4 to switch between them. Every click runs all four so the HUD can show comparison stats — path length and explored cell count — but only the active algorithm's path and search area get drawn:
const algorithms = ['BFS 4-dir', 'BFS 8-dir', 'Dijkstra', 'A*'];
let active = 0;
let results = [];
// inside update()
for (let i = 0; i < 4; i++) {
if (btnp(String(i + 1)) && active !== i) {
active = i;
path = results[active]?.path ?? [];
}
}
if (click()) {
// run all four algorithms, display the active one
results = [
findPathBfs4(sx, sy, gx, gy),
findPathBfs8(sx, sy, gx, gy),
findPathDijkstra(sx, sy, gx, gy),
findPathAStar(sx, sy, gx, gy),
];
path = results[active]?.path ?? [];
}
// inside draw()
const r = results[active];
if (r) {
for (const k of r.explored) {
const [ex, ey] = k.split(',').map(Number);
rectfill(ex * 8 + 2, ey * 8 + 2, ex * 8 + 5, ey * 8 + 5, 8);
}
}
text(algorithms[active] + ' [' + (active + 1) + ']', 1, 1, 7);
if (r) text('path:' + r.path.length + ' explored:' + r.explored.size, 1, 8, 7);Try clicking the same destination with each algorithm. BFS 4-dir produces the longest paths (no diagonals). BFS 8-dir takes shortcuts but ignores terrain cost. Dijkstra finds the true cheapest path through weighted terrain. A* finds the same path as Dijkstra but explores fewer cells getting there. The right choice depends on what your game cares about — simplicity, accuracy, or performance. Take some time to experiment with different start and end positions to get a feel for how each one behaves.
Going Further
- Jump Point Search — an optimization for uniform-cost grids that skips large swaths of open space. Faster than A* on maps with big open areas.
- Flow fields — instead of one path per unit, compute a direction map from every cell to the goal. Efficient when many units all pathfind to the same target (strategy games, tower defense).
- Hierarchical pathfinding — divide the map into clusters, pathfind between clusters first, then within each cluster. Scales to huge worlds where full A* would be too slow.
- Dynamic obstacles — recalculate paths when the map changes. Partial replanning from the blocked cell is faster than re-running from scratch.
- Theta* — any-angle pathfinding that produces smoother paths than grid-constrained A* by allowing line-of-sight shortcuts between non-adjacent cells.