I’ve been researching different methods of random dungeon generation. After reading about a few different methods, I decided to try to use binary space partitioning (BSP) to generate dungeons for my game. BSP trees are frequency used in games, perhaps most notably in Quake, there they are used to determine visibility.
I implemented a recursive node structure in Swift, where each node can have children nodes that contain rooms. Each parent node links it’s children nodes with hallways. Repeating this process creates a traversable dungeon. Tonight I’ve finally worked out most of the bugs, so the dungeon is reasonably presentable.
In this screenshot is my current build, developed using Apple’s SpriteKit game framework.