How does a computer find its way through a maze it has never seen?
Pathfinder shows the A* (A-star) search algorithm at work, slowed down enough to watch. It starts at the white square and looks for the ring. Light cells are the frontier it is about to explore; faint cells are places it has already ruled out. When it reaches the goal, it traces the shortest route back.
Why A* is clever
A plain search spreads out evenly in every direction like a ripple. A* adds a guess: for every cell, it adds the distance already travelled to an estimate of the distance left, and always explores the most promising cell next. That pulls the search toward the goal, so it usually checks far fewer cells.
// score = cost so far + estimated cost to the goal
const f = (cell) => g[cell] + heuristic(cell, goal);
// always expand the open cell with the lowest score
const current = open.reduce((a, b) => f(a) <= f(b) ? a : b);Switch the heuristic to None and A* becomes Dijkstra's algorithm, which has no guess. Watch how much more of the maze it has to explore to find the same path. The cell count under the controls keeps score.
Try it
- Drag across the grid to draw walls; drag over a wall to erase it. The search starts again as you draw.
- Wall off the goal completely, and the search reports there's no way through.
- Raise the speed to see the whole search at once, or lower it to follow each step.
Where this goes on a client site
- Store and venue maps that route visitors to a room or a shelf.
- Explainers that make a product's "smart" feature visible instead of just claiming it.
- Small games and interactive puzzles for campaigns.