Project
Pathfinding Visualiser
2021 (visualiser 2025)
Pathfinding is one of the first things you encounter in game AI. It's how enemies navigate levels, how NPCs find their way around obstacles, and how strategy games calculate unit movement. I originally implemented these algorithms in C# for game projects, where A* is a staple for any character that needs to navigate around the world intelligently.
The visualiser below is a web port built for this site, but the logic is the same.
A* and BFS both explore a grid looking for the shortest route between two points, but they approach it differently. BFS fans out in every direction equally, while A* uses a heuristic to bias its search toward the goal. Watching them run side by side makes that difference obvious in a way that reading code alone never quite does.
Draw walls to create obstacles, hit Maze to generate a random layout, then switch between A* and BFS to compare them. The speed control lets you slow it right down and follow every step, or crank it up to just see the result.
Built on the HTML5 Canvas API with no external dependencies, just the algorithms implemented from scratch in TypeScript.
Visualiser
How it works
Breadth-First Search (BFS)▾
// A FIFO queue guarantees we always process the closest cells first,
// which is what gives BFS its shortest-path guarantee on uniform grids.
function bfs(grid: Cell[], start: Point, end: Point): Point[] | null {
const queue = [start] // cells to explore, in order of discovery
const visited = new Set([toIndex(start)]) // prevents revisiting the same cell
const parent = new Map<number, number>() // records which cell we came from
while (queue.length > 0) {
const current = queue.shift()! // oldest item first — breadth, not depth
if (current.row === end.row && current.col === end.col)
return reconstructPath(parent, end)
for (const nb of neighbours(current, grid)) {
const ni = toIndex(nb)
if (visited.has(ni)) continue // already seen via a shorter or equal path
visited.add(ni)
parent.set(ni, toIndex(current)) // remember how we got here
queue.push(nb)
}
}
return null // queue emptied without finding the end
}BFS fans out level by level. It visits every cell one step away before any cell two steps away, and so on. The FIFO queue is what creates this behaviour. Because it always finds the shallowest path first, it guarantees the shortest result on any grid where all moves cost the same.
A* Search▾
// A* extends BFS by adding a heuristic: an estimate of the remaining distance.
// Rather than exploring all nearby cells equally, it prioritises cells that
// look closer to the goal — so it finds the path with far fewer steps.
function aStar(grid: Cell[], start: Point, end: Point): Point[] | null {
const open = [{ ...start, g: 0, f: manhattan(start, end) }]
const closed = new Set<number>() // fully explored cells
const gScore = new Map([[toIndex(start), 0]]) // cheapest known cost from start
const parent = new Map<number, number>()
while (open.length > 0) {
// Always expand the cell with the lowest f = g + h first
open.sort((a, b) => a.f - b.f)
const current = open.shift()!
const ci = toIndex(current)
if (closed.has(ci)) continue // a cheaper path to this cell was already found
closed.add(ci)
if (current.row === end.row && current.col === end.col)
return reconstructPath(parent, end)
for (const nb of neighbours(current, grid)) {
const ni = toIndex(nb)
if (closed.has(ni)) continue
const g = current.g + 1 // cost to reach this neighbour
if (g >= (gScore.get(ni) ?? Infinity)) continue // not an improvement
gScore.set(ni, g)
parent.set(ni, ci)
open.push({
...nb,
g,
f: g + manhattan(nb, end), // f = actual cost + estimated cost remaining
})
}
}
return null
}
// Manhattan distance: the minimum steps between two points on a grid
// (no diagonal moves, so we just sum the row and column differences)
function manhattan(a: Point, b: Point): number {
return Math.abs(a.row - b.row) + Math.abs(a.col - b.col)
}A* adds one idea to Dijkstra: a heuristic h that estimates the remaining distance to the goal. The Manhattan distance is a perfect heuristic here, it never overestimates, so A* is guaranteed to find the shortest path. In practice it explores a fraction of the cells that BFS would.
Dijkstra's Algorithm▾
// Dijkstra is the general form that both BFS and A* are derived from.
// It always expands the cheapest unvisited node — like A* without the
// heuristic, or like BFS but with a priority queue instead of a plain queue.
function dijkstra(grid: Cell[], start: Point, end: Point): Point[] | null {
const pq = [{ ...start, cost: 0 }] // priority queue ordered by total cost
const dist = new Map([[toIndex(start), 0]]) // cheapest known distance to each cell
const visited = new Set<number>()
const parent = new Map<number, number>()
while (pq.length > 0) {
pq.sort((a, b) => a.cost - b.cost) // min-cost first (a real heap would be faster)
const current = pq.shift()!
const ci = toIndex(current)
if (visited.has(ci)) continue // already settled at a lower cost
visited.add(ci)
if (current.row === end.row && current.col === end.col)
return reconstructPath(parent, end)
for (const nb of neighbours(current, grid)) {
const ni = toIndex(nb)
if (visited.has(ni)) continue
const newCost = current.cost + edgeWeight(current, nb)
if (newCost < (dist.get(ni) ?? Infinity)) {
dist.set(ni, newCost)
parent.set(ni, ci)
pq.push({ ...nb, cost: newCost })
}
}
}
return null
// Note: on a uniform grid where every edge costs 1,
// this produces the exact same result as BFS.
}Dijkstra is the ancestor of both. It explores nodes in order of their total cost from the start, using a priority queue instead of a FIFO queue. A* is Dijkstra with a heuristic added; BFS is Dijkstra simplified for uniform-cost graphs. On a uniform grid all three find the same path. The difference is how many cells they examine along the way.