binary space partitioning
or how to generate some cool dungeons with minimal effort
In this blog post, we’ll explore how to implement a binary space partitioning algorithm for procedural dungeon generation like in this posts image.
How did you do it?
The first step in implementing a BSP algorithm is to define the data structures that we’ll use to represent the dungeon.
class Area Area parent Area leftChild Area rightChild int x, y, width, height class Room Area parent int x, y, width, height
Once we have our data structures defined, we can begin the BSP algorithm. The first step is to create a root node that represents the entire dungeon space.
root_area = Area(x, y, width, height) bsp(root_area, 10)
All that’s left is the basic logic for the bsp() algorithm itself which is fairly easy as well.
def bsp(area, iterations): stop if iterations == 0 if random_value >= .5 split horizontal: split_value = any value from area.y to area.y + area.height area.leftChild = Area(area.x, area.y, area.width, split_value) area.rigthChild = Area(area.x, split_value, area.width, area.height - split_value) else split vertical split_value = any value from area.x to area.x + width area.leftChild = Area(area.x, area.y, split_value, area.height) area.rigthChild = Area(area.x, split_value, area.width - split_value, area.height) bsp(area.leftChild, iterations - 1) bsp(area.rightChild, iterations - 1)
The bsp functions takes a node and the number of iterations until the algorithm should stop splitting the areas any further.
Afterwards one just has to iterate over all areas which do not have any children. Theses are the trees leaves and this is where we want to place our rooms.
Rooms can be created with any rule but I sticked with a rather simple approach that takes a random value of its area’s width and height.
Creating procedural dungeons can be fairly easy and each approach offers some nice way to customize it further making each a versatile tool for different scenarios.