Procedural Dungeons and Everything they have Taught Me

Anchor 1

When I mention I am interested in procedural dungeon generation other students in game tech will recommend this specific Youtube tutorial. I followed this tutorial for a project over break meant to teach myself Unreal Engine, and while it's useful as a stepping stone. It had some serious limitations for what I wanted to pull off.

The Problem with Procedural:

Pros of this system:

Winding halls
Multiple floors
Simple to implement

Cons of this system:

Lack of control over where things spawn
Limited to one doorway size to connect rooms
Cannot create or identify areas with greater importance
Spawns each room as an actor,
spawns rooms and then deletes them if there is overlap, leading to rapid and redundant spawning and despawning

Anchor 2

Alternative 1: Wave Function Collapse

Why Wave Function Collapse?

At this point, I was unsatisfied with the limitation of the room and doorway sizes. I wanted the dungeon to transition from tight structured hallways to larger scraggly caves. I learned about the Wave Function Collapse algorithm, and how it could make infinite randomized areas out of a tiny tile set by matching up compatible tile edges. I wouldn't need to limit myself to only one doorway size anymore! Rooms could take any shape or size.

The snag:

No resources on implementing a Wave Function Collapse algorithm used Unreal Engine's blueprints. I was new to programming, so this intimidated me. The most thorough implementation I could find online was written in Processing5.js, with which I was unfamiliar.

Example of a Wave Function Collapse dungeon floorplan and its tileset. Source from the official Wave Function Collapse Github Page.

Implementation:

This was my first Unreal project where I broke away from step-by-step Blueprint tutorials. Instead, I used Daniel Schiffman's P5.js Web Editor sketch and translated the logic into Blueprints. This exercise taught me twice as much as if I had found an Unreal resource in the first place. It tested my understanding of the logic behind what I was making and forced me to think deeper in my troubleshooting.

I recorded my failed debug trials to play back my print strings and pinpoint where things went wrong.

My first successful Trial! I started with just one tile flipped at different rotations to keep a constant path. Then, I introduced more complex tile combinations.

Debug Tools:

This generator did not work on its first nor thirtieth try. To aid in my troubleshooting, I set up colored debug tiles over each collapsible cell. These tiles indicate the number potential tiles a given cell could collapse into, with green being the lowest. The cell with the lowest number of potential options is the next chosen to collapse. A purple tile means the cell has been collapsed

All for Naught?

As proud as I was of myself for finally getting this generator to work, I quickly realized some glaring issues.

Including any kind of non-navigable tile would inevitably lead to disconnected un-navigable islands.
WFC works on a square grid, which results in a sudden and jarring map cut-off, instead of halls naturally branching and thinning out, like in the first method.

Alternative 2: The Tinykeep Method

I picked up this query again in the Spring.

I had done some research since winter break. I discovered a polular indie game dungeon generation method called the "TinyKeep Method" named after a game that used it. This method scatters rooms around a map using physics simulations, creates non-overlapping connections between these rooms using the Delauney Triangulation algorithm, then connects the rooms with corridors.

Gif showcasing the Tinykeep Method

Backwards introduction to Graph Theory:

Then, the developers mention, they are able to run Graph Traversals on the rooms to figure out which rooms are furthest from which other rooms, or which rooms have the most connections. I could use this to find the rooms furthest from the start and mark them as "treasure" rooms, then mark their connecting rooms as "guard" rooms. At this point, I was not sure entirely how all these complex triangulation calculations would result in a graph data structure, but I assumed it was all a necessary part of the process.

Good News:

I found a Tinykeep Method Unreal Engine sample project!

The Snag:

All of the logic was written in C++, which was new to me. I downloaded Visual Studio for the first time just to open the project files.

And So:

My experience translating the Wave Function Collapse algorithm from P5.js to Blueprints prepared me for this task. I was far less daunted attempting to crack the C++ logic.

Annotations:

I started by pinning screenshots of each of the Dungeon Generator's functions to a Miro board and annotating each of them until I knew exactly what they did. This quickly got me over my fear of C++.

Dev Logs:

I was working on this system as additional work to incorporate into my Game Tech classes, so I wrote additional dev logs for this stage of the project.

Dev Log 1: Goals and annotations

Dev Log 2: The Bower Watson Algorithm

Delauney Triangulation and the Bower Watson Algorithm:

After laying out each of my rooms, I needed to connect them to each other in a was where no connection intersects another. The problem was that all of my intersections were overlapping each other.

My first suspect was that my circumcircle calculation had been completely off. This was because, when I drew debugs for my circumcircles, they looked freakish. I checked my code off of other Bower-Watson implementations (My reference used a version specific to Cartesian coordinates). I checked my project off of other public blueprint projects that work with the algorithm, and only after confirming our functions were Identical did I deem the circumcircle innocent. I hadn't realized that for obtuse triangles, their circumcenter falls outside of the triangle.

Turning rooms into a fun dungeon:

Skip forward 3 weeks and everything works perfectly. I have even learned how to convert my disconnected room boxes into a dynamic mesh. Now, I want to be able to assign rooms a certain "type" based on their positioning. End rooms should be boss rooms. Boss rooms reward the player with access to key rooms. Players should always encounter a locked door first, then must branch and travel further to acquire their key. Here is a draw-over of my ideal dungeon transformation for this procedurally generated map.

At This Point I Learn What a Graph Is.

Once the dungeon's structure was complete and I could start assigning rooms, I was stuck. I thought at that point in the process I should just... Have a graph data structure delivered to me somehow in the output. I went back to the basics and learned how graphs are represented in code. I felt like a wizard, but I was watching intro to comp sci 101 Youtube videos. I attempted to handle our logic with an adjacency matrix over an adjacency list for about a day before I realized I was being silly. Finally, I could assign a start room (the one with the most connections) and use a Breadth First Search algorithm to find the boss room (The room furthest away).

I realize at this point I could have just made an adjacency list for the rooms in my first system back in winter and used it to calculate the importance or danger levels of each room. It would have solved all of my initial problems and I would have been satisfied. But now I am too far gone...

Alternative #3: The Gungeon Dungeon (Flow Charts)

Why Enter the Gungeon:

Enter the Gungeon is unique in its dungeon generation because it starts with pre-defined "Dungeon Flows": Charts that determine big-picture level progression. Then, the dungeon is generated spatially to fit a pre-determined graph.

I read This article that covers in broad terms Gungeon's dungeon generation process and became determined to create something similar.

Getting Stuck:

There was one problem. When Gungeon is ready to spatially generate a dungeon, it chops up it's graph into smaller chunks, severing looping and branching sections of the dungeon so it can generate them separately, then stitch them back together. This is because spawning rooms in a loop requires different logic from spawning them in a branch.

But I could not find a single resource anywhere on how to chop a graph into its component loop and branch pieces. The only solution to this algorithm I was aware of was buried inside the Gungeon code itself.

Code Decompiler:

Nothing has been more beneficial to my learning than looking through real game code using a code de-compiler. Intro classes and Youtube tutorials can only ever get me so far. Any time I watch a "quick and easy" tutorial, it always bugged me that I never knew whether what I was doing was what a "real" game developer would do. I used it to read through all of Gungeon's "Dungeonator" system and translate it to Blueprint.

A New Problem:

After a week, the dungeon generator could successfully generate separate pieces of a dungeon based on a pre-specified graph. It just couldn't put those pieces back together. Here, the dungeon generates all pieces of the graph on the left, but spawns them overlapping on top of each other.

The Looperator:

I planned to continue work on this system over the summer, but needed a final deliverable for my game tech class. I scoped down and focused on what worked, creating the "Looperator". Each level generates a new dungeon in a perfect loop. It chooses a start node, then, in a devious twist, places the exit in an adjacent room. The player must travel through the entire loop to reach the exit right next to their spawn.

Alternative #4: The Maw

"Maw Dungeon"

The Maw Dungeon iteration is the most personalized and extensive version of this dungeon generator so far. It was in development from the end of June to mid-summer 2025. It served as the basis of a dark fantasy dungeon crawler guinea-pig project (titled Maw) I led to learn about multiplayer systems and prepare for SCAD's 2025 multiplayer yearlong studio.

Things the dungeon could do at the beginning of Summer:

Spawn rooms based on an input simple graph.
Spawn rooms based on a looping graph.
Fill in additional rooms if a spawned loop cannot connect back to itself.
Split an input complex graph into component simple and looping graphs to be spawned.
Randomize the rooms spawned based on which exit points have connections to other rooms.

Things the dungeon could not yet do at the beginning of Summer:

Connect spawned component looping and simple graphs to each other.
Handle different room sizes.
Generate complex input graphs based on pre-fab layouts.
Scale in size over time algorithmically.
Handle lock-and-key generation
Spawn enemies or environmental hazards in specific rooms.

Visual Aids 1 day vs 3 weeks into development

Snapping Components:

Snapping component hallways together was deceptively difficult, and took three weeks to work reliably. Unreal actors act differently than Gungeon's Unity actors once spawned, so much of the code could not translate over. It was hard for five reasons.

1. The dungeon graph only kept track of which two rooms connected different components. It did not specify the orientation the rooms needed to connect in. (This is the mechanism that lets us achieve random layouts with identically structured flows). Because of this, the dungeon needed to test each viable connection between doorways on the internal node and connecting node and sort them into valid and invalid pairs. These tests would often go awry due to points 3 and 4.

2. Components needed to snap together in a specific order to minimize potential overlaps. This was done as a breadth-first search, with loops taking priority. Once a component is snapped to the main structure, all of its dependent components would snap next before their dependents would be able to snap.

3. Components did not exist as one actor that could be easily rotated, but multiple room actors. Each room needed to be individually offset and rotated independently.

4. Before room actors were spawned, the dungeon generator worked with data-only objects representing the rooms' positions in space. Those data objects also needed to correctly update their transforms and offsets.

5. Snapping many components often results in failure states. The generator needed several checkpoints it could "restart" the process from to attempt different room layouts. It needed to keep track of how many times it has failed at each stage and determine whether to restart the whole process from scratch, which is expensive.

Good news:

Once the snapping worked, working with the dungeons was a lot of fun.

3 Dungeons containing both loops and branches, spawned using the same graph data. Notice how they have the same number of rooms, and same number and size of chunked off looping sections. Only the orientation of the rooms is different.

Multiple Room Sizes:

Next I added the potential for the dungeon to randomly spawn rooms at different sizes. My first new size was a 2x1 unit room. Each new room size needs to adhere to the initial base size unit, so two 1x1 rooms could spawn flush with one 2x1 room and their doorways would still line up.

Before adding the 2x1 room, all rooms spawned from a designated starting root, jutting straight out. I refactored them to spawn at any initial orientation.

Unfolding the Dungeon: Combining generative grammars with pre-fab flow charts.

Maw's dungeon synthesizes Joris Dorman's generative grammar system with Enter the Gungeon's flow chart layout system. In Maw, the dungeon generates larger each new round. We can't solely rely on flow charts because flow charts are of a static size. We wanted to combine the control of large over-arcing flow control with incremental growth.

My solution was to handle the dungeon in layers of complexity. We could populate our dungeon with structured "sections" of 3 distinct sizes. A 40 room dungeon could be made out of one 30-room section and two more sections of 5 rooms.

A dungeon now generates like this:

Dungeon

=> Floors

=> Sections (5, 10, or 30 module flowcharts)

=> Modules (1-3 room clusters)

=> Rooms

Sections in practice: "section" flow charts available in a generation + their resulting dungeons.

Sections allow for fine-tune control over level progression while allowing maximum randomization within the set constraints.

Lock and Key generation:

One of my favorite parts of this iteration and my "sections" system was the ability to handle lock and key generation. I had enough control over how the dungeon would generate that I could guarantee a player will find a locked door first, then find a key to that door deeper into the dungeon. I could also guarantee these locked sections would be entirely optional and not obstruct the main path. I could then place a modifier on all rooms that start behind a locked door to contain more valuable treasure. I did all of these things.

Two section flow-charts that tag certain modules with "locked" or "key" .

A Generated dungeon containing both of these sections. The path is never obstructed.

I was able to hide the key to one door behind another locked door, but guarantee the player would see both locked doors before finding the key to the first door.

Enemy AI In the Dungeons

Two distinct Enemy Behaviors:

The Maw game had 2 enemy types: Greater Horrors and Lesser Horrors.

Greater Horrors acted as hazards, meant to be avoided. They:

Spawn at the beginning of the game, in the furthest spots away from the player start
May not spawn behind locked doors
Roam the entire length of the dungeons
Have a wide hearing range, and slowly move towards player noise (voice chat, attacks, running and jumping)
Only leave their patrol when attacking or chasing the players
Return to their patrol afterwards.

Fixing uninteresting free-roam behaviors:

When greater horrors free roamed, they:

Stayed in the same room for too long
Walked in circles
Positioned themselves facing walls or obstacles, not surveying their surroundings

To make enemy roaming behavior more engaging, I:

Researched games with similar enemy mechanics (R.E.P.O, Lethal Company)
Incorporated a designer-friendly "Roam-Point" system. Roam points are placed in each room and can...
- Return whether they are navigable or un-navigable, (for example, a roam point in a room behind a locked door, or a room that has flooded, would be un-navigable).
- Return how long a greater horror has been stationed at that roam point recently
- Return what room its positioned in
Programmed a "Roam Point Manager" that helps enemies determine where to patrol next. It
- Keeps track of how long an enemy has spent in a given room, and forces them to navigate elsewhere after a certain time
- Encourages the enemies to move into unexplored spaces, or spaces that have been freshly unlocked

Lethal Company's roam point system visualized

R.E.P.O's roam point system visualized

MAW's Roam point system visualized

Lesser Horror Flee Behavior:

Lesser Horrors are meant to be killed by the player. It would be frustrating if they kept attacking the player when they are hiding from the Greater Horror. To remedy this, Lesser horrors also flee and hide from Greater Horrors.

They must be quicker to notice greater horrors than the player, hiding if the greater horror is even just a room away.

Places to expand on the current system:

Fatal flaw of the current system (and its solutions)

Flaw:
- Dungeon complexity increases exponentially. Generation fails most of the time if it is attempting to place over 50 rooms.
Solutions:
- Break up dungeon generation into groups of 20-something rooms that generate in sequence.
- Rewrite generation to happen Asynchronously, off the game thread, in C++