Maze Generation: Recursive Division

Posted by Jamis on January 12, 2011 @ 08:29 AM

All of the maze algorithms I’ve covered so far (recursive backtracking, Eller’s, Kruskal’s, and Prim’s) were implemented as “passage carvers”: they started with a solid grid and hollowed the passages out of it. Some algorithms can be implemented a different way (and indeed, some must be implemented this way): as “wall adders”, where the process begins with a large empty space, and adds walls until a maze results.

The “recursive division” algorithm is one that must be implemented as a wall adder. This algorithm is particularly fascinating because of its fractal nature: you could theoretically continue the process indefinitely at progressively finer and finer levels of detail.

It works like this:

  1. Begin with an empty field.
  2. Bisect the field with a wall, either horizontally or vertically. Add a single passage through the wall.
  3. Repeat step #2 with the areas on either side of the wall.
  4. Continue, recursively, until the maze reaches the desired resolution.

You’ll find that at every step, you still have a valid maze. Each repetition of the algorithm simply increases the level of detail. Pretty cool!

Let’s walk through an example to get an idea of how this works in practice.

An example

We’re going to start with a larger grid this time, 5×5, just to show how the algorithm quickly converges. (If there is too much hand-waving, call me on it in the comments! I’ll be more than happy to expand wherever things get too obtuse.)

First, we’ll bisect it vertically, because I’m just that kind of a guy. I’ll just close my eyes and point…here…so we’ll add a wall at x=3:

Then, we randomly add a gap in the wall, so that we preserve the connectability of the graph:

And that finishes the first iteration. Now, we repeat these steps on each of the two subfields that we created by adding that wall. Let’s go with the field on the right, first.

Now, theoretically, we could bisect that either vertically or horizontally. However, for best results, if you’re bisecting a field that is taller than it is wide (like we are now), it’s best to bisect horizontally. It’ll prevent really glaring biases in the finished product, and generally makes for more interesting mazes. (Similarly, when bisecting a field that is wider than it is tall, you should prefer a vertical wall.)

So, let’s cut this field in half horizontally this time, and then add a passage through it:

(From here on out, I’m going to merge the “add wall” and “erase passage” steps into a single step: you’ve been warned!)

That completes another iteration. Let’s do one more quick iteration on the top-right field, now, and see how the recursion bottoms out when you hit your target resolution.

The field in the top-right is a square, so we can randomly choose between a horizontal or a vertical bisection. Let’s go with vertical:

Now, we’ve got two new subfields to recurse into, but hark! We can’t divide them any further without passing our target resolution (our grid is only 5×5, remember). So the recursion bottoms out, and we rewind back up the stack.

I’m going to be moving much faster now, chugging along to the end of the algorithm.

And we’re done! The result is a perfect maze.

If you’re not using IE, you can step through the algorithm yourself using this nifty Javascript demo. The one of the left is a 5×5 grid, and the one on the right is a 15×15 grid (so you can get a better feel for how the recursion works on larger mazes).

Implementation

So, how would you implement this? My implementation really only needed a single supporting method, aside from the actual algorithm itself:

1
2
3
4
5
6
7
8
9
def choose_orientation(width, height)
  if width < height
    HORIZONTAL
  elsif height < width
    VERTICAL
  else
    rand(2) == 0 ? HORIZONTAL : VERTICAL
  end
end

The choose_orientation method gave me a simple abstraction for deciding which way a field with the given dimensions ought to be bisected. Once I had that in hand, I just needed a divide method, which recursively divided the field as described:

1
2
3
def divide(grid, x, y, width, height, orientation)
  # ...
end

The algorithm was started by calling divide on the entire grid:

1
divide(grid, 0, 0, width, height, choose_orientation(width, height))

The method itself first checks to see if the maze has reached the target resolution:

1
return if width < 2 || height < 2

Then, it sets a convenience flag so we can query the orientation, and starts answering questions about where the wall needs to be drawn, and where the passage through the wall will be:

1
2
3
4
5
6
7
8
9
horizontal = orientation == HORIZONTAL

# where will the wall be drawn from?
wx = x + (horizontal ? 0 : rand(width-2))
wy = y + (horizontal ? rand(height-2) : 0)

# where will the passage through the wall exist?
px = wx + (horizontal ? rand(width) : 0)
py = wy + (horizontal ? 0 : rand(height))

Then a few helper values get set, to aid in drawing the wall:

1
2
3
4
5
6
7
8
9
# what direction will the wall be drawn?
dx = horizontal ? 1 : 0
dy = horizontal ? 0 : 1

# how long will the wall be?
length = horizontal ? width : height

# what direction is perpendicular to the wall?
dir = horizontal ? S : E

Once that’s all set up, we can actually draw the wall:

1
2
3
4
5
length.times do
  grid[wy][wx] |= dir if wx != px || wy != py
  wx += dx
  wy += dy
end

Lastly, we determine the bounds of the subfields, and recurse:

1
2
3
4
5
6
7
nx, ny = x, y
w, h = horizontal ? [width, wy-y+1] : [wx-x+1, height]
divide(grid, nx, ny, w, h, choose_orientation(w, h))

nx, ny = horizontal ? [x, wy+1] : [wx+1, y]
w, h = horizontal ? [width, y+height-wy-1] : [x+width-wx-1, height]
divide(grid, nx, ny, w, h, choose_orientation(w, h))

And that’s really all there is to it. My complete implementation is here, including some simple ASCII output routines (an ANSI terminal is required):

Conclusion

I really had a blast implementing this algorithm. It’s especially hypnotic to watch the demos as they animate its progress. I’d love to see someone implement a mandelbrot-style “infinite zoom” with a recursive-division maze. I’m not sure there’s a lot of practical value there, but it seems like it could have a high degree of “cool”. :)

As far as the mazes themselves, it’s readily apparent after generating a few that the mazes will tend to have a lot of short cul-de-sacs, like Kruskal’s and Prim’s, and the nature of the algorithm tends to create long walls that span significant portions of the field, which leads to visual artifacts that (in my opinion) detract from the appearance of the maze. Some of this could be overcome by artfully choosing where to place walls, but that will only take you so far. So, alas, I don’t think I’ll be using this algorithm for anything besides demo animations.

Give it a try yourself, though, and see how your implementation turns out. If you come up with something cool, let me know!

Posted in Under the Hood

Comments

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

12 Jan 2011

1. ben said...

Loving this maze posts. This would make a fun book at some point.

2. yachris said...

Really like the animations - they make the algorithms come alive :)

It’d be cool to see a “breadth first” version of this. What I mean is keep a list of rooms. The first room is the whole maze; you take the next room off the front of the list, split it into two new rooms and add each to the end of the list. So instead of recursing down to the smallest rooms in each area, it fills in a the same level of detail everywhere. Takes more memory, but it would easily allow the “infinite zoom” effect.

Thanks!

3. Jamis said...

@yachris, that’d be a great way to approach it—give it a try and let me know how it goes!

4. Samuel Williams said...

I had a different approach.

(1) Generate a random path through the maze, then randomly add walls that don’t intersect that path.

(2) Select a start and end point. Randomly add walls and check that they are still connected. Repeat until appropriate wall density is met.

For (2), I used A* algorithm.

If you are interested in mazes, you might enjoy my A* demonstration: http://www.oriontransfer.co.nz/research/a-star-maze-solver/index

5. Magnus said...

I have a method by which I can solve any maze instantly, after some initial work has been done.

13 Jan 2011

6. Darryl Nester said...

Just discovered this series of posts today—very nice!

I did some similar work creating demos of maze generation a few years ago, intended for an audience of students in an introductory programming course. My demos are here: http://www.bluffton.edu/%7Enesterd/java/maze.html (These illustrate several methods of maze generation on square and hexagonal grids. They should work in any browser, including [shudder] IE.)

In addition, if you want to test your understanding of recursive backtracking mazes, see if you can identify the starting point of the maze in the finished product: http://www.bluffton.edu/%7Enesterd/java/mazegame.html

7. terry said...

love your blog and especially the javascript demos. i would love to forward them to similarly minded techies. do you have a page which just summarises the demos for the various algorithms on one page?

8. Jamis said...

@Darryl, very nice! Using pregenerated image tiles to display the maze is a great idea, I was trying to think of ways to efficiently show different tesselations, and that’s a good one. I may have to steal that eventually. :)

@terry, the source code is in CoffeeScript (which compiles to Javascript), and is available here: http://github.com/jamis/csmazes. A demo of all algorithms implemented in that project is hosted at http://jamisbuck.org/mazes, but that site may not always be in sync with the latest version on GitHub.

9. Michael B said...

Interesting article. I love mazes, and generation of them has always been something that I thought I’d get into but never seemed to find the time.

It still amazes me, though, that someone would intentionally alienate a significant portion of the potential visitors by making one browser or another not support their code. You don’t write code that only works in IE because the users of the other browsers will not be able to use your website, and vice-versa. I’m not trumping any one browser, it just seems like I spend a lot of time trying to get that concept through to far too many people in the development world.

BTW, just out of curiosity I tried it and your samples did work for me in IE 8, both running and stepping.

10. Jamis said...

@Michael, I’m glad it worked for you in IE8. Just so you know, I’m not intentionally alienating IE users. I spent a few hours trying to get these algorithms to render well in IE, and it was some of the most frustrating hours I’ve spent in recent memory. And it was fruitlessly spent, too. I have no idea why it’s working for you (though I’m glad it is), but my experiments all resulted in the mazes rendering with cells wrapping oddly, resizing randomly during animation, and generally being a mess. The closest I got to it working in IE also resulted in the animation performance degrading terribly on other browers at larger resolutions, which wasn’t acceptable to me.

The code for these animations is in the public domain, though, at http://github.com/jamis/csmazes, so if you (or any other IE-minded person) feels passionately enough about this, they are certainly welcome to have a go at it. For myself, this is all a labor of love, and done without a penny received in return, so I’m obviously going to focus on what brings me pleasure, and IE definitely does not do that.

11. Jon Peterson said...

I could certainly see this being combined with your Mandelbrot zoom idea into a game inspired by Falldown ( http://www.albinoblacksheep.com/games/falldown ).

It would probably require some refining of the algorithm to prevent impossible situations from developing - at least to a certain degree - but I think it’s something a lot of people would play if it showed up on Kongregate!

12. Jon Peterson said...

Err… that was supposed to be wrapped in dashes. I did not intend it as strikethru text. Just clarifying! Meant it as an admission that such a game would have different requirements, NOT as a negative implication about your code.

20 Jan 2011

13. TechNeilogy said...

I like this algorithm. The fractal nature of the mazes reflects the type of complexity one finds in natural maze-like structures such as complex buildings, caves, etc. It is not unusual in such venues to find complex groupings of passages connected by narrow halls or single doors. So the mazes generated seem more realistic to me and less like artificial puzzles.

25 Feb 2011

14. shayneo said...

Whats nice about this one, is by backing off from recursing down to fully completing the render you get “rooms” generated. On my experiments on a 100×100 grid, about 5-6 depths recursion generates nice mazes with lots of “rooms”.

05 Apr 2011

15. Josiah Carlson said...

You don’t need to “add walls” in order to implement this algorithm. I implemented it with a “passage carvers” method by only changing a small piece. https://gist.github.com/904686

Also: great articles. I’ve been enjoying going back and reading them when I have free time :)