Different Dungeon Generation Algorithms within one game

By Nino Keijser

Table of Contents

• Introduction
• Approach
  • Choosing Algorithms
• How the algorithms work
• The result
• What the future holds
• References

Introduction

Most of the time, games use a type of algorithm to generate a certain environment or level for the player to walk on. But, that is almost always a single algorithm. For my project, I decided to make (a prototype of) a game where the player walks through levels that are generated with a different algorithm for each new level. This way each level looks and feels completely different and creates a whole different experience per visited level.

Approach

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.

First algorithm

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 to 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.

Second algorithm

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 with 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.

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 start location as possible.

The Hunt-and-Kill algorithm

As I also have told 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 being 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 for 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.

The result

I am rather happy with the result I reached during these couple of weeks. 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 being generated by the Hunt-and-Kill algorithm. I gave it a more stone cave look because most generated levels looked like a cave to me.

However, there was a minor problem with this algorithm. I had a couple of problems during the way of building the algorithm. When I started making the 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.

So how did I’ve fixed this issue? Well, the problem lies 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 I figured that 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.

However, after a bit of brainstorming, I came up with an idea and actually reshaped the issue into a feature (sort of). I figured that I could make the biggest issue – the fact that the starting tile is obstructed and separated from the exit tile – a game feature by applying a new mechanic into these levels. Whenever the issue occurs when the player can’t reach the exit gate, it is made possible to actually dig a tunnel towards the other part of the level by pressing space when near a wall tile.

I gave every wall tile plus the player game object a trigger collider. The player script then checks whether the player collides with a wall tile. If this is the case, it returns the location of this wall to a function in the script of the Hunt-and-Kill algorithm and deactivates the wall game object. Normally, the wall game object is spawned on the location of the wall tile point that is saved in the grid. Therefore, by changing this wall tile to a floor tile on the grid, I can easily respawn a new floor game object where the player can walk on. After that, the function ‘CheckForNewWallPositions()’ is called that loops through all the tiles surrounding the newly placed floor tile. Whenever a tile is empty is neighbouring this floor tile, it is replaced by a wall tile and a wall game object is immediately spawned on that point. This makes it so that the player can mine its way towards the direction it is walking in.

This way, I tackled the issue by negating it and reshaping it into something I could use for the gameplay.

By adding all this into one prototype, I created diverse gameplay with two times more procedural fun with my generated dungeons!

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. But because I didn’t have enough time left I didn’t start on that.

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 sounds, loot systems, enemies/hazards, and (if I feel like it) maybe one or more extra algorithms to enrich the gameplay even more.

Thanks a lot for reading my blog post!

References

• http://pcg.wikidot.com/pcg-algorithm:dungeon-generation
• http://pcg.wikidot.com/pcg-algorithm:drunkard-walk
• https://en.wikipedia.org/wiki/Random_walk
• https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/
• https://www.gamedeveloper.com/design/procedural-vs-randomly-generated-content-in-game-design
• https://codereview.stackexchange.com/questions/127785/hunt-n-kill-algorithm
• https://weblog.jamisbuck.org/2011/1/24/maze-generation-hunt-and-kill-algorithm

Link to my GitHub:
https://github.com/Keijser99/2DLevelGeneration.git