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 ...