Procedural generation is seen by many as a means to an end for the generation of expansive worlds but procedural generation has so many more applications. For instance, it can be used to create a
host of AIs with a multitude of personas to solve a variety of problems or it can be used to create a large system of content, like equipable items that drop randomly within a game. I believe that
procedural generation is a tool that could be used to solve a vast array of problems both in video games and in the real world.
This project’s goal is to implement two procedural generation techniques in a dungeon/rogue-like game, expand them in an attempt to make them more efficient or scalable, and compare them under headings such as efficiency and extensibility. Efficiency includes metrics such as runtime performance, separated into core and post-processing runtime, and memory usage. Extensibility considers how easy it is for a programmer to extend or customize the implementation. Efficiency is focussed on CPU cycles whereas extensibility is focussed on “developer cycles”.
The two techniques that were selected in this project's implementation are Binary Spatial Partitioning (BSP) and Cellular Automaton (CA). I chose these two techniques because they are on opposite ends of the spectrum when it comes to procedural generation techniques and produces extremely different visual results. BSP is a top-down algorithm where we take a predefined area and alter this area based on constraints defined by the user whereas CA is a node-based algorithm where the grid is altered based on a set of constant rules that are applied to the current version of the game for a certain number of iterations.
Once the two techniques were implemented in the dungeon/rogue-like setting, I took both algorithms and extended them to increase their efficiency and scalability. Specifically, I added functionality to the CA algorithm that would increase its efficiency. To do this, I processed an initial area, defined by the user, and using directional input the user is able to process the grid in any direction. This functionality is a form of asynchronous loading that could be used to process areas of the map that the user will visit therefore eliminating unnecessary computations for areas that will never be explored. This was a good indicator to see how extensible each algorithm is and if they would be a good fit for a dungeon/rogue-like game.
After I implemented the additional functionality to extend the existing implementation, I analyzed each technique under the headings discussed above. I then ran some iterations of the project recording data on each algorithm and comparing them. This in-depth analysis will give a better understanding as to which algorithm would be better suited in the setting of a dungeon/ rogue-like game and for a developer at my stage of learning.
Github Link :