Dungeon Generation using Binary Space Trees

The tricky part in procedural generation is not to make things random, but to make them in a consistent way despite it’s randomness. In particular, when making a dungeon you have to face the problem of filling the space with elements in a natural way.

There’s a technique used for filling a plane with rooms that uses binary space partitioning, a a method for recursively subdividing a space into two sets.

Dividing a square into two recursively

So basically we’re going to use the space divisions generated by this method to define the area a room will use and the tree defined implicitly by it to know which rooms to connect.

Making rooms and connecting them using a binary space partition

I’ll teach you how to implement your own generator. I’ll be using C# and Unity to write the examples, but you should be able to use this techniques on any language and engine you want.

Step One: Space Division

So the first thing we need to do is to define a class that represents an area on this space. I’ve created the class Room defined by it’s four borders and with a few auxiliar methods to get it’s width and height.

We also want a way to display those rooms on the screen, so I’ll write a Draw function to do it:

With this we can just create a new room and call it’s Draw method to see it on screen like so:

Great! We’ve drawn a square.

Alright so here’s were the fun begins, we want to divide those squares into two rooms, selecting the cut orientation (horizontal or vertical) randomly. So to do that I’ll extend the Room class with theBinaryRoom class.

First we need to define the min and max dimensions of our rooms and to keep track of the cut orientation and the two child rooms.

Let’s start working on the split function. First we want to attempt a random split in a random direction and check we’re not making a room too small. Then, if the random split couldn’t be done, we need to make sure we’re not surpassing the max directions and force a split if necesary.

For the actual split code we separate each room in two parts making the cut in a random position without making rooms too small:

And lastly we can override the draw function so it propagates through the whole tree only drawing the leaf nodes that contain the actual rooms:

Then if we create a BinaryRoom and call the Split and Draw methods we’ll get something like this:

Step Two: Adding Borders

So we got a random division, but we don’t want the rooms to use the whole space, so let’s add a method to cut their borders recursively:

In this case I’m allways cutting the borders with the same thickness, but you can add randomness to it.

If we call Trim before drawing the rooms we should get an image like this:

Step Three: Adding Corridors

The last step on the generation is to add the corridors, we’re gonna do this by recursively connecting each node with it’s sibling.

But to do so, first we need to know where can we make the connections. For example, if we want to connect an area to another on it’s right we can do it on the following points (marked with red):

So let’s create a function to get all the positions from an area where we can add corridors to the right:

As you can see, we’re just taking the rooms to the right and returning their y positions, I’ve made similar functions to get connections to the Top, Left and Bottom.

Now we need to get the intersection between the connections of the two areas we want to connect, and group the uninterrupted positions so we can select one group and add it to our corridor:

Using the groups returned by this function we can randomly choose one and create a corridor with it resulting in a map like this:

Just make sure to only connect sibling nodes, I’m using this method to do it:

Now you can adjust some parameters as you want and start generating dungeons!