The Buckblog

Remember way back in the first article of this series, where I said that Recursive Backtracking was my favorite for generating mazes? Well, I changed my mind. My new favorite is the Growing Tree algorithm.

This algorithm is pretty cool. Configured one way, it mimics the behavior of the Recursive Backtracking algorithm. Configured another, it works almost exactly like Prim’s algorithm. Another trivial change, and you can generate mazes with attributes of both.

It’s really pretty slick. Here’s how it works:

1. Let C be a list of cells, initially empty. Add one cell to C, at random.
2. Choose a cell from C, and carve a passage to any unvisited neighbor of that cell, adding that neighbor to C as well. If there are no unvisited neighbors, remove the cell from C.
3. Repeat #2 until C is empty.

Pretty straight-forward, really. But the fun lies in how you choose the cells from C, in step #2. If you always choose the newest cell (the one most recently added), you’ll get the recursive backtracker. If you always choose a cell at random, you get Prim’s. It’s remarkably fun to experiment with other ways to choose cells from C.

Let’s look at a simple example.

An example

I’ll demonstrate the “choose newest” cell selection method, which will hopefully be enlightening enough that you can imagine on your own how the “choose random” method might proceed.

The algorithm begins by adding an arbitrary cell to the list. We mark the cell as “in”; I’m also going to assign the cell a number, visually, to help keep track of the relative age of each cell. Also, cells in red are in the list of “live” cells; they’ll go white once they’ve been removed from the list.

So, onward!

Next step: we choose the newest cell from the list, randomly select one of its unvisited neighbors, carve a path to it, and add the neighbor to the list:

Let’s do it again, once more choosing the newest cell from the list:

See the pattern? By always choosing the cell most recently added to the list, each subsequent step simply extends the passage one more step, effectively doing a random walk. But how does the algorithm behave when the passage cannot be extended any further?

Let’s fast forward a bit and see what the behavior is. Here we are now, six iterations further along, and we’ve hit a dead-end at cell #9.

At this point, the algorithm would select the newest cell (#9), and then try to find an unvisited neighbor cell. Alas, there isn’t one! So cell #9 is voted off the island removed from the list:

Then the algorithm goes around again, grabbing the newest cell from the list. This time, that’s #8, and sure enough, there is an unvisited adjacent cell that we can move to:

Did you see that?! It backtracked!

Not really. It wasn’t intentionally backtracking; it just happened that the algorithm’s choice of cell was the same one that the backtracking algorithm would have chosen. And it will continue to choose identically to the backtracker, clear up until every cell has been visited and it has to “backtrack” all the way back to the original cell. At that point, the list of cells will be empty, and the algorithm will terminate.

Pretty cool!

Take a moment and think about how the algorithm would change if, instead of choosing the newest cell each time, we chose one at random. I’ve already told you it would behave like Prim’s algorithm in this case, but can you see why? I hope so, because I’m not going to draw any more diagrams tonight. :)

Instead, you can play with the following demo, which has presets for several different cell-selection methods. Choose a few different ones and compare how they behave.

Cell selection method: Newest (Recursive Backtracker) Random (Prim's) Newest/Random, 75/25 split Newest/Random, 50/50 split Newest/Random, 25/75 split Oldest Middle Newest/Oldest, 50/50 split Oldest/Random, 50/50 split

Implementation

Implementation-wise, this is one of the simplest algorithms (another reason to love it!). In fact, in my own implementation, the most complex part came from code that I added that lets you specify the cell-selection method when the script is executed!

It starts by selecting a random cell and adding it to the list:

1
2

x, y = rand(width), rand(height)
cells << [x, y]

The program them simply loops until the list is empty:

1
2
3

until cells.empty?
  # ...
end

Within the loop, we first select the cell to operate on. I’m going to mask my own program’s complexity here behind a simple “choose_index” method; it takes a number and returns a number less than that.

1
2

index = choose_index(cells.length)
x, y = cells[index]

Next, we iterate over a randomized list of directions, looking for an unvisited neighbor. If no such neighbor is found, we delete the given cell from the list before continuing.

1
2
3
4
5
6
7
8

[N, S, E, W].shuffle.each do |dir|
  nx, ny = x + DX[dir], y + DY[dir]
  if nx >= 0 && ny >= 0 && nx < width && ny < height && grid[ny][nx] == 0
    # ...
  end
end

cells.delete_at(index) if index

When a valid, unvisited neighbor is located, we carve a passage between the current cell and that neighbor, add the neighbor to the list, set index to nil (to indicate that an unvisited neighbor was found), and then break out of the innermost loop.

1
2
3
4
5

grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
cells << [nx, ny]
index = nil
break

And that’s really all there is to it. Some possible implementations of the choose_index method might be:

1
2
3
4
5
6

def choose_index(ceil)
  return ceil-1 if choose_newest?
  return 0 if choose_oldest?
  return rand(ceil) if choose_random?
  # or implement your own!
end

Try it out and see what new cell selection methods you discover!

Conclusion

Personally, I love the flexibility of this algorithm. It’s surprisingly easy—and addicting!—to try crazy new ideas for selecting cells, and the algorithm itself is almost trivially simple to implement. Performance-wise, the algorithm is one of the faster ones (assuming you can make removing a cell from the list reasonably fast), and while memory use is proportional to the size of the maze itself, that’s not unusual for most of these algorithms.

Seriously, what’s not to like?!

Give it a try and link to your implementations in the comments. Share your ideas for new cell selection methods, too—I’d love to see what you come up with!

For reference, the complete source of my implementation, in Ruby, is below. Remember that most of the code in my implementation is for cell selection and displaying the maze; the algorithm itself is only the tiny bit at the end!

Enjoy!