This ongoing project is to create a free, open-source Dungeon Generator for the Unity Engine. The original idea for this tool was for a game I wanted to make called 'OLOS,' or 'One Soul, One Life,' where the player would navigate a dungeon to escape with or without fragments of their soul. But before this could even be realized, I needed a way to generate dungeons to see how gameplay might work in the game. I have seen options for this in the Unity asset store. Still, I took it upon myself to create one from scratch to fit my needs precisely and others.

Planning Stage

Before starting, I knew I had to set up base goals to reach to consider the dungeon generator as a helpful tool off-bat. The necessities that the tool needed to have were:

1. Procedural unpredictable generation (from the player's perspective)

2. Connecting handcrafted rooms procedurally

3. Determining the furthest room from the "spawn room."

4. Easy expandability

These would be the stepping stones to creating a successful dungeon generator. A lot can and will be added in the future, but that is for me to figure out and incorporate.

Generating the Dungeon

Some other dungeon generation tools often generate the main path first, allowing the developer to know exactly how far the exit is from the spawn and enabling them to begin branching off it. While that method does work, it makes the dungeon generation process a little too "predictable." That is okay, especially since predictability is good during development; I wanted the generation process to be more random. For example, I like the player to experience various sizes and experiences of a generated dungeon rather than "the exit will always be 15 rooms away from the spawn". It allows players with a keen eye for detail to determine early in delving through the dungeon if they are going the right way. For example, if the player knows that the spawn-to-exit path is ten rooms, but there are 11 rooms, they could drop everything they do to change directions. I wanted to introduce more unpredictability, so I went a different way in generating a dungeon.

To give a brief overview of how generation works, the tool selects the spawn room and gets the list of "attachment points" (explained in more detail in the next section) of the room, and randomly decides to attach a wall or a doorway to that point. If a door is chosen, the tool randomly selects another room from the given room list. It again selects a random "attachment point" in the new room to attach the connecting doorway. The tool rotates the room to align the doorways and then does a check to see if the new room intersects any already existing rooms. If so, the tool chooses another "attachment point" in the new room different from the ones already attempted and then tries again. Suppose no "attachment points" are valid. In that case, currently, the room that would have a doorway added generates a wall instead. In the future, it will attempt to select a different room similar in "difficulty" until the tool exhausts its choices and creates a wall like before.

Each room goes through its list of attachment points until the Dungeon size is decided, which is the number of rooms allowed during generation time. This allows expanding branches to be generated naturally rather than forcing branching paths into existing paths. When a room is successfully created and validated, each room then adds itself to the dungeon room list.

Connecting handcrafted rooms procedurally

So this was a must-have for the tool; I wanted to have no grand restrictions on how and what types of rooms can and cannot be connected (at least for now, that is something I like to add as an option). I wanted each handcrafted room to connect seamlessly to another room with few setups, so I had to figure out a solution.

The solution I ended up going with is an "attachment point" system, allowing the developer to dictate where an "attachment," such as a door or a corresponding wall, will be generated inside a given room. The "attachment points" are the yellow diamonds in the image below.

This requires the developer to place each "attachment point" individually, as well as make sure that the "X-axis" of the attachment point (the blue arrow in the second photo) faces the interior of the room. The hole in the room's walls is where the doors/walls are planned to be filled. Because of this, the "attachments" must all be of the same footprint. I intend to add a way to allow developers to determine what types of doors can be connected to an attachment point, but that is not the goal for the moment.

This system allows the "attachment points" of a room to be on any axis, which means this system natively allows for staircases to lead to different floors, which is sometimes a pain point some systems may not allow. This also will enable rooms to be of any size or shape. If an "attachment point" has the same footprint, you can make huge rooms, hallways, T-junctions, etc.

Determining the furthest room from the "Spawn Room"

During the generation of the dungeon, the tool needs to know how far the furthest room is from the initial spawn point. This is because of the naturally branching nature of the generation. Because of this, a little more work must be done to figure this out.

When generating a new room, the room is given a "flood value." The "flood value" is an integer that contains the order in which the room was generated from the spawn room. The flood value of the newly generated room is the previous room's "flood value" + 1. This is nice since we now know each room's distance from the spawn, and we select the room with the highest number within the list.

Finding the Main Path

So, at this point, we have the entire list of rooms that the dungeon created and their distance from the spawn point. We must find the path leading back from the furthest point to determine our "main path." You might be tempted to sort the list from lowest to highest and then go down the list from there, but many rooms can have the same "flood value," and doing it like that doesn't work. Sometimes, our furthest path finishes generating early, and there might be branches that generate after that don't quite get as far, so we can't go by room age either. But we can use both in tandem to find our perfect solution.

To find the main path, we take the list of rooms as they were naturally generated and then see the room index with the most significant "flood value." We must keep the original assortment of the rooms the same since this will allow us to discard searching through any rooms after the furthest room index. Once we get that position, the tool adds it to a list for the main path. We then review the rest of the list, looking for the lower number. If the value of the room it checks is not the value we are looking for or a duplicate value already in the list, we skip it and keep going until we reach the end. It could be more straightforward, but how the path is generated one room at a time and added to the scene in unity allows this method to work flawlessly.

Example:

Here is a 15 room dungeon (not including spawn room) that has been generated.

In the first photo, you can see the different assigned flood values to each room as well as the path that the dungeon took to generate the dungeon. You can see that multiple rooms have the same "flood value" as well as the generation of the dungeon was not created quite in sequence, with paths branching off during creation without making a purpose built path initially.

If we take the "flood values" of each room and add them into a list that follows the generation of the dungeon, we get:

0,1, 2, 3, 4, 4, 4, 2, 3, 4, 5, 6, 7, 8, 5, 4

Looking at the list, we know the largest value is 8. So we can safely disregard the values of the room generated afterwards, leaving us with:

0,1, 2, 3, 4, 4, 4, 2, 3, 4, 5, 6, 7, 8

Then to find out the rest of the path, we go down the list removing any duplicate "flood values" while keeping the first instance of a new value that is one less than the previous value. That would look like (Bold being values we keep):

0,1, 2, 3, 4, 4, 4, 2, 3, 4, 5, 6, 7, 8 → 0, 1, 2, 3, 4, 5, 6, 7, 8

Now we have all the rooms with the correct "flood values" in order, that should equate to the main path. Lets take a look:

And that's it! We successfully have found the main path!

Future Plans

This is not yet done, I still have many planned features for the tool for more control over what rooms can connect to what, how many rooms of a certain type are allowed to generated, support for different door types/sizes, locked door and keys, etc. I think so far this is a good foundation for a more complex generation process.

Encountering Problems

There was a LOT of things I've learned throughout the process of making this tool. I don't have time currently to write it all down, but i soon will whenever I get the time to but I would love to talk if you want to know :)