Lurking Behind dev log – Random dungeon generation #3

Since the last dev log update, I have moved one of the more extensive systems from the old Unity project – the random dungeon generator. Thinking back, I could have just faked the dungeon layout for the early stages of development, however, this seemed a perfect system to move, while waiting for Godot 4 to be released as I was expecting some significant improvements from this version, like 2D sphere casting, which I want to use for my dash ability. Furthermore, I still think that this system is dope as hell. So I bit the bullet and have been chipping away at it by going through my old code and seeing what can be moved.

While I did go through all of this code just recently, a lot of time has passed since the original creation of this system and I wasn’t smart enough back then to comment on the whys instead of the whats so certain sources of information or reasons why some magic numbers are the way they are, are kind of lost to the times.

Inspiration for this system came from seeing games like Binding of Issac (a game I draw a lot of inspiration from, even though I haven’t played it), Warframe or Phantasy Star Universe, where the dungeons are made out of presets, in which every room has set amount of entrances/exits and the unused ones are just made non-interactive. I disliked that. So making my dungeon without any blocked doors was one of the goals for this system. Every step within the process is almost its own subsystem, which helped to achieve the second goal: modularity. Meaning that I could tweak a specific part of the generation without affecting the others too much. The last goal was for the dungeon to spread out and not be linear.

So without further ado, let’s delve into the first pass of the dungeon generation.

Step 1 – Layout

The first step is quite easy: make a 2D bool array and use TRUE to represent every room within the dungeon. A very straightforward process. If I remember correctly, I used the formula mentioned in this video to calculate how much the dungeon spreads.

Step 2 – Connections

The second step is about determining how rooms are connected to each other. The general process was like this:

1. Start with an array created in the first step and make a second array in the same dimensions.
2. For every room in the layout array create a new instance of room connections in the connection array.
3. When creating the connection node, check if the neighbouring nodes have been created, if yes – use their data on whether or not to connect with the current node.
4. If there is no neighbour in the connections array, but there is one in the layout array – flip a coin to decide if the current room wants to connect with said neighbour.

And that’s basically it for the connection generation. I liked it this way since I think it leads to more interesting dungeons when compared to dungeons in which the room connects to every one of their neighbours. The connections array also determines which room exterior preset will be used. By “room exterior preset” I mean where the entrances/exits of the room will be. For the current setup I’ve made 15 presets of box-shaped rooms with entrances/exits. In the future I mean to change their size and just strip them down to show only the entrances/exits while also using different shapes for the room. Why? Because I sometimes like to hurt myself and I think this will lead to more exciting situations.

The smart cookies out there might have figured out a potential issue with all of this: what happens if due to randomization some rooms become isolated and inaccessible to the player? And I must say: you really are smart! Though doubtfully a cookie (though a snack nonetheless :P). These are, what I decided to call, islands and the way I solve them is described in the final step.

Step 3 – Islands

The final step serves several purposes: resolve islands and help make inform the gameplay. And the process looks something like this:

1. Using the connections array from the previous step, create a node graph.
2. Using the starting node (usually the center of the dungeon) as the goal and with the help of Dijkstra’s algorithm calculate how far every room is from the goal.
3. Every room that does not have a path – chuck it into a separate array.
4. After the initial pass is done – go through every unconnected room and try to get a path to other unconnected nodes. The groups of nodes that are connected to each other, but not the rest of the dungeon are the islands.
5. Go through every island and pick 2 random rooms within (or just one if the island is one room big) and find the nearest rooms that do not belong to the current island. Once found – connect them via portals. The reason why I pick two rooms is for the cases, where the boss enemy follows you into one of the islands instead of accepting your fate, you can slip away.
6. And finally, recalculate all of the distances from the nodes to the starting node while thinking with portals.

It was important to recalculate the distances for the gameplay. Now that we now know how far every room is we can put weaker enemies in the rooms that are closer to the starting point, while putting objectives further! But that’s a tale for another time!

Below is a collection of images (masterfully created in Paint) illustrating the process and showing the final result in the game!

The keen eyes ones will notice that some islands have wrong distances set to them. That is definitely not a feature or some super smart logic – just a bug, but after all this time I need something else to work on, so let’s say “tiny imperfections won’t stop me from making a masterpiece✨” 😎.

Even though I am quite happy witht the system, I sitll made mistakes and this isn’t as optimal as it could be, but it will be running only at the startup of the level so I didn’t have to prioritze the optimaztion as much.

Thanks for reading! See you next time!