The new dungeon generator is finished!

The majority of the work behind dungeon layout creation is finished, and I'm very happy with the results. In the future I'll be making things more interesting by adding lots of flavor to the rooms themselves, as well as some larger dungeon flavor features.

So for anybody who is interested, here's an overview of the algorithm I used:

1. Apply a template to the dungeon. This template can be chosen specifically, selected from a set of templates, or chosen completely at random - it's up to the Area definition file. This template marks the areas of the dungeon that will be left completely blank. For example, a template file for a big whole in the middle could look like this:


.......
.......
..xxx..
..xxx..
..xxx..
.......
.......




2. Next, a fully connected maze is generated, avoiding areas that have been marked by any templates. Here's a plain old maze and one after a cross shaped template was applied:








3. Rooms are then added to the maze. They can only start on even numbers and be of odd numbered size, and have a minimum dimension of 5. This all ensures that no matter where the room is placed, it will connect with the maze in some way. I'm currently just creating the rooms one at a time, checking random locations until I find a legal one. For now, I have 2 room styles - rectangles and circles - and the rectangles may have a random number of corners indented for flavor. Here is the normal maze with a high number of rooms placed on it followed by a different maze with only a few rooms:








4. Dead ends are removed, tunnels that only loop back into the same room are removed, and tunnels with kinks in them are attempted to be simplified. To reduce kinks I find and isolate each tunnel, creating a sequence from the start to the finish. I then check each point along the tunnel for any points further down the tunnel that are very close. If such a point is found, all the points between the two are deleted and a shortcut is carved out between them. The results are very obvious on sparser maps. Here are the final results of the cleanups of the dungeons generated above:











The concepts are quite simple. Implementing it took some time, but now that it's all working I can easily change how a particular dungeon looks simply by adding a new template, changing how many rooms get added, and even changing the density of the maze that gets generated. I may actually go into more detail on the template, because I came up with them, and I think they are actually quite flexible and easy to use.