The Buckblog

This next algorithm is crazy, crazy simple. It also is the only one of the algorithms I’ve covered with the ability to generate a perfect maze without keeping any state at all. It can build the entire maze by looking at only a single cell at a time.

Here’s how it works: for every cell in the grid, randomly carve a passage either north, or west.

That’s it. You can mix it up if you want, and choose between other diagonal sets: north/east, south/west, or south/east, but whichever diagonal set you select must be used consistently throughout the entire maze.

There’s another nifty attribute of this algorithm: if you can guarantee that for any given cell, you will always carve a particular direction, then you never need to keep any of the maze in memory. When you need to display some portion of the maze, you just “rebuild” it, trivially. This means you could create infinitely large mazes in very little memory.

It’s not all roses, though. A side-effect of this algorithm is that it has a strong diagonal bias. Also, two of the four sides of the maze will be spanned by a single corridor. But for some applications, that might be acceptable.

It’s almost too simple to bother, but let’s take a quick look at the algorithm in practice.

An example

I’ll use a trivial 3×3 grid.

Because this algorithm doesn’t need to consider the state of any adjacent cells, we can start from and proceed to anywhere we want; let’s begin with the bottom-right corner:

Then, we randomly carve a passage either north, or west. Let’s choose…north!

Let’s work through the rest of that bottom row similarly, carving west from the middle cell, and north from the south-west corner:

Note that for the bottom-left (south-west) corner, “west” was not an option, since it would take us outside the bounds of the grid. Thus, our hand was forced and we had to choose north. But we’re okay with that, right?

Let’s move on and process the second row:

Again, we were limited in our choices in the western-most cell: all we could choose was north, so we did.

Now, look what happens for the final row:

Because we can’t go north in any of those, we have to choose west. And for the north-west corner, we can’t choose either north, or west! So we simply mark it visited and trust that the algorithm will connect it by other means.

Notice the corridors spanning the north and west boundaries. This is one of the side-effects I mentioned. Also, while it’s not so visible in a maze this size, the maze has a strong north-west bias; there are no dead-ends (and never will be any dead-ends) facing either north or west. Thus, if you start at the south-east corner, getting to the north-west corner is trivial—you’ll never hit a dead-end. (Going the other direction is harder; it’s like carving wood with the grain, versus against the grain.)

Play around a bit with the following demo to see what I mean. You can also select a different bias here, to see how that changes things.

Bias: Northwest Northeast Southwest Southeast

Implementation

The implementation of this algorithm is as trivially simple as you might think. You only need to cover every cell of the grid. One way to do that is to simply iterate over every row and column, in order:

1
2
3
4
5

height.times do |y|
  width.times do |x|
    # ...
  end
end

Within the loops, you determine which directions are valid:

1
2
3

dirs = []
dirs << N if y > 0
dirs << W if x > 0

And then you randomly select one:

1
2
3

if (dir = dirs[rand(dirs.length)])
  # ...
end

Once you’ve selected your direction, you just carve a passage between the two cells:

1
2
3

nx, ny = x + DX[dir], y + DY[dir]
grid[y][x] |= dir
grid[ny][nx] |= OPPOSITE[dir]

And you’re done!

Conclusion

The sharp-eyed among you might have noticed the connection between the name of the algorithm, and its output. Yes, the “Binary Tree” algorithm creates a random binary tree! Imagine that.

Every cell has one connection toward the “root” (in the direction of the bias, e.g. north or west), and zero, one, or two connections in the other direction (south or east). The root is, in this case, the north-west corner. If you could reach in and pluck up the north-west corner, giving it a good tug, it would uproot its children, and their children, and their children, until you’re left with a binary tree dangling downward like the knobbly roots of some tenacious weed.

Now, there are obviously other ways to build mazes based on binary trees. A particularly fun one is to make a variation of the Growing Tree algorithm: select a root node anywhere in the grid and add it to the list. Then, while the list is not empty, you remove a node from the list, add up to two passages leading away from it, and add those neighbors to the list. (I call this the “Growing Binary Tree algorithm”.) You’ll end up with another random binary tree, but without the obvious blemishes of the Binary Tree algorithm.

Nevertheless, the Binary Tree algorithm is fun to implement, and can be perfectly suitable for some applications (for instance, if you’re inside the maze, the biases will be less obvious). And if you need stupendously enormous mazes that can’t exist entirely in memory, why, this is an excellent algorithm as well.

My full implementation is below. Give it a try yourself, and share what you come up with!

Enjoy!