Maze Generator

Draw a grid of rooms with a wall between every pair of neighbors. Knock down walls until every room can be reached from every other, and stop the moment that is true. You are holding a maze.

Walter Pullen, whose Think Labyrinth pages are the closest thing the subject has to a field guide, calls it a perfect maze: no loops or closed circuits, no inaccessible areas, and exactly one path from each point to any other point. The Princeton algorithms text says the same thing in other words: no inaccessible locations, no cycles, no open spaces. Pullen then adds the sentence that matters to anyone who writes the code. In computer science terms, such a maze is a spanning tree over the set of cells: the rooms are the points, the missing walls are the links, and nothing is left out or joined twice.

That one idea carries most of what follows. If a perfect maze is a tree, then making a maze is choosing a tree, and the interesting question stops being whether the result can be solved. It always can. The question is which tree you were handed, and why that one.

There are more trees than intuition suggests. The integer sequence catalogued as A007341 counts the spanning trees of a square grid, and its notes say plainly that the same numbers count the perfect mazes on that grid. A grid of 2 by 2 cells has 4. A grid of 3 by 3 has 192. A grid of 4 by 4 has 100,352, and 5 by 5 has 557,568,000.

So even a small maze is a draw from an enormous hat. A maze generator is a rule for drawing, and no rule is obliged to give every tree the same chance. Most do not. The difference between them is not correctness, since they all produce valid mazes. It is texture.

Why the same grid feels different

Take the recursive backtracker, which Wikipedia’s article on maze generation calls one of the simplest ways to make a maze by computer. The description is short: choose a starting cell, carve through to a random neighbor that has not been visited, keep going, and when every neighbor has been visited, back up to the last cell that still has an unvisited neighbor. It finishes when it has backed all the way to the start.

Because it always pushes forward while it can, it lays down long passages and branches only when it is cornered. Pullen has a word for this quality, “river”: an algorithm with more river flows into empty space like water and leaves fewer but longer dead ends. The recursive backtracker, he writes, has about as high a river factor as possible, and usually a very long and twisty solution.

Prim’s and Kruskal’s methods come from the problem of finding a cheapest spanning tree, with the weights thrown away. Kruskal’s, as Pullen describes it, takes every wall in random order and removes one only if the cells on either side are not yet connected, so passages appear all over the grid at once. The form of Prim’s used here starts at one cell and grows outward, each time attaching a random cell from the frontier. Wikipedia sums up the result: both are biased toward many short dead ends.

Pullen’s comparison table puts numbers on the feeling. On a square grid, about 10 percent of the cells in a recursive backtracker maze are dead ends. For Kruskal’s the figure is about 30 percent, and for the frontier form of Prim’s about 36 percent. He also gives the ceiling: the highest share a square perfect maze can reach is 66 percent, a single passage with one-cell stubs along both sides.

You can see the gap in one experiment. Set the tool above to a square grid of 16 by 16, the recursive backtracker and seed 2026. It reports 256 cells, 28 dead ends, a solution of 161 steps between the two farthest cells, and a longest corridor of 43 cells. Change only the algorithm to Prim’s and the same seed gives 85 dead ends, a solution of 43 steps and a longest corridor of 6. Same grid, same count of walls removed, and a walk that is nearly four times shorter. Turn the braid slider to 50 percent on the first maze and 14 of its 28 dead ends are gone.

The growing tree algorithm makes the connection explicit. Keep a list of live cells, pick one, carve from it to an unvisited neighbor and add that neighbor to the list, removing a cell once it has no unvisited neighbors left. Pullen points out that always picking the newest cell gives the recursive backtracker, and always picking at random behaves much like Prim’s, though not exactly. Everything between is a dial, which is exactly how the tool’s mix slider works.

Bias, and the two fair methods

Some methods leave marks you can see from across the room. The binary tree algorithm visits each cell once and carves either up or sideways, choosing at random, and never looks at anything else. Pullen notes the price: two edges of the maze become one long passage each, and the routes tend to run diagonally. The sidewinder is a close relative that leaves only one long passage, across the top. Both are fast, and both show their grain.

At the other end are two methods designed to have no bias at all. The first takes two lines to state. Walk at random from cell to neighboring cell until every cell has been visited, and for each cell keep the edge by which it was first entered. The kept edges form a spanning tree, and the abstract of Andrei Broder’s 1989 paper says the tree is chosen uniformly at random among all the spanning trees of the graph. David Aldous published the same random walk construction in 1990, and the method carries both names.

It is also painfully slow to watch, because the walk wanders over finished ground while the last few cells wait. Broder gives the expected time as proportional to n log n for almost all graphs and n cubed for the worst ones. Pullen puts its average running time at about seven times that of the standard methods.

David Wilson’s method keeps the fairness and removes most of the waiting. Start with one cell in the maze. From any cell outside it, walk at random until you touch the maze, remembering for each cell only the direction in which you last left it, then carve along those remembered directions, which erases every loop the walk made. The title of Wilson’s paper names the gain: random spanning trees generated more quickly than the cover time. The older method cannot finish before its walk has covered every cell.

What does fair buy you? Pullen’s table has a column for it. Wilson’s and Aldous-Broder are marked uniform. Kruskal’s and Prim’s can produce every maze but not with equal probability. The recursive backtracker is marked “never”, meaning there are mazes it cannot produce at all. A uniform maze has no grain to exploit, and about 29 percent of its cells are dead ends.

Loops, other grids, and getting out

Not every maze has to be a tree. Remove a dead end by opening one more wall and you create a loop; do it to every dead end and you have what Pullen calls a braid maze. He warns that a well-designed braid can be much harder than a perfect maze of the same size, because the solver goes in circles instead of bumping into walls.

Loops also break the oldest solving advice. Keeping a hand on one wall is fast and needs no memory, but Pullen notes that it need not find the shortest route, and it fails outright when the goal sits inside a closed circuit: you walk around the island and arrive back where you began. Tremaux’s method, marking each passage as you walk it and treating an already-visited junction as a dead end, will solve any maze on foot.

On paper there is a better tool. Breadth-first search checks every cell one step from the start, then every cell two steps away, and so on, using a queue. The Princeton text presents it as the classic method for finding a path with the fewest edges. Pullen describes the same thing as flooding the maze with water and tracing back from the goal.

None of this depends on squares. Pullen’s glossary names the common alternatives after Greek letters: sigma for interlocking hexagons, delta for interlocking triangles, theta for concentric circles with the start or the goal in the middle. The algorithms only ask which cells are neighbors. Hexagons need a small convention for that, and the usual one, in Red Blob Games’ guide, is to offset every other row or column.

Older than the puzzle

The branching maze is younger than the word for it. The single-path, seven-course design became associated with the Labyrinth on coins as early as 430 BC, and depictions of the Labyrinth from the Roman era until the Renaissance are almost invariably unicursal, with no choices to make. Branching mazes returned only when hedge mazes became popular during the Renaissance.

The pavement labyrinth at Chartres belongs to the older kind. The cathedral’s own account places the start of construction around 1200, names similar labyrinths at Reims, Amiens and Saint-Quentin, and recalls the story behind the form: Daedalus building the maze, and Theseus surviving it thanks to Ariadne’s thread.

The thread came back in 1950, when Claude Shannon built a mechanical mouse named Theseus. It explored a maze of 25 squares by touching walls, stored what it learned in telephone relays, and took the direct path on its second trip.

What the numbers cannot tell you

A generator can count dead ends, measure the solution and time how long a walk takes. It cannot tell you how hard a maze will feel. Nothing in the sources above offers an accepted measure of difficulty, and the reading the tool shows is a rough guide built from two counts. Fairness is not difficulty either: the unbiased methods are fair to the trees, not to the person holding the pencil.