Binary Space Partitioning

by Derek (2026-10-16)

Let's talk about map generation.

I bet I know what you're thinking: We already talked about that. Well, yes. But, actually no. Map generation is a large topic. We're going to talk about this a lot.

The Basic Map Generation placed rooms at random. Probably a little too at random. It led to a lot of overlapping; both rooms and corridors.

What we're going to try this time is called Binary Space Partition, or BSP. With this, we divide up the space and place rooms evenly across the map. More specifically, we'll start with our entire map. Then we'll choose either to split horizontally or split vertically. Then we'll choose someplace around the middle (for some loose definition of middle) so that both sides are big enough to hold rooms. This leaves us with two ~~maps~~ regions. And then we just recursively split those regions. And keep going until the regions are about the right size. In our python flavored pseudocode:

def split(map):
  if rightSize():
    return

  if horizontalSplit():
    splitPosition = random()
    map.left = top(splitPosition)
    map.right = bottom(splitPosition)
  else:
    splitPosition = random()
    map.left = left(splitPosition)
    map.right = right(splitPosition)

  split(map.left)
  split(map.right)

Those of you paying close attention will notice that we haven't actually built a game map. What we've built is a binary tree of regions in the map. Let's see what it looks like:

It's a good start. We've split up the map into regions. But we don't actually have rooms, yet. So, what we're going to do is walk our tree. There are options for how to walk a binary tree. What works best for our purpose is a post-traversal. This means that we do something at a node after dealing with it's children. The code looks a little like this:

def postTraverse(map, f):
  if map has left:
    postTraverse(map.left, f)
  if map has right:
    postTraverse(map.right, f)
  f(map)

Now, we just need to figure out what to do at each node. The leaves are easy: we carve out a room. And we'll use our random number generator to give it a little variety in height and width. Now, if it isn't a leaf, then we know that there's both a left node and a right node by how we constructed the tree. So, we'll just connect the left branch to the right branch with a corridor.

def cavreOut(map):
  if map has left:
    map.left.connect(map.right)
  else:
    randomRoom(map)

As always the devil is in the details. There are several choices for how we connect the left and right nodes. What I've chosen to do, because I think it creates the cleanest looking map, is connect the closest pair of rooms from the right and left node. Pulling this all together give us this map:

Nice rooms. Corridors that don't crash through rooms. There is a problem with it, though: There are no loops. If we want to go from one room to another, there's only a single path. I consider that an important part of roguelike maps. There's a solution to this, and we'll talk about it. But, not today.