Braiding Mazes

Background

So far, we’ve assumed that all of our mazes are perfect—that is, they have no loops in them. We’ve said that there must be only a single path to get from one point in a maze to any other point, and it is never allowed to intersect itself.

The sad fact is that most real environments are not actually perfect mazes. Whether we’re navigating the stacks of a library or the streets of a town, we can generally get from one place to another via multiple possible routes. This is mirrored in video games: in Pac-Man, for instance, we can take one path into an area and return by another, cleverly escaping those ghosts on our tail. Dungeon crawlers (NetHack) and “open world” games (Zelda, Final Fantasy) give us quite a bit of freedom to move between areas using various paths. First-person shooters like Doom, Quake, and Descent use mazes with loops to enable all kinds of great tactical scenarios. From a game design perspective, allowing paths to intersect themselves can open up exciting new ways for a game to be played.

So, it’s time to shake things up a bit. We’re going to look at two different ways to relax that “no self-intersections” rule: braiding by removing dead ends and thus adding loops to our mazes, and weaving, which allows passages to intersect by moving over and under each other.

Let’s start with braiding.

Defining a braid maze

A maze with no dead ends is called a braid maze. There’s no reason this has to be all-or-nothing, though. Mazes may be heavily braided (with all or most dead ends removed), lightly braided (with only a few dead ends removed), or anything in between. The process we’ll consider here called dead-end culling, will let us produce a maze with any level of braiding we desire.

Braiding our mazes

Previously, we added a method called deadends to Grid. We made it return a list of all the dead-end cells in the grid and used it to compare maze algorithms based on the number of dead ends they generated.

It turns out that we can use that same method here. Once it tells us where the dead ends are, the process for culling or removing them is straightforward: we just need to link each dead-end cell to one additional neighbor. This effectively erases one of its walls and adds a loop to the maze. Following that logic, it also means that a braid maze is not a perfect maze—it will always have at least one loop in it.

Let’s implement this. Thanks to our deadends method, we’re about halfway there already. All that’s left is to loop over the cells it returns and link each one to a random neighbor. We’ll make this the responsibility of a new method on Grid. The new method, braid, is highlighted in the code below:

The updated Grid class