In my last post about the topic of randomly generated dungeons I wrote about my first approach to reach the goal of nice looking levels. These levels contained rooms connected by a set of corridors using a perfect maze.
Main disadvantages of this method were the strong constrains on the shape of the rooms, big gaps between rooms and therefore long corridors and the unbounded calculation time. To overcome these issues I've revamped the whole generation process.
To provide a huge amount of flexibility and to not limit the shape of the rooms to anything I've divided the room placement step into two phases.
In the first phase the properties of all rooms of the dungeon get calculated. At the current state only one starting and one end room along with a couple of simple rectangular empty rooms are present but I plan to add a lot of different room types with different events (e.g. bossfights) to the game.
All these rooms are then put into the same location on a map.
Putting all the rooms into one place of course results in a huge amount of overlapping parts. To resolve this the algorithm in the second phase slightly moves every room iteratively a bit in the direction, in which the most intersections get solved. After a definitively finite amount of time all room-to-room collisions get resolved and I have a good disjunct room placement.
The space between rooms can even be specified by simply creating an imaginary border around the walls so that the virtual room size in the moving process is bigger than the actual room itself.
There are still some problems with this approach which still persist and need to be solved. One big issue is the so called granular convection which results in small rooms staying in the center while bigger rooms tend to move to the outer regions of the map. I have some ideas how to solve this but I still need to verify these and try things out.
For corridor creation I've come up with an algorithm which is a mixture of some sort of flood filling paired with randomness. After placing every room on a map, there are a couple of points corridors can attach to. Starting at one of those points, the underlying map grid gets filled remembering the source direction. Everytime the filling process reaches another attachment point, a corridor along the traveled path gets created.
To provide some kind of randomness and to not create only perfect short corridors, I use some weights to negatively manipulate the traversal.
Of course there are a lot more details in this algorithm but I don't know, whether you are interested in this. I don't want to bore you with that fine-grained stuff. Instead I'll show you some pictures of the resulting dungeons I took some months ago.
In this picture you can see some debug information of the generation process. The numbers represent the weights during the flood-fill algorithm. If you follow the weights in the corridors in descending order, you may find the room the algorithm started with. Sorry for the poor quality by the way.
This is a very large dungeon with 500 rooms of slightly varying sizes. There exists exactly one path from every room to every other room and the corridors are very short and straight.
In contrast to the previous picture this is a dungeon generated with complex corridors. The room placement is the same and there are still 500 rooms with exactly one path from one room to another. This layout is really for hardcore players only. :)
As always I am still not that happy with the generation. For now I think the quality of the resulting dungeons is good enough but I am pretty sure that I will rebuild the whole generator sometime. I still want more control over the corridors. I want to create loops, deadends and branching corridors and the current generator is not really capable of doing those things.
I already have an idea how to further improve the system and maybe there will be a "Dungeon generation #03" soon.
