Maze Generation

About this piece

The grid starts as a faint lattice of closed cells, sized to your screen at about 20 pixels a cell (between 6 and 72 columns, 4 and 44 rows). The carving takes 13 seconds whatever the size. Carved cells take a light cobalt tint and their remaining walls are drawn firmly, so the maze grows as a solid region eating into the lattice. When every cell has been reached, the picture rests for under a second. Then the flood runs for 4.5 seconds and the path is traced in 1.6 seconds. The solved maze is held for 5 seconds, and the next run starts on a fresh grid with the other algorithm. The line along the bottom names the algorithm and counts the carved cells and the depth of the stack (or the length of the walk). At the end it gives the path length and the number of dead ends. With reduced motion switched on you get one still: the first maze, carved, flooded and solved.

The recursive backtracker, step by step

The Wikipedia article on maze generation algorithms (read 13 October 2026) describes this method as a randomised depth-first search, “also known as the recursive backtracker”. On this plate it runs like this:

push the entrance cell; mark it visited
while the stack is not empty:
  look at the cell on top of the stack
  if it has unvisited neighbours:
      pick one at random, knock out the wall between,
      mark it visited, push it
  else:
      pop

The coral line is that stack, drawn cell to cell, and the dot is its top. Because every cell on the stack was reached from the one below it, the line is always a corridor of the finished maze leading straight back to the entrance. That is the “backtracking”: when the walker is boxed in, it retreats along that line until it finds a cell with an unvisited neighbour, and branches off there. The line grows long and then shrinks, often by hundreds of cells at a time. On a 52 × 27 grid (1,404 cells) the run is exactly 2,808 events long: the entrance pushed, 1,403 steps forward, and 1,404 pops back out. The stack is written out as a plain array rather than as recursion, so a big grid cannot overflow the browser’s call stack.

Wilson’s algorithm: walks that erase their own loops

The odd runs use the algorithm David Bruce Wilson published in 1996 (“Generating random spanning trees more quickly than the cover time”, Proceedings of the 28th ACM Symposium on Theory of Computing, pp. 296–303, doi:10.1145/237814.237880). One random cell is put in the maze. From a cell not yet in it, a walker wanders at random. Whenever its path crosses itself, the loop it just closed is erased. When it touches the maze, the loop-free path that is left is carved in as a new branch. Then the next walk starts from another cell that is still outside. The coral line is the current walk, and you can watch it fold back on itself and lose whole loops at once.

The first walk is the slow part. It has to find one single cell by chance, so on these grids it takes about 45% of all the steps of the run (46% over 20 seeds at 52 × 27). Later walks have a whole maze to bump into and end quickly. The plate gives that first walk 30% of the carving time instead of 45%. Every step is still drawn, just faster, so the run does not sit for six seconds on one wandering line.

Why the two mazes look different

Both algorithms make a perfect maze: every cell can be reached and there is exactly one route between any two cells. In graph terms the maze is a spanning tree of the grid, with exactly one passage fewer than it has cells. What differs is which spanning tree you tend to get. Wikipedia puts it in one line: “depth-first search is biased toward long corridors”, while Wilson’s algorithm gives “an unbiased sample from the uniform distribution over all mazes”. Every possible maze on the grid is equally likely. Measured on this plate’s own code, over 20 seeds on a 52 × 27 grid:

• Dead ends (cells with one open side): 10.3% for the backtracker and 29.1% for Wilson’s. The backtracker only turns back when it is truly boxed in, so it leaves few stubs. A uniform maze is full of short side branches.
• The path from entrance to exit: 473 cells on average for the backtracker and 147 for Wilson’s, on a grid where the shortest possible route is 78 cells. A backtracker maze is one long snake with a few branches, and the route through it wanders over a third of the grid.
• Straight corridor cells (open on two opposite sides): 31% against 17%. That is the “long corridors” you can see in the backtracker’s runs, against the twitchier, more branching texture of Wilson’s.

You can see the difference without counting. The backtracker’s flood creeps along a few long tubes and takes a long time to reach the far corner. Wilson’s spreads out more evenly, like ink soaking into paper.

The solve: a breadth-first flood

Once the maze is carved, a breadth-first search starts at the entrance. Every cell one step away is reached first, then every cell two steps away, and so on. Each cell records how many steps it took to reach and which cell it was reached from. The flood is drawn in that order, coloured by distance along the theme’s ramp: deep cobalt at the entrance, coral at the cell furthest from it, and the moving front drawn brighter. When the flood is done, the path is read backwards from the exit, cell to parent cell, until it reaches the entrance. That is why the line grows from the bottom-right corner. Breadth-first search always finds a shortest path. In a perfect maze there is only one path to find, so it is also the only one. The test suite checks this on every maze it builds: it lists every route from entrance to exit that visits no cell twice, and requires exactly one, equal to the solver’s.

How it is computed

Each run is carved once, up front, into a record of events: dig, pop, walk, erase a loop, join. The picture is that record replayed up to a count that depends only on how many seconds the run has been going. The frame rate decides how often the picture is redrawn, never what is in it. The test suite plays two full runs at 30 and at 144 frames per second and compares the maze, the stack and every canvas call at each whole second; they are identical. On 20 seeds, for both algorithms and on three grid sizes, it checks that every maze has exactly one passage fewer than it has cells, reaches every cell and contains no loop. It also plants the defect a buggy carver would have, one extra knocked-out wall, and the checks go red. The same code paints the gallery tile, this page and the embed, and the test confirms the three copies are identical line for line. Every colour comes from the site’s palette in the current theme. Nothing in the drawing code picks a colour of its own.

The two plates it sits nearest

• Truchet Tiles also looks like a maze, but it is one random tile per cell with no plan, so its corridors close into loops and leave regions you can never enter. Here every wall is knocked out on purpose, and the result is guaranteed to have one route between any two cells, which is exactly what Truchet tiles cannot promise.
• Hilbert Weave is a single path that visits every cell of a grid with no choices at all. A backtracker maze is the random relative of that: one long path through almost every cell, branching only where the walker got stuck.

Honest limits

Two algorithms out of many. Kruskal’s, Prim’s, Eller’s, the binary-tree and sidewinder methods and the Aldous–Broder walk all make perfect mazes with textures of their own. This plate shows only the backtracker and Wilson’s, because their difference is the clearest one to watch.

The numbers are for this grid shape. The percentages above were measured on 52 × 27 grids, over 20 seeds. They hold at other sizes within a point or two (at 20 × 12: 11.1% and 29.0% dead ends), but a single run can differ from the average, so the readout gives that run’s own count.

Fixed entrance and exit, no loops. The way in is always the top-left cell and the way out the bottom-right, and the mazes are always perfect. Puzzle mazes often add loops on purpose to defeat the “keep one hand on the wall” trick. These have none, so that trick would solve every one of them.

Small screens get small mazes. On a phone the grid is only about 16 × 9 cells, and the difference between the two algorithms is much harder to see than on a desktop.

Curious how the loop and canvas fit together? Read how it works →