Perfect Mazes
A perfect maze has exactly one path between any two cells — no loops, no isolated sections. Algorithms that generate such mazes must visit every cell while carving passages.
Depth-First Search Backtracker
- Start at a random cell and mark it
visited. - Randomly pick an unvisited neighbour, remove the wall between, push current cell onto a stack, and move to the neighbour.
- If no unvisited neighbours remain, pop a cell off the stack (back-tracking) and continue.
- Repeat until every cell has been visited.
The result is a snaking, bias-free maze with long corridors punctuated by bursts of branching where the algorithm back-tracked.
Implementation Details
- The grid is stored as a 2-D array of cell objects, each tracking which walls remain.
- The stack is implicit in the recursion; we use a manual array to avoid exceeding the call-stack in JavaScript.
- One cell is carved per animation frame so you can watch the algorithm explore in real-time.
Controls
Press Regenerate in the gallery to seed a fresh maze with a new random starting point.