When designing a map generator, look twice; sometimes, a few tricks are all you need to turn bad output into good output. In the spirit of my earlier article, I'm going to take a well known bad map generator, figure out what's wrong with it and turn it into a good one. Along the way, I'm going to take a look at what it is that makes some dungeons fun to explore and others not.
The algorithm I'm starting with is recursive, and it looks like this:
It's fairly simple, and it's easy to extend with things like circular rooms, vaults and such. There's no need to worry about connecting things, because it all connects itself. There are some tricky details; in particular, things can be rotated different ways, and the doors off of rooms can be anywhere along the wall. Take a look through the implementation (C++) before continuing.
Common sizes for single-screen maps are around about 64x20 (smaller in the y direction because monitors are wider than they are tall, and ASCII characters in most fonts are taller than they are wide.) So, here's that program's first output after debugging:
This output is... reasonable. It has rooms and corridors, everything's connected up. It has a lot of dead ends, but that's not too hard to fix (dead ends are easy to detect and remove.) But there's something not quite right about it, which is hard to put a finger on. One good test is to try making a much bigger map, and seeing if the problem is obvious there. So, let's make a map that's 80x80.
Now this map has something VERY wrong with it: the path through the map is a single, long spiral from the outside of the map in!
So, what happened here? Well, the algorithm starts off by placing a room at the bottom. Then it adds features to the left, top, and right walls, in that order. Starting with the left wall, it makes a corridor, then puts a room at the end, and... by the time it comes back to the first room, it's already built the entire map, so there's no space to add. It builds a path of rooms and corridors, and because it adds to the left wall of rooms first, the path tries to turn left. Failing that (because the edge of the map or an old part of the path is in the way), it continues straight; and if both the left and straight paths are blocked, it turns right. It does this until most of the map is filled, then backs up and fills in the gaps.
From a gameplay perspective, this map is actually not bad at all. The player will have to explore the whole map, and won't have to backtrack much. But he won't have to think much either; there's no possibility of taking an alternate route to avoid danger, shortcuts or getting lost. On top of that, one of the original ideas was that this algorithm would be extensible; it should be easy to add new room types, vaults, crossroads, etc. But it's so quirky that adjusting the things it generates could produce something completely unexpected. This is the sort of level generator you would use once as dungeon level 71 to introduce variety, not something you could use repeatedly.
So, how to fix it? Instead of connecting the left, opposite, and right walls in order, the order could be randomized. That'll help somewhat, but there will still be a single path covering most of the map, it just won't be a neat spiral anymore. But there's a simple solution:
But there's still something wrong, although it's a little less blatant. There are no loops! The whole map is one big tree.
In technical terms, this map is acyclic (without cycles, that is, loops). This has very bad gameplay implications. Suppose you're in the teal area, and you have used a detection spell to determine that the stairs are in the green area. You'll have to backtrack all the way to the beginning and explore the other half of the dungeon before you can get to the stairs which were a few steps away. You still can't find alternate routes around danger, or run away effectively.
Obviously, cycles need to be introduced somehow. This could be done as an extra stage in the map generation: add some extra connections after the level is finished. However, by that point all of the information about where corridors should go has already been discarded. It's better to make the map and make cycles at the same time.
The answer is to change the rule used to make corridors. Instead of checking whether a passage "fits" in the same way as a room "fits", a corridor which would overlap a room should instead connect to that room. The only case where a corridor should not be placed is when it hits the corner of the room, as shown on the right.
The changes are again straightforward. The room builder needs to be changed to mark its corners, and the corridor placer needs to check for intersection and stop digging once an intersection is reached. So, with only this changed, what does the output look like? Here it is:
This is a huge improvement; with this map, if a player knows where something is he can head in the right general direction and be pretty sure he'll find it. There are, however, a few glaring issues. The first is corridors that are so short they have two doors in a row. That's ugly. The second is long dead ends, like the one across the top of the map.
We can explicitly check the length when digging a corridor to see if it would make a double door, and disallow that. We can also get rid of dead ends just by checking whether an intersection occured, and not allowing corridors which don't intersect anything. Implementation (show differences). With these changes, the map's appearance changes drastically:
Two things have obviously changed. First, there are no dead ends anywhere. Second, there much fewer corridors in general. The problem is that when digging into empty space, there is nothing for corridors to intersect with, so corridors won't be placed; and when digging back into already-filled area, the corridor length usually comes out short.
There is lots of room left to improve this algorithm. The corridor handling could be changed to dig corridors into empty space, but keep track of them and delete the dead ends later. There is no support for pre-build and non-rectangular rooms yet, though in principle that should be easy to add. For any level generator, there are always tricks tricks and refinements to make a better level. That will be the subject of my next article.
Appendix
Copyright (C) 2005 by Jim Babcock. Permission is granted to republish this article on the sole condition that proper credit is given.