Varied Dungeon Generation
By Robert Rijkmans
Dungeon generation is very interesting. One of my favorite Games in this category is Pokemon Mystery dungeon, but after playing it so much you will find some downsides. To me this is the relatively simple dungeon generation. Using a grid system the Dungeons have simple rooms with corridors, with the width of a single tile, connecting them. This is what motivated me to want to make more varied dungeons.
After doing research on Procedural Content Generation (PCG), my choice was to use Cellular Automata in this regard. Usually Cellular Automata is used to generate cave like environments, however you can manipulate this with the rules that are used for the algorithm. The result is the core of my dungeon generation.
Index
- Research on fun dungeons
- Algorithm decision
- Cellular Automata
- Rules
- Region Detection and extraction
- Map Creation
- Map Interpretation
- Event Placement
- Tile Placement
- Future
- Resources
Research on fun dungeons
My first task was to figure out what I could do to make a dungeon more fun. For this I looked at articles and videos on the matter, as well as these types of games I enjoy and what makes them fun.
One of the games I looked at is Spelunky. Spelunky is a roguelike 2D platformer with random generated levels. The levels are generated in a 4×4 grid and there is a critical path you can take to the end of the level. The interesting thing is that the level is half designed and half generated. This makes it that the game has a more curated experience.
What I find interesting is that the game can also include random events on each map. It’s not guaranteed to show up in a single run and this also gives a run a fresh feel when you encounter such an event. Another part of the game I enjoy is the secret paths throughout a run. Throughout the levels find items and use secret passes, that are always present in every run but random in placement, to get access to a level beyond the normal final boss of the run. The addition of this makes the game harder but allows you to get to the true ending of the game.
Another game as stated earlier is Pokemon Mystery Dungeon (PMD). This game is a turn based rpg dungeon crawler with randomized dungeons. What makes these dungeons fun is the strategic aspect to it. enemies in the dungeons can be just as strong as your character so you have to take advantage of your party members and items to get through a dungeon. The dungeons themself are never a straight path and most of the time there are multiple paths to the exit. In this game there are also a varied amount of event’s that you can encounter while dungeon crawling. These events can be beneficial or detrimental to you.
I looked at more but for the sake of not making this part too long, I’ve placed bullet points I took of my research at the end of this post.
In conclusion what i want from my dungeon generation is:
- having multiple paths you can take form the start
- having hallways that are not always a straight line to a room
- having a lock and key system
- hidden routes through a run
- having events in a map
And on the technical side:
- have a system that allows me to add or remove parts with relative ease.
- having an output that can be easily interpreted to a game.
- having the generation time be less then a second so it won’t interrupt gameplay during a level transition.
Algorithm decision
Next up was deciding what algorithm I wanted to use.
I found an algorithm called wave function collapse.
With it you can input for example a small texture and get a larger texture that resembles the structure of the input. Using this for dungeon generation could make different types of dungeons with only having to make a small input.
Next up was cellular automata.
Cellular automata is an algorithm that allows you to make cave-like structures. This makes it more limiting in what you can do with it, but it’s easier to implement and manipulate than the wave collapse function.
Binary space partitioning.
This algorithm can be used to make dungeons with a room structure and having paths connecting them. As I don’t want to have the straight paths, I could find another way to connect the rooms.
When I got the potential algorithms I started to look for tutorials on how to implement them. This could give me an impression on how long it would take to get started. During this I found a tutorial on cellular automata that gave me inspiration on what I wanted to do.
The tutorial on how to detect regions in the structure created by cellular automata.
With this I came to an idea on how I could use cellular automata to make a dungeon you could normally not get. By detecting regions and turning it into a single part, I could combine multiple parts to create a dungeon. This is why I chose Cellular Automata.
Cellular Automata
Now that I decided to use cellular automata, I started working on it. With the help of a tutorial I got a basic result you get from the algorithm.
To get this result there are a few steps. using a 2D integer array (int[,]) and randomly placing 1 or 0 in the array. I will be referring to a position in the array as a cell from now on. After filling the array you can apply rules to each cell based on the state of cells around it. With each iteration you get a different result. In the picture below you can see how it progresses.
As I want smaller regions to extract it started playing with the settings I had. By increasing the amount of black cells the overall areas get smaller. Also by playing with the cell rules I got more interesting looking areas
In order to have areas to place I need to first have them as separate arrays for ease of use. To accomplish this I use the following code to loop through an area and create an extra int[,] of to fit it.
When this was done all I had to do was make it a function that returns a list of the regions. This code is also where I build on in my pathfinding.
Map Creation
Pathfinding
To create a level I want to connect the areas I have together. To do this I wanted to know where would be a good point in the area to connect to another part. For this I need pathfinding.
In terms of pathfinding there are 2 main choices I had, A* and Dijkstra. A* is a depth first algorithm and is faster. Dijkstra is breadth first and slower.
As I don’t have specific points to pathfind to, Dijkstra allows me to find these points.
In my implementation of dijkstra, I don’t check diagonally as I don’t want to pass through walls diagonally and include an area I cannot get to. This in turn simplifies the implementation of the algorithm. Since I only have to look at the direct neighbors, checking for the distance traveled is a simple matter. A diagonal space will always have the distance of horizontal + vertical movement. Therefore there is no constant need to look at all possible paths that are faster, as they are constant.
The downside of this is that it’s not usable for actual pathfinding for Ai enemies during playtime. So for this I would likely have to use A*
In the picture above you can see the dijkstra map of an area. The numbers represent the distance from the starting point beginning at 1. The red areas are the endpoints where I want to connect other parts to. To find these, take the cells that don’t have any other cells next to them to look at and save them in a list. Then after all cells are looked at I go through the saved cells and look around them horizontally and diagonally. When there are cells with the same or higher value around them, then those cells do the same. In the end the only cells that are left are the cells at the end (the red cells).
When the boolean is false it means the point it’s looking at is an end point.
Part Placement
Now that I have endpoints I want to have them sorted in corners. This will make it easier to decide what points to connect. The corners are: Top-left, Top-Right, Bottom-Left and Bottom-Right. The reason for this is that it’s easier to categorize this way. Checking if it’s over or under half of the x and y axis is easier and more flexible to do than going strictly Up,Down, Left and Right. With this I can look for points to connect to in a certain category, as seen in the picture below.
Doing this the way I envisioned was a nightmare and to get it working properly It would take more time than I had.
This map is not what I wanted. It Always has a similar structure to having a diagonal layout with some rooms not even connected. This is likely the cause of how I calculate the offset of parts. After trying to fix it I made so many adjustments that I lost sight of what function did what and decided to remake the map combiner anew.
This time deciding to make it simpler, I place the center of each part on top of each other and move them to the direction I want until they don’t overlap anymore. This results in a more consistently square map.
This feels somewhat better. Now I decide what parts are placed where by an int[,] with the index value of the parts from a list. By doing this it was also easier to keep track of the offsets for each part as I could also store them in a similar sized array.
Working out from the middle I could calculate the offset from the previous part. Still running it multiple times felt a bit of the same. So I tried to randomize the part placement. And it this Did not change much.
The problem was that I always started in the middle and went from top to bottom and left to right. So in order to change that I randomized where in the array I start instead of just the middle. I also randomized what direction would go first. and that resulted in this.
This was more like what I wanted. After testing a couple of times I was satisfied enough with this map. there was some overlap with other parts.
But looking at the maps it doesn’t seem like much of a problem and the overlap is unlikely to overlap more than 1/3rd of the other part.
Filling The Map
Now I have a map, but nothing in it. So next up i’m gonna fill in the map. First, I want to figure out how to do this. There are 2 options I could think of:
- Selecting a random location and adding an event to it.
For this I would first need to look for empty spaces and randomly select 1 or more of them. I would also have to make sure that that space wouldn’t be selected again.
- Select a map part before placing it.
To do this I could set the entire area to an event then place the map and have an area designated this way. For this I would also have to prevent the area from being selected again.
I decided on the 2nd one. Setting a part as an event is much easier as I already know what part goes where. This allows me also to easily make sure some events don’t get too close to each other.
In the picture below you see colored areas. The green area is the starting zone, the others are events that could be anything I implement. The colors are linked to the value the tile has. In this case 0 is a wall, 1 is an empty tile, 2 is the starting zone, ect.
Some areas get put on top of existing ones but that is not that much of a problem. I can have the detailed event be in a place that doesn’t overlap.
Next I want to add an endPoint of the map. This is quite easy as I already have a pathfinding algorithm that does this. I don’t use it anymore for the parts so I can use it here to find a point for the exit. I want this exit to be a lock and key so I will put a key somewhere. For this I have to make another variant that finds a location further away from the exit. I don’t want the key to be next to the lock so this variant has a minimum distance for the key to be placed. It also has a Maximum distance so if no point falls below the minimum distance the key will be placed at the furthest point.
Now the last step is defining the events. To keep it simple I reduced the number of events to 3. The purple area will have enemies sitting around, the red area will have treasure chests and the brown area will have a boss.
As it turns out I still need to go through all the areas because of the overlapping parts. So I use a variant of the region detection algorithm to get the final areas of the map. Then I put them through another algorithm and set the event area to the map.
When the tiles get placed I can use these points to place enemies and chests on those tiles.
Actual tile placement
Now that the Generation is finally done it’s time to create a playable map. I’m using 2D sprites for this. Using 2D makes it easier to go for the top down view. I also want to make it look like the map is a little tilted from the top. Doing this can decrease the amount of sprites necessary and the amount of pirates placed, resulting in less visual clutter.
I go through the int[,] map from bottom to top and left to right. I can use this to have a wall sprite after an empty wall. and a black sprite if it’s after a wall sprite and before a new empty tile. I can leave out walls that are not next to empty tiles and set the background color of the camera to black. Then it will seem like the empty space is a wall and reduce the amount of tiles I need to place.
Game View:
Scene View:
Now the last thing to add is basic behaviour. for the enemies i’ll keep it simple and have them shoot a red ball as seen above. The key can be collected and when stepping on the locked tile with the key will open the door and reveal a stairs. Lastly the treasure chest will open and give the player a shield to protect itself from damage.
As you can see in the video the loading of a new dungeon is not that noticable when the screen is faded to black below you see a stopwatch that kept track on how long it took for a dungeon to generate
As you can see the generation proccess took around 100 milliseconds. This is far below my criteria of 1 second (1000 milliseconds).
Future
For the future of this project, I want to add more meaningfull game design. Right now the boss monster has no meaning and it could be used to get the key. The group of enemies are just standing around and could also following the player, making them more of a threat. These kinds of additions would give more meaning Interesting gameplay than it is now in being a simple representation for the dungeon generation.
Another thing I would like to have added is more structure in the overal game. Right now i only have 1 type of dungeon generated, altough different it always contains the same elements. By giving a structure of a beginning and end I could add more things to it. For example the further you go in the more events are placed or new harder events are added. A secret path could also bring you to harder areas more quickly. This will take a long a while to implement and Unfortunately i don’t have time for it now.
Sources
Dungeon design:
https://felipepepe.medium.com/what-makes-a-good-rpg-dungeon-505180c69d00
Dungeon generation:
https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm
Cellular Automata:
spelunky:
map generation by Helbert Wolverson:
Dungeon generation trough wave function collapse:
GDC – PCG for everyone:
GDC – No man’s sky continous world generation:
GDC – Ten Principles for Good Level Design
GDC – Level Design in a Day: A Series of First Steps – Overcoming the Digital Blank Page
dungeon design:
EPC2016 – Joris Dormans – Cyclic Dungeon Generation
Brian Bucklew – Dungeon Generation via Wave Function Collapse
Unity] Procedural Cave Generation (E01. Cellular Automata)
https://www.youtube.com/watch?v=v7yyZZjF1z4
[Unity] Procedural Cave Generation (E05. Detecting Regions)
https://www.youtube.com/watch?v=xYOG8kH2tF8
And a Link to the github:
https://github.com/robert0o/RnDCellularAutomata
Research bulletPoints:
Dungeon Design:
- straight up puzzles is geloofwaardiger in een trial/proving ground
- rooms can affect different rooms, makes a mental map (central hub can make this easier)
- allowing changes to be undone gives more possibilities
- avoid linearity
- lock n’ key (bijv. door needs a key, environment in the way, guardian enz)
- traps (niet cheap traps, geen feedback is slecht)
- Keep amount of combat in check, keep the feeling of progress, combat difficulty can increase
- consistent theme, enemies, traps, environment
- optional parts with extra rewards
half design, half generated
generation 4×4 rooms. generate lines beginning to end. layers have templates and parts are generated. have strict design but randomly placed
cuz of generation mastering mechanics is necessary
personal experience:
optional routes with rewards (secret bazar, worm, aliens, zombie)
randomized events (snake pit, trapped treasure, shopkeeper, kali)
Pokemon mystery dungeon:
start with almost always 2 paths.
Sometimes have limited vision (can always see the whole room)
turn based grid movement. strategic positioning.
strategic item usages with limited bag size.
Some dungeons replace some walls with water/air/lava paths.
Some dungeons have a room with a vault and you need a key.
generation:
- rooms with corridors through them
- has different patterns like seemingly binary partition, rooms at the edges and connected with a spider web of corridors.
- slight change on random events
- some fixed events
Dungeon design:
“So CRPG dungeon design is intrinsically tied to the “verbs” that are available to the player – if can he jump, climb, sneak, fly, teleport, swim, fight ranged enemies, lockpick, break objects, directly maneuver with objects, talk to npcs, push objects, etc”
shurugeon castle (wizards & warriors)
takes place in a castle, the layout is realistic enough. has a lock and key structure in the form of a ritual to make the boss beatable. collect 5 pieces and perform the ritual.
pieces obtained by using “verbs” of the game.
Sen’s Fortress (Dark Souls)
uses 3D movement to its advantage. Having traps and falls to restrict movement and enemy attacks can also push you into those if you’re not careful. positioning and movement is key.
Level Design in a Day: A Series of First Steps – Overcoming the Digital Blank Page
Create area’s that give a feel a theme/something without being a closed off space
- give the player options
- but not to many options
- Too complex of a map can make the player lose sight of what they want to do.
- “Alway design a thing by considering it in its next larger context – a chair in a room, a room in a house, a house in an environment, an environment in a city plan”
Eero Saarinen (1910-1961)
GDC – Ten Principles for Good Level Design
- have a visual language that can help direct the player through visuals (colors geometry shapes, lighting), conclusion can useful to create feeling (oppressive )
- Good level design tells what to do, but not how
Generation algorithms
Wave Function Collapse
- Can generate different results depending on the input. (caves, dungeons, ect.)
- Can influence it more by sectioning parts and run it separately
- drawback: expensive for large scale
- giving a to specific input can give to similar results (multiple colors)
Cellular automata:
- can give cave like structures
Cyclic dungeon generation:
- Gives a more designed feel
- easily expandable levels
Dijkstra Maps:
- can find a critical path
- allows you to find what areas are not accessible
- allows you multiple uses like (getting the hardest to reach location, easiest to reach location, area around the critical path, ect.)
