Procedurally Generated Dungeon

By Boyd van Nobelen



The dungeons from Enter the Gungeon and the Binding of Isaac have a particularly appealing appearance and atmosphere. For me, every level is a totally unique experience. There are various levels, and none of them are identical. This increases the game’s replay value, meaning I can play it over and over again. The rooms are both exciting and difficult for me. The various room types, including the boss rooms, enemy rooms, chest rooms and shop rooms are interesting. They each serve their own purpose, which is also something I will include. The objects in the room that serve as cover for projectiles is also something I want to incoorperate in this project.


The scope for this project will be about the generation of the dungeon, and not the gameplay aspects, such as combat or character progression. The dungeon will have items and enemies, but they are not interactable. However I still plan on taking gameplay aspects into account when designing the dungeon layout and content. This is because I think it is important to realize that the result should still be applicable a game that uses generated dungeons.


Binding of Isaac and Enter the Gungeon served as inspiration for my attempt to make a randomly generated dungeon. There will be boss rooms, battle rooms, chest rooms, shop rooms, and a spawn room. The layout of the dungeon itself will also be procedurally generated. The main goal of this project is to generate a dungeon where each dungeon is unique each time one is generated.


  • Room layout
    • Enemy room
    • Boss room
    • Shop room
    • Chest room
  • Physics based dungeon layout
  • Connecting the rooms
    • Delaunay triangulation
    • Minimum spanning tree
    • Grid
    • A* pathfinding
  • Conclusion

Room Layout

Enter the Gungeon and the Binding of Isaac each have a set of roomtypes with each room having their own unique functionaliy in the dungeon. So for my project I decided to include these types of rooms. These rooms include spawn rooms, chest rooms, shop rooms, boss rooms, and enemy rooms. I’ll describe how I created these rooms in this chapter and why I did them that way. I’ll also discuss the various things I’ve tried. Since the player is the only object in the spawn room, I won’t discuss the generation of this room.

Enemy room

I wanted to have some obstacles within the room where the player could hypothetically hide from enemies or bullets. To implement this I initially had the idea to implement cellular automata with the rules of game of life in a square room. Cellular automata combined with these rules make for some interesting shapes and it also looks somewhat natural. I read a blog about cellular automata (Shiffman, z.d.) and modified the rules to Conway’s game of life (Lipa, z.d.). However I quickly realised that the rooms were not traversable. To address this issue I modified the room to create a cross shape in the center of the room. This way the player could finish the room.

The room is now finishable. But I wasn’t happy with the result. You can clearly see that the rooms is split up in four parts, which makes it look less natural. Also the potential combat would be affected too much. With this layout the player will almost be forces to play in the center of the room, where there is barely any cover. The cover provided by the cellular automata leads to dead ends which is not optimal for the gameplay since the player could be cornered by enemies.

To improve the rooms design I did some more research and I stumbled on an algorithm called lazy flood fill. What this algorithm does is it starts on a specific tile. Then the algorithm recursively explores adjacent tiles to decide wether or not they should be filled in, using a chance value that gets smaller with each iteration. If the chance value is less than a random number between 1 and 100, the tile is not filled and that iteration of the algorithm stops. By using this random chance it can create natural looking patterns. This results in rooms layouts that feel more natural and less rigid. To implement this I watched a tutorial from Klayton Kowalski (2021) and modified some parts of the algorithm.

To make it look even more natural I added cellular on top of the lazy flood fill algorithm to make it more smooth.

The cellular smoothing function iterates through each tile and checks how many neighbouring tiles it has. For floortiles it checks the surrounding tiles and counts how many of them are empty tiles. If there are more than four empty tiles surrounding a floor tile, it will become empty.
I place the walls after I generated the layout. So after all the floor tiles are defined, each empty tile that has at least one surrounding floortile will become a walltile. Because the lazy flood fill may skip some tiles, there is a possibility that there are empty tiles in within the room that will be changed to walltiles. This can result in a single walltile in the room. So for empty tiles I want to check how many neighbouring tiles are floor tiles. If an empty tile is completely surrounded by floortiles, the empty tile becomes a floor tile. This will result in there not being single walltiles in the room, which removes the lone walls that make the room look less natural.
The resulting smoothed room layout will have fewer small isolated walls, and will have a more natural and continuous distribution of floor and empty tiles. This code uses the cellular automata rule of “life” where the state of a tile depends on its neighboring tiles.

Based on the images, it’s clear that the lazy flood fill algorithm, combined with cellular automata, can result in some very interesting and visually appealing room layouts. The rooms look natural, with irregular shapes and organic patterns. Also this way of generating rooms will sometimes result in there already being some obstacles, which was not intended but it is an positive side effect that can add to the challenge and replayability of the game.

As you can see in the following image, there are two types of decoration in Enter the Gungeon: decorations that are spawned near walls and decoration that is spawned near the center of the room. The Binding of Isaac also spawns in obstacles in their rooms

To achieve this, I iterated through each tile in the room and checked if it was near a wall or not. If the tile was near a wall, it had a chance to spawn in a decoration. On the other hand, if the tile was not near a wall, I set a different decoration tile and spawn-chance.
The decorations near the wall can be next to eachother, while the decorations that are not near walls are supposed to have some spacing between them. So for each decoration that is spawned, a 5×5 area around the decoration will be occupied. This will make sure that these decorations can’t be spawned directly next to eachother.

This addition to the room layout has resulted in more interesting and dynamic rooms, adding to the game’s overall immersion.

Then at last I added enemies in the room. To do this I made use of the poisson disc sampling algorithm. In broad terms this algorithm generates points in a way that no two points are too close to each other. In the context of spawning in enemies this means that they are not clustered, which would make the gameplay overwhelming or too difficult.

I followed a tutorial made by Sebastian Lague (2018) to implement this algorithm.

The GenerateSpawnPoints function first calculates the size of the cells in the grid based on the radius of the minimum distance between points. It then creates an empty grid and initializes a list of points and spawn points. The region’s center is first added to the list of spawn points in the function.
The code then starts a loop where a random spawn point is chosen from a list of spawn points. The direction and the distance between the minimum and maximum radius are then generated at random. By ensuring that the generated point is not too close to any other existing point in the list of points, or in the adjacent grid cells, the function determines whether the generated point is valid.
This is done by determining whether the candidate point is on a walkable tile, within the radius of an impassable item (which can block the player or spawn an enemy outside of the region), or inside the region size. If none of these apply, the function moves on to the next stage. Then, this program effectively searches for neighboring points using a grid approach. It determines which cell the candidate point is in and looks for any previously created points around that cell. Next, it determines the distance between each adjacent point and the candidate point. If any of those distances are less than the threshold, it returns false.
The function updates the grid by marking the appropriate cell with the index of the newly added point after determining whether the point is valid and adding it to the list of points. The list of spawn points also includes the newly formed point. The function discards the point and tries it again if it is invalid.
The function keeps going over the list of spawn points until the list is empty. The function then provides a list of enemy spawn points.

At last, to add a little bit more feel to the room I decided to spawn in floortiles that look broken. My idea behind this is that the enemies took over the dungeon and is now ruined. It can also have the player guessing what happened and think about possible stories of the dungeon. This adds to the overall look and feel of the dungeon.

When all of the algorithms are used together, the result is a procedurally generated room layout. The room layout is randomly generated each time the game is played, making each playthrough unique. The Poisson Disc Sampling algorithm is used to determine the placement of enemies, ensuring that they are spread out evenly and not too close to each other. Meanwhile, the decorations are spawned near the walls and the center of the room, but are kept a minimum distance apart to avoid crowding. The end result is a challenging and engaging battle room that is different every time the game is played.

Boss room

The boss rooms in Enter the Gungeon are very big with a boss in the middle. To make the boss room in my project exciting I took inspiration from Dark Souls 1. In Dark Souls there is a boss called Moonlight Butterfly. It is considered by many to be the easiest boss in the game. I think it is a good boss, just not for Dark Souls. It has an interesting moving pattern and looks cool. The player can’t hit it when it attacks. When the boss stops attacking, it positions itself in range for the player to hit it (Fextralife, 2018). To add my own spin to this, I decided to make the room into a big pitfall with four little islands where the player could stand. The boss in the room would do the same as the Moonlight Butterfly, it would attack when the boss is not hittable and when the attacks are done it would become hittable again. I will not actually make this boss functional. These are just the design choices that went in to making this room.

To generate the four islands I used the lazy flood fill algorithm. To connect all the rooms together I used Bresenham’s line algorithm (Flanagan, z.d.). It is a simple and efficient algorithm used to draw a line between two given points in a discrete grid system. The algorithm uses only integer arithmetic, making it fast and ideal for real-time applications.

The function creates a loop from 0 to the distance inclusive. For each iteration, it calculates a normalized value ‘t’ as a ratio of the current iteration ‘i’ to distance. This value ‘t’ is used to interpolate between the start and end x and y coordinates, and the resulting values are rounded to the nearest integer. The resulting position with the rounded x and y coordinates is added to the line List. At the end it returns a list of positions that indicate the positions of the bridge tiles.

The lazy flood fill algorithm used to generate the islands make it so that the islands are always somewhat different from one another. Bresenham’s line algorithm connects the islands which could create interesting boss mechanics if elaborated further.
Overall, while the boss room design may be simple, the use of these algorithms allows for a level of variability and potential for expansion that adds to the overall gameplay experience.

Shop room

In Enter the Gungeon and Binding of Isaac they have a shop room where the player can buy new upgrades. This room has a NPC who sells the upgrades. To add a room with a similar feel to it to my project I designed a room that features an NPC selling items. The central feature of this room is an NPC sitting next to a variety of items available for purchase. The room is designed to provide players with an opportunity to upgrade their equipment and enhance their gameplay experience. By adding special floor tiles and an NPC in the center of the room, the shop room becomes more engaging and immersive for the player. I also added some decorations near walls like in the battle room.

Chest room

The chest room is basically the same as the shop room but with some minor changes. There isn’t an NPC and there aren’t items the player can buy. The room consists of a chest and some decorations. To have a different feel in the chest room I added coins and candles as decoration to make the room feel like a treasure trove.

Physics based layout

To create a procedurally generated dungeon layout similar to Enter the Gungeon, I drew inspiration from an article by Adonaac (2015) and decided to use physics to generate the layout of the dungeon. By spawning all the rooms on top of each other and pushing them apart using physics. This can make the dungeon feel less predictable and more immersive. It provides players with new environments to explore each time they play. Additionally, it can assure that the player never sees the same layout twice, which will make the game replayable. With this strategy, I can arrange the rooms to be closely spaced apart so that the player doesn’t have to walk through a lengthy hallway to get to the next room. The player’s experience is streamlined as a result.

On my first iteration I spawned all the rooms in a small square. This resulted in the dungeon being very vertically oriented. This was due to the limitations of the Unity physics engine, which caused rooms to be pushed away from each other only in a horizontal or vertical direction when overlapping.

To fix the issue and create a more balanced dungeon layout, I decided to place the rooms in a horizontal strip instead of a square. This resulted in a more clustered and natural looking layout. Also, this change aligns with the tightly-clustered dungeon layouts in Enter the Gungeon.

One of problem I encountered when trying to let the rooms push eachother out was lag. I already generated the layout of the rooms at the start. Each tile in the scene had a boxcollider attached to it. Which resulted in a large number of calculations being done for every overlapping tile. The other problem was that when rooms overlapped, they would sometime stay overlapped. This was because the walls in the rooms already had boxcolliders. This meant the rooms couldn’t push eachother outwards and the rooms would get stuck and twitch inside eachother.

To fix these issues I decided to take a different approach. Instead of generating the layouts of all the rooms at the start, I put one boxcollider with the size of the room on each room at the start without generating the interior. This way all the tiles in the rooms that overlap with other tiles don’t need to get calculated, and only the boxcolliders of the room itself will be calculated. Once none of the rooms were colliding with each other, I generated the room layouts and removed the rigidbody and boxcollider from the room object. This approach resulted in faster and more efficient generation of the dungeon.

Connecting the rooms

The design of the rooms and the connections between them in a randomly generated dungeon are crucial for producing an exciting and engaging gameplay environment. The corridors between rooms must be as effective as possible, as well as simple to follow. Finding the quickest route between every room will help the player navigate through all the rooms more quickly.
In this chapter, I’ll go over the methods I used to connect the rooms together and why I used them.

Delaunay triangulation

Delaunay triangulation can be used to connect points. In the context of generating dungeons it is used to form the corridors in the dungeon that go from one room to another. It also guarantees that there are no overlapping corridors. Delaunay triangulation is based on a mathematical concept that maximizes the minimum angle between any two edges in a triangle. This helps give the dungeon a more natural feel. It works by calculating the circumcircle of each triangle and making sure that none of the other points are inside the circumcircle (Moussa, 2023).

How the algorithms works is it first makes a super triangle. A super triangle is a triangle which covers all the points given to the algorithm. It iteratively adds points to the triangulation by first determining the triangles that contain the point, removing those triangles and adding new triangles made by the point and edges of the deleted triangles.
At each step it checks whether the newly added triangles violate the rule that the circumcircle of the triangle contains any other points. If there is a point within the circumcircle, it removes the triangle and flips its edge until the rule is not violated anymore. Here you can see an example when an edge is flipped.

Delaunay Triangulation broken (z.d.)
Delaunay Triangulation ok (z.d.)

This cycle repeats until all the points are added in the triangulation and there are no violations of Delaunay properties present. Then the final step is to remove the supertriangle.

To implement this I utilized existing code (Bl4ckB0ne, z.d.) as a reference and made sure to thoroughly understand how the code works. I checked the code to make sure it worked and refactored where needed to have it work in my project. I want to acknowledge the authors of the code I used and give them credit for their work.

Minimum spanning tree

With all the rooms connected, I can calculate the minimum spanning tree. A minimum spanning tree is a subset of edges which together connect all connected nodes, while minimizing the total sum of weights on the edges (Numpy and Spicy Documentation, z.d.). In simpler terms a minimum spanning tree is a list of edges that are connected in a way that they are traversable in the most efficient way. In the context of dungeon generation this means that all the rooms are visitable and that the path to each room is as short as possible.

To make the minimum spanning tree I used Kruskal’s algorithm. The algorithm works by first sorting all the edges in the graph by weight, and then adds them to the minimum spanning tree as long as they don’t create a cycle. I watched a video by Wiliam Fiset (2017a) who explained how the algorithm works to implement this in my project. This algorithm also makes use of the union find algorithm for which I took inspiration from Tenn (z.d.) to implement it.

The function starts by sorting the edges by weight. Then it creates an array of subsets to keep track of the groups of vertices. Each subset has its own individual parent and starts at a rank of zero, this means the subsets has zero vertices in it. It then maps the vertices to the index in the Vertices list. Then it iterates through the sorted edges and checks if it would create a cycle. If it doesn’t create a cycle, the edge gets added in the minimum spanning tree.

To check if the edges would form a cycle I made a Find function which uses recursion to find the root of the vertice. The function uses recursion to find the root node of the subset that contains a vertex at index ‘i’. It also uses a technique called path compression. What this does is it sets the parent of each visited vertex directly to the root node during the recursion, so that the next time Find gets called it will have a shorter path to the root.

I created a Union function to combine the nodes. An array of subsets, together with an x and y value that indicate the vertex indices, are passed into this function. It recursively locates the vertices’ root nodes at the subsets’ x and y indices. If the two subsets have different root nodes, the function changes the parent of the smaller subset to be the root of the bigger subset. The parent of one of the subsets is updated, and its rank is increased, if both subsets have the same rank.

As you can see all the rooms are visitable, but this still isn’t what I want. In Enter the Gungeon and Binding of Isaac the rooms are interconnected. There isnt only one way to get to a specific room. To recreate this I added back some random edges from the Delaunay triangulation. To not have really long hallways I added a constraint on this, as such the long edges will not be added back to the minimum spanning tree. In Enter the Gungeon the hallways are never that long. This is because when the player has to walk in a boring corridor for a long time, it takes away from the immersion.


To create the paths that result from the previous algorithms, I need to know where in the world to spawn the corridors. I also need to know what tiles are traversable for the pathfinding algorithm. To achieve this I made a grid of nodes which represents the walkable and not-walkable tiles, and gives them a postion based on integers. I followed a tutorial from Sebastian Lague (2014a) to implement this.

This function creates the grid. It first calculates the position of the bottomleft corner of the grid. With this I can calculate the worldposition of each individual node, which I can later use to determine the position of the corridors. Then it checks if that position is on top of a floor, wall, or pitfall. This is useful because the pathfinding algorithm in the next chapter needs to known which tiles are walkable and which are not. It then assigns the tile type and the position to the node.

The second function I needed calculates the worldposition to a grid coordinate which is necessary for the pathfinding algorithm. I did this by converting the position into a percentage of how far along the grid it is. Then I clamped these values to always be between 0 and 1. This is because when an object is out of bounds, it will still return a percentage and not throw an error. I get the indices by multiplying the grid size by how far along the axis the worldposition is and round that to an int. I subtracted one from the grid size since arrays start at zero. At last I return the node on the grid that is on the worldposition given to the function.

The last function I need for the pathfinding algorithm is one that returns a list of neighbouring tiles. I decided to only return the neighbours on cardonal directions (up, down, left, right). If I chose to return all the neighbouring nodes, the path could go in diagonal ways. I don’t want this since in Enter the Gungeon the directions of corridors are only horizontal or vertical. Also when the corridors are diagonal, the player would have to navigate a one tile wide corridor, which isn’t optimal since the player would walk against the walls. I could fix this by having a wider corridor but this doesn’t look good in proportion to the size of the dungeon.

A* pathfinding

A* pathfinding is an algorithm that finds the shortest path between two positions. It does this by evaluating the costs of the nodes. The cost is based on the distance from the current node to the goal node called ‘gCost’ and and estimate of the remaining distance to the goal node called ‘hCost’. The total cost of the node is the sum of these two values and is called ‘fCost’ (Lague, 2014b).
There are several different pathfinding algorithms I could use. One reason I went with A* pathfinding is because it is faster when working in a large grid (Rachmawati & Gustin, 2020). This is good for when I would upscale the dungeon or if I want to make the rooms bigger. Another reason why I opted to using A* is because the algorithm takes into account both the distance to the goal node and the cost of the path so far, making it more optimal than the other available options.
To implement this I watched a video that explains how the algorithm works (Lague, 2014b) and read a blog post with an explanation and some pseudocode for the algorithm (Swift, 2017).

I first start a stopwatch to check how long each path takes to calculate. Then I use the NodeFromGridWorld function to get the nodes in the graph where the target and start node are. Then I define a list of nodes called openSet representing the nodes that are being considered for the path, and a hashset for the nodes that are already evaluated called closedSet. Then I add the starting node to the openSet list to start the pathfinding.

For the actual pathfinding itself the function start a loop that stops when there are no more nodes being evaluated or if the path has reached the goal node. In each iteration the algorithm takes the node from the openset with the lowest fCost. On the occasion that there are multiple nodes with the same fCost, it takes the node with the lowest hCost.
If the current node is the goal node I retrace the nodes in the path to a new path list and create the path with the CreateHallway function.
Otherwise it gets the neighbouring nodes of the current node. If the node is not walkable or if the neighbouring node is already evaluated, the for loop skips this neighbour. It then calculates the new fCost for the node. If the node is not in the open set, it gets added to it. If it is already in the open set the algorithm will determine wether the path to the neighbouring node from the current node is shorter. If that is the case, the costs and parent of the node will be updated and added to the openset.

The paths are found relatively quick. Sometimes a path can take longer to find. I think this is because of the added edges from the minimum spanning tree. The rooms all have 4 openings at the start and paths can not interect. So when a path already occupies an entrance and a new path tries to go in, the path takes a small detour to find the next opening of the room. Right now this is not anything to worry about but in the future this could lead to a longer search time.

At first I only had the floortiles spawn in on the paths. This felt boring and not pleasing to look at. To make the hallways more lively I added torches that spawn in each third tile.


One of my criteria was that each dungeon should feel unique. To accomplish this I set a minimum and maximum value for the room size, amount of enemy rooms and the amount of chest rooms. I also randomized the amount of random edges being added back into the minimum spanning tree. This way each dungeon layout will be different from one another.


Throughout this journey of generating a procedurally generated dungeon I learned alot. I learned about different algorithms and how to use them in code. Before this project I never understood how procedural generation works, and now I know alot more about it.

One if the goala I had was that each dungeon should be unique and different from one another. I think this goal is for the better part accomplished. There are just a few things I could improve on. Such as the tiles used for this project. The way the tiles are now makes the dungeon look too 2D. To improve this I could add a bit op depth in the tiles. This could be accomplished by using a tilemap with tile rules. The way I generate the rooms now is based on a 2d array of tiletypes where a gameobject is instantiated based on the tiletype.
I also only really used a couple types of tiles. To make the dungeon even more exciting I could add more tile sprites for different rooms to give each room a different look and feel.
To further improve this project I could add game functionality. This way I would be able to test if the dungeon is fun to play and gives a different experience with each dungeon.

Overall I am proud of the end result and upon reflection, I feel that this project has provided me with a lot of helpful knowledge and experience in game development. I have learnt more about procedural generation, but I have also learned more about the fundamentals of programming and how to solve problems. This project has forced me to think critically and creatively and has allowed me to put what I’ve learned into practice. I am eager to learn more about procedurally generated content and I will probably start my own personal project about this topic soon.


Adonaac, A. (2015, September 3). Procedural Dungeon Generation
. Game

Bl4ckb0ne. (z.d.). GitHub – bl4ckb0ne/delaunay-triangulation: C++
version the delaunay triangulation

Delaunay condition broken. (z.d.).

Delaunay condition ok. (z.d.). Wikipedia.

Fextralife. (2018, May 23). Moonlight Butterfly Boss Guide – Dark
Souls Remastered

Flanagan, C. (z.d.). The Bresenham Line-Drawing Algorithm.

Kowalski, K. (2021, February 13). Lazy Flood Fill | Procedural
Generation | Game Development Tutorial

Lipa, C. (z.d.). Conway’s Game of Life’.

Moussa, A. (2023, March 13). Delaunay Triangulation and Voronoi
. Gorilla

Numpy and Scipy Documentation  — SciPy v1.10.1 Manual.

Rachmawati, D., & Gustin, L. (2020). Analysis of Dijkstra’s Algorithm
and A* Algorithm in Shortest Path Problem. Journal of physics.

Sebastian Lague. (2014a, December 18). A* Pathfinding (E02: node

Sebastian Lague. (2014b, December 19). A* Pathfinding (E03:
algorithm implementation)

Sebastian Lague. (2018, November 23). [Unity] Procedural Object
Placement (E01: poisson disc sampling)

Shiffman, D. (z.d.). The Nature of Code.

Swift, N. (2017, May 28). Easy A* (star) Pathfinding – Medium.

Tenn, C. (z.d.). Algorithms: Union-Find in C#.


Gustavo Vituri (z.d.) – Tiny Ranc Asset Pack –

Krishna Palacia (2023, January 18) – MINIFANTASY DUNGEON –

Min (2017, February 18) – Roguelike CharEnemiesTiles –×8-rogue-like-charenemiestiles