About

A maze is a spanning tree of a grid graph. Every cell connects to every other cell by exactly one path. Getting the generation wrong produces either trivial puzzles (too few dead-ends) or unsolvable structures (cycles or isolated regions). This tool implements five distinct spanning-tree algorithms, each producing mazes with measurably different topological properties: corridor length distribution, branching factor, and bias direction. The Recursive Backtracker uses depth-first search and produces corridors with a high "river" factor (mean path length before a junction). Kruskal's randomized edge approach and Prim's frontier growth yield shorter, more branching passages. Aldous-Broder generates a provably uniform random spanning tree at the cost of O(n²) expected time. Binary Tree is O(n) but introduces a visible northeast diagonal bias. Solution overlay uses A* with Manhattan heuristic. The tool approximates ideal maze difficulty for a given grid size but does not account for human perceptual biases toward certain wall patterns.

Formulas

A* evaluates cells by minimizing the cost function:

f(n) = g(n) + h(n)

where g(n) is the actual cost from start to node n, and h(n) is the heuristic estimate to the goal. The Manhattan heuristic is:

h(n) = |x_n − x_goal| + |y_n − y_goal|

Total cells in the grid: V = r × c. A perfect maze (spanning tree) has exactly V − 1 passages. Total possible internal edges in the grid graph: E = 2rc − r − c. The ratio of opened passages to total possible edges determines maze density.

Kruskal's uses a Union-Find (disjoint set) structure. Two cells merge only if find(a) ≠ find(b), preventing cycles. Path compression and union by rank give near-O(1) amortized operations via the inverse Ackermann function α(n).

Reference Data

Algorithm	Time Complexity	Dead-End %	River Factor	Bias	Uniform?	Best For
Recursive Backtracker	O(n)	~10%	High	None	No	Long winding corridors
Kruskal's	O(E log E)	~25%	Low	None	No	Short branching paths
Prim's	O(E log V)	~20%	Medium	None	No	Organic tree-like shapes
Aldous-Broder	O(n²) expected	~15%	Medium	None	Yes	Unbiased uniform sampling
Binary Tree	O(n)	~30%	Low	NE diagonal	No	Fast generation, teaching
A* Solver	O(E log V)	N/A	N/A	N/A	N/A	Optimal shortest path
Spanning Tree Properties
Edges in tree	V − 1 where V = rows × cols
Total grid edges	2rc − r − c for r rows, c cols
Dead-end cell	Cell with exactly 1 open passage
Junction cell	Cell with 3 or 4 open passages
River factor	Mean straight-line run before turn or junction
Perfect maze	No loops, no isolated cells. Exactly one path between any two cells.
Cycle detection	Union-Find (Kruskal's) prevents merging same-set cells
A* heuristic	Manhattan: \|x₁ − x₂\| + \|y₁ − y₂\|

Frequently Asked Questions

A perfect maze is a spanning tree of the grid graph. Every pair of cells is connected by exactly one path. There are no loops and no isolated regions. A grid of r × c cells produces exactly (r × c) − 1 open passages in a perfect maze. All five algorithms in this tool generate perfect mazes.

Aldous-Broder performs a random walk visiting cells until all cells have been visited at least once. This is the Coupon Collector problem. For V cells, the expected number of steps is O(V × ln(V)), but worst-case can be O(V²). The tradeoff is that it produces a provably uniform random spanning tree, meaning every possible maze is equally likely. Other algorithms have statistical biases in their output distributions.

Binary Tree always carves either North or East for each cell. This creates two unbroken corridors along the entire north row and east column. The maze has a visible diagonal texture running from southwest to northeast. Dead-ends cluster in the south and west edges. This bias makes it unsuitable for fair game-level generation but excellent for teaching maze concepts due to its O(n) simplicity.

The tool caps at 100×100 (10,000 cells) to maintain interactive animation performance in the browser. At that size, Recursive Backtracker completes in under 50ms. Aldous-Broder may require several seconds. For static (non-animated) generation, the algorithms could handle larger grids, but canvas rendering at thousands of pixels becomes the bottleneck. Export to PNG preserves full resolution regardless of screen size.

In a perfect maze, there is only one path between any two cells. A* will find it. The Manhattan heuristic is admissible (never overestimates) for grid movement, so A* is guaranteed optimal. In this context, "shortest" and "only" are the same path. The solver animates exploration to show which cells A* evaluates, which is always a subset of total cells due to the heuristic pruning.