In this blog post, we’ll explore how to implement a binary space partitioning algorithm for procedural dungeon generation like in the following 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, heightOnce 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.
Bottom Line
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.
