Procedural Generation

Author: Adam Stagg

For our game, we want to have procedurally generated dungeons that the player will go to when they leave the hub world. We had a pre-built dungeon for testing purposes, but we did not have a procedural generation algorithm yet. I started researching into the wave function collapse algorithm, and looked to implement this for our dungeons. This would be a way to randomly make dungeons that have controllable parameters, and are dynamic in nature. There are not pre-built rooms, but instead tiles with sockets (connections between tiles) that govern how the dungeon can be pieced together.

This algorithm was implemented in stages. First, I wanted to randomly place tiles to verify that the sizing and spacing of tiles was correct. After this, I implemented rotations for tiles, so they can rotate in the world. This added a new issue, the sockets needed to be rotates as well. Not only that, but sometimes rotating a socket will make it change which tiles it can connect to. This was solved by adding a _v0, _v1, _v2, or _v3 to the socket to tell which rotation the socket is. After I got all of the rotation logic done, it was time for the actual generation part. To do this, I implemented a priority queue system. Tiles that have less possibilities will be generated first, and work outwards from that. Whenever a tile is placed, the potential tiles will propagate to the neighbors. This part is currently implemented, however the priority queue is currently not giving the expected results. By next build, this will be fully implemented and have dungeons generating.