The Buckblog

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!