Maze

A perfect maze is one where exactly one path leads from any cell to any other: no rings, no cut-off corners. In mathematical terms it is a spanning tree of the grid, a graph that connects every cell and contains no cycles. A grid has an astronomical number of such trees: a 20 × 20 square has about 10¹⁸⁷, far more than there are atoms in the observable universe. A good generator must choose among them fairly.

How it works

The popular algorithms are biased. Depth-first search draws long corridors with rare forks, Prim's algorithm scatters short dead ends. David Wilson's algorithm returns every spanning tree with the same probability. Starting from one root cell, it repeatedly launches a random walk from a cell outside the maze until the walk hits the maze, erases every loop the walk has made, and attaches what remains. Erasing the loops comes free: each cell remembers only its last exit, so old loops simply vanish.

In tile mode the grid is wrapped into a torus, right edge glued to left and top to bottom, so the maze runs on without a seam. “Loops” knocks through a share of the dead ends, preferably into another dead end, opening circular routes. Colouring “by distance” is a breadth-first search from the root: colour spreads along the passages like water, showing how far apart by corridor two seemingly adjacent cells are.

A bit of history

The loop-erased random walk was introduced by Gregory Lawler in 1980. The earlier Aldous–Broder algorithm could already produce uniform spanning trees, but slowly; in 1996 David Wilson showed that loop erasure gives exactly the uniform distribution, and faster. The path between two cells of a uniform maze is distributed just like a loop-erased random walk, and as the grid gets finer it becomes a fractal curve of dimension 5/4. Oded Schramm linked it to the stochastic Loewner evolution in 2000, and in 2004, together with Lawler and Wendelin Werner, proved its conformal invariance. Gustav Kirchhoff could already count the trees in 1847, as the determinant of a matrix.

What to tweak

• “Grid” set to “hexagonal” gives each cell six exits and more winding corridors.
• “Loops” at 0.2–0.4 turns the tree into a maze with rings, where the one-hand rule no longer guarantees a way out.
• “Colouring” set to “by branch” paints the longest branches first, revealing how the tree is built.
• A wide “Passage width” with “Roundness” at 1 turns the maze into pipes or coral; “Style” set to “walls” gives the classic newspaper puzzle.
• Put the “Halftone” effect on top and the maze turns into a print made of dots.