The entire week was spent on a new dungeon layout algorithm. Binary space partitioning (BSP) has been replaced by what I’m calling dynamic space partitioning. Dungeon generation now occurs by adjoining new rooms to existing rooms. It’s similar, at a high level, to the Dungeon-Building Algorithm from Mike Anderson. A key difference is that before generating and placing a new room, the maximum amount of free space available from a connection point on the edge of an existing room is calculated, thus creating a new partition. When the new room is placed, the partition is resized to match the size of the new room, releasing the unused space from the original partition. This approach yields a more rational dungeon layout (if a dungeon layout can ever be considered rational), prevents overlapping rooms, and is more efficient than similar approaches that randomly generate new rooms until finding a room that fits.
I had hoped to have some amazing example maps to share by the end of the week. The core algorithm has been implemented, but it produces terrible maps in its current state. The sizes of rooms and corridors are completely random (within their bounding boxes), as is distribution and number of connection points per feature. More logic is required to generate playable, sensible maps, but I’m not certain of how much more yet. My plan is to identify common patterns in the many hand-drawn dungeon maps I’ve collected and generate rules from those patterns. I do miss some of the benefits of BSP – filling the entire map space is guaranteed, creating corridors between sibling nodes is simple and clean, and using different themes for different sections of the dungeon was easy.
Next week, I’ll continue to focus on the new dungeon layout generator. My plan for a playable demo by the end of 2022 is still possible (I’m not replacing the entire map generator, just the first step that places rooms and corridors), but less likely with the increased scope.