DnD Dungeon Generation

By Sem Clous

Table of content

  1. Introduction
  2. Procedural Dungeon Generation
    1. Binary space partitioning (BSP)
    2. Random walk Algorithm
    3. Combining algorithms
  3. Object placement
    1. Doors
    2. Tables and other objects
  4. Result
  5. How to proceed and improve
  6. Sources

Introduction

In Dungeons & Dragons, dungeons, as the name implies, are a big part of gameplay. There are always dungeons involved in pre-written campaigns which are well structured and often involve some sort of fight. This fight is usually performed in a room that is slightly larger than the others. Additionally, various dungeon types exist, there are caves, castle dungeons, dwarven ruins etc., with the occasional combination of several types.
The goal of this project is to procedurally generate dungeons that can be used for custom Dungeons & Dragons campaigns. The dungeon should be generated with one of two types of rooms, cave, castle, or a combination of both. After this is accomplished the dungeon should be filled with objects, such as tables, chairs, cupboard, treasure and more.

This blog post will go over the process of developing a dungeon generator that can generate dungeons for a Dungeons and Dragons campaign. These dungeons should, of course, be tweaked, by hand and on paper, to fit whatever dungeon is desired by the players and should serve mostly as a solid base for a dungeon. Unless, of course, the players are entirely satisfied with the resulting dungeon which would be ideal.

Procedural Dungeon Generation

There are various algorithms that can be used to generate dungeons or rooms. There is Cellular Automata, which generates a large cave-like structure. Binary Space partitioning, which generates a more structured dungeon layout with rectangular rooms. The random walk algorithm which also generates cave-like rooms but also allows for corridors to be generated which allows for a more dungeon-like feeling as opposed to a large cave and many more. To generate two types of rooms at least two algorithms are likely required. As such the first step to take was looking into what algorithms would be best to use for this purpose. The first two that came up are Binary Space Partitioning, or BSP for short, and the Random walk algorithm.

Binary Space Partitioning (BSP)

Binary Space Partitioning is an algorithm that uses a bounding box, which is essentially a set of integers forming a box, to generate a set of rectangles in a random fashion. This is done by taking a random point on the box’s axes and creating a split there. This results in a new box, both of these boxes are saved to a list or, in our case, rooms. This is then performed for the newest box created in this manner until the declared minimum room size is reached. This means that the minimum room size set by a user affects the number of rooms that is generated, if the size is smaller more rooms are generated because it takes more iterations to reach the minimum size. This algorithm however, results in a series of rectangles which cannot be used to create a dungeon as these are bordering one another. To generate the actual rooms an offset is used, the actual rooms are then generated within each of the boxes’ bounds, a higher offset results in larger spaces between each room. An example of the generated rooms can be found below, notice the varying offsets and their result.

Random Walk Algorithm

The Random walk algorithm generates a series of random paths to create cave like structures. The algorithm takes a path length and a number of iterations where the path length dictates the length of each path generated per iteration. Meaning that a greater path length generally results in a larger room or dungeon depending on the number of iterations. If a small amount of iterations is used this merely results in a room that is less dense and has more gaps. One other thing that can be adjusted is the starting location of each path, this can be randomized or the same for each path. The former of the two, again, depending on the iterations, will result in a larger, more spread out room as each path starts at a random point on the existing paths. The latter will likely be smaller as it starts at the same location each time, this will result in a more dense construction. Below are a few example displaying this, From left to right: Long path length + medium iterations, Long path length + many iterations, Long path length + medium iterations + random starting location.

Random Walk algorithm

Combining Algorithms

Combining these algorithms could result in a nice mix of cave-like rooms and rectangular rooms which is one of the main goals of this project. This would be done by generating rooms using BSP and then taking the center of each of these rooms and generating a cave-like room starting from that location. This should only be done for a set number of rooms that meet certain requirements. The first and most simple version of combining these algorithms resulted in a BSP generated room layout filled entirely with cave-like rooms or alternatively, a random mix of rectangular and cave-like rooms.

Combining both algorithms randomly

This is not quite what was intended as most D&D dungeons are either a little more structured than this or more chaotic. The generated dungeons are a bit weird in that the cave-like rooms show some very straight edges, this is easily fixed by adjusting the path length and iterations of the random walk algorithm however. Additionally, there appears to be no structure in the mixed dungeon and most cave rooms in D&D are more akin to what a Cellular Automata algorithm might generate. A few examples of D&D dungeons are shown below.

Generating something similar to the image on the right would likely take a rather complex algorithm as a combination of square rooms is directly integrated into a cave structure. As such, to generate something that comes close to the goal for this project each room with only a single corridor connected to it will be marked as a potential cave room. This can be reasoned as someone digging a hole through the walls of an existing dungeon and stumbling on a cave room or perhaps digging out an entire secret room for themselves. The goal is to generate a BSP structure with only a small number of rooms generated as cave-like rooms, depending on the user’s inputs. This is done by finding each room that has only a single corridor connected to it and keeping it in a list. Each room in the list will then have a cave-like room generated at its center by the random walk algorithm. When generating this room, the generated room is checked to ensure it does not exceed the bounds of the BSP generated room. This will prevent the cave rooms from overlapping with neighboring rooms. The percentage of cave rooms and the number of connected corridors a room must have to be a candidate for a cave room can be easily adjusted.

Object Placement

As the main goal of the project was accomplished there was time left to add object placement to the generated dungeons starting with doors and later tables, chairs and other random objects often found in D&D dungeons. Most D&D dungeon generators do not generate objects with the dungeons, so there was no real reference material for this part of the project. Instead examples have been used from battle maps and other images of dungeons that have been filled with objects.

To allow for some customization the option to generate cluttered rooms is available which should result in a more abandoned or ruined look. If this option is not used the generated rooms will be organized, similar to the images above. Additionally, the percentage of objects can be adjusted to fit the user’s wishes.

Doors

To place the doors, the list of corridor locations is looped through to place doors at the start and end of each corridor. This list was made earlier to detect which rooms are only connected to a single corridor and is as such, easy to use for the doors. Seeing as a door can be placed in four orientations we must check several tiles around each of the corridor locations to confirm what orientation the door needs to have.

Tables and other objects

To place objects the user can set a percentage of rooms that they would like to have filled with objects. This currently works as follows: The percentage functions as a chance for a room to contain objects and the number of rooms that contain objects cannot exceed this percentage. E.g: if there are ten rooms in total and the percentage is set to seventy percent there cannot be more than seven rooms filled with objects. This means that there is a chance that there are less rooms filled than the given percentage but there can never be more. The objects were handled like this because implementing a proper limit would have taken a lot of work at the time. If it had been known before hand that this would pose a problem, the way rooms were created would have been adjust to accommodate for proper object placement.

To place the objects, tables are placed first in one of 6 possible locations which are picked randomly by grabbing a set of x and y values that combine to represent one of these locations. They are the upper left corner, central left and lower left corner of the room and the same for the right side of the room. This is done to make the table placement feel a bit more natural. The tables are placed first because the table locations are used to place the chairs afterwards. After the tables are placed the chair locations are determined, for now each location in all eight directions around the table is filled with a chair. So, when the tables have been placed and the chair locations have been determined all other objects are placed along the walls unless the “cluttered objects” boolean is set to true.

Getting potential object locations

Finally, the treasures are spawned in any room that is not already filled with objects. Depending on the percentage of filled rooms this results in only a handful of rooms, the user can then set the percentage of those rooms that is filled with treasure. These rooms are currently empty aside from the treasure as treasure rooms are often either trapped or defended by enemies in D&D dungeons. Again, this can be easily adjusted on paper after having generated the map.

Result

After implementing all of the above functioning the dungeon is decently customizable. The main options involve the dungeon density, size, room size, number of corridors connected to cave rooms, percentage of cave rooms, number of rooms that are filled, object percentage and treasure percentage. These dungeons should form a decent base for any dungeon master or D&D player to build a dungeon with, adjusting the map on paper where they desire.

How to Proceed and Improve

The way that objects are organized especially along the walls are far from what would be normally found in a dungeon in dungeons and dragons. To organize them properly more constraints should be added to ensure their placement resembles that of a proper dungeon. Furthermore, carpets and rugs and torches could be a nice addition to the rooms to make them feel less empty.
The orientation of the objects was also quite a hassle to properly set, as such, the sprites that were used or made were usable regardless of their orientation.
To further improve the project the way the number of filled rooms is handled should be adjusted to ensure they are always equal to the desired percentage. Additionally, doors are currently not quite perfect, this is especially visible in locations where a cave room was generated or where a corridor is adjacent to a room resulting in a series of doors in the incorrect orientation. To fix this, again, several additional constraints should be added to the door placement code.

Sources

Due to the nature of this project most of the described code was written by me. The tutorials used form the basis for this project, these implement the BSP and Random Walk algorithm and combine them, meaning each room is generated as a cave room as a result. I have then taken this code and adjusted it to fit the project resulting in the above.

Related Posts