Recursive Backtracking Maze Generator

Basic explanation

A perfect maze is a grid in which every cell is reachable and there is exactly one simple path between any pair of cells. Graph-theoretically that means the passages form a spanning tree of the cell graph: $V-1$ edges on $V$ vertices, connected and acyclic.

The original project grew out of a Java ASCII game suite. The generator builds an odd-sized wall grid, carves passages by randomized recursive backtracking (depth-first search with a stack), then lets the player move 0 toward X. The browser work below reconstructs that generator and places it beside other classical spanning-tree maze algorithms so structural bias can be measured, not merely eyeballed.

Interactive laboratory

Use the visualizer to animate carving on a fixed seed, step event-by-event, and read the tracking legend: the pale cell is the previous position, the line is the edge being processed, and the outlined dot is the current cell.

Spanning trees and generation

View cells as vertices of a grid graph with edges to orthogonal neighbours. A perfect maze selects a subset of those edges forming a tree. Different algorithms correspond to different random processes on that graph:

• Recursive backtracking - randomized DFS. Follow unvisited neighbours, carve, and push history; at a dead end, pop until a branch remains. Typically produces long corridors and few junctions. Work is essentially linear in the number of cells once adjacency is fixed.
• Randomized Prim - grow from a frontier of walls bordering the maze. Repeatedly open a random frontier edge into an unvisited cell. Tends toward short branches and many dead ends because growth hugs the existing region.
• Kruskal - shuffle potential walls and join cells with a disjoint-set structure whenever they lie in different components. Growth is delocalized across the grid; the result is an unbiased random spanning tree among Kruskal’s sampling measure.
• Recursive division - start from open space and insert long walls with single gaps. Creates room-like blocks and strong axis-aligned texture; operation count tracks recursive chamber splits.
• Wilson’s algorithm - loop-erased random walks from unvisited cells until they hit the tree. Samples spanning trees uniformly (among all spanning trees), at the cost of discarded loops.
• Aldous-Broder - a simple random walk that adds an edge the first time it enters a new cell. Also uniform over spanning trees in the limit, but can revisit cells many times; operation counts are often highest here.

Uniformity matters theoretically: Wilson and Aldous-Broder target the uniform measure on spanning trees, while DFS and Prim induce visibly biased ensembles. The comparison panel later on this page reports dead ends, junctions, mean straight-run length, diameter, and operation counts on a shared seed - metrics that survive browser timing noise.

From the original Java game

The terminal demo preserves the early playable loop: odd dimensions, ASCII walls, move counting, and high scores. Source for Maze, Game, and Main remains downloadable above.

+-+-+-+-+-+-+-+-+-+-+
| |     |   |       |
+ + + + + + +-+-+ +-+
|   | | | | |0  |  X|
+ +-+ + + + + + +-+ +
| |   |   |   |   | |
+-+ +-+-+-+-+-+-+ + +
|   |     |     | | |
+ +-+-+-+ +-+ +-+ + +
|       |   |   |   |
+ +-+ +-+-+ +-+ +-+ +
|   | |   |   |   | |
+-+ + + + +-+ + + + +
|   |   |     | |   |
+-+-+-+-+-+-+-+-+-+-+

Comparing algorithmic bias in detail

Hold width, height, and seed fixed. Diameter is exact on a tree (longest shortest path). Operation counts expose algorithmic work - frontier checks, union-find probes, or random-walk steps - rather than animation speed. Read the notes under each card against the theory above: long corridors versus bushy dead ends, localized versus global growth, biased versus (asymptotically) uniform spanning trees.

Engineering notes

The Java version validates odd sizes and shares a small Game lifecycle with the wider ASCII suite. The TypeScript laboratory factors generation into pure functions returning event traces, so animation is a replay of discrete edge operations rather than a live mutation of a single opaque grid. That separation is what makes fair side-by-side comparison possible.