The Buckblog

I’ve said before that generating mazes is a great default project when experimenting with a new programming language. I’ve yet to find a better one (but I’d love to hear recommendations). However, before you can dive into generating a maze (especially in a syntax you are unfamiliar with), you had better have a solid grasp of how the process works.

With mazes, you can take your pick of a solid double-handful of algorithms: recursive backtracking, Prim’s, Kruskal’s, Eller’s, Aldous-Broder or Wilson’s algorithms, recursive division, hunt-and-kill, and more.

My favorite, and the one I implement by default, is recursive backtracking. It is fast, easy to understand, and straightforward to implement. You’ll need sufficient memory to store the entire maze in memory, though, and it requires stack space again proportional to the size of the maze, so for exceptionally large mazes it can be fairly inefficient. But for most mazes, it works a charm.

Here’s the mile-high view of recursive backtracking:

1. Choose a starting point in the field.
2. Randomly choose a wall at that point and carve a passage through to the adjacent cell, but only if the adjacent cell has not been visited yet. This becomes the new current cell.
3. If all adjacent cells have been visited, back up to the last cell that has uncarved walls and repeat.
4. The algorithm ends when the process has backed all the way up to the starting point.

I generally implement the field as a grid of bitfields (where the bits in each cell describe which direction passages have been carved). That’s probably just the C programmer in me asserting dominance, though; feel free to experiment with other representations.

In Ruby, I usually initialize the grid like so:

1

grid = Array.new(height) { Array.new(width, 0) }

Next, the algorithm itself is kicked off by calling the worker function:

1
2
3
4
5

def carve_passages_from(cx, cy, grid)
  # work, work, work
end

carve_passages_from(0, 0, grid)

This begins carving passages in the grid, starting at the upper-left corner, (0,0). And as you might have guessed from the algorithm’s name, this works recursively, as we’ll see next.

The carve_passages_from method first creates a list of directions that ought to be tried from the current cell:

1

directions = [N, S, E, W].sort_by{rand}

We sort the list in random order, so that the path will meander, rather than having a bias in any particular direction.

Then, the function iterates over each of those directions, determining the coordinates of the cell in that direction and deciding if the cell is valid or not. Note that a cell is valid only if it lies within the bounds of the maze, AND it has not previously been visited: we only want to carve passages into untouched cells, to avoid creating circular loops in the maze.

1
2
3
4
5
6
7
8

directions.each do |direction|
  nx, ny = cx + DX[direction], cy + DY[direction]

  if ny.between?(0, grid.length-1) && nx.between?(0, grid[ny].length-1) && grid[ny][nx] == 0
    # cell is valid!
    # ...
  end
end

Finally, if the cell is valid, we carve a passage out of the current cell and into the next cell. Then, we recursively call carve_passages_from on the new cell:

1
2
3

grid[cy][cx] |= direction
grid[ny][nx] |= OPPOSITE[direction]
carve_passages_from(nx, ny, grid)

And that’s really all there is to it!

For all of you not using IE (and I honestly hope no reader of my blog uses IE), here’s a Javascript demo you can play with to see the algorithm in action:

My complete Ruby implementation, including some lines to output the maze as ASCII, is here:

Start by writing your own implementation in a language you’re comfortable in, just to wrap your mind around the algorithm. Try replacing the recursion with iteration (always a fun exercise). Consider extending it to include weave mazes (where passages move over or under other passages), or braided mazes (mazes where deadends are removed to create loops in the maze), or symmetrical mazes, or wrapped mazes. Or even different cell tesselations. If you’re at all like me, you may find that your “toy” project has taken on a life of its own, and you’re suddenly researching new and exciting ways to build mazes!

Once you understand the algorithm, though, the real fun is trying it in a language you’re unfamiliar with. It’ll show you conditionals, bit manipulation (if you use the bitfield storage like I showed above), iteration, recursion, and console output (if you decide to render your maze, too). When you’ve finished, you’ll have a good idea of how the language looks and works in practice, and not just for trivial “hello world” apps.

Give it a try! Please share your implementations in the comments (links to gist.github.com are preferred).