The Buckblog

The next maze algorithm I’m going to cover, the Aldous-Broder algorithm, is one of the simplest imaginable. It’s also one of the least efficient. In fact, it is so inefficient that you might wonder why anyone would even bother implementing it, let alone discovering it and having their name attached to it.

D. Aldous and A. Broder were two researchers, working independently, who were investigating uniform spanning trees. A spanning tree, as you may or may not already know, is any tree that connects all the vertexes in a graph. A uniform spanning tree is one chosen randomly (and with equal probability) among all the possible spanning trees of a given graph.

Riveting, isn’t it?

There are actually applications for this. Outside of recreational maze generation, I mean. I don’t know what they are myself, but Wikipedia informs me that they are in probability and mathematical physics. (If you know more specifically how uniform spanning trees are being applied in research, please share in a comment!)

Anyway: Aldous and Broder were researching these uniform spanning trees, and independently arrived at the following algorithm:

1. Choose a vertex. Any vertex.
2. Choose a connected neighbor of the vertex and travel to it. If the neighbor has not yet been visited, add the traveled edge to the spanning tree.
3. Repeat step 2 until all vertexes have been visited.

Remember: this algorithm is notable in that it selects from all possible spanning trees (i.e. mazes) of a given graph (i.e. field) with equal probability. The other algorithms I’ve covered don’t have this property.

Let’s walk through a trivial example. If you haven’t spotted yet why the algorithm is so ineffecient, hopefully the example will demonstrate it.

An example

For this demonstration, we’ll use a 3×3 grid. Any bigger than that and we could be here all day.

We choose a cell at random:

And travel to a random neighbor:

And since the neighbor had not been visited before, we carve a passage between the two:

Simple enough! Let’s do a few more quick iterations: choose a random neighbor, and carve a passage to it (but only if it hasn’t been visited before):

Now, watch what happens next. We choose a neighbor at random, but two of the three neighbors are already visisted, which means there’s a very good chance of one of them being picked. Sure enough:

That neighbor’s already been visited! However, this move is allowed by the algorithm; the only constraint is that because the neighbor has been visited before, we don’t carve a passage to it from the previous cell.

Sure, alright. So, we’ll go with it. I think you’re seeing the pattern here, so I’ll just march through the rest of the process:

I hope you noticed how the cursor seemed to meander a bit, there at the end. If you run an animation of Aldous-Broder, you’ll probably find yourself shouting “JUST GO OVER THERE” to the cursor, once or twice. This is because Aldous-Broder, while easy to implement, lacks any real heuristics. And you can’t really add any heuristics without changing the probability curve.

Try the following demo to see just how frustrating Aldous-Broder can be to watch:

I guess it really comes down to what you want out of a maze generator. If you absolutely must have a perfectly uniform spanning tree, then your options are limited.

Implementation

One of the really nice things about Aldous-Broder is how trivial it is to implement. If you can implement the grid data structure, the algorithm itself is almost hardly worth mentioning.

But I’ll mention it anyway.

My implementation begins by choosing a random point, and then computing the number of cells in the grid that remain unvisited:

1
2

x, y = rand(width), rand(height)
remaining = width * height - 1

Then, we just loop until all cells have been visited:

1
2
3

while remaining > 0
  # ...
end

Within the loop, we just iterate over a list of random directions, until we find one that doesn’t take us outside the maze:

1
2
3
4
5
6

[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
    # ...
  end
end

Once a valid direction is found, we check to see if the new cell is unvisited:

1
2
3

if grid[ny][nx] == 0
  # ...
end

If so, we carve a path, and decrement the remaining number of visited cells:

1
2
3

grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]
remaining -= 1

Regardless of whether the cell has been visited or not, we then make the new cell the current cell, and break out of the innermost loop (the one where we look for a valid direction):

1
2

x, y = nx, ny
break

And that’s it. All that remains is to fire it off and sit back while it does it’s little drunkard’s walk all over our nice clean grid.

Conclusion

Aldous-Broder isn’t the most efficient algorithm on the block, or the smartest, but it is definitely well-suited for the problem domain that it was created for: finding uniform spanning trees. However, even there, there are more efficient algorithms. Next time, I’ll demonstrate Wilson’s algorithm, a (slightly) more efficient way to find a uniform spanning tree.

In the meantime, try your hand at Aldous-Broder. It shouldn’t set you back more than a couple of minutes, and it really is pretty fun.

For reference, here is my own (Ruby) implementation of Aldous-Broder:

Enjoy!