Procedural 2D Grid Dungeon Generator
I am always a big fan of roguelike games like Binding of Isaac and procedural sandbox games like Terraria, so for my master's thesis, I made a procedural dungeon generator create artificial and natural looking levels with clear gameplay purpose in mind. Where the path to the next level is reasonable, enemies and loots are evenly spread out, and path doesn’t cross each other. Also worth mentioning, the dungeon and all object inside it is generated with noise, which means they are always going to be the same as long as the inputs and the seed is the same.
Binary Space Partition:
The first challenge for me is that the dungeon need to be evenly spread out throughout the map and connected. The method I choose is Binary Space Partition, I cut the map into multiple pieces at middle, then connect them with tunneling algorithm. The unused room become consider split path and connected to the closest main path afterward. After the dungeon's layout is decided, I only need to render the rooms and path as square rooms and corridors to get a level that looks like it came from mystery dungeon.
Cellular Automata:
By using cellular automata B678/S345678 I was able to consistently create cave looking structure, but the problem is to ensure the cave is connected and evenly spread out. Instead of randomly initialize the noise map for cellular automata, I needed something that would maintain the layout of the dungeon. First I tried to make tiles closer to the path have high chance to be open, but that results in the cave extremely tight and straight. Instead of following the path, I made the cave avoid spaces between the path to prevent it from crossing.
Gameplay Object
To generate gameplay objects such as monsters and chests, I have a list of customizable bias variable to calculate the chance for objects to spawn at a specific position. First, I get heat maps for the main path, split path, and gameplay object. Then I multiply the heatmap value with the bias, add the results together and store them in a weighted list. For example, if a monster have a spawn bias of main path: 1, side path: .5, monster: -1, chest: 1, that means it have higher chance to spawn near a main path than a side path, unlikely to spawn near another enemy, and likely to spawn near a chest.
