- 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.
Additional reading on BSP and general PCG room generation: