Layout and graph generation

The goal for this week is to be able to generate a dungeon, with rooms and corridors, that has a sensible layout.

Firstly, I tried to generate a layout using Binary Space Partitioning(BSP). It creates a large cell, and splits this cell down into a tree-like structure, until a specific condition is met. In this case, the condition is cell size. If a cell is to small to be split, it stops. Eventually, this condition is met in all cells and the splitting stops in the entire tree, thus marking the end of the layout generation. The results is a layout with many smaller rooms, but a general lack of larger ones. This can be seen in the picture below. This isn’t a very good way of generating interesting layouts for the dungeon, so alterations are in order.
Layout tech test 1

Adding some additional conditions in the decision between vertical and horizontal splitting does improve the layout slightly, but it still feels out of place. Another issue that I have started to notice, is a clear pattern or repetition in the layouts. This can clearly be seen in the picture below. While the layout does not represent the final rooms that will be generated, I still feel the need to look into it. Optionally, I could go for another approach to generating the layout.
Layout tech test 2

Secondly, after the layout has been generated, we need to connect the individual layout cells to each other in order to create corridors. The are several ways to do this, the easiest being to use the existing structure of the BSP tree that was generated. The drawback to this is that the resulting node graph will be non-looping, meaning no matter what direction you take, you will find an end. It could be used directly to generate corridors, but it would not allow for further generation options.
Another option is to preform a polygonal edge-edge test between all the node cells. This will create large node graph of neighbors for each cell. This is however, a very CPU intensive algorithm, and does not scale well with larger amounts of cells. This due to the fact that all cells need to check all other cells. We could take advantage of the fact that the layout still has the BSP tree structure, but that is a future topic.
The resulting node graph from the edge testing is still not very usable to generate corridors. It would more or less connect all the rooms to each other, allowing the player easily traverse the map(see the picture below for a visual representation). The node graph needs to be trimmed into something more usable. Prim’s Algorithm is perfect for this, as it is a Minimum Spanning Tree(MST) algorithm. A MST is the graph that connects all the nodes with the lowest edge weights in a larger node graph(for more information, see http://en.wikipedia.org/wiki/Minimum_spanning_tree). The difference can be seen in the picture below. This new graph could now be used to generate corridors to connect the rooms and it would look OK.
Layout Tech Test 2

As you might have noticed in the picture above, the edge testing is not perfect. It is very picky that the edges must be a perfect match in order to be considered connecting. While not a problem due to the nature of the BSP tree generation, it does cause some unwanted behavior. A fix for this will be updated at a later time.

Leave a Reply

Your email address will not be published. Required fields are marked *