Mazes, rooms, and pathways

You can tell it's the holiday season, because I've been playing games and thinking about games, a lot.

So I thoroughly enjoyed Robert Nystrom's recent essay: Rooms and Mazes: A Procedural Dungeon Generator.

Nystrom takes us through a variety of different approaches to generating dungeons for adventure games, because it turns out there are a lot of things to consider.

For example:

You could make a roguelike with perfect dungeons, and many simple roguelikes do that because generators for those are easier to design and implement.

But I find them less fun to play. When you hit a dead end (which is often), you have to do a lot of backtracking to get to a new area to explore. You can’t circle around to avoid certain enemies, or sneak out a back passage.

Nystrom proceeds to explore two basic approaches to dungeon generation:

• Start with a maze. Trim back the maze to leave holes in the space, then turn those holes into rooms.
• Start with a bunch of randomly-placed rooms. Flood-fill the spaces between the rooms with mazes, then connect things together

As he puts it:

Where Buck and Karcero start with the maze and then add the rooms, mine does things in the opposite order. First, it places a bunch of random rooms. Then, it iterates over every tile in the dungeon. When it finds a solid one where an open area could be, it starts running a maze generator at that point.

The best part of the article is the illustrations. Nystrom fills the article with live demonstrations of various techniques, which bring the code to life and make it easy to understand the alternatives and how they impact the resulting generated dungeon.

If you've ever tried your hand at generating a dungeon (and what game-playing computer programmer hasn't?!), I think you'll really enjoy reading Rooms and Mazes.

Who knows? It may even get you excited enough to start writing that game you've been putting off...