The maze book for programmers!

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

# The Buckblog

## Maze Generation: Growing Tree algorithm

27 January 2011 — The author admits to finding a new favorite maze algorithm, and proceeds to describe, walk through, and animate it. Sample code is given — 5-minute read

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!

 1

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:

 1 2

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

 1 3 2

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.

 1 3 2 7 8 4 5 6 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:

 1 3 2 7 8 4 5 6 9

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:

 1 10 3 2 7 8 4 5 6 9

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:

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

Wow, this looks really neat and simple. I can’t wait to try and implement something like this in my language. Experimenting is fun!

Oh! Thanks for this :)

Thanks for this series. I have always been interested in maze generation but had a hard time finding material. Your articles make everything clear.

Nice!

What if you add a ‘counter’ variable to count the number of ‘new’ cells visited? So if the counter == number of cells, it will short circuit the algorithm, thus ending the program without cleaning up C (which I think it’s not necessary).

Just my 2 cents, but great article/explanation anyway! :D

Been following your articles covering maze generation for a couple of weeks now. Keep ‘em coming—they’re great!

Very cool. It reminds me of the algorith I’ve been using for various maze projects over the years. It is also pretty much how my maze algorithm worked from the late 80s, when cycles and memory came at a premium. Nice to see it written up, good job!

The only implementation I have is from a 512 byte game competition in 2001; I changed the algorithm a bit to fit better with the game and graphics generation logic. Here is a write up on the game>

http://www.burninghorizon.com/pub/c64/tinyrinth/tinyrinth.htm

Thanks Jamis, I also have implemented it in C, Java, VB, C# and many other languages – I just never kept any of it.

There is a complete write-up about the code in that C=hacking link at the top of the tinyrinth page. I think I describe the algorithm in there somewhere, but not as well as you have here. I also describe what all the machine code/assembly is doing.

Thanks again for the write-ups, I love mazes and was originally sad to not see something describing the algorithm I had been using, but I was too lazy to do anything about it. Now you have, thanks.

Thanks for a amazing series of maze posts! The Growing tree algorithm is for sure one of the coolest.

How about creating dungeons like in Rogue/NetHack?

Great post!

I am actually interested how you created the demo. Did you actually write the Javascript by hand and then condense it or did you use some extraction framework which auto-generated the Javascript?

Here is my implementation in Canvas, I’ll be trying the other algorithms you explained later.

Thanks for the explanations!

http://www.javierparra.com.mx/experiments/maze/

I worry a touch that your Newest/Random 75/25 split maze generator on this page isn’t working properly. When I run ‘test.rb 15 15 newest:75,random:25’, i get something qualitatively different. Yours expands and looks like fairly strict breadth-first search. My test code sticks out long corridors and has many moments of looking more like a backtracker than prim’s; the 15×15 example on this page never does.

Another twist to this would be to delete cells that have no free routes as they are blocked in also – i.e. adjacent to the path currently being plotted. Should speed up the back tracking.

I’ve been programming mazes since I first saw a recursive back tracking method in a type in from a magazine article (BBC Micro User).

Every new language I’ve learned I’ve programmed a maze in.

Here’s a screenshot of a very early one – 8086 assembler http://www.defsdoor.org/dosmaze.png . The blobs make it strangely mesmerizing and calming.

My most recent was good old fashioned C when I was learning a bit of openGL http://www.defsdoor.org/sdlmaze.png

Absolutely love this series of maze blogs.