Maze generation algorithms, and how to solve a maze once you know how it was made
· 8 min read · Tyamka team
How computer mazes are generated, from depth-first search to Prim and the growing tree, and why the hand-on-wall rule works in some mazes and not others.
Most mazes you meet on a screen were not drawn by hand. A program carved them from a grid of closed cells, and the method it used decides what the maze feels like, long winding corridors or a field of short dead ends. The method also decides how long the wrong branches are, and that is a large part of what makes one maze harder than another. The examples come from the maze game online on this site, where every maze is generated the moment you press Start.
A maze is a tree
Start with a rectangle of cells, every wall standing. Generating a maze means knocking down walls between neighbouring cells until every cell can be reached. If you stop the moment everything is connected and never open a wall that would make a loop, you get what is called a perfect maze. Between any two cells there is exactly one route.
In graph terms, a perfect maze is a spanning tree of the grid. The cells are the nodes, the open passages are the edges, and a grid of n cells has exactly n − 1 passages. That is why the Wikipedia article on maze generation describes it as "generating a random spanning tree". Every algorithm below is a different way to pick that tree at random, and each leaves its own texture.
Depth-first search, or the recursive backtracker
The best known method walks. From the current cell, pick a random neighbour you have not visited, knock down the wall, and step into it. When there is no unvisited neighbour left, back up along your trail until there is one, and continue from there.
Because it goes as far as it can before backing up, its mazes have, in the words of the Wikipedia article, "a low branching factor and contain many long corridors". They look tangled, but when you stand at a junction there are few choices, and a wrong branch can run a long way before you find out it was wrong.
Prim's algorithm
Randomised Prim grows the maze from a frontier. Start with one cell. At each step pick a random cell on the edge of what has been carved so far and connect it to the maze.
Because the choice jumps around the whole frontier, the result is bushy. There are many junctions and many short dead ends, often only a cell or two deep. Such a maze looks busy, yet most wrong turns show themselves at a glance.
Kruskal, Wilson and the rest
Randomised Kruskal takes the walls in random order and removes each one if the two cells behind it are not yet connected. Wikipedia notes that it "tends to produce regular patterns which are fairly easy to solve".
Wilson's algorithm and the Aldous-Broder algorithm also build perfect mazes, but they pick one fairly, so that every possible perfect maze on the grid is equally likely. Wilson's does it with loop-erased random walks. Aldous-Broder gets the same result but is, in Wikipedia's words, "one of the least efficient maze algorithms". The other methods are biased towards their own texture, which is exactly why they are useful for games.
The growing tree, a dial between the two
In 2011 the programmer Jamis Buck described the growing tree algorithm on his blog. It keeps a list of active cells. At each step it picks a cell from the list and carves to an unvisited neighbour, adding that neighbour to the list. A cell with no unvisited neighbours is dropped.
Everything depends on which cell it picks. As Buck put it, if you always take the newest cell, "you'll get the recursive backtracker", and if you always take a random one, "you get Prim's". Mixing the two, say newest cell half the time and random cell the rest, gives something in between.
Our Maze uses exactly this dial. Levels 1 to 8 pick the newest cell a quarter of the time, so they lean towards Prim, with many short dead ends. From level 9 the share of the newest cell rises step by step to three quarters on level 15, and the branches get long. It stops at three quarters on purpose. A pure backtracker has so few junctions that the maze turns into a walk.
How to solve a maze, by hand or by rule
Keep a hand on the wall
The oldest rule is to put one hand on a wall and never lift it. Turn right whenever you can, or left, as long as you stick to one side. The Wikipedia article on maze solving explains when this is guaranteed. The maze has to be simply connected, which means all its walls are joined together or to the outer boundary.
A perfect maze always qualifies, because it has no loops. So in a maze made by any of the algorithms above, a wall follower walks past every cell before it gets back to the start. It does not stop by itself, but it is bound to pass the goal, even one in the middle of the maze.
The rule can fail in mazes with loops, when the start or the goal sits next to a wall section that is not attached to the rest. The follower may then circle that island forever. The Pledge algorithm, named after Jon Pledge of Exeter, deals with this when the goal is an exit on the outer edge. You keep a preferred direction and a running count of your turns, and leave the wall only when the count is back to zero. Trémaux's method works in every maze but needs marks on the floor to record which passages you have already walked.
Why the rule is a poor fit for our game
The hand-on-wall rule is guaranteed, but it is slow. It walks into every dead end on its side and back out again. In Maze a step into any side branch costs one of your three lives, and you stay where you were. In a tree every side branch ends in a dead end sooner or later. Following the wall would cost a life at every dead-end branch on your side before the ring, and three of them end the level.
The game is built the other way round. The whole maze is visible from Start, walls cost nothing, and stepping back along the path is free, so the skill is to find the route with your eyes before you move.
Methods that work when you can see the whole maze
- Fill the dead ends. Look for cells with three walls, other than the dot and the ring. Each one is a dead end, and so is the corridor leading to it, up to the nearest junction. Mentally shade them and the branches shrink until only the route remains. Wikipedia calls this dead-end filling, and it works because it can never cut off the start from the finish.
- Trace from both ends. Follow the route from the dot, then from the ring back towards the dot. A branch that looks promising from one end is sometimes plainly wrong from the other.
- Judge junctions early. When a corridor forks, follow each branch with your eyes until it ends or joins the route. On the Prim-like early levels branches tend to be short.
- Move in stretches. Once you are sure of a corridor, walk it in one go. You can hold an arrow key to keep walking, and walls stop you for free.
Why some mazes feel harder than others
Size is the obvious part. Maze grows from 5 × 5 on level 1 to 14 × 14 on level 15. The route grows too. Every maze on a level has a route of exactly the same length, from 8 steps on level 1 to 44 on level 15, so every attempt at a level has the same number of scoring steps and the same maximum score.
Texture matters just as much. In a bushy maze each wrong choice is short and easy to rule out. In a corridor maze a branch can run halfway across the board before it turns out to be a dead end, and you have to trace it all the way. That is why the late levels move the dial as well as growing the grid.
The clock adds pressure. There is no time limit, but the maze stays hidden until Start, so the time you spend planning counts. Every new step towards the ring earns 10 points and a speed bonus that shrinks the longer you pause. A step within 24 milliseconds of the last one keeps the full bonus, walking a clear corridor at 8 cells a second keeps most of it, and a pause of half a second earns only the base points. A pause at a junction costs a little on one step. A wrong turn costs a life.
Where to go next
Try the maze and watch how the late levels change. Two other logic games have their own guides, mental math tricks for Bigger Sum and a strategy for the sum puzzle. All the games are on the all games page.