The maze book for programmers!

Algorithms, circle mazes, hex grids, masking, weaving, braiding, 3D and 4D grids, spheres, and more!

# The Buckblog

## Maze Generation: Recursive Backtracking

27 December 2010 — The first article in a series about maze generation algorithms — 4-minute read

I’ve said before that generating mazes is a great default project when experimenting with a new programming language. I’ve yet to find a better one (but I’d love to hear recommendations). However, before you can dive into generating a maze (especially in a syntax you are unfamiliar with), you had better have a solid grasp of how the process works.

With mazes, you can take your pick of a solid double-handful of algorithms: recursive backtracking, Prim’s, Kruskal’s, Eller’s, Aldous-Broder or Wilson’s algorithms, recursive division, hunt-and-kill, and more.

My favorite, and the one I implement by default, is recursive backtracking. It is fast, easy to understand, and straightforward to implement. You’ll need sufficient memory to store the entire maze in memory, though, and it requires stack space again proportional to the size of the maze, so for exceptionally large mazes it can be fairly inefficient. But for most mazes, it works a charm.

Here’s the mile-high view of recursive backtracking:

1. Choose a starting point in the field.
2. Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
3. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
4. The algorithm ends when the process has backed all the way up to the starting point.

I generally implement the field as a grid of bitfields (where the bits in each cell describe which direction passages have been carved). That’s probably just the C programmer in me asserting dominance, though; feel free to experiment with other representations.

In Ruby, I usually initialize the grid like so:

 ```1 ``` ```grid = Array.new(height) { Array.new(width, 0) } ```

Next, the algorithm itself is kicked off by calling the worker function:

 ```1 2 3 4 5 ``` ```def carve_passages_from(cx, cy, grid) # work, work, work end carve_passages_from(0, 0, grid) ```

This begins carving passages in the grid, starting at the upper-left corner, (0,0). And as you might have guessed from the algorithm’s name, this works recursively, as we’ll see next.

The `carve_passages_from` method first creates a list of directions that ought to be tried from the current cell:

 ```1 ``` ```directions = [N, S, E, W].sort_by{rand} ```

We sort the list in random order, so that the path will meander, rather than having a bias in any particular direction.

Then, the function iterates over each of those directions, determining the coordinates of the cell in that direction and deciding if the cell is valid or not. Note that a cell is valid only if it lies within the bounds of the maze, AND it has not previously been visited: we only want to carve passages into untouched cells, to avoid creating circular loops in the maze.

 ```1 2 3 4 5 6 7 8 ``` ```directions.each do |direction| nx, ny = cx + DX[direction], cy + DY[direction] if ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0 # cell is valid! # ... end end ```

Finally, if the cell is valid, we carve a passage out of the current cell and into the next cell. Then, we recursively call `carve_passages_from` on the new cell:

 ```1 2 3 ``` ```grid[cy][cx] |= direction grid[ny][nx] |= OPPOSITE[direction] carve_passages_from(nx, ny, grid) ```

And that’s really all there is to it!

For all of you not using IE (and I honestly hope no reader of my blog uses IE), here’s a Javascript demo you can play with to see the algorithm in action:

My complete Ruby implementation, including some lines to output the maze as ASCII, is here:

Start by writing your own implementation in a language you’re comfortable in, just to wrap your mind around the algorithm. Try replacing the recursion with iteration (always a fun exercise). Consider extending it to include weave mazes (where passages move over or under other passages), or braided mazes (mazes where deadends are removed to create loops in the maze), or symmetrical mazes, or wrapped mazes. Or even different cell tesselations. If you’re at all like me, you may find that your “toy” project has taken on a life of its own, and you’re suddenly researching new and exciting ways to build mazes!

Once you understand the algorithm, though, the real fun is trying it in a language you’re unfamiliar with. It’ll show you conditionals, bit manipulation (if you use the bitfield storage like I showed above), iteration, recursion, and console output (if you decide to render your maze, too). When you’ve finished, you’ll have a good idea of how the language looks and works in practice, and not just for trivial “hello world” apps.

Actually, once you understand this algorithm, I think the best place to go next would be to change it to a breadth-first traversal. The intuition here is that a maze is an undirected graph, and this algorithm constructs the maze by traversing that graph in depth-first order. This is dandy, but as Jamis noted, it requires stack size proportional to the size of the maze (in the worst case). Actually, it would be more precise to say that it require stack size proportional to the longest acyclic path through the maze, which is (in the worst case) the entire maze, but in the average case will be much much less.

Anyway, the motivation for breadth-first traversal is that you no longer have to maintain the longest acyclic path, you simply maintain a queue of unvisited cells. The worst-case complexity is a lot better here, seeing as it can’t be the entire maze (actually, I believe it’s closer to logarithmic in the size of the maze). The average case is also nicer, since a breadth-first traversal drops cells which have been completely visited, requiring a lot less memory.

Which of the maze algorithms is the one where you start with a set for each cell, then randomly pick two rooms to join from different sets, then merge their sets, and once you only have one set, you know you can get to any place from any other place in the maze?

I don’t understand where steps 3 and 4 come in then. Which part of your code does the backtracking to the previous cell with unvisited adjacent cells? It looks like the code will just terminate when it reaches a cell that has no more valid adjacent cells instead of backing up.

Thanks for the help. I tried to implement some of these algorithms myself a while back, but I got bogged down in the data structure implementation for each of them (sometimes the mathematical descriptions in algorithms textbooks are a little too abstract for me) and gave up. This has inspired me to have another go!

Hey there, Jamis. I saw your post a few weeks ago (on reddit) and I figured I could try your approach on learning a new language with mazes.

So far, the repository at https://github.com/alexandream/mazes is what I managed to accomplish with recursive backtracking. I plan on making quite a lot of experiments on it, as I polish my lispy ways ;)

If anyone wants to run it: with racket installed you only need to run

gracket driver.scm

Yeah, and thanks for this blog post: I had a hell of a fun implementing this: first in Guile with Postscript for graphics, then in Racket.

One thing, I mistyped the cmd line in the previous one. It’s

gracket -f driver.scm

So, I was looking through your code again. :-) How exactly does your display code work? In particular, why do you do the checks for the adjacent cell and for east and south? Things like this, for example, seem unintuitive: print((gridy & S != 0) ? ” ” : ”_”) – here you are printing nothing when it has something (south) – I would have expected the reverse. Why wouldn’t something naïve like ‘if has_south: print ; if has_north: print ; etc’ work?

Here’s a Groovy version: https://gist.github.com/805416

Great advice, I learned a few things about Groovy along the way. I ported your code instead of rewriting from scratch so I could spend more effort thinking about how things are done in Groovy.

Here’s a C implementation, it makes you appreciate higher level languages. :D

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 ``` ```#include #include #define WIDTH 20 #define HEIGHT 20 enum {N=1,E=4,S=2,W=8}; int DX[9]; int DY[9]; int OPPOSITE[9]; int carve_passage_from(int cx, int cy, int *grid[]); int shuffle_array(int *array, int size); int main(int argc, char *argv[], char **envp) { int x,y; OPPOSITE[N] = S; OPPOSITE[E] = W; OPPOSITE[S] = N; OPPOSITE[W] = E; DX[N] = 0; DX[E] = 1; DX[S] = 0; DX[W] = -1; DY[N] = -1; DY[E] = 0; DY[S] = 1; DY[W] = 0; int grid[WIDTH][HEIGHT]; /** Seed the random generator **/ srand((unsigned int)time((time_t *)NULL)); memset(&grid[0], 0, sizeof(grid)); carve_passage(0, 0, grid); /** Display the grid **/ printf(" "); for(x = 0; x < (WIDTH * 2); x++) { printf("_"); } printf("\n"); for(y = 0; y < HEIGHT; y++) { printf("|"); for(x = 0; x < WIDTH; x++) { printf( ((grid[x][y] & S) != 0)?" ":"_"); if((grid[x][y] & E) != 0){ printf((( (grid[x][y] | grid[x + 1][y]) & S) != 0) ?" ":"_"); } else { printf("|"); } } printf("\n"); } } int shuffle_array(int *array, int size) { int i; for( i=0; i<(size - 1); i++) { int r = i + (rand() % (size - i)); int temp = array[i]; array[i] = array[r]; array[r] = temp; } } int carve_passage(int cx, int cy, int *grid[WIDTH][HEIGHT]) { int dx, dy, nx, ny; int directions[4] = {N, E, S, W}; //shuffle the direction array shuffle_array(directions, 4); int i; for(i = 0; i < 4; i++) { printf("Direction: %d\n", directions[i]); } //iterates through the direction then test if the cell in that direction is valid and //within the bounds of the maze for(i = 0; i < 4; i++) { dx = DX[directions[i]]; dy = DY[directions[i]]; printf("Check direction=x:y - %d=%d:%d\n", directions[i], dx, dy); // check if the cell is valid nx = cx + dx; ny = cy + dy; // check if we are on valid grid if ( ((nx < WIDTH) & (nx >= 0)) & ((ny < HEIGHT) & (ny >= 0)) ) { //check if grid is not visited if (grid[nx][ny] == 0) { printf("Valid cell x:y %d:%d\n", nx, ny); grid[cx][cy] = (int)((int)grid[cx][cy] | (int)directions[i]); grid[nx][ny] = (int)((int)grid[nx][ny] | (int)OPPOSITE[directions[i]]); carve_passage(nx, ny, grid); } } } } ```

(edit: broken code-paste fixed)

Ah, I was in the same boat as @Isacc: I thought the direction bits indicated walls. It wasn’t until comment #14 that it made sense to me.

Here’s a C# version [optimized for my understanding, not brevity ;)] here:

https://gist.github.com/828805