PDGenerator

PDGenerator

Roughly 8 weeks ago, I started a project which seemed interesting and required some thinking. I purposely decided when I started that I didn’t want to lookup how to do something like this in an effort to see what I was capable of coming up with. I knew there would be problems which I had never tackled and it was a great experience to learn as I went, improving my abilities to solve these complex problems. What I created in this time was a thing I have decided to call PDGenerator. PDGenerator is a static API for creating procedurally generated dungeons in C++.

The approach I took for this was inspired by the dungeons created in Runescape for the skill Dungeoneering. In Runescape, they generate the dungeons in a very grid-like fashion.

A map of a Large dungeon in Runescape.
Image Courtesy of Zybez.net

Having played a lot of Runescape, it was easy for me to come up with some basic rules to use for the algorithms needed. I have put them in a bulleted form below.

  • A dungeon should always be a grid. The width and height of the grid don’t need to be the same.
  • Rooms can only connect in the 4 cardinal directions (North, East, South, West)
  • Every room should always be reachable from any other room (directly or indirectly).
  • The dungeon should always be fully solvable.

This of course doesn’t encompass the features I was looking to have, but they were guidelines to keep my end result focused and served as a baseline for testing as I progressed through the project. Since I was already basing the basic rules for the dungeon generation on Runescape, I decided to also base some of the features off of the game as well. In particular, the use of locked doors and keys where each door/key combination is unique. This made it tricky towards the end when I was generating keys for the doors, which I will go into more detail about later.

I would like to spend a little bit of time in this post to go over the various components of the generator and while this won’t encompass all the details, it will broadly go over the important parts. To start this off, I am providing two code snippets. The first snippet is the BuildDungParams structure which contains the information needed to create a dungeon. The second snippet is the BuildDungeon function in the API.

I will avoid mentioning the individual values in the BuildDungParams structure because I have them nicely commented to explain their functionality. This brings us to the BuildDungeon function which I have provided. Before we dig in too far, I would like to point out that I have some typedefs such as pd_dung_ptr and I will do my best to include these typedefs at the top of the code snippets when they are used in the code snippets. I will now breakdown this function into its parts and talk about each one in more detail. To make things easier to explain, I will be using a 5×5 (25 room) dungeon as an example throughout this process.

Random Seed

In the settings for the dungeon, you can specify whether or not to use a custom seed. This is to allow the user the flexibility of creating a dungeon using a specific seed or to do it truly randomly. The generator always makes sure to seed the rand function to avoid problems such as the user forgetting to.

Create Dungeon

This function is fairly simple so I won’t show a code snippet but i’ll briefly summarize it. It creates a dungeon of the width and height specified by the user. It then populates the dungeon with rooms based off this width and height. These rooms are based off the room settings provided by the user in variables such as RoomMinWidth and RoomWidth. If the min and max are different, it uses a range, adding some randomness to the room size. It returns the result of this process as a pd_dung_ptr. In the case of our 5×5 dungeon, we will be getting a dungeon with 25 rooms in a grid something along the lines of this.

1

Connect Dungeon

The goal of this function is to generate the connections for the dungeon. Up to this point, we only have a dungeon with rooms that are not connected to anything. This function takes in a dungeon and creates connections for the rooms. This will guarantee that every room is connected to at least 1 other room and that every room can reach any other room. I have provided pseudocode below due to the complexity of the implementation.

Given our 5×5 dungeon example, you could expect a connected dungeon to look something like this. In this particular case, I had a setting which was adding a few redundant connections during the algorithm to improve the connectivity of the dungeon.

2

Seed Dungeon

I created this function as a way to help ensure that a dungeon can have more connections than what the ConnectDungeon function gives. Since we are dealing with RNG, you never really know how it could end up. Worst case scenario, its just a really long winding hallway. This function calculates a number of connections to add (dungeon size * percent), picks a room, picks a random neighbor and adds a connection there if one doesn’t exist. You can also tell it to enforce the number it calculates to add which basically just means it will guarantee that many are made (unless you hit the max number of connections in the dungeon). If we were to seed our 5×5 dungeon example, we might now have a dungeon that looks something like this.

3

Create Locked Doors

This function is also fairly simple. It just gets a list of the connections, calculates how many locked doors to add (num connections * percent) and adds that many locked door to random connections. This function is always enforced, but like before, it will stop if it hits the max amount of locked doors. If we took our 5×5 dungeon example, we might see something like this.

4

Create Keys

This is either the first or second most complicated function for the generation. What made this tricky is ensuring that a dungeon is always fully solvable. I’m sure there are lots of great ways to do this, but I decided to take an approach similar to a flood fill algorithm. The goal is to get all accessible rooms from a starting point and pick a random room to spawn a key in. I have provided some pseudocode below. Just keep in mind that this leaves out some details.

If we were to visualize this with our 5×5 dungeon, you could expect something like this. In this particular case, the seed I was using didn’t do a great job of placing the keys. The algorithm also doesn’t discourage placing more than one key in a room which you could see as both good and bad. Regardless, this dungeon should be fully solvable and is ready to return to the user in the form of a pd_dung_ptr.

5

Notes

The dungeon itself tries to store the data as separately as possible. The goal is to keep things as decoupled as possible, making it easier to deal with the data. A dungeon stores an array of rooms. These rooms only know their grid position, if they are the start of the dungeon and what keys (if any) they have in them. If this were to be expanded further, they might also contain information such as what the room contains (such as items, monsters, the layout, etc).

The dungeon also stores the connections in an array. Connections just store which two rooms are connected and if that connection is locked. Because these are stored in an array, it means that finding a connection for a room could be time consuming. To counter this, the dungeon also has a lookup for connections. This lookup stores a reference to the indexes of all the connections a room has, making it quick and easy to grab a connection for a room. Since a connection also stores if it is locked (aka the locked door), I implemented a lookup for these locked doors which makes it quick and easy to find which connections are locked. Granted, this lookup wouldn’t do much if a large amount of connections were locked.

The dungeon also provides a ton of helper functions for accessing information that is stored. Anything from finding rooms, connections, locked doors, room floods and so forth.

The dungeon also has the ability to export itself to JSON. This was useful for debugging and also makes it a convenient way to export the important information in the case that you want to create your own storage objects for the data or want to save it to a file or even use it in an external application.

Reflection

Looking back on this project, I was able to accomplish a lot in the roughly 8 weeks I had. I also learned a lot about how to generate a good procedural dungeon (something that I think I was not able to accomplish). In particular, the way I did the generation made it difficult to intelligently layout a dungeon and if I were to change things, I would try to incorporate many of the things I did for generating a dungeon as part of the process of connecting rooms. There are a few other tricks like this that can help make a dungeon more interesting to traverse and explore. One thing I wish I had spent time on doing was incorporating dead ends to the dungeon. Currently, the only time there is a dead end is if the room connection algorithm got unlucky in the RNG and this doesn’t really count.