The maze book for programmers!

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

# The Buckblog

## Maze Generation: Recursive Division

12 January 2011 — A novel method for generating fractal-like mazes is presented, with sample code and an animation — 6-minute read

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!

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

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!

(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

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

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

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?

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.

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!

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.

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.

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”.

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