game dev stuff #2

binary space partitioning procedural dungeon generation

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.

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.