I'm currently starting on my 4th set of dungeon generation routines for my game Heroic Adventure!. The first two attempts were horrible beyond mention. The 3rd attempt, although slightly buggy, was actually pretty good. The 4th attempt has only just begun, but I have big plans for it. For now, I'm going to focus on what went wrong and what turned out ok with the 3rd one.
Dungeon generation can be accomplished by a variety of methods, some with very clever names like “game-of-life“ and “drunkards walk“. Ok, the purists among you will argue that Drunkards walk is more suitable for cave generation, and they would be right. The routines I am working on are what you would call “room and passage“, but I digress. The basic concept of a dungeon in most computer games is a labyrinth of rooms connected by winding passageways.
Some folks like to use organic methods that they claim makes the dungeon look as if it were dug out over a period of time. They start with one room, and another adjacent room, then maybe a corridor, with a chance of a room or bend at the end of it. They keep branching out until they more or less fill the map. Ok, that's not bad, but we can do better.
Another approach is to fill the level map (an x,y array) with “rock” and then hollow out a bunch of random shapes (rooms) and then try to connect them all via semi-random paths (passages). A followup algorithm is used to check that all rooms are accessible from any point on the map. This approach is so random that you usually end up with two results. A) incredibly beautiful, visually appealing maps (5%) or B) a jumbled mess resembling spaghetti with doors. (95%) If you are designing the “caverns of chaotic doom” then perhaps this is the way for you.
The approach I took with HA! was a mixture of both. I fill the level with “rock” and then dig out a single room of random shape and size (within limits). Then, I store the coordinates of the first room, pick a direction that has lots of free space and place a second room, also of random shape and size. Once I have two rooms, I connect the second room back to the first in a fairly direct path (no diagonals). Now I place another random room (always checking for overlap) and then connect it back to the second room, etc etc etc. This ensures that all areas of the map are accessible from all other areas (if coded properly). If a passage runs into another passage before reaching it's destination room, it simply connects to the passage and stops. This is a simple approach that doesn't offer too many bells and whistles. The result often looks like this: http://www.mystictriad.com/dev/mapexample12.png or this http://www.mystictriad.com/dev/mapexample11.png Here's a big one that looks really cool: http://www.mystictriad.com/dev/mapexample20.png
The problems with this approach are many. For starters, the dungeons all look more or less the same. All the rooms are basically square or rectangular. Special rooms are extremely difficult to implement in this algorithm and debugging is a tedious nightmare that takes forever. There is no weighting to room placement and side by side rooms happen often with mixed results. I had to write a second routine to go through and scrub the map of extraneous doors and poorly placed room to hallway connections.
Attempt 3 still has the occasional disconnected cluster of rooms, which is an infrequent but serious bug. I know what's causing it, but it takes me over an hour to debug each level the generator creates. I'd rather write a new generator and use what I've learned so far.
The code for “attempt 3” is written in VB.NET 1.1 (2003) and is publicly available for download at www.heroicadventure.com. If you use it for anything interesting, let me know. If you fix it, then definitely let me know! :) Meanwhile I'm moving on to attempt 4.