Maze Generation: Growing Tree algorithm

Posted by Jamis on January 27, 2011 @ 07:48 AM

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!

Posted in Under the Hood

27 Jan 2011

1. Tristan Leroux said...

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

2. alex said...

Oh! Thanks for this :)

3. Mark said...

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

4. behindthecodes.com said...

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

5. Jamis said...

@behindthecodes, yes, that would be a nice optimization! In general though, I think you’ll find that the time saved will not be too significant (you only notice it in the demo because there is a 0.2s delay between frames). But if you were generating a lot of mazes, or very large mazes, that would be an optimization worth considering.

I’ve tried to avoid adding optimizations to the code I’m demonstrating, to keep the algorithm clear and concise, but there is no doubt that there are many, many ways to speed these algorithms up! Keep sharing the ideas you have!

(In fact, a series on ways to optimize these algorithms could be interesting, if anyone’s looking for topics to write about.)

6. King Inky said...

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

7. Jamis said...

Thanks, @King! I’ve got quite a few more in the pipeline (two more about maze algorithms, and ideas for several related topics.) Stay tuned!

8. Mark said...

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

9. Jamis said...

@Mark, that is very cool. :) Thanks for sharing that! My assembly-fu has never been strong, but I’m going to make some time to read through your code. Thanks for sharing!

10. Mark said...

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.

11. Jonas said...

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?

12. Jamis said...

@Jonas, I’m really not sure how they generate the dungeons in NetHack (et al.) but you’ve got me curious. They are definitely circular, sparse mazes, so if they’re using one of these algorithms they’re probably running a “sparsify” phase afterward to cull dead-ends and then a “braid” phase to add circular connections. I might take a look tonight to see how they’re doing it.

13. Jamis said...

For the curious: Roguelike Dungeon Generation. Guess that answers my question. :) It’s not one of the algorithms I’ve covered, and seems well-suited to it’s purpose: sparse graphs with circular connections. And rooms.

Great post!

28 Jan 2011

15. qball said...

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?

16. Jamis said...

@qball, the demos are actually written in CoffeeScript, which compiles to Javascript. The CoffeeScript sources are on Github, at https://github.com/jamis/csmazes. The code is all public domain, so you can do with it what you will, but it should be noted that the code is optimized for animating the algorithms, not for generating mazes quickly. The code should be “fast enough” for most purposes, but if you need lightning-fast maze generation, you’ll want to implement the algorithms yourself.

29 Jan 2011

17. Huevoos said...

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/

18. Jamis said...

@Huevoos, thanks for sharing! The “animate” mode when the mazes get large is pretty hypnotic to watch. Well done :)

30 Jan 2011

19. J said...

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.

31 Jan 2011

20. defsdoor said...

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.

21. Jamis said...

@J, good catch! There was indeed a bug in the JS demo that caused the 25/75 and 75/25 splits to be weighted incorrectly. I’ve fixed that, and it should be working fine now. (You may need to clear your browser’s cache to pick up the fix.)

@defsdoor, that might not be as much of an improvement as you think, since the cost to determine whether a cell has any free sides will be the same whether you do it immediately, or whether you wait and let the algorithm pick up the cell later. Either way, all four sides need to be tested, and the cell subsequently removed. Still, intuition is often wrong in these sorts of things; if you try this, please let me know what you find out!

03 Feb 2011

22. defsdoor said...

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.