In working to make level randomization as interesting as possible in this iteration, I decided to try to take additional time to refactor a proven method, partially as a development exercise and partially to give the gameplay a bit more of a spin. As a dungeoncrawler, hewing close to the “Gauntlet” bone of hacking and slashing, while still trying to bring something unique to the table. I decided to do some custom carving to the BSP Dungeon generation concept that has been useful in every generation of roguelike.
From gamers.org:
A Binary Space Partitioning (BSP) tree represents a recursive, hierarchical partitioning, or subdivision, of n-dimensional space into convex subspaces. BSP tree construction is a process which takes a subspace and partitions it by any hyperplane that intersects the interior of that subspace.
To adapt it to my needs I first decided that I didn’t want corridors. In this particular game, I didn’t think they would serve to make the gameplay more interesting. In my testing, having a stealth element along with a heavier emphasis on inventory management makes long thin rooms more of an interesting texture to include. While S2 does have some of the above mechanics, I still thought the game would benefit from a different approach.
The first step is to define the level size, and then start subdividing to achieve room grids. This first gif shows the sectioning taking place. The prospective room will need to fit inside of the grid section, room size being dictated by the room walls proximity to the grid subdivisions.
From there, the rooms are generated directly touching other with no corridors being spawned. Running a modified Jumper run checking for random coordinates within the spawned rooms, while traveling on walkable tiles, create door tiles that will be painted later.
During room generation, the expansion function is setting wall and floor values in line with the room size value. This way, it’s more efficient to write a function to handle identifying the interactive doors and static walls that will exist during gameplay. I considered using this phase to identify potential level objects and their best locations, but I ultimately decided against it since it would be better to run with that after the level solve state is confirmed.
Above, you can see doors being placed in locations where the player can access them, away from corners to into level void that contains no interactivity. Now at this stage, I am comfortable dropping interactive level objects, so that I know they won’t interfere with pathfinding and will be available for the player to destroy. From there, the tile values are passed to the identifying function, and the appropriate wall/floor/door/level object is placed, and given a physics object if necessary.
The result has been a positive gameplay experience which can be scaled for difficulty. A few tweaks were needed here and there, but ultimately it’s solid and works very well as a basis for PCG level generation in this roguelike. If anyone is interested in some pseudo-code I can work something up.
Additional reading on BSP and general procedural room generation:
http://www.gridsagegames.com/blog/2014/06/procedural-map-generation/
https://www.youtube.com/watch?v=UFrF2-U_VTs
