applets.

Maze Maker

← All apps

About Maze Maker

A hedge maze seen from above. Pick one of seven ways to grow it and press BUILD to watch it grow (INSTANT skips the show). Then press SOLVE to watch a searcher find the way from the gate at the top left to the way out, or walk it yourself with the arrow keys (or W A S D), or by dragging from the gate. The clock starts on your first step. Going back along your own trail rubs it out. B builds, Esc stops.

Every maze here has exactly one route between any two places, until you knock through some dead ends with the Dead ends removed slider, which makes loops. The same seed with the same settings always gives the same maze, so you can send someone a seed and race them through it. Changing the size, method, dead ends or way out redraws the maze from the same seed straight away.

THE STORY

The original, Maze Generator.py, was a few lines of Python that print a screenful of random / and \ characters. It looks like a maze, but nothing guarantees a way through. It is the same trick as the famous one-line Commodore 64 program 10 PRINT CHR$(205.5+RND(1)); : GOTO 10, which has a whole book about it, published in 2012.

A real maze is what mathematicians call a spanning tree of the grid: every cell joined, no loops. The ways to grow one come from the study of networks. Joseph Kruskal published his method in 1956 and Robert Prim his in 1957 (Vojtěch Jarník had found Prim's in 1930), both for linking places as cheaply as possible; with random costs they make random mazes. The recursive backtracker is a depth-first search. In 1996 David Wilson showed that random walks that rub out their own loops pick every possible maze with exactly equal chance. Eller's method, named after Marlin Eller, builds one row at a time, so it could make an endless maze. The binary tree and sidewinder are quick and simple but leave a visible lean: straight corridors along the top (and, for the binary tree, down the right).

For getting out, the oldest rule is to keep one hand on the wall. It always works when every hedge is joined to the outside, but not when the goal is in the middle with a loop of hedge round it, which is why some maze designers put islands in. Breadth-first search was used for the shortest way through a maze by Edward F. Moore in 1959. A* was published in 1968 by Peter Hart, Nils Nilsson and Bertram Raphael at the Stanford Research Institute, for the robot Shakey.

HOW IT WORKS

Backtracker: wander to a random unvisited neighbour; when stuck, back up until there is one. Long winding corridors and few dead ends. Prim's: grow outwards, each time joining a random cell from the edge of what is built. Short spiky dead ends everywhere. Kruskal's: knock down the walls in random order, unless the two sides are already joined. Wilson's: from a random cell, walk at random until you hit the maze, rubbing out any loop you make on the way, then keep that walk. Slow at first, then fast. Eller's: join cells along a row at random, then drop at least one passage down from each group. Sidewinder: run east, then go north from somewhere in the run. Binary tree: each cell opens north or east by a coin toss.

Dead ends removed knocks through roughly that share of them, picked at random, each into a neighbour (another dead end if there is one, which clears two at once, so a few more can go than the slider says). Breadth-first looks at cells in order of distance from the gate, like water spreading, and always finds a shortest route. A* looks first at the cell where the distance walked plus the distance still to go (counted along the grid, ignoring hedges) is least: it also finds a shortest route, usually after looking at fewer cells. The wall follower keeps its right hand on the hedge; it is lost when it comes back to the same place facing the same way. "Cells looked at" counts each cell once; the wall follower's route is every step it walked, there and back again.

FURTHER WATCHING AND READING

Speed

Grow the maze

Way out

Find the way

SearcherCells looked atRoute (steps)
Breadth-first––
A*––
Wall follower––
You––
0:00.00 steps