Procedural Dungeon Generator

Procedural Graphics Independent Study Completed Under Professor Adam Mally — Spring 2021

Unity, C#, HLSL

Overview

In my final semester of senior year, I undertook an Independent Study centered around the topic of procedural graphics. For this course, I completed multiple assignments in WebGL and Typescript, along with creating shaders in ShaderToy.

For the final project of this Independent Study, the subject matter was open ended. I was allowed to choose any procedural technique I was interested in and implement it in a project accompanied by a presentation.

I decided to create a Procedural Dungeon Generator in Unity using C#.

Process: Inspiration

To give a quick overview of this project, I was inspired by a video game from my childhood: Pokemon Mystery Dungeon! I liked how there are infinite dungeon possibilities. Creating a dungeon layout itself is a simple task, but they add on more aspects to the dungeons which make it unique and interesting. For example, there are some deadends in the dungeon layouts, enemies that follow you, pick up items, special tiles that can either help you or hinder you, and various dungeon themes. And by themes, I don’t just mean different artwork— I mean different dungeon layouts. I remember in some dungeons as you get further towards the boss battle at the end, the dungeons either get more sprawling or they even just get smaller and more ominous.

Scenes from Pokemon Mystery Dungeon: Blue Rescue Team

The method that I chose to use when generating dungeons is known as BSP trees, or binary space partitioning trees.

Process: Room and Corridor Generation

A BSP is made by recursively partitioning a space into two. In this case, we can consider our space to be our “dungeon grid” and we are constantly dividing it into sections to create containers for the rooms of our dungeons. The BSP Trees will be divided into containers, and each container has rooms. We want to use the rooms inside the leaves of each container as the rooms for our dungeon.

Slide describing room generation

After getting all the rooms, I wanted to connect them while making sure each room is reachable and there are no “islands” that are not reachable via corridors. To do so, I connected siblings in the BSP Tree to each other, and I also connected siblings to other siblings to make sure each room is accessible. I used the following two methods to actually connect rooms:

Methods for connecting sibling rooms

Process: Adding Noise

At this point, the dungeon rooms are just rectangles. To make them more organic looking, I wanted to add noise to them. First, I got the signed distance function (SDF) of each room. I applied Fractal Brownian Motion noise as I approached the external border of the box, and then I UV warped the pixels with another layer of FBM noise. These were the results:

Levels of noise in dungeon generation

I used tiles from a Pokemon game for the tile placement.

Process: Tool Overview

There are a variety of parameters that the user can change in the tool for various outputs.

Dungeon size
- This is the size of the root container for the dungeon. It is a square so this is the length of one of the sides of the square.
Iterations num
- How many iterations we will run the BSP Tree splitting algorithm for
Corridor thickness
- How thick should we render the corridors
Horizontal Split Threshold
- This denotes the probability of having horizontal and vertical splits during the container generation. If the horizontal split threshold is higher, there will be more horizontal container splits. If the threshold is lower, there will be more vertical container splits.
Split Factor Min / Max
- The split factor denotes how much space each container will be given when splitting into containers. For example, when we are finding points along the width and length of the parent container to split along, this split factor number will dictate the least amount of space we want to leave and the most amount of space we want to split along.
Room Width / Height Factor
- These sliders can be used to affect how big or small the width and height of the rooms that are generated will be
Noise Type
- There are three different types of noise which we went over in the room type section of this presentation. We can generate dungeons with different types of room noise.
Add Corridors
- Choose to add corridors or not-- this is mainly for debugging purposes and not for actual gameplay. Noise generation does not affect corridor generation.
Tile prefabs
- Users can input their own tile prefabs to be generated during gameplay.

Overview of the parameters in the Unity Editor for Dungeon Generator tool

Final Results

Because there is an aspect of randomness to generating these dungeons, if you hit the “generate dungeon” button on the same parameters, you will get different looking dungeons. Here are some examples with the parameters in the screenshot on the previous slide. The only thing I change here is the type of noise applied to each room.

Final results of Dungeon Generator tool

Future Work

In the future if I were to expand on this tool, I would fix a few things. For example, in my noisy dungeons, there are some little tiles that cannot be reached. I would clean up this excess noise before rendering to save time and memory. In addition, I would add more variety in dungeon types.

I would definitely want to implement some sort of gameplay aspect to it. I could add a player character which would actually be able to move about the dungeon. To do this, I would have to add some actual physics to the players as well as adding colliders to the dungeon walls and floor to make it physically walkable. I could add levels too.

For example, there should be stairs randomly generated in some dungeon away from where the player spawns so that the player tries to find those stairs to go to the next level. I could also add quests that you need to complete on each floor before being able to climb the stairs to the next level. Maybe the character needs to pick up x y and z items to go to the next level. More possibilities include special tiles that one could step on, such as a tile that when you step on it you get thrown to the side of the dungeon, or you drop all your items. After implementing these features, I could also add enemies spawning in dungeons that follow you based on some AI. This would involve creating a basic combat system as well, which could be interesting.

All of these gameplay aspects could contribute to creating some sort of storyline too.

Presentation

The presentation has notes detailing each slide. Here is a link to view it in Google Slides.