{"id":78,"date":"2022-09-28T09:38:51","date_gmt":"2022-09-28T09:38:51","guid":{"rendered":"https:\/\/summit-2223-sem1.game-lab.nl\/?p=78"},"modified":"2022-12-06T14:54:38","modified_gmt":"2022-12-06T14:54:38","slug":"dungeon-generation","status":"publish","type":"post","link":"https:\/\/summit-2223-sem1.game-lab.nl\/?p=78","title":{"rendered":"2D Procedural Dungeon Generation"},"content":{"rendered":"\n
\n
\n
\n
\"\"<\/figure>\n\n\n\n
\"\"<\/figure>\n<\/figure>\n<\/div>\n<\/div>\n\n\n\n

By Nicky Wu <\/p>\n\n\n\n

<\/div>\n\n\n\n
    \n
  • Table of Contents<\/strong>\n
      \n
    • Introduction<\/li>\n\n\n\n
    • 1.    Dungeon Generation Algorithms\n
        \n
      • 1.1 Binary Space Partition (BSP)<\/li>\n\n\n\n
      • 1.2 Cellular Automata<\/li>\n\n\n\n
      • 1.3 Drunken Walk<\/li>\n\n\n\n
      • 1.4 Diffusion Limited Aggregation<\/li>\n\n\n\n
      • 1.5 Flood Fill\n
          \n
        • 1.5.1 Depth First Search (DFS) and Broad First Search (BFS)<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • 1.6 Wave Collapse Function<\/li>\n\n\n\n
        • 1.7 Delaunay Triangulation<\/li>\n\n\n\n
        • 1.8 Minimal Spanning Tree<\/li>\n<\/ul>\n<\/li>\n\n\n\n
        • 2.    Testing and validation\n
            \n
          • 2.1 Choosing the right foundation<\/li>\n\n\n\n
          • 2.2 Choosing PCG algorithms\n
              \n
            • 2.2.1 Drunken Walker<\/li>\n\n\n\n
            • 2.2.2 Cellular Automata<\/li>\n\n\n\n
            • 2.2.3 Diffusion Limited Aggregation<\/li>\n\n\n\n
            • 2.2.4 Wave Collapse<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\n\n\n\n
            • 3.    Implementation\n
                \n
              • 3.1 Room Bounds\n
                  \n
                • 3.1.1 Binary Space Partitioning<\/li>\n\n\n\n
                • 3.1.2 Drunken Walk<\/li>\n\n\n\n
                • 3.1.3 Cellular Automata<\/li>\n\n\n\n
                • 3.1.4 Diffusion Limited Aggregation (By using a walker)<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                • 3.2 Room Regions\n
                    \n
                  • 3.2.1 Detecting Regions<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                  • 3.3 Placing the walls<\/li>\n\n\n\n
                  • 3.4 Room Corridors<\/li>\n\n\n\n
                  • 3.5 Combining Algorithms\n
                      \n
                    • 3.5.1 Deducting floors<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                    • 3.6 Scriptable Objects<\/li>\n<\/ul>\n<\/li>\n\n\n\n
                    • 4.    Conclusion<\/li>\n\n\n\n
                    • 5.    What the future holds<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n
                      <\/div>\n\n\n\n

                      Introduction<\/h1>\n\n\n\n

                      During the first four weeks of the semester, we took a look at different kinds of topics in Game Development such as shaders, performance, Machine learning and procedural generated content.<\/p>\n\n\n\n

                      At the end of the fourth week, I have decided I wanted to do something with PCG since it was the most interesting topic for me. I already wanted to do something with rooms being unique or have a different kind of layout to them and came up with the following idea:<\/p>\n\n\n\n

                      \u201cCreating dungeon rooms by using multiple PCG algorithms\u201d<\/em><\/p>\n\n\n\n

                      I find this idea quite interesting because a lot of PCG algorithms creates a certain pattern or something unique that only this algorithm can produce. By combining these, I think it might result to something more unique. For this R&D project, I have decided to focus on creating a dungeon by using PCG algorithms with an emphasis on unique room structure.<\/p>\n\n\n\n

                      In this blog post I\u2019ll talk about the dungeon algorithms I have looked at, which of the algorithms I used and how I implement it to my framework.<\/p>\n\n\n\n

                      I have made two small sketches of how I want the level to look like and what the algorithms should output.
                      <\/p>\n\n\n\n

                      1. Dungeon Generation Algorithms<\/h1>\n\n\n\n

                      There are a lot of different kinds of procedurally content generation algorithms which are used in games. In this chapter I\u2019ll explain how some of these popular algorithm works in a high-level context.  <\/p>\n\n\n\n

                      1.1 Binary Space Partition (BSP)<\/h2>\n\n\n\n

                      This algorithm is very popular among the PCG games since it is easy to implement and understand. This algorithm sub-divides a (room) boundary until it reached its desired width and height. Then these boundaries will get added to a binary tree [See figure 1]. You can use this tree to connect every room and use the room boundaries for other purposes.<\/p>\n\n\n\n

                      \"https:\/\/media.geeksforgeeks.org\/wp-content\/uploads\/20200630014725\/space.jpg\"
                      Figure 1: Binary Space Partitioning (GeeksforGeeks, 2020).<\/figcaption><\/figure>\n\n\n\n

                      1.2 Cellular Automata<\/h2>\n\n\n\n

                      Another popular level generation algorithm is called Cellular Automata. This is an algorithm that uses the cells\u2019 neighbors to determine the outcome after each iteration. The cells have two possible states; dead and alive. <\/p>\n\n\n\n

                      \"\"
                      Figure 2: Cellular Automata Example (Celusniak, 2019)<\/figcaption><\/figure>\n\n\n\n

                      These rules are defined in the algorithm and there are a lot of rule sets to use for this algorithm. One of the popular rule set is called \u2018Conway\u2019s Game of life\u2019. This rule set creates cave-like levels which is perfect for a cave level.<\/p>\n\n\n\n

                      The base cellular automata implementation can be summarized into these steps:<\/p>\n\n\n\n

                        \n
                      • Fill the grid with noise (wall and floor tiles)<\/li>\n\n\n\n
                      • Place random open cells in the grid <\/li>\n\n\n\n
                      • Use a rule set to determine the fate of the cell in the current generation<\/li>\n\n\n\n
                      • Get the next cell and repeat step 3 until desired output <\/li>\n<\/ul>\n\n\n\n

                        1.3 Drunken Walk<\/h2>\n\n\n\n

                        The drunken walk algorithm involves a walker who randomly choose one of the four direction (north\/south\/east\/west) based on its current position to walk to. These walk points are saved in a list and are used to determine when the position of the grid is open or not. <\/p>\n\n\n\n

                        This algorithm is reliable to create levels because all the spaces are connected due to it being walked on once by the walker. You can add a fill percentage to the walker as well, to let it know how many spaces it still need to open in order to finish the generation.<\/p>\n\n\n\n

                        This can be summarized into these steps:<\/p>\n\n\n\n

                          \n
                        1. Fill the grid with walls (closed objects)<\/li>\n\n\n\n
                        2. Pick a start position for the walker<\/li>\n\n\n\n
                        3. Pick a random cardinal direction (north\/south\/west\/east)<\/li>\n\n\n\n
                        4. Take a step in this direction and save this point<\/li>\n\n\n\n
                        5. Repeat from step 3 until the desired amount of opened cells is reached<\/li>\n<\/ol>\n\n\n\n

                          This is the most basic form of the drunken walk, there are more complex and optimized algorithms based on the Drunken Walk algorithm to get different outputs and .<\/p>\n\n\n\n

                          1.4 Diffusion Limited Aggregation<\/h2>\n\n\n\n

                          Despite its complex name, the algorithm is quite simple to understand. It makes use of random placed particles throughout the canvas and moves randomly.<\/p>\n\n\n\n

                           When a particle hits a floor or something that is defined as \u2018open\u2019, the position of that particle will be added to the floor. Then it repeats with all the other particles until it reached a certain fill percentage. There are a lot of ways to implement this and it will create different kinds of fractal patterns.<\/p>\n\n\n\n

                          \"Diffusion-Limited
                          Figure 3: DLA simulation (Sayama, 2011)<\/figcaption><\/figure>\n\n\n\n

                          In figure 3, you will see how these particles connect with each other in order to create a fractal pattern. The blue particles will move indefinitely until it hits one of the red particles. The red particles can be seen as the \u2018floor\u2019 or \u2018open\u2019 tile. <\/p>\n\n\n\n

                          The basic implementation can be summarized into these steps:<\/p>\n\n\n\n

                            \n
                          1. Create a grid and spawn particles in the grid<\/li>\n\n\n\n
                          2. Make the particles move at random directions<\/li>\n\n\n\n
                          3. Convert some of the particles into floor tiles so they won\u2019t move<\/li>\n\n\n\n
                          4. When a particle touches a floor tile, turn it into a floor tile<\/li>\n\n\n\n
                          5. Repeat step 4 until desired fill amount<\/li>\n<\/ol>\n\n\n\n

                            1.5 Flood Fill<\/h2>\n\n\n\n

                            The Flood Fill algorithm is used to detect all the tiles that belongs to the current region. The region is based on where you start. You can compare it to the \u2018paint bucket\u2019 tool in any paint program. Where it will eventually iterate over all the cells in the region.<\/p>\n\n\n\n

                            \"https:\/\/www.algorithm-archive.org\/contents\/flood_fill\/res\/example.png\"
                            Figure 4: Flood Fill Visual (Arcane Algorithm Archive, n.d.)<\/figcaption><\/figure>\n\n\n\n

                            1.5.1 Depth First Search (DFS) and Broad First Search (BFS)<\/h3>\n\n\n\n

                            These methods of flood fills are used to change the way how the flood fill behaves. In the depth first search, the algorithm focuses first on getting towards the deepest part of the region. The broad first search is focusing on the surface, where its neighbors will get checked next iteration.<\/p>\n\n\n\n

                            1.6 Wave Collapse Function<\/h2>\n\n\n\n

                            This algorithm makes use of the way the sprite is connected with other sprites. These are used to set the rules for what the algorithm can output for certain cells in the grid. <\/p>\n\n\n\n

                            The algorithm starts to put a random sprite in the grid and starts from there.  Based on the adjacent cells, the algorithm gets a list of possible sprites to put in the adjacent cell. This will get repeated until every cell has been drawn.<\/p>\n\n\n\n

                            \"https:\/\/robertheaton.com\/images\/wfc-examples.png\"
                            Figure 5: Wave Collapse Examples (Heaton, 2018)<\/figcaption><\/figure>\n\n\n\n

                            1.7 Delaunay Triangulation <\/h2>\n\n\n\n

                            \u201cBy definition, a Delaunay triangulation is a triangulation in which no vertex lies within the circumcircle of any triangle.\u201d (Simpson, 2015)<\/p>\n\n\n\n

                            Delaunay triangulation is a mesh algorithm to connect vertices together and keep making triangles out of it by using its edges. Watson\u2019s method is one of the more popular algorithms to implement this algorithm.<\/p>\n\n\n\n

                            There are a lot of application for Delaunay triangulation despite it outputs a meshes. You can use it in a different context as well which doesn\u2019t involve modeling.<\/p>\n\n\n\n

                            1.8 Minimum Spanning Tree<\/h2>\n\n\n\n

                            A minimum spanning tree is useful to find the shortest path to connect all the vertices with each other. In game context, this tree can be used to find the shortest path to connect all the rooms with each other. The vertices can be seen as room centers instead. Delaunay Triangulation can be used in conjunction with the minimum spanning tree.<\/p>\n\n\n\n

                            There are a lot of methods to implement this algorithm, one of the more popular algorithm is called Primm\u2019s algorithm. <\/p>\n\n\n\n

                            \"https:\/\/miro.medium.com\/max\/451\/1*-gNoEeTMGYnCG5SSLi1Wtg.png\"
                            Figure 6: Minimum Spanning Tree Visual (Chothe, 2021).<\/figcaption><\/figure>\n\n\n\n

                            Primm\u2019s algorithm<\/strong><\/p>\n\n\n\n

                            Primm\u2019s algorithm starts with a vertex, then check its edges. It will then choose the edge with the lowest value. Then it will go to the next cell, the one that the chosen edge is connected to. All the vertex that has been visited will be put in a tree as well in case of a loop forming in the tree.<\/p>\n\n\n\n

                            This method is also known to be greedy since it always try to choose the lowest value without considering the other vertices.<\/p>\n\n\n\n

                            2. Testing and validation<\/h1>\n\n\n\n

                            2.1 Choosing the right foundation<\/h2>\n\n\n\n

                            I want to have a base project to work on; in order to implement the algorithms without having compatibility issues. I have searched around on the internet for a tutorial which also meets the following criteria:<\/p>\n\n\n\n

                              \n
                            1. The framework contains two of more PCG algorithms that I have researched above<\/li>\n\n\n\n
                            2. The tutorial also looks back at previous code and refactor it<\/li>\n\n\n\n
                            3. Tutorial covers flexibility where users can simply play around with the framework without having the need to change tons of parameters<\/li>\n\n\n\n
                            4. Adding a new PCG algorithm should be fairly straightforward<\/li>\n\n\n\n
                            5. The framework makes use of a hashset to place the floors or walls etc<\/li>\n<\/ol>\n\n\n\n

                              There were a lot of tutorials that makes use of a 2D array or a list and they don\u2019t look back to refactor the code. These kinds of tutorials did not meet the criteria. I did found one tutorial series that fits the stated criteria which was the tutorial series from Sunny Valley (Sunny Valley Studio, 2020)<\/p>\n\n\n\n

                              Despite the long tutorial, it did cover a lot of the topics that I want to learn about. One of the many things are scriptable objects. Which are used to save the parameters for the algorithm. These can be used to get good results quickly.<\/p>\n\n\n\n

                              2.2 Choosing PCG algorithms<\/h2>\n\n\n\n

                              I want to have three algorithms which one can fit in each criteria:<\/p>\n\n\n\n

                                \n
                              1. Algorithm outputs a cave-like room<\/li>\n\n\n\n
                              2. Algorithm outputs a pattern<\/li>\n\n\n\n
                              3. Algorithm outputs a chaotic\/random room<\/li>\n<\/ol>\n\n\n\n

                                All the algorithms should be customizable as well so it will be possible to influence the output.<\/p>\n\n\n\n

                                I have tested the following algorithms:<\/p>\n\n\n\n

                                  \n
                                1. Drunken Walker<\/li>\n\n\n\n
                                2. Cellular Automata<\/li>\n\n\n\n
                                3. Diffusion Limited Aggregation<\/li>\n<\/ol>\n\n\n\n

                                  Go to the implementation chapter for more information on how I implemented these algorithms.<\/p>\n\n\n\n

                                  2.2.1 Drunken Walker<\/h3>\n\n\n\n

                                  The drunken walker outputs a random room, without any constant pattern. Every time you run this algorithm, it will generate a different kind of room. This drunken walker can be expanded as well to create more random rooms. The problem is that you don\u2019t have a lot of structural control to this algorithm which isn\u2019t a big issue for me. It will output a different kind of room depending on the parameters you give to the algorithm. <\/p>\n\n\n\n

                                  I have implemented this in the framework and it seems to be fit the third criteria.
                                  <\/p>\n\n\n\n

                                  2.2.2 Cellular Automata<\/h3>\n\n\n\n

                                  This algorithm is pretty interesting, it outputs a different kind of room (structural wise) depending on the ruleset that it uses. It is very easy to just play around with the ruleset since it only uses its neighbors to determine the cells. There\u2019s a different output depending on the ruleset that you use. I have implemented the conway\u2019s game of life and the mazectric ruleset to see what they produce.<\/p>\n\n\n\n

                                  \"\"
                                  Figure 7: Cellular Automata Output (Mazectric)<\/em><\/em><\/figcaption><\/figure>\n\n\n\n
                                  \"\"
                                  Figure 8: Cellular Automata Output (Conway's Game Of Life)<\/em><\/em><\/figcaption><\/figure>\n\n\n\n

                                  Conway\u2019s ruleset seems to produce a more cave-like with corridors while the mazectric ruleset, creates a maze with very long hallways. I do think this should fit the first criteria and is very customizable. During the feedback session, I had feedback regarding that this algorithm doesn\u2019t always make all tiles walkable so there\u2019s a percentage of useless floor tiles.<\/p>\n\n\n\n

                                  2.2.3 Diffusion Limited Aggregation<\/h3>\n\n\n\n

                                  The last algorithm that I have implemented is the diffusion limited aggregation algorithm. I have played around with this algorithm and it seems to keep some kind of pattern based on the method that give to the algorithm. This will fit the second criteria. I\u2019m pretty sure I\u2019ll find more ways to extend this algorithm to create more kinds of patterns.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n
                                  \"\"<\/figure>\n\n\n\n
                                  \"\"<\/figure>\n\n\n\n

                                  2.2.4 Wave Collapse<\/h3>\n\n\n\n

                                  For the wave collapse I have used an already existing project because it might be taking too much time for me to implement it in the current framework. I have used this project () to see what the wave collapse is producing.<\/p>\n\n\n\n

                                  \"\"
                                  Figure 9: Wave Collapse Simulator (Donald, n.d.)<\/figcaption><\/figure>\n\n\n\n

                                  I played around with the online project and it seems to be producing pretty good results but I don\u2019t think I can make much use of this algorithm since it is really hard to control this algorithm. You only define the rules by saying how the sprite is connected with each other but at the end the algorithm chooses the sprite at random (based from a list of possible sprites). There\u2019s not much customization there besides changing the input (sprites) and how they connect with each other.<\/p>\n\n\n\n

                                  3. Implementation<\/h1>\n\n\n\n

                                  3.1 Room Bounds<\/h2>\n\n\n\n

                                  In order to get the rooms with their own bounds, I have used binary space partitioning for it and converted it into an object. Then I have used a hashset to track what position within the bound should be a floor tile<\/p>\n\n\n\n

                                  3.1.1 Binary Space Partitioning<\/h3>\n\n\n\n

                                  The binary space partitioning algorithm is used to get all the room bounds in the level and I don\u2019t need the connections between the rooms so I only need a list and a queue to do this instead of a binary tree. <\/p>\n\n\n\n

                                  These room bounds are used for the algorithms to create their room. Since I don\u2019t need the connection between the rooms, I only used a queue and a list of room bounds to keep track of the algorithm.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  First I start with one bound; this is the level bounds. Then I split this level bound into two smaller bounds. Every time a bound isn\u2019t at the right size, it will split itself again until it reaches the right size. When it reaches the right size it will stop and add the bounds to the room list.<\/p>\n\n\n\n

                                  3.1.2 Drunken Walk<\/h3>\n\n\n\n

                                  The way how I implemented this algorithm is by making using a walker and put it at a random spot in a grid filled with walls. But since I have my own algorithm to place walls, this is not needed so a Hashset which represents the floor tiles is enough for me.<\/p>\n\n\n\n

                                  I have added a walker who acts like a paint brush and will randomly move throughout the Hashset.<\/p>\n\n\n\n

                                  \"\"
                                  Figure 12: Drunken Walker Drawing<\/em><\/figcaption><\/figure>\n\n\n\n

                                  The walker it moves at random directions and save the positions that it has previously walked on. These spots are converted into floor tiles and saved in a Vector2int Hashset. This method will be called multiple times until it has opened a certain amount of tiles. <\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  The method accepts a start position and the walk length. The start position defines where the walker starts to walk. The walk length defines how many tiles the walker can open before it dies. You can call this method anywhere in the code and it only outputs a Vector2int Hashset.<\/p>\n\n\n\n

                                  3.1.3 Cellular Automata<\/h3>\n\n\n\n

                                  In order to implement this algorithm, I started to add a way to add noise in the grid (Hashset) which fills the grid randomly with floor tiles. I have added the random starter cells (alive) around the center of the grid.<\/p>\n\n\n\n

                                  Then I iterate over the whole grid and used its neighbors and a ruleset to determine the fate of the cell. The cell can either die, live or reborn (alive again). I currently have implemented two rulesets; the Mazectric and the Conway\u2019s Game Of Life.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n
                                  \"\"<\/figure>\n\n\n\n

                                  I make use of the 8 directions to determine the neighbors of a cell. I iterate over two for-loops, one for I do a neighbor check via checking all the 8 directions of the current cell. Then I add them in a list and return this to the caller. All the neighbors should be within the grid\u2019s boundaries so it won\u2019t continue infinitely.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n
                                  \"\"<\/figure>\n\n\n\n

                                  By using a switch to determine what ruleset I want to use. In this switch statement I check the cell\u2019s neighbors and determine what the state of this cell is in the next iteration.<\/p>\n\n\n\n

                                  The maze ruleset makes use of the amount of neighbors that a cell has. The maze ruleset states that a cell survives when it has at least one or up to 5 neighbors. A cell will be alive when it has exactly three neighbors. This ruleset creates a maze with relatively short hallways, there\u2019s also a modified version which makes long hallway. This ruleset is called \u2018Mazectric\u2019, the only difference is that cells will die if they have 5 neighbors. I wanted the maze to have longer hallways and thus is why I chose for this ruleset instead of the maze one.<\/p>\n\n\n\n

                                  I combined and simplified all the rules into two if statements; when there\u2019s more than 4 neighbors, kill the cell and when it\u2019s less the cell is alive.<\/p>\n\n\n\n

                                  3.1.4 Diffusion Limited Aggregation (By using a walker)<\/h3>\n\n\n\n

                                  This implementation of DLA is based on bracket productions\u2019 implementation (Bracket Productions. (n.d.). Where it is also using a walker to simulate as a \u2018particle\u2019.<\/p>\n\n\n\n

                                  The way I have implemented Diffusion Limited Aggregation is a bit different. The normal way of this would be to generate an amount of particles in the grid that randomly moves around the grid. When it hits a floor tile, then the particle will become a floor tile. Then you have to wait until a different particle hits a floor tile. <\/p>\n\n\n\n

                                  The reason why I don\u2019t think this will work that well is because not all the particles will hit a floor tile and you have to iterate over all of them. I don\u2019t think this is performant enough which is why I strayed a bit away from the normal implementation. I do plan to test the performance in the future plans.<\/p>\n\n\n\n

                                  \"\"
                                  Figure 16: DLA Graph Visual<\/em><\/figcaption><\/figure>\n\n\n\n

                                  I started opening some random cells in the grid (depending on the method). In case of the center attraction, I open the cells that\u2019s around the center of the boundary. I randomly open tiles if the center attractor is not the chosen method.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  Instead of spawning hundreds of particles at once, I started to spawn a single walker, who walks towards a random floor tile. During it the walk cycle, the particle will \u2018jitter\u2019 which simulates the way how the particles are randomly moving in the grid but it still have a higher chance to head towards the right direction. This means that every walker will eventually hit a floor tile. <\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  The spawn area of a walker is near the boundaries of the room, I also do a distance check if this spawn position is too close to a floor tile. The walker behavior is also called \u2018Walking inward<\/strong>\u2019. I also have implemented the central attractor and walking outward methods to this algorithm.<\/p>\n\n\n\n

                                  Central Attractor<\/em><\/h4>\n\n\n\n

                                  This walker method involves a walker who is placed randomly in the room. This walker heads towards the center of the room (or one of the starting positions). Then when it hits the center tile (or any other open tile) it will open the previous tile. This modification creates a room with an open center.<\/p>\n\n\n\n

                                  Walking Outward<\/em><\/h4>\n\n\n\n

                                  This is similar to the central attractor except it starts the walker at the center and is trying to walk to one of the wall boundaries. When it hits a wall, it destroys the wall and it repeats again until a certain amount of walls are broken.<\/p>\n\n\n\n

                                  3.2 Room Regions<\/h2>\n\n\n\n

                                  During the feedback session, someone mentioned that some of the floor tiles aren\u2019t reachable, making it useless. I received some feedback of how I can deal with this problem. One of the suggestions was to use the flood fill algorithm to detect the walkable tiles and then find a way to connect these not walkable tiles with the walkable tiles.<\/p>\n\n\n\n

                                  Not all floor tiles are walkable after the floor generation. This is where the flood fill algorithm comes in. This algorithm makes it possible to detect all the regions in the room and will assign the tiles accordingly. When a tile isn\u2019t reachable from the main region, it will create a new region.<\/p>\n\n\n\n

                                  3.2.1 Detecting Regions<\/h3>\n\n\n\n

                                  The way how I implement this is quite simple. I have used the flood fill algorithm for this. I start from a point and add the neighbors (four ordinal directions) to a queue to be checked in the next iteration. This will continue until all of the tile of that region has been added to the list. <\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  Here I check for a starting point in the (new) region. <\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  Now I put their neighbors in a queue to be checked if it belongs to the region.<\/p>\n\n\n\n

                                  When there are more tiles that are not reachable, I\u2019ll manually add this tile back to the queue so it will start the flood fill all over again. This repeats until all tiles are added to their own regions.<\/p>\n\n\n\n

                                  \"https:\/\/cdn.discordapp.com\/attachments\/1016336564667814018\/1032403047567085611\/unknown.png\"<\/figure>\n\n\n\n

                                  In order to turn these regions into a single region, I used a simple distance check between these two regions. The two closest coordinate will have a walker that walks from point A to point B in order to open these regions. It repeats this until there\u2019s only one region left.<\/p>\n\n\n\n

                                  If you can look at image below, you will see a cell with an orange background, this means that this tile has been opened because of the walker. To make it less performant heavy, I limited this algorithm to a room instead of the whole level.<\/p>\n\n\n\n

                                  \"https:\/\/cdn.discordapp.com\/attachments\/1024650869200920576\/1033123857210548316\/unknown.png\"<\/figure>\n\n\n\n

                                  3.3 Placing the walls<\/h2>\n\n\n\n

                                  In order to place the walls, I iterate over all the floor tiles and check its neighbor. <\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  I check all the eight directions for the neighbors and when there\u2019s no neighbor in that direction (an empty tile), a wall will be placed there. This will be done for the corridor floor tiles as well.<\/p>\n\n\n\n

                                  3.4 Room Corridors<\/h2>\n\n\n\n

                                  I also wanted to connect the rooms by using corridors. The current implementation of this is by using a walker that goes from one room center to the other. All the tiles the walker has walked on, will be turned into corridor floor tiles. <\/p>\n\n\n\n

                                  To make sure the walker doesn\u2019t walk to the same room, I have created a list of rooms then choose a random index to start then check the shortest distance to the next room. After the walker has walked to that room center, I remove the previous room then the walker repeats with all the other rooms.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  As you can see on the image above, there\u2019s no way to know when the walker goes through a room, it will create a corridor that goes through the rooms. This is not a result that I want to see. I could used the connections that are created through the BSP algorithm but then I have a problem with the dungeon being too linear.<\/p>\n\n\n\n

                                  This could be fixed if I used the Delaunay Triangulation algorithm. Where I use the room center to connect with each other (I see it as a vertex). Then I can use the edges of the triangles to connect the rooms together. By creating a minimum spanning tree, I can get the shortest path to connect all the rooms. Then I can use the remaining edges to make loops in the dungeon so it won't be linear. Unfortunately I did not have enough time to implement this. <\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  I did manage to use a Delaunay Triangulation library and applied it to the framework. But since I don't have a minimum spanning tree, I can't really use it to draw the corridors.<\/p>\n\n\n\n

                                  3.5 Combining Algorithms<\/h2>\n\n\n\n

                                  In order to combine the algorithms to create one room, I have used a hashset for it. A hashset is a unordered list data type where all the elements are unique. It makes use of a \u2018hash\u2019 value to determine when the element is unique or not. Since I just needed to combine the output of the algorithms, I merge them in a single hashset. I only have to make the algorithm output a hashset in order to make this work. The hashset will automatically know what floor tiles to add and what to ignore.
                                  <\/p>\n\n\n\n

                                  3.5.1 Deducting floors<\/h3>\n\n\n\n

                                  One of the feedback that I have receive was that the rooms were sort of the same and suggested to use some of the algorithms to deduct the floor tiles instead. This was very interesting and creates even more interesting rooms. So to implement this, I just deducted the floor positions from the hashset instead of adding it to the hashset. Fortunately I do not have to worry about tiles being inaccessible because the flood fill algorithm will take care of that.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n
                                  \"https:\/\/cdn.discordapp.com\/attachments\/1024650869200920576\/1037869022915600504\/unknown.png\"<\/figure>\n\n\n\n

                                  3.6 Scriptable Objects<\/h2>\n\n\n\n

                                  Since the base framework makes use of the scriptable objects to store parameters for the algorithms, I did the same with the other algorithms that I have implemented.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n

                                  This is an example of how a scriptable object with parameters would look like.<\/p>\n\n\n\n

                                  I went a bit further and implement a way to put these parameters in a list. This is called an algorithm set which contains a list of these scriptable objects. You can add the algorithm sets to the room level parameter scriptable object which will be used for the dungeon generator. So if you want the dungeon generator to use multiple algorithm sets for the room generation, you can.<\/p>\n\n\n\n

                                  \"\"<\/figure>\n\n\n\n
                                  <\/div>\n\n\n\n

                                  4. Conclusion<\/h2>\n\n\n\n

                                  I have learned a lot during the past few weeks. I never thought there were this many algorithms in the procedural content generation topic. I kept hearing about cellular automata during my study but that\u2019s pretty much all I know about PCG before I started with this semester.<\/p>\n\n\n\n

                                  Now that I have implemented some of the PCG algorithms, I have a much better understanding regarding how they work and when you should use it.<\/p>\n\n\n\n

                                  Unfortunately I did not reach my goal since it\u2019s missing some of its key features. This will be explained further in the next chapter.<\/p>\n\n\n\n

                                  5. What the future holds<\/h2>\n\n\n\n

                                  There\u2019s a lot to improve on this project and there are missing features that are quite important to fix some of the problems.<\/p>\n\n\n\n

                                  At this moment I haven\u2019t implemented the Minimum Spanning Tree and Delaunay triangulation, this is really unfortunate because I want to connect the rooms together by using the shortest route. Then I can use the other edges to make loops in the dungeon so it won\u2019t be linear.<\/p>\n\n\n\n

                                  The room types are all the same except for the start and end rooms. There can be something added there to check whenever a room should be a different kind of room (like a treasure room).<\/p>\n\n\n\n

                                  The way how the walls are placed is static; you don\u2019t really have any control over the kind of wall sprite you want to place there. So improvements can be made in that part of the algorithm.<\/p>\n\n\n\n

                                  The implementation of diffusion limited aggregation is still missing some of the features such as being able to mirror the other half.  <\/p>\n\n\n\n

                                  Flood fill takes a long time to complete, I should see if there's a better way to detect these regions or optimize it further.<\/p>\n\n\n\n

                                  <\/div>\n\n\n\n

                                  Bibliography <\/h1>\n\n\n\n