Maze Generation: Recursive Backtracking

Posted by Jamis on December 27, 2010 @ 06:49 AM

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.

Give it a try! Please share your implementations in the comments (links to gist.github.com are preferred).

Posted in Under the Hood

Comments

Have something to add? Click here to leave a comment.

27 Dec 2010

1. Daniel Spiewak said...

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.

2. Jamis said...

@Daniel, good suggestion! I’m actually going to write up a description of Eller’s algorithm next, which is a very clever way of doing just such a breadth-first traversal. It only requires that memory proportional to a single row of the maze be kept in memory, making it ideal for tight memory conditions. As I said, though, it’s “clever”, so it’s harder to understand and implement than the recursive backtracker, but still a lot of fun.

3. will said...

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?

4. Jamis said...

@will, that sounds like Kruskal’s algorithm. I’ve never implemented it myself, but I’d like to give it a try…maybe tonight. :)

5. Jamis said...

Done! For the curious, here’s an implementation of Kruskal’s algorithm: https://gist.github.com/756896. It works as will described, placing each cell into its own set, then iteratively joining adjacent disjunct sets until only one set remains. I think I still prefer recursive backtracking for simplicity and the esthetics of the result, but Kruskal’s is definitely an intriguing approach. I’ll do a post about it later, to go into it in more depth.

13 Jan 2011

6. Isaac said...

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.

7. Jamis said...

@Isaac, remember that the carve_passages_from method is called recursively; thus, when the method terminates, the program continues from where that method was last called, which may be within the method itself!

Picture it this way: carve_passages_from is called with a a location of (1,1). That invocation of carve_passages_from chooses a direction and then calls carve_passages_from AGAIN with a new location of (1,2). If that newest invocation of carve_passages_from cannot find a valid cell to move into, it will terminate, and return to the invocation of carve_passages_from at (1,1), which allows that loop to continue looking at adjacent cells (possibly choosing the neighbor at, say, (1,0), and calling carve_passages_from on that cell).

Does that make sense? If you’d like to see an implementation that uses iteration instead of recursion, I’ve got one here: https://gist.github.com/754545—it uses an explicit stack, which makes the backtracking more obvious.

8. Isaac said...

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!

9. Jamis said...

@Isaac, that’s awesome! Please do have another go, and let me know how it turns out. Most of these algorithms are actually pretty straightforward once you wrap your mind around them; if you have any further questions, feel free to ask!

18 Jan 2011

10. Alexandre said...

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

19 Jan 2011

11. Jamis said...

@Alexandre, thanks for sharing what you’ve created! I love seeing these algorithms in other languages, as well as seeing how others approach the implementation.

12. Alexandre said...

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

25 Jan 2011

13. Isaac said...

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?

14. Jamis said...

@Isaac, it sounds like you’re reversing the meaning of the direction bits; if S is set, it means there is a passage to the south, not a wall, which is why the display routine prints a space instead of an underscore when that bit is set.

Good question about why I’m only printing south and east! The reason is that I begin by printing the top border, which gives me the initial north wall. Then each row begins by printing the initial west wall. So, when I display the cell at 0,0, I’ve already got the N and W walls, and I only have to emit the S and E walls. Moving to 1,0, I’ve already got the W wall (from 0,0), so I only need to print S and E, again. In general, by printing the S and E walls at x,y, I’ve also printed the N wall for x,y+1, and the W wall for x+1,y.

I hope that makes sense. :)

I’ll admit the display routines in my sample code are warts; they were optimized for brevity, because I didn’t want them to detract from the algorithm itself. Once I finish writing about these algorithms (three more to go!) I’d like to cover topics like displaying mazes, etc.

31 Jan 2011

15. Ken Liu said...

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.

16. Jamis said...

@Ken, thanks for sharing! I’m glad the exercise showed you more about Groovy; that (learning about a new programming language) was my ultimate goal with these articles, after all!

06 Feb 2011

17. Francis said...

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 <stdio.h>
#include <time.h>

#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)

18. Jamis said...

@Francis, thanks for sharing your implementation! Sorry about the broken formatting; I’ve cleaned that up. In general, it’s probably best to post your implementation somewhere else (I recommend gist.github.com) and then link to it here, because the code-paste format for my blog is not very discoverable. :/

15 Feb 2011

19. Shannon said...

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