Procedural Dungeon Generation

Source code available here

I recently used three different techniques to generate dungeon structures. This was done as part of my final year project. All techniques were implemented with Unity and used a common procedure to produce a 3D representation of the dungeons. The full report I wrote to go with these generators can be found here

Cellular Automaton Generation

 Arguably not the best technique to use for dungeon generation, and much better suited for cavern generation, the results did give interesting shaped domains.

Binary Space Partitioning Generation

A much more common technique used to generate dungeons. Produces very uniformed shaped dungeons.

Delaunay Triangulation Generation

Based off the generation technique created by Phi Dinh for his game Tiny Keep. This techniques creates much less uniformed dungeons than the BSP technique and gives very appealing results. My implementation uses the incremental algorithm for constructing a Delaunay triangulation combined with the edge flipping technique.

Source code available here

Unity Dungeon Generator

Github Repository

This week I decided to take a little break from FlyBy and work on something  fun, so I decided to try and make a BSP Dungeon Generator in Unity.

To begin with I needed to create the Binary Tree that would store the space inside it. I decided to represent the space just using Unity’s primitive cubes. Splitting a BSP Node would take the cube it stored, break it in half randomly, and create two new cubes that would be stored as its left and right children nodes. After 5 splits of the tree it resulted in this:

The level split up into sections

Each color square is a leaf of the BSP Tree

With the level now partitioned it was time to start adding rooms to each section. I decided I would create a room prefab, and make several variations of it for each possible number of exits. Then when it came time to generate the connections between rooms just change the room to the correct prefab. So I created a prefab that looked like this:

A room with 4 exits

A room with 4 exits

Then it was a case of just randomly putting these into leaf nodes on the tree. Randomizing its position and size depending on the size of space that node was holding:

Stretched room prefabs

Stretched room prefabs

And doing this cause the prefabs to get horribly stretched, making the exits a non uniform size, and look like a complete mess. At this points I re-thought my plan and decided to store everything as tiles in a grid. this would mean that each room would be made out of lots of floor and wall tiles. Although significantly more expensive, it is a much more flexible approach. After making these changes I ended up with this:

Rooms now made out of tiles

Rooms now made out of tiles

Ah, that looks much better. Now to start connecting them. I decided to go with the most simple approach possible. To begin with I connect sibling rooms, these being rooms that share the same parent node in the BSP tree. To actually connect the rooms I created a ‘Digger’ class that would move from a start position towards a target position changing the tiles it touches into floor tiles, and surrounding the tiles it creates with walls, if those tiles are empty. The Diggers movement was a very naive ‘while My_x is less than Target_X, My_x ++’ sort of affair. Ideally I would like to go back and make the ‘Digger’ use a form of path-finding to find the shortest path avoiding other rooms and such, but that is a job for another day. The results of connecting siblings looks like this:

sc4

Siblings connected to each other

Not too bad, but we do get the unideal double connecting of rooms. I fix this by checking if nodes are already connected before connecting them. At this point it is just a matter of continuing traversing up the tree connecting the rooms with parents higher up the tree, until we are back at the root of the tree. At this point the dungeon should be fully connected! Lets have a look:

A fully connected dungeon!

A fully connected dungeon!

Top down view

Top down view

That doesn’t look too bad. At this point I decided to do a few iterations of a cellular automaton to ‘clean up’ the dungeon a little. This mainly removes corner pieces to make the dungeon feel more open and remove wall pieces that are sticking out awkwardly by themselves. I am pretty pleased with these results but there are plenty of improvements that could be made. If you are interested in the code for this project check out the Github Repository.

Github Repository