Introduction. 1
The Progress. 2
Procedural Dungeon Generation. 3
Objects. 4
Results. 5
What the future holds. 6
Sources. 7

Introduction

For my R&D project I picked Procedural Generated Dungeon in the style of D&D. Dungeon & Dragons is something I enjoy with friends. This is the reason I thought it would be efficient if I could develop something for our sessions. A big part of D&D are the dungeon, this is where the fighting takes place, as stated in the name Dungeon and Dragons.

The dungeons in D&D differ a lot from each other. This is because the setting changes a ton. You can be in a cave where the rooms are more cave like or you can be in a house / castle where the rooms are more square like. The objects in a room differ from room to room. There can be enemies, loot, tables or different kind of structures.

During this project I will focus on developing procedural generated dungeon that differ from each other. There will be objects in them, like the loot and enemies these are in my opinion the most important of a D&D dungeon. There are some guys who have done this last semester, I want to differ myself from them. This means I will not use their algorithms in my final product. I try to find a new useful algorithm that can be implemented for D&D.

Some examples of D&D dungeons:

Figure 1 https://boingboing.net/2019/10/24/oleg-dolya.html

Figure 2 https://slyflourish.com/your_only_dungeon_map.html

Requirements

For my D&D based dungeon I want that the rooms can easily be regenerated and have rooms at very different locations. The rooms should have a certain meaning to them like figure 1. They don’t need to be filled with items because D&D is imagination based it only needs some little information like this is a room that contains enemies, this is a restroom, this is the sleeping corridor etc… The most important one is that there is a different in shape.

The Progress

At first I looked at the most common algorithms that gets used for dungeon generation. These were: Random Room Placement, Cellular Automata, BSP and Procedurally Build. Then I searched for how do D&D dungeons look like and what do they have in common. After that I simply made the dissension which one suits my case the most and I will follow up on that. The requirement that I use comes from playing the game itself and asking my Dungeon Master what he would have as a requirement. When the first test was finished a wasn’t satisfied with the outcome and needed to look at something else. With some searching I came across Delaunay Triangulation and that looked promising. This was my second and third test. The third test was promising however still not to my liking and I couldn’t change it a lot to suit my liking. So after 3 weeks of testing algorithms, I needed something new. A teacher of mine recommended to look up Wave function collapse. Wave function collapse happens to be the algorithm with the most leeway and customization. This is the algorithm that suits my case the most. It was the progress of elimination that effectually found the algorithm.

Procedural Dungeon Generation

To develop procedural generated dungeons there are a lot of algorithms that could suffice this. There is Random Room Placement, Cellular Automata, BSP Tree & Procedurally Build. Not every algorithm suits my case. That is why I will investigate them all and pick the one or two that suits my requirements. These are the most common once and later in the article there will be more that gets explained. (slsdo, 2011)

Random Room Placement:

one of the most simple and probably the most used dungeon algorithm. 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.

Afbeelding met zwart, roofvogel, wit, groep

Automatisch gegenereerde beschrijving

Cellular Automata:

Based on the cellular automata method by Jim Babcock, this algorithm uses cellular automation to create natural-looking caves. 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 neighbours were walls, or if it was not a wall and 5 or more neighbours were.

Afbeelding met shoji, betegeld, toilet

Automatisch gegenereerde beschrijving

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.

Procedurally Build:

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

From my experience and some examples I found, I think the best algorithms that suit my issue are Random Room Placement & BSP Tree. I don’t think Procedurally Build fits here because, D&D rooms don’t tend to have a “centre room”. These are the once I try at first after that I can always experiment. http://www.rombdn.com/blog/2018/01/12/random-dungeon-bsp-unity/

First try

At first I tried the BSP algorithm as you can see above. I tried to generate room and corridors using the BSP algorithm. I found an example where the picture below is linked to. However, BSP doesn’t suit my case the way I want it. It is to squarish. (Beaudon, 2018)

Afbeelding met tekst

Automatisch gegenereerde beschrijving

Figure 7 http://www.rombdn.com/blog/2018/01/12/random-dungeon-bsp-unity/

Second test:

With the first test I found that BSP isn’t really for me. I searched some more and found that tinykeep has a very cool algorithm that suits my case. I will try to recreate their algorithm. I will also make use of Delaunay triangulation.

For the second test I tried to find the algorithm that is used for Tinykeep. After a long search I finally found the algorithm that gets used and this will be the algorithm that I will use for my assignment.

As you can see does this algorithm spawn rooms from the centre and pushes them away like a separation. It essentially generates a ton of rooms where after the all are spawned it finds a couple of main rooms to get used. (Widdin, 2018) (vazgriz, 2019) (Adonaac, 2015)

Delaunay Triangulation

A Delaunay triangulation is a triangulation in which no vertex lies within the circumcircle of any triangle. The circumcircle of a triangle is simply the circle that passes through the three vertices of that triangle. At first it generates a triangulation, then it check to see if any vertices fall within the circumcircle of another triangle. If they do, it swaps the diagonal separating the two triangles. (Simpson, 2015) (Wikipedia, n.d.) (Wikipedia, 2022)

The process of a Delaunay triangulation

First, generate a triangle that encloses the entire domain to be triangulated. This triangle is called the supertriangle. For each point in the domain, add the point to the triangulation by subdividing the triangle containing that point. After that it will have a new node surrounded by three triangles, seen in green in the image on the right, and across the far edge of each new triangle is an opposing node, shown in red. For each new triangle created, if the opposing node for that triangle is not part of the supertriangle, it checks whether the opposing node is within the circumcircle of the new triangle. If it is, it swaps the diagonal separating the newly inserted node and the opposing node. In the picture, two diagonals need to be swapped.

Swapping the diagonal between two triangles gives two new triangles. Again, a circumcircle test is required for the new opposing nodes, and the process continues. until the circumcircle test is satisfied for all triangles connected to the recently inserted node.

The entire process then repeats until all nodes in the domain have been inserted and triangulated. The final step is to remove any triangles connected to the supertriangle vertices, leaving only the domain of interest.

When all the rooms are spawned it generates a Delaunay graph that together with a prims algorithm finds certain rooms and connects them. When these rooms are found the other rooms gets deleted and a note between them gets formed. As seen on the right.

Third test:

This test is uses the same algorithm as the second test. However this one is able to generate an image. (jongallant, 2017)

Code

With this piece of code I was able to add rooms to the dungeon. It first looks for one starting room and after that is found it assigns the other rooms to the dungeon. Because this algorithm has multiple connections, it has to be able to add a room to either a single connection or a double connection.

The algorithm makes use of a grid to place the rooms. So before it can add the rooms to the dungeon it has to be defined first so it actually exists. It also makes use of a Texture2D. This is was creates the image on the right on the first page of the third test. This is also the place where the different colours gets assigned so the difference can be found.

Fourth Test

Wave Function Collapse:

The algorithm takes in an archetypical input, and produces procedurally-generated outputs that look like it. (mxgmn, 2022) (Heaton, 2018)

Afbeelding met tekst, kruiswoordpuzzel

Automatisch gegenereerde beschrijving

In quantum mechanics, wave function collapse occurs when a wave function—initially in a superposition of several eigenstates—reduces to a single eigenstate due to interaction with the external world. This interaction is called an observation, and is the essence of a measurement in quantum mechanics, which connects the wave function with classical observables such as position and momentum. Collapse is one of the two processes by which quantum systems evolve in time; the other is the continuous evolution governed by the Schrödinger equation. Collapse is a black box for a thermodynamically irreversible interaction with a classical environment.

Calculations of quantum decoherence show that when a quantum system interacts with the environment, the superpositions apparently reduce to mixtures of classical alternatives. Significantly, the combined wave function of the system and environment continue to obey the Schrödinger equation throughout this apparent collapse.[4] More importantly, this is not enough to explain actual wave function collapse, as decoherence does not reduce it to a single eigenstate.

Historically, Werner Heisenberg was the first to use the idea of wave function reduction to explain quantum measurement. (Wikipedia, n.d.)

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 contraints that we specify, thus making it much more controllable than a lot of other procedural generation.

In WFC, the goal is to fill in a grid with tiles such that nearby tiles connect to each other. In the terminology we used above, 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.

Maxim discovered that with a reasonable choice of tiles, and a sensible randomization routine, it’s rarely necessary to backtrack so we can skip implementing that. That means that the WFC algorithm, at its most basic, looks like the following:

For each cell, create a boolean array representing the domain of that variable. The domain has one entry per tile, and they are all initialized to true. A tile is in the domain if that entry is true.

While there are still cells that have multiple items in the domain:

Pick a random cell using the “least entropy” heuristic.

Pick a random tile from that cell’s domain, and remove all other tiles from the domain.

Update the domains of other cells based on this new information, i.e. propagate cells. This needs to be done repeatedly as changes to those cells may have further implications.

WFC’s special approach to constraint solving is a process of elimination. Each grid location holds an array of booleans for what tiles it can and cannot be. During the observation phase, one tile is selected and given a single random solution from the remaining possibilities. This choice is then propagated throughout the grid, eliminating adjacent possibilities that don’t match the input model.

The final feature is backtracking. If an observation & propagation result in an unsolvable contradiction, they’re reverted and a different observation is attempted. (Parker, 2017)

With wave function collapse I am able to make my own input by placing tiles on the canvas and the algorithm generates a dungeon from it.

As you can see here in the editor all the tiles have been implemented and received a spot. If I wanted to have more tiles I could very easily add them.

As first the algorithm should be able to take an input and assign values to this input. After this there has to be a way to place these inputs by drawing it on a canvas. To make drawing easier there has to be a way to cycle trough the inputs. If the only way is to select the inputs it will take hours to make something happen.

When some stuff gets drawn it needs to fine its neighbours and figure out what needs to happen with them.

Besides being able to draw stuff their should also be a way to delete this and have everything restored to the original. When the input gets deleted by hand it will take a long time and it isn’t efficient.

It is helpful for the maker if he knows what buttons should be pressed to draw stuff on the canvas. So these different inputs should be defined and put in the inspector.

Results/ conclusion

My main objective was creating a D&D dungeon that uses a different algorithm then some previous students. During my research I can across some algorithms, some were useful and different and others weren’t. I have found an algorithm that differs from last semester students and that can definitely be applied for a D&D dungeon. It is called wave function collapse, the algorithm gets explained above. To simplify it, the algorithm takes an input as gets seen on the left side of the picture, it takes this input and collapse it in a bigger output. It mixes the input and places the tiles at random places. There has to been constrains to the input otherwise there are no rules for the output to follow.

Is this dungeon ready to get used for D&D? probably not. There are enemies in the dungeon as well as items and other loot. Most of the rooms are connected to each other however, they most of them are chunks they aren’t separated into smaller rooms which are also needed. So if the Dungeon Master can pick a pencil and “end” the rooms so they aren’t to big it probably can get used.

Afbeelding met tekst, scorebord

Automatisch gegenereerde beschrijving

What the future holds

The outcome isn’t perfect and it can’t currently be used for DND. However this is a new way to generate a DND dungeon. As you can see some corridors lead to nothing and some rooms are a little too big or just don’t end. It is possible to use flood fill and get rid of those lonesome corridors/ rooms. Also I couldn’t really find a way to specify the rooms. If I assign a different colour to it, it doesn’t get picked up and used properly. So this is also something the next person can look at. Lastly some DND rooms have height difference at the moment it isn’t possible to showcase that.