By Timo Titarsole

Table of contents

• 1 Introduction
• 2 Algorithms
  • 2.1 Random Room Placement
  • 2.2 Cellular Automata
  • 2.3 BSP Tree
  • 2.4 Procedurally Build
  • 2.5 Wave Function Collapse
  • 2.6 Delaunay Triangulation
  • 2.7 Which algorithm will I use?
• 3 Tests
  • 3.1 Criteria
  • 3.2 Test 1
  • 3.3 Test 2
  • 3.4 Test 3
  • 3.5 Test 4
  • 3.6 Results
• 4 Implementation
  • 4.1 Creating the 2d dungeon
  • 4.2 Converting to 3d
  • 4.3 Multiple floors
  • 4.4 Minimap
  • 4.5 Final Product
• 5 What the future holds
• Sources
• Picture Sources

1 Introduction

For my research I choose 3d dungeon generation, specifically something similar to enter the gungeon. I also wanted to have special rooms. The research is mainly focused on the result of the generation, so what the layout looks like.  I specificly want a room layout that is similar to enter the gungeon.

2 Algorithms

Here are some of the most commonly used algorithms for dungeon generation according to slsdo (n.d.).

2.1 Random Room Placement 

One of the most simple and probably the most used dungeon algorithms. This method places rooms randomly on the grid, then loops over each room and attempts to connect them. If given the chance, random tunnels can also be dug out to give the dungeon a more natural feel.

Different types of dungeons can be generated based on minimum and maximum room size and the number of rooms. The A* algorithm uses the Manhattan method to calculate its heuristics, and a Binary Heap is used to store the nodes.

2.2 Cellular Automata

Cellular automata is a model of a spatially distributed process that consists of an array (usually two-dimensional) of cells that “evolve” step-by-step according to the state of neighboring cells and certain rules that depend on the simulation. Usually cellular automation uses the 4-5 rule: a tile becomes a wall if it was a wall and 4 or more of its nine neighbors were walls, or if it was not a wall and 5 or more neighbors were.

2.3 BSP Tree

This is an algorithm that takes advantage of a tree data structure called BSP tree to make sure there are no overlapping rooms during dungeon generation.

1. Start with a rectangular dungeon.
2. Choose a random direction (horizontal or vertical) and location (x for vertical or y for horizontal).
3. Split the dungeon into two sub-dungeons using the parameters obtained in step 2.
4. Pick a random sub-rectangle and repeat step 2 for n iterations.
5. After n iterations, place random sized rooms in each of the rectangles.
6. Connect each room by looping through all the split rectangles and connect each split sub-regions.

2.4 Procedurally Build

Based on the method described by Mike Anderson, this is another fairly simple algorithm, and one that most resembles how an actual dungeon is built. The algorithm first generates a room in the center of the grid, then connects more rooms and corridors to the room and newly placed elements. In effect, the dungeon “grows” outward from the center room.

1. Fill the whole map with solid earth
2. Dig out a single room in the center of the map
3. Pick a wall of any room
4. Decide upon a new feature to build
5. See if there is room to add the new feature through the chosen wall
6. If yes, continue. If no, go back to step 3
7. Add the feature through the chosen wall
8. Go back to step 3, until the dungeon is complete

2.5 Wave Function Collapse

Here is an explanation of wave function collapse according to Boris (2021).

Wave function collapse is an algorithm developed by Maxim Gumin based on work by Paul Merrell for generating tile based images based off simple configuration or sample images.

Wave function collapse is a constraint problem with a twist – there are thousands of possible solutions. The idea is that if we make our guesses at random, instead of getting a solver, we get a generator. But that generator will still obey all the constraints that we specify, thus making it much more controllable than a lot of other procedural generation.

In wave function collapse, the goal is to fill in a grid with tiles such that nearby tiles connect to each other. Each tile is a different value, and each cell in the grid is a variable representing the choice of tile. And the rules about which tiles can be placed where are the constraints.

2.6 Delaunay Triangulation

Here is an explanation of Delaunay triangulation according to Adonaac (2015).

First the rooms get placed, this can be done with multiple methods.

The first method starts by trying to place randomly sized rooms at random locations on the grid. If an existing room would collide with the prospective room, the placement fails and the process repeats with a new randomly generated room. The number of placement attempts is predetermined.

The second method is more interesting. First you wanna generate some rooms with some width and height that are placed randomly inside a circle. A lot of rooms will be overlapping each other, so you want to separate them. After separating them you get the final room layout.

Once all the rooms have been placed, a Delaunay triangulation is performed using the center tile of each room as a vertex, creating a graph of all the rooms.

The Delaunay triangulation is then used to create a minimum spanning tree connecting all the rooms. To make the dungeon more interesting, some edges which were removed from the triangulation are re-added to the tree.

Finally, the A* pathfinding algorithm is used to create pathways between rooms which are connected in the modified tree.

2.7 Which algorithm will I use?

The only algorithm here that is not really applicable for my use case is cellular automata. 

Random room placement as described above is also not something I am interested in using, the way the rooms are connected does not look good to me.

Bsp is the algorithm I will try to implement first. It seems to be the most popular algorithm for dungeon generation. It is also relatively simple compared to the other algorithms.

Procedurally build also seems interesting to me, it grows more outward from a center room and that is something that I see other games do as well. The problem is that there are not always corridors between the rooms, so I am probably not going to implement this algorithm. 

Wave function collapse seems very cool but the results look a bit unnatural to me. The layouts of dungeons made with WFC that I have seens are not the type of layout I want my dungeons to have. You also don’t get a lot of control about the output.

Delaunay triangulation is the algorithm I am most interested in, but I will not be starting with this one because it seems more complex to implement than BSP.

3 Tests

3.1 Criteria

My test plan is as follows. I will try out BSP and Delaunay triangulation and try to find out if the algorithms would be useful for my use case. To determine the usefulness, i set a couple of criteria:

• The dungeon needs to have hallways between every room.
• The dungeon needs to have a room layout that looks similar to enter the gungeon. (just the placement of the rooms, not the hallways)
• The algorithm has to be easily converted to 3d.
• The algorithm should have a lot of customizability.

3.2 Test 1

I followed a tutorial (Beaudon, 2018) to test bsp.

I was not happy with the results of this specific implementation of BSP. This dungeon layout looks too squarish.  There are hallways between every room but for some hallways I don’t think they look very good. I could convert the algorithm to 3d so that was not really a problem. BSP also has customizability.

I was hoping that BSP could have a different result if I tried another implementation, so I wanted to try following another BSP tutorial to see if I get different results.

3.3 Test 2

I followed another tutorial (Bladecast, n.d.) on BSP to see if I can get different results with a different implementation.

The results were pretty much the same. The layout is still too square and I just don’t think this type of layout looks good. In this test, the hallways look even worse than the last test. Like the last one, I could convert the algorithm to 3d so that was not really a problem. It also has customizability.

The good thing I found in both tests is that the dungeon is generated very quickly. You don’t have to wait for the dungeon to be made, the moment you click play the dungeon is already generated.

3.4 Test 3

For my third test, I wanted to try out Delaunay triangulation.

I followed a tutorial (Adonaac, 2015) and used parts of a github repo as base for this test (jongallant, n.d.).

The result looked much better compared to BSP, but it is much more complex than BSP.

The dungeon did not generate quickly, but I personally don’t mind that.

The room layout is a lot more like enter the gungeon, so it already looks much better than BSP. This algorithm did not give me a hallway between every room, and this is not what I wanted. I actually wouldn’t mind if it was less common, so I will try and fix that because I like the way this layout looks. This algorithm also has a lot of customizability. I also think that I will be able to convert this algorithm to 3d pretty easily.

3.5 Test 4

For my fourth test I decided to try and fix the lack of hallways between rooms.

This result is much better than the result of the third test. The layout is still good, but now there are more hallways. There is still a chance for rooms to not have a hallway in between them, but it is low enough for me to think it isn’t ugly. I actually like that there isn’t a hallway between rooms in some cases.

3.6 Results

In the end, both algorithms were customizable and easily converted to 3d.

Test 1 and 2 showed me that BSP is not what I was looking for. It had a layout that I did not like and the hallways in both tutorials did not look good. I could have improved them by using a different algorithm for the hallways, but that would still not fix the layout.

Test 3 showed me that Delaunay triangulation was what I was looking for, but it was not properly implemented yet. There was a lack of hallways, and that didn’t look very good.

Test 4 had the result that I was looking for and gave me something to build on for making a 3d dungeon.

4 Implementation

After the tests, I decided to make a 3d version of the dungeon from test 4.

4.1 Creating the 2d dungeon

First I generate some rooms that are placed randomly inside a circle. A lot of rooms will be overlapping each other, so they get separated by Unity physics. After separating I find the main rooms, these rooms are the rooms that are bigger than the average by a given value. After that I get the final room layout.

After that a Delaunay triangulation is performed using the center tile of each room as a vertex, creating a graph of all the rooms.

The Delaunay triangulation is then used to create a minimum spanning tree connecting all the rooms. To make the dungeon more interesting, some edges which were removed from the triangulation are re-added to the tree.

After that the connections get processed. This will check if they overlap with secondary rooms. If they overlap, the secondary room becomes enabled and will become part of the hallway.

After the rooms are generated, the room layout gets converted to a grid. It will also add padding for the walls. After that the hallways are generated, these hallways are made out of 2 straight lines.

After the previous steps are done, the walls are added to the dungeon. 

4.2 Converting to 3d

After I made the 2d dungeon, I wanted to convert it to 3d. To do this I took all the tiles in the 2d grid version and converted them to 3d objects. After everything is done, a ceiling gets added.

4.3 Multiple floors

To add multiple floors, I wanted to make a scriptable object that gives me the option to give every floor different values.

After that I made a script that instantiates dungeon generators based on the scriptable objects.

After that I turn off every floor that is not the current floor.

4.4 Minimap

To show the player where they are in the dungeon, I wanted to add a minimap

I made a canvas with a minimap on it. The minimap contains a background, map, and player dot. The player dot moves on top of the map to show the location of the player. 

4.5 Final Product

5 What the future holds

In the future I would like to use this dungeon generator in my own games, but for that to happen it will need to be improved more first.

The dungeon meshes are currently not optimized. The meshes already use static batching, but performance could be improved by a lot by combining meshes. I could also generate a single mesh for the walls and floors for every room, and then combine them.

There is also a problem with generating walls. Sometimes walls get generated in places where they shouldn’t be, this can block the path and make it impossible to finish the dungeon.

Sources

Adonaac, A. (2015, September 3). Procedural Dungeon Generation Algorithm. Game Developer. https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm

Beaudon, R. (2018, January 12). Random 2D dungeon generation in Unity using BSP (Binary Space Partitioning) trees – Romain Beaudon. http://www.rombdn.com/blog/2018/01/12/random-dungeon-bsp-unity/

Bladecast. (n.d.). How to procedurallygenerate a dungeon bsp method unity tilemap. Bladecast. Retrieved 7 November 2022, from https://bladecast.pro/unity-tutorial/how-to-procedurally-generate-a-dungeon-bsp-method-unity-tilemap

Boris. (2021, November 12). Wave Function Collapse Explained. BorisTheBrave.Com. https://www.boristhebrave.com/2020/04/13/wave-function-collapse-explained/

jongallant. (n.d.). GitHub – jongallant/DungeonGenerator: A dungeon generator for Unity. GitHub. Retrieved 7 November 2022, from https://github.com/jongallant/DungeonGenerator

slsdo. (n.d.). Procedural Dungeon Generator | Future Data Lab. Retrieved 6 November 2022, from https://slsdo.github.io/procedural-dungeon/

Picture Sources

Adonaac, A. (2015, September 3). Procedural Dungeon Generation Algorithm. Game Developer. Figure 7 retrieved from https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm

Heaton. (2018, December 17). The Wavefunction Collapse Algorithm explained very clearly. Robert Heaton. Figure 6 retrieved from https://robertheaton.com/2018/12/17/wavefunction-collapse-algorithm/

lsdo. (n.d.). Procedural Dungeon Generator | Future Data Lab. Figure 2 ,3, 4, and 5 retrieved from https://slsdo.github.io/procedural-dungeon/