Maze Generation with Depth-First Search
The flood fill algorithm turned out to be a graph search in disguise: cells are nodes, neighboring empty cells are connected, and filling a region means visiting everything reachable from one starting point. Maze generation runs the same idea in reverse. Instead of exploring a graph that already exists, it builds one, by deciding which walls between neighboring rooms to knock down.
What makes a perfect maze
Picture a grid of rooms with a wall between every pair of neighbors. A maze is what you get after removing some of those walls. It is called perfect when every room can be reached and there is exactly one way to get from any room to any other: no loops, no closed-off areas.
In graph terms, that is a spanning tree: the rooms are the nodes, an
opening in a wall is an edge, and a tree connecting n nodes always has
exactly n - 1 edges. So a perfect maze with 266 rooms needs exactly 265
openings, never more, never fewer. Any algorithm that builds a random
spanning tree on the grid builds a perfect maze.
The recursive backtracker
The simplest of those algorithms is a randomized depth-first search, usually called the recursive backtracker:
- Start in any room and mark it as visited.
- If the current room has unvisited neighbors, pick one at random, knock down the wall in between, and move there.
- If it has none, it is a dead end: go back to the room you came from and try again from there.
- Stop once you are back at the start with nothing left to visit.
Step 2 can never create a loop, because it only ever opens a wall into a room that has not been visited yet. And since step 3 keeps backtracking until every room has been tried, no room is left out. Together, that is exactly a spanning tree.
Implementation
#include "plot.hpp"
#include <stdint.h>
// Change the seed to get a different maze.
const uint32_t SEED = 1;
const int MW = 19; // rooms per row
const int MH = 14; // rooms per column
const int GW = 2 * MW + 1; // grid width: rooms plus the walls between them
const int GH = 2 * MH + 1;
const int CELL = 16;
enum { WALL, UNVISITED, ON_STACK, DONE };
int grid[GH][GW];
// The path from the start to the current room. Every room is pushed
// exactly once, so MW * MH entries are always enough.
int stackX[MW * MH];
int stackY[MW * MH];
int top = -1;
// A small xorshift generator instead of rand(), so the same seed gives
// the same maze everywhere, not just with one particular C library.
uint32_t rng = SEED;
uint32_t next_random() {
rng ^= rng << 13;
rng ^= rng >> 17;
rng ^= rng << 5;
return rng;
}
void push(int x, int y) {
top++;
stackX[top] = x;
stackY[top] = y;
grid[y][x] = ON_STACK;
}
// One step of the depth-first search: look at the room on top of the
// stack. If it has unvisited neighbors, pick one at random, knock down
// the wall in between and move there. If not, it is finished: step back.
void step() {
int x = stackX[top];
int y = stackY[top];
int dx[4] = {2, -2, 0, 0};
int dy[4] = {0, 0, 2, -2};
int options[4];
int n = 0;
for (int k = 0; k < 4; k++) {
int nx = x + dx[k];
int ny = y + dy[k];
if (nx > 0 && nx < GW && ny > 0 && ny < GH && grid[ny][nx] == UNVISITED) {
options[n++] = k;
}
}
if (n == 0) {
// Dead end: this room is finished. Step back to the previous one,
// and the opening we came through is finished as well.
grid[y][x] = DONE;
top--;
if (top >= 0) {
grid[(y + stackY[top]) / 2][(x + stackX[top]) / 2] = DONE;
}
return;
}
int k = options[next_random() % n];
grid[y + dy[k] / 2][x + dx[k] / 2] = ON_STACK; // knock down the wall
push(x + dx[k], y + dy[k]);
}
void setup() {
PlotCanvas(640, 480);
// Rooms sit on odd coordinates, everything else starts out as wall.
for (int y = 0; y < GH; y++) {
for (int x = 0; x < GW; x++) {
grid[y][x] = (x % 2 == 1 && y % 2 == 1) ? UNVISITED : WALL;
}
}
push(1, 1);
}
void frame() {
// Two steps per frame: carving forward and backtracking both count.
for (int n = 0; n < 2 && top >= 0; n++) step();
// Entrance top left, exit bottom right, once the maze is complete.
if (top < 0) {
grid[1][0] = DONE;
grid[GH - 2][GW - 1] = DONE;
}
PlotBackground(250, 250, 250);
int ox = (640 - GW * CELL) / 2;
int oy = (480 - GH * CELL) / 2;
for (int y = 0; y < GH; y++) {
for (int x = 0; x < GW; x++) {
int c = grid[y][x];
if (c == WALL) PlotColor(40, 44, 52); // wall
else if (c == UNVISITED) PlotColor(30, 100, 200); // not visited yet
else if (c == ON_STACK) PlotColor(220, 60, 60); // on the current path
else PlotColor(70, 170, 90); // finished
PlotFilledRectangle(ox + x * CELL, oy + y * CELL,
ox + x * CELL + CELL - 1, oy + y * CELL + CELL - 1);
}
}
}
The grid stores rooms and walls together: rooms sit on odd coordinates, and the cells between them are walls that can be knocked down. A maze of 19×14 rooms becomes a 39×29 grid, which is easy to draw cell by cell and keeps the walls as part of the picture. Dark cells are walls, blue rooms have not been visited yet, red marks the current path from the start, and green rooms are finished.
As with flood fill, the recursion lives in an explicit stack instead of
the call stack, so the animation can take one step per call. Each step
either moves forward into a new room or backtracks out of a finished one.
Every room is entered once and left once, except for the starting room,
which is never entered from anywhere, so the whole maze takes exactly
2 × 266 - 1 = 531 steps no matter what the random choices are.
The random numbers come from a tiny xorshift generator rather than
rand(), because rand() produces different sequences with different C
libraries, and the same seed should give the same maze everywhere. Change
SEED in the code above and press "Compile & Run" to get a new one.
Long corridors, few dead ends
Depth-first search always pushes on as far as it can before turning back,
and that shows in the result. With SEED = 1, the path stack reaches a
depth of 191 out of 266 rooms at one point, and the way from the entrance
in the top left corner to the exit in the bottom right winds through 102
rooms. Like the naive recursive flood fill, a truly recursive version
would nest that deep in its call stack, which is fine here but not for
mazes with millions of rooms.
Other algorithms that also build perfect mazes produce a noticeably different texture. Randomized Prim's algorithm grows the maze outward from the start by repeatedly picking a random room on the edge of the maze built so far, rather than following one path as far as possible. Averaged over 200 seeds on the same 19×14 grid:
| dead ends | path from corner to corner | |
|---|---|---|
| Recursive backtracker | 28.4 rooms (11 %) | 109.8 rooms |
| Prim's algorithm | 92.7 rooms (35 %) | 33.9 rooms |
The backtracker makes long, winding corridors with few side branches. Prim's algorithm makes lots of short dead ends and a much more direct solution. Both are perfect mazes: same number of rooms, same number of openings, just arranged very differently.
Conclusion
A perfect maze is a random spanning tree drawn on a grid, and the recursive backtracker builds one with nothing more than a stack and a random choice per step. Generating the maze is half of the story, though. Finding the way through it is a graph search of its own, and that is where breadth-first search and A* come in.