I’ve been working on C-Dogs SDL lately, and one thing that often bothered me about that game is that its default random map generator provides an uneven experience. It’s exciting at the start when everything’s unexplored and there are many corridors and rooms to visit, but in the late stage when you are hunting for keys and objectives, backtracking all over the map, it can be quite tedious.
C-Dogs’s map generator is quite configurable and produces a wide variety of maps, but at its core it’s pretty simple:
- Start with an open area
- Randomly place rooms around the place
- Randomly lock some rooms, and place keys in the rooms

The lock-and-key system is in series: the yellow key is in an unlocked room, the green key is in a room locked with the yellow key, the blue key is in a room locked with the green key and so on. Here’s a tree to illustrate this simple structure:

Because the keys (and objectives) could be in any one of several randomly placed rooms, you may need to criss-cross the map many times to collect them all. That’s a lot of backtracking! Another issue is the structure - rooms are isolated from each other, all leading outside. This gives all maps a similar feel. What if there were a map generator that could:
- Provide a more interesting structure
- Feel more like an indoors experience, like a building interior or dungeon?
I was first inspired by sauer2, maker of many C-Dogs SDL custom campaigns, which often take place indoors. These have cool features like:
- Corridors linking many rooms
- Rooms connected directly to each other
- Locks separating entire sections of the map at a time
- Branching pathways
- Minimal required backtracking

Searching online, I came across a neat technique that uses binary space partitioning to generate a building interior. The algorithm recursively splits the area in half, placing a corridor at the split, and continues splitting (while alternating horizontal/vertical splits). Areas left unsplit are then filled with rooms. It’s a simple yet flexible technique.

As the structure of the map is a deeper tree, by finding a critical path that starts and ends at leaf nodes but passes through the root, we can get a fairly long main path, with shorter branches along the way. Here’s what that looks like, in my initial adaptation:

Read more