HvA GPE Gamelab

2D Procedural Dungeon Generation

By Nicky Wu

  • Table of Contents
    • Introduction
    • 1.    Dungeon Generation Algorithms
      • 1.1 Binary Space Partition (BSP)
      • 1.2 Cellular Automata
      • 1.3 Drunken Walk
      • 1.4 Diffusion Limited Aggregation
      • 1.5 Flood Fill
        • 1.5.1 Depth First Search (DFS) and Broad First Search (BFS)
      • 1.6 Wave Collapse Function
      • 1.7 Delaunay Triangulation
      • 1.8 Minimal Spanning Tree
    • 2.    Testing and validation
      • 2.1 Choosing the right foundation
      • 2.2 Choosing PCG algorithms
        • 2.2.1 Drunken Walker
        • 2.2.2 Cellular Automata
        • 2.2.3 Diffusion Limited Aggregation
        • 2.2.4 Wave Collapse
    • 3.    Implementation
      • 3.1 Room Bounds
        • 3.1.1 Binary Space Partitioning
        • 3.1.2 Drunken Walk
        • 3.1.3 Cellular Automata
        • 3.1.4 Diffusion Limited Aggregation (By using a walker)
      • 3.2 Room Regions
        • 3.2.1 Detecting Regions
      • 3.3 Placing the walls
      • 3.4 Room Corridors
      • 3.5 Combining Algorithms
        • 3.5.1 Deducting floors
      • 3.6 Scriptable Objects
    • 4.    Conclusion
    • 5.    What the future holds

Introduction

During the first four weeks of the semester, we took a look at different kinds of topics in Game Development such as shaders, performance, Machine learning and procedural generated content.

At the end of the fourth week, I have decided I wanted to do something with PCG since it was the most interesting topic for me. I already wanted to do something with rooms being unique or have a different kind of layout to them and came up with the following idea:

“Creating dungeon rooms by using multiple PCG algorithms”

I find this idea quite interesting because a lot of PCG algorithms creates a certain pattern or something unique that only this algorithm can produce. By combining these, I think it might result to something more unique. For this R&D project, I have decided to focus on creating a dungeon by using PCG algorithms with an emphasis on unique room structure.

In this blog post I’ll talk about the dungeon algorithms I have looked at, which of the algorithms I used and how I implement it to my framework.

I have made two small sketches of how I want the level to look like and what the algorithms should output.

1. Dungeon Generation Algorithms

There are a lot of different kinds of procedurally content generation algorithms which are used in games. In this chapter I’ll explain how some of these popular algorithm works in a high-level context.  

1.1 Binary Space Partition (BSP)

This algorithm is very popular among the PCG games since it is easy to implement and understand. This algorithm sub-divides a (room) boundary until it reached its desired width and height. Then these boundaries will get added to a binary tree [See figure 1]. You can use this tree to connect every room and use the room boundaries for other purposes.

https://media.geeksforgeeks.org/wp-content/uploads/20200630014725/space.jpg
Figure 1: Binary Space Partitioning (GeeksforGeeks, 2020).

1.2 Cellular Automata

Another popular level generation algorithm is called Cellular Automata. This is an algorithm that uses the cells’ neighbors to determine the outcome after each iteration. The cells have two possible states; dead and alive. 

Figure 2: Cellular Automata Example (Celusniak, 2019)

These rules are defined in the algorithm and there are a lot of rule sets to use for this algorithm. One of the popular rule set is called ‘Conway’s Game of life’. This rule set creates cave-like levels which is perfect for a cave level.

The base cellular automata implementation can be summarized into these steps:

  • Fill the grid with noise (wall and floor tiles)
  • Place random open cells in the grid 
  • Use a rule set to determine the fate of the cell in the current generation
  • Get the next cell and repeat step 3 until desired output 

1.3 Drunken Walk

The drunken walk algorithm involves a walker who randomly choose one of the four direction (north/south/east/west) based on its current position to walk to. These walk points are saved in a list and are used to determine when the position of the grid is open or not. 

This algorithm is reliable to create levels because all the spaces are connected due to it being walked on once by the walker. You can add a fill percentage to the walker as well, to let it know how many spaces it still need to open in order to finish the generation.

This can be summarized into these steps:

  1. Fill the grid with walls (closed objects)
  2. Pick a start position for the walker
  3. Pick a random cardinal direction (north/south/west/east)
  4. Take a step in this direction and save this point
  5. Repeat from step 3 until the desired amount of opened cells is reached

This is the most basic form of the drunken walk, there are more complex and optimized algorithms based on the Drunken Walk algorithm to get different outputs and .

1.4 Diffusion Limited Aggregation

Despite its complex name, the algorithm is quite simple to understand. It makes use of random placed particles throughout the canvas and moves randomly.

 When a particle hits a floor or something that is defined as ‘open’, the position of that particle will be added to the floor. Then it repeats with all the other particles until it reached a certain fill percentage. There are a lot of ways to implement this and it will create different kinds of fractal patterns.

Diffusion-Limited Aggregation: A Real-Time Agent-Based Simulation - Wolfram Demonstrations Project
Figure 3: DLA simulation (Sayama, 2011)

In figure 3, you will see how these particles connect with each other in order to create a fractal pattern. The blue particles will move indefinitely until it hits one of the red particles. The red particles can be seen as the ‘floor’ or ‘open’ tile. 

The basic implementation can be summarized into these steps:

  1. Create a grid and spawn particles in the grid
  2. Make the particles move at random directions
  3. Convert some of the particles into floor tiles so they won’t move
  4. When a particle touches a floor tile, turn it into a floor tile
  5. Repeat step 4 until desired fill amount

1.5 Flood Fill

The Flood Fill algorithm is used to detect all the tiles that belongs to the current region. The region is based on where you start. You can compare it to the ‘paint bucket’ tool in any paint program. Where it will eventually iterate over all the cells in the region.

https://www.algorithm-archive.org/contents/flood_fill/res/example.png
Figure 4: Flood Fill Visual (Arcane Algorithm Archive, n.d.)

1.5.1 Depth First Search (DFS) and Broad First Search (BFS)

These methods of flood fills are used to change the way how the flood fill behaves. In the depth first search, the algorithm focuses first on getting towards the deepest part of the region. The broad first search is focusing on the surface, where its neighbors will get checked next iteration.

1.6 Wave Collapse Function

This algorithm makes use of the way the sprite is connected with other sprites. These are used to set the rules for what the algorithm can output for certain cells in the grid. 

The algorithm starts to put a random sprite in the grid and starts from there.  Based on the adjacent cells, the algorithm gets a list of possible sprites to put in the adjacent cell. This will get repeated until every cell has been drawn.

https://robertheaton.com/images/wfc-examples.png
Figure 5: Wave Collapse Examples (Heaton, 2018)

1.7 Delaunay Triangulation 

“By definition, a Delaunay triangulation is a triangulation in which no vertex lies within the circumcircle of any triangle.” (Simpson, 2015)

Delaunay triangulation is a mesh algorithm to connect vertices together and keep making triangles out of it by using its edges. Watson’s method is one of the more popular algorithms to implement this algorithm.

There are a lot of application for Delaunay triangulation despite it outputs a meshes. You can use it in a different context as well which doesn’t involve modeling.

1.8 Minimum Spanning Tree

A minimum spanning tree is useful to find the shortest path to connect all the vertices with each other. In game context, this tree can be used to find the shortest path to connect all the rooms with each other. The vertices can be seen as room centers instead. Delaunay Triangulation can be used in conjunction with the minimum spanning tree.

There are a lot of methods to implement this algorithm, one of the more popular algorithm is called Primm’s algorithm. 

https://miro.medium.com/max/451/1*-gNoEeTMGYnCG5SSLi1Wtg.png
Figure 6: Minimum Spanning Tree Visual (Chothe, 2021).

Primm’s algorithm

Primm’s algorithm starts with a vertex, then check its edges. It will then choose the edge with the lowest value. Then it will go to the next cell, the one that the chosen edge is connected to. All the vertex that has been visited will be put in a tree as well in case of a loop forming in the tree.

This method is also known to be greedy since it always try to choose the lowest value without considering the other vertices.

2. Testing and validation

2.1 Choosing the right foundation

I want to have a base project to work on; in order to implement the algorithms without having compatibility issues. I have searched around on the internet for a tutorial which also meets the following criteria:

  1. The framework contains two of more PCG algorithms that I have researched above
  2. The tutorial also looks back at previous code and refactor it
  3. Tutorial covers flexibility where users can simply play around with the framework without having the need to change tons of parameters
  4. Adding a new PCG algorithm should be fairly straightforward
  5. The framework makes use of a hashset to place the floors or walls etc

There were a lot of tutorials that makes use of a 2D array or a list and they don’t look back to refactor the code. These kinds of tutorials did not meet the criteria. I did found one tutorial series that fits the stated criteria which was the tutorial series from Sunny Valley (Sunny Valley Studio, 2020)

Despite the long tutorial, it did cover a lot of the topics that I want to learn about. One of the many things are scriptable objects. Which are used to save the parameters for the algorithm. These can be used to get good results quickly.

2.2 Choosing PCG algorithms

I want to have three algorithms which one can fit in each criteria:

  1. Algorithm outputs a cave-like room
  2. Algorithm outputs a pattern
  3. Algorithm outputs a chaotic/random room

All the algorithms should be customizable as well so it will be possible to influence the output.

I have tested the following algorithms:

  1. Drunken Walker
  2. Cellular Automata
  3. Diffusion Limited Aggregation

Go to the implementation chapter for more information on how I implemented these algorithms.

2.2.1 Drunken Walker

The drunken walker outputs a random room, without any constant pattern. Every time you run this algorithm, it will generate a different kind of room. This drunken walker can be expanded as well to create more random rooms. The problem is that you don’t have a lot of structural control to this algorithm which isn’t a big issue for me. It will output a different kind of room depending on the parameters you give to the algorithm. 

I have implemented this in the framework and it seems to be fit the third criteria.

2.2.2 Cellular Automata

This algorithm is pretty interesting, it outputs a different kind of room (structural wise) depending on the ruleset that it uses. It is very easy to just play around with the ruleset since it only uses its neighbors to determine the cells. There’s a different output depending on the ruleset that you use. I have implemented the conway’s game of life and the mazectric ruleset to see what they produce.

Figure 7: Cellular Automata Output (Mazectric)
Figure 8: Cellular Automata Output (Conway’s Game Of Life)

Conway’s ruleset seems to produce a more cave-like with corridors while the mazectric ruleset, creates a maze with very long hallways. I do think this should fit the first criteria and is very customizable. During the feedback session, I had feedback regarding that this algorithm doesn’t always make all tiles walkable so there’s a percentage of useless floor tiles.

2.2.3 Diffusion Limited Aggregation

The last algorithm that I have implemented is the diffusion limited aggregation algorithm. I have played around with this algorithm and it seems to keep some kind of pattern based on the method that give to the algorithm. This will fit the second criteria. I’m pretty sure I’ll find more ways to extend this algorithm to create more kinds of patterns.

2.2.4 Wave Collapse

For the wave collapse I have used an already existing project because it might be taking too much time for me to implement it in the current framework. I have used this project () to see what the wave collapse is producing.

Figure 9: Wave Collapse Simulator (Donald, n.d.)

I played around with the online project and it seems to be producing pretty good results but I don’t think I can make much use of this algorithm since it is really hard to control this algorithm. You only define the rules by saying how the sprite is connected with each other but at the end the algorithm chooses the sprite at random (based from a list of possible sprites). There’s not much customization there besides changing the input (sprites) and how they connect with each other.

3. Implementation

3.1 Room Bounds

In order to get the rooms with their own bounds, I have used binary space partitioning for it and converted it into an object. Then I have used a hashset to track what position within the bound should be a floor tile

3.1.1 Binary Space Partitioning

The binary space partitioning algorithm is used to get all the room bounds in the level and I don’t need the connections between the rooms so I only need a list and a queue to do this instead of a binary tree. 

These room bounds are used for the algorithms to create their room. Since I don’t need the connection between the rooms, I only used a queue and a list of room bounds to keep track of the algorithm.

First I start with one bound; this is the level bounds. Then I split this level bound into two smaller bounds. Every time a bound isn’t at the right size, it will split itself again until it reaches the right size. When it reaches the right size it will stop and add the bounds to the room list.

3.1.2 Drunken Walk

The way how I implemented this algorithm is by making using a walker and put it at a random spot in a grid filled with walls. But since I have my own algorithm to place walls, this is not needed so a Hashset which represents the floor tiles is enough for me.

I have added a walker who acts like a paint brush and will randomly move throughout the Hashset.

Figure 12: Drunken Walker Drawing

The walker it moves at random directions and save the positions that it has previously walked on. These spots are converted into floor tiles and saved in a Vector2int Hashset. This method will be called multiple times until it has opened a certain amount of tiles. 

The method accepts a start position and the walk length. The start position defines where the walker starts to walk. The walk length defines how many tiles the walker can open before it dies. You can call this method anywhere in the code and it only outputs a Vector2int Hashset.

3.1.3 Cellular Automata

In order to implement this algorithm, I started to add a way to add noise in the grid (Hashset) which fills the grid randomly with floor tiles. I have added the random starter cells (alive) around the center of the grid.

Then I iterate over the whole grid and used its neighbors and a ruleset to determine the fate of the cell. The cell can either die, live or reborn (alive again). I currently have implemented two rulesets; the Mazectric and the Conway’s Game Of Life.

I make use of the 8 directions to determine the neighbors of a cell. I iterate over two for-loops, one for I do a neighbor check via checking all the 8 directions of the current cell. Then I add them in a list and return this to the caller. All the neighbors should be within the grid’s boundaries so it won’t continue infinitely.

By using a switch to determine what ruleset I want to use. In this switch statement I check the cell’s neighbors and determine what the state of this cell is in the next iteration.

The maze ruleset makes use of the amount of neighbors that a cell has. The maze ruleset states that a cell survives when it has at least one or up to 5 neighbors. A cell will be alive when it has exactly three neighbors. This ruleset creates a maze with relatively short hallways, there’s also a modified version which makes long hallway. This ruleset is called ‘Mazectric’, the only difference is that cells will die if they have 5 neighbors. I wanted the maze to have longer hallways and thus is why I chose for this ruleset instead of the maze one.

I combined and simplified all the rules into two if statements; when there’s more than 4 neighbors, kill the cell and when it’s less the cell is alive.

3.1.4 Diffusion Limited Aggregation (By using a walker)

This implementation of DLA is based on bracket productions’ implementation (Bracket Productions. (n.d.). Where it is also using a walker to simulate as a ‘particle’.

The way I have implemented Diffusion Limited Aggregation is a bit different. The normal way of this would be to generate an amount of particles in the grid that randomly moves around the grid. When it hits a floor tile, then the particle will become a floor tile. Then you have to wait until a different particle hits a floor tile. 

The reason why I don’t think this will work that well is because not all the particles will hit a floor tile and you have to iterate over all of them. I don’t think this is performant enough which is why I strayed a bit away from the normal implementation. I do plan to test the performance in the future plans.

Figure 16: DLA Graph Visual

I started opening some random cells in the grid (depending on the method). In case of the center attraction, I open the cells that’s around the center of the boundary. I randomly open tiles if the center attractor is not the chosen method.

Instead of spawning hundreds of particles at once, I started to spawn a single walker, who walks towards a random floor tile. During it the walk cycle, the particle will ‘jitter’ which simulates the way how the particles are randomly moving in the grid but it still have a higher chance to head towards the right direction. This means that every walker will eventually hit a floor tile.

The spawn area of a walker is near the boundaries of the room, I also do a distance check if this spawn position is too close to a floor tile. The walker behavior is also called ‘Walking inward’. I also have implemented the central attractor and walking outward methods to this algorithm.

Central Attractor

This walker method involves a walker who is placed randomly in the room. This walker heads towards the center of the room (or one of the starting positions). Then when it hits the center tile (or any other open tile) it will open the previous tile. This modification creates a room with an open center.

Walking Outward

This is similar to the central attractor except it starts the walker at the center and is trying to walk to one of the wall boundaries. When it hits a wall, it destroys the wall and it repeats again until a certain amount of walls are broken.

3.2 Room Regions

During the feedback session, someone mentioned that some of the floor tiles aren’t reachable, making it useless. I received some feedback of how I can deal with this problem. One of the suggestions was to use the flood fill algorithm to detect the walkable tiles and then find a way to connect these not walkable tiles with the walkable tiles.

Not all floor tiles are walkable after the floor generation. This is where the flood fill algorithm comes in. This algorithm makes it possible to detect all the regions in the room and will assign the tiles accordingly. When a tile isn’t reachable from the main region, it will create a new region.

3.2.1 Detecting Regions

The way how I implement this is quite simple. I have used the flood fill algorithm for this. I start from a point and add the neighbors (four ordinal directions) to a queue to be checked in the next iteration. This will continue until all of the tile of that region has been added to the list.

Here I check for a starting point in the (new) region.

Now I put their neighbors in a queue to be checked if it belongs to the region.

When there are more tiles that are not reachable, I’ll manually add this tile back to the queue so it will start the flood fill all over again. This repeats until all tiles are added to their own regions.

https://cdn.discordapp.com/attachments/1016336564667814018/1032403047567085611/unknown.png

In order to turn these regions into a single region, I used a simple distance check between these two regions. The two closest coordinate will have a walker that walks from point A to point B in order to open these regions. It repeats this until there’s only one region left.

If you can look at image below, you will see a cell with an orange background, this means that this tile has been opened because of the walker. To make it less performant heavy, I limited this algorithm to a room instead of the whole level.

https://cdn.discordapp.com/attachments/1024650869200920576/1033123857210548316/unknown.png

3.3 Placing the walls

In order to place the walls, I iterate over all the floor tiles and check its neighbor. 

I check all the eight directions for the neighbors and when there’s no neighbor in that direction (an empty tile), a wall will be placed there. This will be done for the corridor floor tiles as well.

3.4 Room Corridors

I also wanted to connect the rooms by using corridors. The current implementation of this is by using a walker that goes from one room center to the other. All the tiles the walker has walked on, will be turned into corridor floor tiles. 

To make sure the walker doesn’t walk to the same room, I have created a list of rooms then choose a random index to start then check the shortest distance to the next room. After the walker has walked to that room center, I remove the previous room then the walker repeats with all the other rooms.

As you can see on the image above, there’s no way to know when the walker goes through a room, it will create a corridor that goes through the rooms. This is not a result that I want to see. I could used the connections that are created through the BSP algorithm but then I have a problem with the dungeon being too linear.

This could be fixed if I used the Delaunay Triangulation algorithm. Where I use the room center to connect with each other (I see it as a vertex). Then I can use the edges of the triangles to connect the rooms together. By creating a minimum spanning tree, I can get the shortest path to connect all the rooms. Then I can use the remaining edges to make loops in the dungeon so it won’t be linear. Unfortunately I did not have enough time to implement this.

I did manage to use a Delaunay Triangulation library and applied it to the framework. But since I don’t have a minimum spanning tree, I can’t really use it to draw the corridors.

3.5 Combining Algorithms

In order to combine the algorithms to create one room, I have used a hashset for it. A hashset is a unordered list data type where all the elements are unique. It makes use of a ‘hash’ value to determine when the element is unique or not. Since I just needed to combine the output of the algorithms, I merge them in a single hashset. I only have to make the algorithm output a hashset in order to make this work. The hashset will automatically know what floor tiles to add and what to ignore.

3.5.1 Deducting floors

One of the feedback that I have receive was that the rooms were sort of the same and suggested to use some of the algorithms to deduct the floor tiles instead. This was very interesting and creates even more interesting rooms. So to implement this, I just deducted the floor positions from the hashset instead of adding it to the hashset. Fortunately I do not have to worry about tiles being inaccessible because the flood fill algorithm will take care of that.

https://cdn.discordapp.com/attachments/1024650869200920576/1037869022915600504/unknown.png

3.6 Scriptable Objects

Since the base framework makes use of the scriptable objects to store parameters for the algorithms, I did the same with the other algorithms that I have implemented.

This is an example of how a scriptable object with parameters would look like.

I went a bit further and implement a way to put these parameters in a list. This is called an algorithm set which contains a list of these scriptable objects. You can add the algorithm sets to the room level parameter scriptable object which will be used for the dungeon generator. So if you want the dungeon generator to use multiple algorithm sets for the room generation, you can.

4. Conclusion

I have learned a lot during the past few weeks. I never thought there were this many algorithms in the procedural content generation topic. I kept hearing about cellular automata during my study but that’s pretty much all I know about PCG before I started with this semester.

Now that I have implemented some of the PCG algorithms, I have a much better understanding regarding how they work and when you should use it.

Unfortunately I did not reach my goal since it’s missing some of its key features. This will be explained further in the next chapter.

5. What the future holds

There’s a lot to improve on this project and there are missing features that are quite important to fix some of the problems.

At this moment I haven’t implemented the Minimum Spanning Tree and Delaunay triangulation, this is really unfortunate because I want to connect the rooms together by using the shortest route. Then I can use the other edges to make loops in the dungeon so it won’t be linear.

The room types are all the same except for the start and end rooms. There can be something added there to check whenever a room should be a different kind of room (like a treasure room).

The way how the walls are placed is static; you don’t really have any control over the kind of wall sprite you want to place there. So improvements can be made in that part of the algorithm.

The implementation of diffusion limited aggregation is still missing some of the features such as being able to mirror the other half.  

Flood fill takes a long time to complete, I should see if there’s a better way to detect these regions or optimize it further.

Bibliography 

Used Assets

Posted

in

by

Nicky Wu

Tags:

, , , ,

Comments

Leave a Reply

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