Different Dungeon Generation Algorithms within one game
By Nino Keijser
Table of Contents
- 1. Introduction
- 2. Approach
- 3. Minor setback
- 4. Working on a new algorithm
- 5. The final result
- 6. What the future holds
- 7. References
Most of the time, games use a type of algorithm to generate a certain environment or level for the player to walk through. But that is almost always a single algorithm. For my project, I decided to make (a prototype of) a game where every next level is generated with a different algorithm. This way each level looks and feels completely different and creates a whole different experience per visited level.
2.1 Choosing Algorithms
For starters, I wanted to set out which algorithms I can use for generating dungeons and choose two or three of them. I started to orientate myself in the different algorithms that could be used for generating environments or moreover for generating dungeons. I started a few tutorials to see what was possible and in what kind of way I wanted to generate a dungeon. After a while, my eye fell on a certain algorithm called The Drunkard Walk, which I found already great only because of the name itself.
In the Drunkard Walk algorithm, an invisible ‘walker’ walks on a grid that is set beforehand. The dungeon then will be generated on the places the walker has been on the grid. The unique thing with this algorithm is that every direction the walker will walk towards is totally random, which means that the walker can pass the same tile(s) over and over, but could also create a massive single room. Because of this, I was already sold for a first algorithm. It was a really simple algorithm, but nonetheless felt unique and really took my interest to see how this would work in a dungeon generator.
After choosing my first algorithm, I decided to research different ways of generating dungeons by taking a couple of tutorials. This was mostly to see how to implement algorithms into Unity.
In between these tutorials, I made a small playable character to walk through my generated dungeons.
After I finished a couple of tutorials, I still wasn’t really sure how I could implement the Drunkard Walk into a Dungeon Generation, so I got the tip to look into tilemaps.
By using tiles as the building blocks of my dungeon generation, I could let the walker walk through the grid and mark every point it visits so that I can generate floor tiles on those points. Moreover, I could generate walls around the placed floor tiles to let a player walk through the generated dungeon. More of the development of this can be read in the next chapter.
After I finished the first generated dungeon, I began to orientate myself again to see what other algorithm(s) I could implement. Because the dungeon that I currently generate with the Drunkard Walk algorithm is tile-based, I needed another algorithm that could work in a similar way, or at least be able to generate dungeons with tiles.
After I searched a bit for algorithms that meet these criteria, I stumbled upon the Hunt-and-kill algorithm. This algorithm actually looks a bit like the Drunkard Walk algorithm, but with some differences.
This algorithm also has a walker that walks in random directions around the grid, like the Drunkard Walk algorithm does, but it will never walk over already visited points. Moreover, when this walker gets to a point that doesn’t have unvisited points on the grid (so when it becomes stuck on the grid), the walker will be ‘killed’. The algorithm will then search for an unvisited point in the grid, starting from the far upper left point and then following the points like a typewriter (following the points on the x-axis, going one down on the y-axis when it reached the end). This is repeated until the grid is full.
2.2 How the algorithms work
So let’s go more in-depth into how the algorithms work in my Unity project.
Drunkard Walk generator
As for the dungeon generation that uses the Drunkard Walk, I already explained a bit about it in the previous chapter, but now I will dive a bit deeper into the process.
So the Drunkard Walk algorithm works like this: It firstly starts with setting up a grid in the scene. This grid is actually an enum turned into a two-dimensional array, meaning that this array has two parameters.
These parameters are there to store the width and height of the grid. I set the grid to 30×30 tiles, but it can easily be adjusted. This will be followed by the setup method, which declares every point in the grid to be an empty spot. It also spawns a walker in the scene and sets its position and direction, sets the spawn point for the player, and sets the first location of the walker as a starting tile, so that a special starting point tile can be spawned later on. After this is done, the bigger method starts, which tracks every point that the walker is standing on, which then is changed from an empty tile into a floor tile. This method also lets the walker change its direction and take a step after this. Furthermore, it will keep it away from the border, so that it won’t walk out of the boundaries and create all sorts of errors. This will keep happening until it either reached the max tiles or went above the max set iterations (which is set by default on 100.000).
After all the floors are set, the generator will then loop through the entire grid and place walls around them, so that the player can’t walk into the abyss. The loop that does this checks for every floor tile in the scene if it has empty tiles as neighbours and changes those neighbours to wall tiles. To add some aesthetics to the dungeon, the generator will also check whether certain wall tiles have a floor tile under them and change them to a wall that has a bottom edge so that it creates a sort of feel of depth to the walls.
After this all has been set up, the generator will then loop through the grid again and spawn all the actual tiles as game objects on the corresponding tiles. This will be followed up by a couple more methods that spawn a player in the scene and set the exit tile the furthest away from the player’s start location as possible.
As I also have written already, the Hunt-and-Kill algorithm actually has a lot in common with the Drunkard Walk algorithm but distinguishes itself from it because of certain steps that it takes. By not letting the walker walk on already visited tiles, ‘killing’ the walker when it hasn’t an available tile around it to walk towards, and searching for a new empty spot, it actually becomes a sort of advanced version of the Drunkard Walk.
This is achieved by checking for every decided direction whether it is an empty spot. If it is an empty spot, it will redecide its choice of direction. This will continue until the walker walks to a tile where all of the cardinal directions (north, east, south, and west) are occupied by already visited tiles. If this is the case, the walker will ‘kill itself’ by setting its position to an empty tile in the far upper left part of the grid as possible. This process continues until either the set amount of tiles is met or when the max iterations count is reached.
3. Minor setback
I was rather happy with the result I reached with both of the algorithms. In the form where I defined my project at first, I wrote about generating a dungeon with a single algorithm. However, I got the idea later on of implementing multiple algorithms in one prototype to create a unique experience. This developed into the idea to have different levels which will have each a different algorithm that generates the environment.
The first dungeon was being generated with the Drunkard algorithm, which I gave a classic ‘stone bricks and slabs’ look to support the dungeon feeling.
The second dungeon that is generated when you enter the next level is generated by the Hunt-and-Kill algorithm. I gave it a more stone cave look because most of the generated levels had a cave-like look to me.
However, in the last two weeks of the project, I stumbled upon an issue that I couldn’t fix. When I started making the Hunt-and-Kill algorithm, I just duplicated my Drunkard Walk algorithm and started to reshape it into the Hunt-and-Kill algorithm, because the way the algorithms are working is so similar. This was easier said than done because this gave me more trouble than I thought. After trying a few different approaches (and even a clean retry on the code), I eventually managed to get to a point where levels were being generated like the one in the video above, but unfortunately, this wasn’t always the case. Some levels were generated in a way that the floor tiles that the player spawned on weren’t connected to the floor tiles that had an exit gate near them. This way, it was not possible to finish that level.
The issue with the algorithm mostly lay with the fact that the Hunt-and-Kill algorithm ‘hunts’ for a new position when it is stuck. This means that it will find a new location on the grid to walk further, which most of the time means that this new location is too far from the starting point to connect the start and exit tiles with walkable floor tiles.
This problem does have a couple of solutions available, but because I struggled too long with my problem there was too little time left to fix this problem. Furthermore, I was a bit afraid that I was going me it even worse if I went on trying to fix the issue any longer.
I did eventually come up with a mechanic that fixes the problem by making it possible for the player to literally delve their way from the starting tile to the obstructed exit tile. Whenever the player is close to a wall and presses the spacebar, the wall will be replaced by a floor tile and every empty tile around that floor tile with a wall tile.
While I thought that I was reshaping the problem into a solution by making a mechanic of it at first, I was just neglecting the problem and finding an easy way out of it. Because of that, I needed to work on this project for around two weeks extra. This is why I completely scrapped the Hunt-and-Kill algorithm and started to implement another algorithm.
4. Working on another algorithm
Because I didn’t want to repeat the issue that I got the first time with the Hunt-and-Kill algorithm, I decided to look for an algorithm that was almost completely the opposite of the Drunkard Walk algorithm.
I dived into a couple of different algorithms again and eventually stumbled upon a few algorithms that matched my requirements. Because I wanted to use an algorithm that worked a lot different than the Drunkard Walk algorithm, I was mostly looking for algorithms that had a form of ‘order’ in them, as opposed to the more ‘chaotic’ way the Drunkard Walk behaved.
I eventually chose to work with the Binary Space Partitioning algorithm (or BSP in short). This algorithm was actually the algorithm with the most order I could find to use for my dungeon generator. In short, the BSP algorithm divides the roster it can spawn the dungeon into a couple of rectangles. These rectangles then get divided again. After that, the algorithm randomly chooses which of the two of those split rectangles will be a room for the dungeon. Lastly, the algorithm will take all the room centers and draws corridors between them.
Instead of the spawning of prefabs that I used for the Drunkard walk, the BSP-generated dungeon is built with a tilemap in Unity.
With the BSP algorithm, which has a top-down-mansion-like output for the dungeon, I almost have the exact opposite of the Drunkard Walk, which has a top-down-cavern-like output.
5. The final result
After I implemented the BSP in my prototype, I finally had two different algorithms that successfully generate a different type of dungeon, which swaps when you go to the next level. Because both algorithms could make it a little bit difficult for the player to find the exit (the Drunkard walk dungeon being chaotically built and the BSP dungeon being too big sometimes), I decided to add a simple minimap in the top right corner, so that navigation is a bit easier. The minimap is actually a different camera that shows the dungeon from a point that is more zoomed out than the standard camera and projects it on a raw image.
In the video below, you can see the result of a dungeon generated by the Drunkard Walk algorithm:
As you can see, the Drunkard Walk algorithm creates a very chaotic dungeon where rooms and corridors are almost absent. Despite not creating very big dungeons, this algorithm still makes it hard to see spot the exit tile very quickly.
In the next video below, you can see the result of a dungeon generated with the BSP algorithm:
As you can see in this showcase, the dungeon generated with the BSP algorithm is far more ordered than the dungeon generated with the Drunkard Walk algorithm. This is because the BSP algorithm actually defines rooms and corridors, unlike the Drunkard Walk algorithm that just walks around and places tiles where it went.
As you can see in the code snippets above, this method defines the different rooms for the dungeon and divides them with a 50/50 percent chance.
After all the room locations are determined by the BSP algorithm, they are then collected in a script to actually make it able to draw them in the scene.
An interesting Class that I discovered during the development of this dungeon algorithm is the HashSet class. This HashSet Class works sort of the same as the Dictionary Class, but the difference is in the fact that HashSets don’t use a value for each key that they collect.
In the case of the room creation, I used the HashSet Class to collect floor, corridors and walls, which can then be easily recalled.
The room locations are actually determined by a smaller method that is shown below. This method checks every room in the list of rooms and gives them a location in the scene. This way, the tiles of the walls and floors can be drawn in the correct positions depending on the size of each room. An offset is also applied so that they can be tweaked in the inspector.
To draw the corridors between the rooms, the center of each room in the room list is collected with a foreach-loop. After that, the script searches for rooms that are neighbours of each other and collects their centers. When these are determined, the script draws a (as short as possible) line between the rooms via a method that has some similarities with the Drunkard Walk:
As you can see in the CreateRooms() method, I also used the room centers that are used for the corridors to also determine the start location of the player and the spawn location of the exit tile. The player is placed in the center of the first room that is added to the list of room centers. The exit tile is spawned in the last room of that list.
Simple Looting system
After I successfully finished both of the algorithms, there was still some time left so I decided to also implement a simple loot system in my dungeons.
I did this by implementing chests that spawn randomly in the dungeons, which the player can interact with. Depending on the outcome of the loot system, the player obtains a certain amount of points by opening one of the chests.
To do this, I made a small list of integers called table that decreases in size. In my case, it is 40, 30, 20, 10. However, this is tweakable into other numbers to the developer’s liking.
To rest of the script goes as follows: a method that I called LootChest() creates a random value between 0 and the sum of all the integers in the table list (in my case this is 100).
After this, it uses a for-loop to search through the separate integers in the list. It then checks if the random value is below the current integer in the table. If this is the case, it takes the location of the integer + 1 (because otherwise you sometimes get 0 points) and multiplies it with 10. The latter I chose because I rather want to see points tenfold than in single ones.
If the random value is higher than the current integer in the table, this integer gets subtracted from the random value. The method will then go to the next integer in the list and repeats the first step in the for-loop.
A picture of this method can be seen below:
With the loot system script working fine, I then made a chest game object that is being spawned in both the dungeons. Because both the dungeons are created with different algorithms, I needed to create different methods of spawning the chests in the dungeons.
The chests are spawned in the BSP dungeons by looping through the centers of the rooms. I then used a random value that determines whether a chest can be spawned in a certain room center. If this is the case, I used two other random values that give an offset to the chest spawn point, so that a chest never spawns in the same location as the exit tile or the player.
For the Drunkard Walk dungeons, I just loop through all the floor tiles and check how many walls are surrounding those tiles. If it is 2 (or something else, depending on what you set in the inspector) or more and not the same location as the starting point or the exit point, the script uses a random value that determines whether the chest can be spawned on that location. To make it even more tweakable, I made it possible to set a certain max of spawnable chests.
The final gameplay of my prototype game with both the dungeons and lootable chests in both of them can be watched below:
6. What the future holds
I’ve called this project a prototype a couple of times in this blog post because that is how I feel this game is: a prototype. For this project, I mostly focused on the algorithms and traversing between levels with different algorithms, but it is lacking other gameplay whatsoever. Furthermore, I described in my initial idea of the project that when I had time left at the end of the project, I also wanted to implement treasure chests scattered throughout the dungeon that the player can find, to encourage the player to explore the dungeons a bit more and let them have a sort of score system. While the player can successfully loot the chests and receives points for it, I still find it not fully done. The score resets every time the player goes to the next level and it misses some feedback to show what the player actually got out of the chest. If I plan on continuing with this project, this is certainly something I want to flesh out a bit more.
I had a lot of fun creating the procedurally generated levels and liked to think of new features that could be implemented into the game. This means that I surely have future plans to continue working on this prototype and actually make this a little game. What I still want to add for example are sound effects, enemies/hazards, and maybe even one or more extra algorithms to enrich the gameplay and exploration of the game even more.
Thanks a lot for reading my blog post!