Digging Deeper into the Binary Tree Algorithm

Entrances and exits

At this point, though, you might wonder how it can be a maze if there is no way into or out of that box. Aren’t mazes supposed to have starting points and ending points? That’s a fair question! The truth of the matter is that it’s entirely up to us.

Earlier, we talked a bit about the idea of perfect mazes. It all comes back to that again. The maze we just drew is a perfect maze, and one of the attributes of a perfect maze is that there exists exactly one path between any two cells in it. Any two! We pick them, and there’s guaranteed to be a path between them.

This means we can choose any two cells in our maze, make one of them the starting point and the other the ending point, and we can be confident knowing that there’s a real solution to our maze. Just like that. Want to enter on one side and exit on the other? We'll choose two cells on the boundaries of our maze, erase the outer walls of those cells, and we’re all set.

It depends on what we want our maze to do. The maze in Pac-Man, for instance, has no exit at all because the goal is simply to eat all the pellets before the ghosts get you. Other games, like Zelda, allow us to enter a maze, but the goal is to reach a point inside it, so we can defeat some boss creature and obtain the treasure.

So don’t be surprised when the examples in this course omit the “start” and “finish” points. Those will be up to us and our imagination.

Understanding texture

Looking at our maze, we might notice a few odd things. For instance, the northern row and the eastern column are both unbroken corridors. These are completely expected if we think about it. Remember what happened on those boundary cells where erasing a wall would have taken us outside the bounds of the maze? We always chose the valid direction instead, north or east, forcing those boundaries to merge into a single passage.

This contributes to what we call the maze’s texture. Texture is a general term that refers to the style of the passages of a maze, such as how long they tend to be and which direction they tend to go. Our first impression of a maze is often strongly influenced by the maze’s texture.

Some algorithms will tend to produce mazes that all have similar textures. Binary Tree, for example, will always produce mazes with those two unbroken corridors on the north and east. The following figure represents a bare handful of mazes randomly generated using Binary Tree, and notice how they all have those same long corridors on the north and east.