The idea: a perfect maze is a spanning tree
Think of the grid as a graph. Each of the 20 × 12 = 240 cells is a vertex, and each of the 448 inner walls is an edge between two neighbouring cells. Carving a wall opens that edge.
A perfect maze has exactly one path between any two cells: no cell is cut off and there are no loops. That is exactly a spanning tree of the grid graph. It always has 240 cells joined by 239 passages. Every maze generator on this page is a way to pick one spanning tree at random.
Both grids start fully walled in. Every step of the animation runs the left and the right generator at the same time. By default, each side carves 3 more passages per step. In Options you can change this to a number of moves per step, which shows the work that carves nothing. When a side is done it shows its statistics and its solution from S (top-left) to G (bottom-right), found with breadth-first search.
The generators and what they keep
| Generator | Working structure (drawn) | One move |
|---|---|---|
| Recursive backtracker (randomized DFS) | Stack of cells (light orange, top dark orange) | Carve to a random unvisited neighbour and push it. With no such neighbour, pop (backtrack). |
| Randomized Prim | Frontier: cells next to the maze (green) | Take a random frontier cell and join it to a random neighbour already in the maze. Add its new neighbours to the frontier. |
| Randomized Kruskal | Union-find sets (one colour per set) | Test the next wall of a shuffled list. If its two cells are in different sets, carve it and merge the sets. Otherwise keep it (red), because a passage would close a loop. |
| Wilson | The current random walk (light orange) | Step the walk to a random neighbour. If it steps onto itself, erase that loop. When it reaches the maze, carve the walk into the maze. |
| Aldous-Broder | One walker | Step to a random neighbour. Carve only if that cell is new. |
| Eller | Sets of the current row only | Decide one east wall of the row, or carve one passage down to the next row. |
| Binary tree | Nothing | Visit one cell and carve north or east (a coin flip). |
| Sidewinder | The current run of cells | Extend the run east, or close it by carving north from a random cell of the run. |
Texture: dead ends and corridors
All of them make perfect mazes, but the mazes feel different. The page measures that texture when a maze is done:
- Dead ends: cells with only one opening.
- Junctions: cells with three or four openings.
- Corridors: the runs between two cells that are dead ends or junctions. The page shows their average and longest length, in passages.
- Solution: the number of cells on the only path from S to G.
| Demo (seed 7) | Left | Right |
|---|---|---|
| DFS vs Prim | DFS: 25 dead ends, corridors avg 5.1 (longest 22), solution 135 cells, 479 moves | Prim: 83 dead ends, avg 1.6 (longest 5), solution 35, 239 moves |
| Kruskal vs Wilson | Kruskal: 69 dead ends, avg 1.9 (longest 6), solution 51, 405 moves (166 walls kept) | Wilson: 68 dead ends, avg 1.9 (longest 10), solution 49, 1198 moves (863 walk steps, 236 loops erased) |
| Aldous-Broder vs Wilson | Aldous-Broder: 61 dead ends, avg 2.1, solution 55, 3392 walk steps, 3153 of them wasted | Wilson: the same maze as above, 863 walk steps |
| binary tree vs sidewinder | Binary tree: 61 dead ends, avg 2.0 (longest 18), solution 31 cells, the shortest possible | Sidewinder: 73 dead ends, avg 1.8 (longest 6), solution 33 |
| Eller vs Kruskal | Eller: 73 dead ends, avg 1.8 (longest 9), solution 35, 351 moves | Kruskal: as above |
| Prim vs Kruskal | Prim: as above | Kruskal: as above |
| DFS vs Aldous-Broder | DFS: as above | Aldous-Broder: as above |
DFS runs as deep as it can before it turns back, so it makes long winding corridors, few dead ends and a long solution. Prim and Kruskal add cells all over the place in random order, so they make many short dead ends and short corridors. (Demo: DFS vs Prim, Demo: Prim vs Kruskal)
The numbers come from one maze each (seed 7), so they vary from seed to seed. The pattern does not: try other seeds in Options.
Uniform spanning trees: Aldous-Broder and Wilson
A generator is uniform if every possible maze on the grid is equally likely. DFS, Prim and Kruskal are not: each prefers its own texture. Aldous-Broder and Wilson are both proven uniform. They produce mazes from exactly the same distribution.
Aldous-Broder just walks at random and carves into each cell the first time it gets there. Near the end, almost every step lands on a cell that is already in the maze and carves nothing. Wilson starts one walk at a time from a cell outside the maze and lets it run until it hits the maze. The walk keeps no loops: when it steps onto its own path, the loop is erased (a loop-erased random walk). Then the whole walk becomes a corridor. (Demo: Aldous-Broder vs Wilson counts moves, so you can see the cost: 3392 walk steps against 863.)
Wilson's first walks are slow, because the maze is a single cell and hard to hit. Later walks are short, because the maze is big. Aldous-Broder is the other way round: it is fast at first and very slow at the end, when it has to stumble onto the last few new cells.
Bias: binary tree and sidewinder
Binary tree carves only north or east from every cell. The top row can only go east and the right column can only go north, so both are straight corridors. Every cell has a path that only goes up and right to the top-right corner, which shows as a diagonal grain. Sidewinder also makes the top row straight. Below it, it works in runs: it goes east for a while, then carves one passage north from the run. Any path upwards never has to turn down again. (Demo: binary tree vs sidewinder)
In the binary-tree maze the solution from S to G is always 31 cells, the shortest possible: east along the top row, then down the right column. A maze whose solution is that easy to guess is a weak maze.
Both need no memory beyond one row and are very fast, which is why they are popular for huge mazes. The price is the bias.
Eller: one row of memory
Eller builds the maze row by row and keeps only the current row's sets. In each row it joins neighbouring cells of different sets at random. It never joins two cells of the same set, because that would close a loop. Then every set carves at least one passage down, so no set is cut off from the rows below. Cells in the next row that got no passage start new sets. In the last row it joins every pair of different sets, so everything ends up connected. It is the same idea as Kruskal (union of sets, never a loop), but it only ever looks at one row. (Demo: Eller vs Kruskal)
The forced joins of the last row often leave a long straight corridor along the bottom, which you can see in the demo.
How the race is counted
A move is one unit of a generator's work: a push or a pop, one wall tested, one step of a walk, one cell visited. With the step unit carved wall, each animation step runs every generator until it has carved the chosen number of passages. Both grids then grow at the same rate, which makes the textures easy to compare. With the step unit move, each step runs the same number of moves on both sides, so a generator that wastes moves (Aldous-Broder, Kruskal's kept walls, DFS backtracking) falls behind. Every generator carves 239 passages in the end.
What the page leaves out
- Other generators: Hunt-and-kill, growing tree, recursive division (which adds walls instead of carving them), and others.
- Mazes with loops ("braid" mazes), made by removing some dead ends afterwards.
- Other grids: hexagonal, triangular or circular cells, and 3D mazes.
- Proofs that Aldous-Broder and Wilson are uniform, and their expected running times.
See also Grid Pathfinding (its maze map is made by a randomized DFS) and Grid Pathfinding Side by Side.