Dijkstra's — Terrain Costs
What if your hero doesn’t just want the shortest path — they want the cheapest one? A battlefield isn’t all flat floors. There’s mud that slows you down, roads that speed you up, rivers you’d rather not wade through. Breadth-First Search treats every tile the same. Dijkstra’s algorithm knows better.
Edsger Dijkstra published this algorithm in 1959 — originally to find the shortest driving route between two Dutch cities. Six decades later, it’s still powering pathfinding in games from Civilization to Dwarf Fortress to your next project.
What You’ll Master:
- Weighted terrain — mud, roads, and everything in between
- The priority queue: processing cheapest tiles first
- Why “shortest” and “cheapest” aren’t always the same thing
- The upgrade path to A* (spoiler: it’s one extra line)
Prerequisites:
- Completed the BFS tutorial
- Comfortable with the node/queue pattern from last time
What Just Happened?
Notice how the path snakes toward the blue road tiles even when a more direct route through the mud would use fewer steps? That’s Dijkstra’s algorithm at work — it found the route with the lowest total cost, not the fewest tiles.
Click somewhere reachable only via the mud patches and watch what happens. The algorithm will begrudgingly wade through when there’s no better option, but it’ll always find you the cheapest route.
This changes everything for world-building:
- Roads feel faster because they genuinely are — your AI will use them
- Swamps and mud become natural obstacles that influence routing without being walls
- Terrain variety has real mechanical consequences, not just visual flavour
From Breadth-First to Dijkstra’s: One Key Change
BFS uses a simple queue — tiles are processed in the order they’re added. Dijkstra’s replaces that with a priority queue — tiles are always processed in order of cheapest accumulated cost.
// BFS: tiles queued in discovery order
const queue = [];
queue.push(startNode);
const current = queue.shift(); // always the oldest
// Dijkstra's: tiles queued by cost (cheapest first)
const openList = [];
openList.push(startNode);
openList.sort((a, b) => a.cost - b.cost); // sort every step
const current = openList.shift(); // always the cheapest
That single conceptual change — from “oldest first” to “cheapest first” — is the entire difference between the two algorithms. The rest of the code is almost identical.
The Full Implementation
Here’s Dijkstra’s with proper terrain cost support:
// Terrain movement costs
const TERRAIN_COST = {
floor: 1,
road: 0.5, // faster — AI will prefer these
mud: 4, // slower — AI will avoid when possible
water: 8 // very slow — AI only uses if necessary
};
class DijkstraNode {
constructor(x, y, parent = null, cost = 0) {
this.x = x;
this.y = y;
this.parent = parent;
this.cost = cost; // total cost from start to this tile
}
key() { return `${this.x},${this.y}`; }
}
function findPathDijkstra(startX, startY, targetX, targetY, map) {
const startNode = new DijkstraNode(startX, startY);
const openList = [startNode];
const bestCost = {}; // cheapest known cost to each tile
bestCost[startNode.key()] = 0;
while (openList.length > 0) {
// Always process the cheapest node next
openList.sort((a, b) => a.cost - b.cost);
const current = openList.shift();
// Reached the target!
if (current.x === targetX && current.y === targetY) {
return buildPath(current);
}
for (const dir of DIRECTIONS) {
const nx = current.x + dir.x;
const ny = current.y + dir.y;
if (!isWalkable(nx, ny, map)) continue;
// Cost to enter this neighbour
const terrain = map[ny][nx];
const stepCost = TERRAIN_COST[terrain] ?? 1;
const newCost = current.cost + stepCost;
const key = `${nx},${ny}`;
if (bestCost[key] === undefined || newCost < bestCost[key]) {
// This is a better route — record it and queue the node
bestCost[key] = newCost;
openList.push(new DijkstraNode(nx, ny, current, newCost));
}
}
}
return null; // no path exists
}
The bestCost map is crucial. Unlike BFS — where you only visit each tile once — Dijkstra’s might revisit a tile if a cheaper route to it is discovered later. The bestCost check ensures we only ever follow the cheaper option.
Terrain Costs in Practice
How you assign costs shapes how your world feels to play. Some examples:
// An RPG overworld
const OVERWORLD_COSTS = {
grass: 1,
forest: 2, // slows movement slightly
mountain: 5, // significant obstacle
swamp: 8, // almost impassable
road: 0.5 // AI will always prefer these
};
// A factory floor stealth game
const FACTORY_COSTS = {
floor: 1,
catwalk: 1,
grating: 2, // noisy — guards avoid, player beware
oil_spill: 6, // hazard
conveyor: 0.5 // free movement if going with the belt
};
// A naval strategy game
const NAVAL_COSTS = {
open_sea: 1,
shallows: 3, // slow for big ships
reefs: 10, // dangerous
harbour: 0.5 // fast passage
};
The same algorithm, wildly different game feel.
Why Not Just Use BFS With More Walls?
You could fake terrain cost by duplicating tiles — turn every “mud” tile into a 4-tile-wide detour that forces longer paths. But that:
- Makes your map data enormous
- Breaks down with fractional costs (0.5 for roads)
- Is a maintenance nightmare when you want to tweak costs
Dijkstra’s handles it natively and elegantly.
Performance: The Priority Queue Problem
The sort() call above is fine for small maps, but it’s O(n log n) every step. On a large map with thousands of open nodes, that adds up. The proper solution is a min-heap (binary heap priority queue):
class MinHeap {
constructor() { this.heap = []; }
push(node) {
this.heap.push(node);
this._bubbleUp(this.heap.length - 1);
}
pop() {
const top = this.heap[0];
const last = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = last;
this._sinkDown(0);
}
return top;
}
get size() { return this.heap.length; }
_bubbleUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (this.heap[parent].cost <= this.heap[i].cost) break;
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
}
}
_sinkDown(i) {
while (true) {
let smallest = i;
const left = 2 * i + 1, right = 2 * i + 2;
if (left < this.heap.length && this.heap[left].cost < this.heap[smallest].cost) smallest = left;
if (right < this.heap.length && this.heap[right].cost < this.heap[smallest].cost) smallest = right;
if (smallest === i) break;
[this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
i = smallest;
}
}
}
// Usage: replace openList.sort() + shift() with heap.push() + pop()
const openHeap = new MinHeap();
openHeap.push(startNode);
// ...
const current = openHeap.pop(); // O(log n) instead of O(n log n)
For tutorial-scale maps (under 50×50), the sort version is perfectly readable and fast enough. Graduate to a proper heap when you start seeing frame-rate hiccups.
What Dijkstra’s Can’t Do (Yet)
Dijkstra’s is optimal — it will always find the cheapest path. But it’s not fast. It explores tiles in all directions, including ones completely away from the target, because it doesn’t know where the target is relative to the current search frontier.
Watch the demo again. See how the search ripples outward in every direction, even away from where you clicked? On a large open map this wastes a lot of work.
The fix is to give the algorithm a sense of direction — a heuristic estimate of how far each tile is from the target. That’s exactly what A* does.
Dijkstra’s + heuristic = A*. You’re one tutorial away from the gold standard.
Next up: Greedy Best-First — lightning-fast but occasionally wrong. Understanding its trade-offs is the final piece before A*.