A* Maze Solver
A maze is carved with recursive backtracking, then A* searches for the exit — biased toward the goal by a Manhattan-distance heuristic. Watch the explored cells, the live frontier, and the shortest path appear as the algorithm runs, line by line.
- Start
- Goal
- Explored
- Frontier
- Path
Keyboard: Space play/pause · → step a line · R replay · N new maze
A* algorithm show the code · the running lines highlight live
expandNext():
open.sort((a, b) => b.f - a.f) // by f = g+h
current = open.pop() // lowest-f node
if current === goal:
return reconstruct(current) // parents → start
for each neighbour n of current:
if n is a wall or off-grid: skip
n.g = current.g + 1 // steps so far
n.h = manhattan(n, goal) // estimate left
n.f = n.g + n.h
if a cheaper path to n exists: skip
open.push(n) // join the frontier
closed.push(current) // mark exploredHow it works
1 · Build the maze
Recursive backtracking carves corridors from a solid grid, stepping two cells at a time and backtracking at dead ends. The result is a perfect maze — exactly one route between any two cells.
2 · Score every cell
A* ranks open cells by f = g + h: the steps taken so far
(g) plus the Manhattan distance left to the goal
(h). The heuristic keeps the search pointed at the exit.
3 · Expand the best
Each tick expands the lowest-f cell and queues its
neighbours. When the goal pops off the queue, parent pointers are
walked back to reveal the shortest path.
Two implementations
Python · pygame
The original desktop program. The same maze and search, animated in
a pygame window. Lives in python/ in the repo.
JavaScript · canvas
A faithful, file-for-file port in the repo — verified to produce the same path and node-expansion count as the Python on identical mazes.
This live demo
Runs an optimised version of that algorithm — heap-based A* with a scaled canvas renderer — so it stays smooth on custom mazes all the way up to 501×501.