The Binary Tree Algorithm
Learn what the Binary Tree algorithm is and how it can be used for random maze generation.
We'll cover the following
The Binary Tree algorithm for mazes
The Binary Tree algorithm is, quite possibly, the simplest algorithm around for generating a maze. As its name suggests, it merely requires us to choose between two possible options at each step. For each cell in the grid, we decide whether to carve a passage north or east. By the time we’ve done so for every cell, we have a maze!
This process of looking at cells is called visiting them. Visiting them in some order is walking the grid. Some walks might be random, choosing directions arbitrarily from step to step, like the ones we’ll see in this course. Others are more predictable. For Binary Tree, it turns out that we can do it either way. The algorithm really doesn’t care what order we use to visit the cells. Let's see how it's done below.
The Binary Tree algorithm explained and illustrated
Let's walk this together with an example and see how the Binary Tree algorithm comes together in practice. We'll flip a coin at each step to decide which direction we ought to carve a passage.
The algorithm can be better understood by looking at the slides below side by side.
The Binary Tree algorithm itself doesn’t care where in the grid we begin walking. For the sake of this example, we’ll just go with the cell in the southwest corner.
Our choice is this: do we erase that cell’s northern wall or its eastern wall? Let’s see what the coin says. If it comes up heads, we’ll carve north. Tails, we’ll carve east. And we've got heads. Looks like we erase the northern wall.
The two cells are linked by a connecting passage, and we haven’t technically visited that second cell yet. We could choose to visit that cell next (because Binary Tree really doesn’t care which order we visit the cells), but moving across a row and visiting its cells in sequence is simpler to implement. Let’s wait and hit that northern cell when this row is finished. For now, let’s just hop over to the one immediately to the east of us.
Flipping the coin, we get tails. This means we’ll erase the eastern wall of our current cell.
And flipping the coin for the next cell gives us tails again.
Moving east again, our current cell becomes the one in the southeast corner. We could certainly flip the coin here, too, but consider what would happen if the coin came up tails. We’d have to carve a passage through the outer wall of the maze. This is not generally a good idea. We’ll talk more in a moment about adding entrances and exits to our mazes, but for now, we want to avoid tunneling out of bounds. Since that effectively forbids going east, north becomes our only viable option. No need to flip a coin—let’s just take care of business and carve north.
In fact, that constraint exists for every cell along that entire eastern boundary. None of them can host an east-facing passage. We might as well just take care of those now by carving north on each one of them. We’ll consider each of them visited as well.
Now, for the sake of demonstration, let’s jump all the way to the northwest corner and see what happens next. (Yeah, this is a bit unorthodox, but remember, Binary Tree only needs us to visit all the cells—it doesn’t care what order we use to do that.)
Once again, we could flip a coin, but consider what happens if the coin lands heads-up: we’d have to carve through that northern wall. We don’t want that. Instead, we’ll forego the coin flipping and just carve east.
Again the constraint applies to every cell along that entire northern boundary. We can’t carve north from any of them, so by default, all of them had to carve through east instead.
One more special case to consider. Let’s jump to the northeast-west corner. We can carve neither north nor east from here. Our hands are tied. With nothing to choose from, we choose nothing. Of all the cells in our grid, this is the only one for whom nothing can be done. We shrug our shoulders and skip it.
We'll just go ahead and grab our own coin now and flesh out the rest of those cells that haven’t been visited yet. Once a decision has been made for every cell, we should be left with a maze shown in the last slide below.
The algorithm has been explained with illustrations in the slides below.
Get hands-on with 1200+ tech skills courses.