By Mohammad Al Hadiansyah Suwandhy
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 project I wanted to make is a sort of tool in which the player can apply a couple of PCG algorithms in a level to use for their game. The main inspiration for the edge case of the tool is the game Amnesia. The idea is that a player traverses through a hedge maze into a mansion. The areas will make use of PCG algorithms.
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.
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.
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.
The 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 added entrance and exit points which positions can be edited in the editor. Then I blocked the exit point with a “Door” and spawned a “Key” at a random position inside the maze.
For the mansion, 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. 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 devided 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 do this we can use the Delaunay Triangulation algorithm. As mentioned before the Delaunay triangulation can assign logical edges between 2 points. By running the Delaunay Triangulation through our rooms (the points) we can create a logical web of edges between rooms. Once we have the connections we now need to create a Minimal Spanning Tree to get the shortest web of connections between rooms. Using the MST connections we can create corridors between rooms.
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.
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 however didn’t get the results I wanted out of it. I had a lot of trouble applying the theory into the development project and fell behind at an early stage of the process.
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
Adonaac, A. (2015, September 3). Procedural Dungeon Generation Algorithm. Game Developer. https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm
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