Mazes for Programmers

Chapter 9Braiding and Weaving Your Mazes

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

The sad fact is that most real environments are not actually perfect mazes. Whether you’re navigating the stacks of a library or the streets of a town, you can generally get from one place to another via multiple possible routes. This is mirrored in video games: in Pac-Man, for instance, you can take one path into an area and return by another, cleverly escaping those ghosts on your tail. Dungeon crawlers (NetHack) and “open world” games (Zelda, Final Fantasy) give you ...