By Mohammad Al Hadiansyah Suwandhy
Introduction
During the first month of Gameplay Engineering, we have been have received a bootcamp. Within the bootcamp we were introduced to topics like 3d meshes, shaders, performance, multiplayer and AI/PCG. For this bootcamp we made some individual exercises to get a better understanding on these topics. After the bootcamp was finished, we had to choose one of those topics to do an R&D project for. Between all the topics, I choose to do PCG in the end.
The Goal
The project I wanted to make is a generator in which a game developer can randomly generate a mansions in a level to use for their game. The main inspirations are games like Amnesia.
Layouts from Amnesia the Dark Descent
Besides a mansion layout, I opted to add a hedge maze as well. The idea is that a player traverses through a hedge maze right into a mansion. This will be done by using PCG algorithms.
Researching PCG Algorithms
Before we get generating we need to learn about the different algorithms first. There are a plethora of algorithms to choose from. The algorithms I studied upon (and tested) are as followed:
Depth First Search
Depth-first search (DFS) is an algorithm for traversing a tree or graph. The algorithm starts at the root node and explores as far as possible along each branch before backtracking and working its way sideways into neighboring nodes. The algorithm requires a mechanism to memorize which nodes it has visited. On top of that each node should know which child nodes it has to make traversal possible.
Delaunay Triangulation
The Delaunay Triangulation algorithm is an algorithm that connects a group of vertices into a triangular mesh.
The Delaunay triangulation takes 3 vertices and draws a circle that overlaps the position of the 3 vertices. Once the circle is made, the algorithm will assign edges to the 3 vertices.
Once it has finished this process, it will then take the next vertex and repeat the triangulation process for all the remaining vertices.
Delaunay correction
There is a catch to adapting the Delaunay algorithm and it’s that not a single vertex must remain within a circle. If a vertex were to remain we should remove an edge and connect that edge to the vertex that is located within the circle. Once the connection is made, we need to make new circles that overlap with 3 vertices.
Binary Space Partitioning(BSP)
BSP is an algorithm that divides a huge room into subsections and in turn divides these subsections into smaller subsections. The subsections can be divided on the horizontal and the vertical axis at random. The dungeon that implements the BSP algorithm is being represented through a binary tree system. This algorithms makes it so that the rooms wouldn’t overlap and always be located within the constrains of the given max height and max width.
Random Walk
The random walker algorithm works by having a “walker” start on a tile and letting it “walk” around in random directions. This is a completely random way to make a pathway and can create vastly different results for each run. The way the walker walks around, has earned this algorithm another name: “drunken walk”. You can make the patterns a bit more interesting by for example having the walker “skip a few steps”, meaning that instead of having the walker move 1 tile at a time, you can randomly make it move 2 or more tiles out.
Random walker code
Different results from testing out the drunken walk algorithm in Unity 3D
Although the results were pretty cool to see, I didn’t see how the complete randomness of the algorithm will help me in my goal so I opted not to use this algorithm further.
Voronoi Diagram
Voronoi is a way to partition an plane into parts that are based on points. Each point in the set has a corresponding region that consists of all the points closer to that site than to any other. These regions are called Voronoi cells. The resulting structure make the plane seem more “natural” and “cell -like”.
Example of how a Voronoi Diagram looke like
Simple Voronoi implementation
Results of the Voronoi tests
Cellular Automata
Cellular automata are mathematical models used to simulate processes that evolve over time. They consist of a grid of cells, each of which can be in one of a finite number of states. The state of each cell changes according to a set of rules that depend on the states of neighboring cells. Imagine a grid made up of cells, where each cell has a certain state—like being on or off, alive or dead, or different colors.
Simple Cellular Automata implementation
Test run of Cellular Automata in Unity using 3d grid
Although the results were pretty cool to see, the structure would be more akin to a cave system rather than a man-made structure. It didn’t seem like this would help me with my goal, so I opted not to use this algorithm further.
Wave Function Collapse
Wave Function Collapse occurs when a wave function reduces a cell, in a superposition containing multiple possibilities, to a single possibility due to environmental factors. It is based on a topic in quantum mechanics that shares the same name. In this algorithm, a cell has rule sets to which it will allow only specific cell types to be adjacent to it. With this we are able to use it to create unique game level that follow constraints in order to make coherent levels.
The hedge maze
Now that I have studied up on some algorithms and tested them, its time to see which ones are going to be useful for me to achieve my goal. The first thing I wanted to do for my goal was to create a hedge maze.
For the hedge maze I incorporated the Depth First Search Algorithm. I gave the maze a grid of “rooms”. These rooms all have their own walls that can open up at will. This is how I can create a pathway in a grid filled with these rooms. The rooms can check on their neighbouring rooms to get information for themselves and have a “unvisited” status.
To setup the DFS, first I choose a starting room. From this room the DFS shall look into the neighbours of its current room and puts every neighbour labelled as “unvisited” into a list. Then it picks an unvisited neighbour from this list at random to be the next current room.
Once the DFS has chosen its next room it will set that room as the new current roon and will then mark the room as “visited”, effectively removing said room as an option for the DFS to choose next, and put the rooms it has visited into a stack for future use. The DFS shall proceed to repeat this process until it has hit a dead end.
Before the DFS goes into the next room, it checks which direction it was headed towards. Once it knows the direction, it opens up the walls of the room in said direction and then changes the current room into the next room. From the next room it then also opens up the walls behind to complete the connection between both rooms.
Once the DFS has hit a dead end it will use the stack from earlier to retrace its steps back to a previous room. The reason this is done is because a good amount of those previous rooms still have neighbours that are unvisited, which means that there can be more pathways that can be created.
Once the DFS has marked every room as unvisited, a pathway has been created.
To make the dungeon more interesting, I wanted to add entry and exit points and wanted a “key object” to spawn within the maze. On top of that, the current script was also made for cell prefabs that are sized 1×1. I wanted to update the maze to include these features.
The exit and entry points of the maze are randomized, however the developer can choose on which side they want them to be located at. I did this by opening up the walls at a random cell on the given edges in the maze grid that were chosen in the inspector. Then I blocked the exit point by spawning in a “Door”. The door rotates in the right direction based on what side exit is at. Lastly spawned a “Key” at a random position inside the maze by randomly choosing a cell within the grid as a spawnpoint.
Maze V2
After having the DFS maze, I tried to see if I could make the maze more complex. For the other version I tried apllying WFC using the same prefabs I used in the DFS one. To set up for the WFC, I had to make each individual cell possibility into a prefab.
After the prefabs are made, I added a script that remembers what possible neighbours each side of a tile can have.
After the tiles and all their neighbouring possibilities had been set-up, the WFC logic can be implemented. After having added walls surrounding the maze, I got the following results:
Results from a WFC test
The wave function collapse offers some very complex maze variety however it also had the possibility to create unreachable “dead zones”
Unreachable part of the maze through WFC
The Mansion
The mansion was going to be a bigger challenge as the structure is going to be much more complex. This means that the criteria are going to be much more difficult to achieve. As was said at the intro of this document, my main inspirations are Amnesia layouts. Therefore, the criteria would be that the mansion layout for the PCG mansion should be somewhat comparable to those maps.
I decided that I would go with a room first approach. This means that I would place the rooms into the map first before adding the corridors. The reason for this decision is because when looking at the maps above, the main vocal points are the rooms.
For the room placement I decided to test it using the Binary Space Partitioning algorithm. The BSP will create rectangular subsections of a giant “cell”. This cell will be divided into 2 smaller subsections. This process will be repeated until a set number of iterations.
Once all the sections have been made, rooms of random sizes and positions will be spawned within each subsection. These rooms should be added to a list.
Once we have all the rooms we need to make connections between rooms. However we need to ensure that the rooms are connected to the closest neighbouring rooms and not rooms from across the map.
To create the corridors, we can get the middle positions between 2 rooms. Using these positions we can create an L-shaped corridor that connect from room1 to the middle point to room 2.
Now that we have a way to make corridors between rooms, we can run a few tests to see how the layout looks like. The results are as followed:
The result of BSP looked pretty good, however compared to the maps I wanted to achieve, the layout didn’t seem to offer the right structure complexity and variety.
Random room placement
Given that I wasn’t too happy with how BSP turned out, I tried different approach. Another test I performed is the usage of a simple random room placement algorithm. Within this algorithm I place rooms of random sizes within a grid. The code will check if newly created room won’t overlap with already created rooms.
After all the rooms have been created, I used the same CreateCorridor logic from the BSP algorithm and applied it.
Interestingly enough, randomly placing rooms in a grid, resulted in more unique and interesting layouts to use. However the biggest problem now, was that the corridors are going through other rooms.
Prim’s Algorithm
Prim’s algorithm is a method used to find the Minimum Spanning Tree (MST). A Minimum Spanning Tree is a subset of edges that connects all vertices in the graph with the minimum total edge weight and no cycles. The MST is constructed by connecting rooms with the shortest possible paths. We start with one room and gradually add the shortest edges until all rooms are connected.
After all the edges are determined, we create corridors between the 2 rooms of an edge. Using the familiar create corridor function.
After the layouts were finished I added walls for each room and created doorways where the corridors intersect.
Final verdict
For this project I’ve learned a lot about some procedural generation algorithms. I have gained a lot of insight on their use cases and what results they give. Even though I haven’t used all of them for the goal of my project, getting to test them out first was a great learning experience.
In terms of the final product, the hedge maze for the garden has worked out very well and created the image of the maze I had in mind.
The Mansion maze proved to be more complex than I thought because unlike dungeons, mansions adhere to a more stricter and complex rule set to fully be able to realize through the PCG algorithms I had studied up on. I initially wanted to try and make it so that every space inside the borders of a “mansion” had been used, however upon studying up on the algorithms and seeing the mansion layouts from other PCG games, I found out that trying to do that with PCG whilst also trying to get a somewhat coherent and complex layout for a mansion, would prove to be very difficult as a lot of room placement first-algorithms leave empty spaces between the rooms and corridors. If provided with bigger chunks of more complex tiles and prefabs, then biggest potential towards achieving what my goal is, would probably lie in WFC.
For future expansions, the algorithms can be better optimized since the grid contains a lot of individual cubes that aren’t really performance friendly to calculate all at once. Prefabs can also be added to get some polish alongside the layouts that are being generated and the code can also be further expanded into adding another layer on the y-axis. For now, we have managed to get some pretty good layouts that are starting to resemble the ones from my inspirations.
Sources
BSP Tree FAQ. (n.d.). https://people.eecs.berkeley.edu/~jrs/274s19/bsptreefaq.html
SilverlyBee. (2021, September 22). Explaining Maze Generation Using Depth First Search in 51s #shorts [Video]. YouTube. https://www.youtube.com/watch?v=e5zDG4JIsyg
javidx9. (2017, July 10). Programming Mazes [Video]. YouTube. https://www.youtube.com/watch?v=Y37-gB83HKE
Ace. (2011b, May 5). Rendering: How BSP tree works [Video]. YouTube. https://www.youtube.com/watch?v=Hebi641Ph7c
Richard Fleming Jr. (2013, June 16). Binary Trees [Video]. YouTube. https://www.youtube.com/watch?v=S5y3ES4Rvkk
DV Gen. (2023, April 16). Procedural Generation with Wave Function Collapse and Model Synthesis | Unity Devlog [Video]. YouTube.
https://www.youtube.com/watch?v=zIRTOgfsjl0
Adonaac, A. (2015, September 3). Procedural Dungeon Generation Algorithm. Game Developer. https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm
Beaudon, R. (2018, January 12). Random 2D dungeon generation in Unity using BSP (Binary Space Partitioning) trees – Romain Beaudon. http://www.rombdn.com/blog/2018/01/12/random-dungeon-bsp-unity/
Creating Simple Procedural Dungeon Generation. (2021, April 9). TomStephenson. https://www.tomstephensondeveloper.co.uk/post/creating-simple-procedural-dungeon-generation
SCIco. (2020, May 9). Delaunay Triangulation [Video]. YouTube. https://www.youtube.com/watch?v=GctAunEuHt4
Adonaac, A. (2023, December 8). Procedural Dungeon Generation Algorithm. https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm
Garnet. (2023, January 2). Random Map Generator in UNITY! [Tutorial] [Video].
https://www.youtube.com/watch?v=6B7yOnqpK_Y
Alex K. Dev. (2023, March 10). How to generate a voronoi diagram in Unity – tutorial [Video]. YouTube.
https://www.youtube.com/watch?v=-fYI_5hQcOI
Michael Sambol. (2012, October 28). Prim’s algorithm in 2 minutes [Video]. YouTube. https://www.youtube.com/watch?v=cplfcGZmX7I
