Advertisement

How to Use BSP Trees to Generate Game Maps

by

When filling in an area randomly with objects, like rooms in a random dungeon, you run the risk of making things too random, resulting in clumping or just an unusable mess. In this tutorial, I will show you how to use Binary Space Partitioning to solve this problem.

I will be leading you through some general steps to use BSP to make a simple, 2D map, which could be used for a dungeon layout for a game. I will show you how to make a basic Leaf object, which we will use to divide an area up into small segments; then, how to generate a random room in each Leaf; and, finally, how to connect all of the rooms together with hallways.

Note: While the example code here uses AS3, you should be able to use the concepts in pretty much any language you want.

Demo Project

I've created a demo program that shows off some of the power of BSP. The demo is written using Flixel, a free, open-source AS3 library for making games.

When you click the Generate button, it runs through the same code as above to generate some Leafs, and then draws them on to a BitmapData object, which it then displays (scaled up to fill the screen).

Screenshot from Demo program - Generating the Random Map
Generating the Random Map. (Click to load the demo.)

When you hit the Play button, it passes the generated map Bitmap over to the FlxTilemap object, which then generates a playable tilemap and shows it on the screen for you to walk around in:

Screenshot from Demo program - Playing the Map
Playing the Map. (Click to load the demo.)

Use the arrow keys to move.


What is BSP?

Binary Space Partitioning is a method of dividing an area into smaller pieces.

Basically, you take an area, called a Leaf, and split it—either vertically or horizontally—into two smaller Leafs, and then repeat the process on the smaller areas over and over again until each area is at least as small as a set maximum value.

When you're done, you have a hierarchy of partitioned Leafs, which you can do all sorts of things with. In 3D graphics, you might use BSP to sort which objects are visible to the player, or to help with collision detection in smaller, bite-sized pieces.


Why Use BSP to Generate Maps?

If you want to generate a random map, there are all sorts of ways to go about it. You could write simple logic to create randomly sized rectangles at random locations, but this can leave you with maps that are full of overlapping, clumped, or strangely-spaced rooms. It also makes it a little more difficult to connect the rooms to each other and to ensure that there are no orphaned rooms.

With BSP, you can guarantee more evenly-spaced rooms, while also making sure you can connect all the rooms together.


Creating Leafs

The first thing we need is to create our Leaf class. Basically, our Leaf is going to be a Rectangle, with some extra functionality. Each Leaf will either contain a pair of children Leafs, or a pair of Rooms, as well as a hallway or two.

Here's what our Leaf looks like:

Now, you need to actually create your Leafs:

After this loop finishes, you'll be left with a Vector (a typed array) full of all your Leafs.

Here's an example with lines separating each Leaf:

Sample of an area divided by Leafs
Sample of an area divided by Leafs

Creating Rooms

Now that your Leafs are defined, we need to make the rooms. We want a sort of 'trickle-down' effect where we go from our biggest, 'root' Leaf all the way to our smallest Leafs with no children, and then make a room in each one of those.

So, add this function to your Leaf class:

Then, after you've created your Vector of Leafs, call our new function from your root Leaf:

Here's an example of some generated Leafs with rooms inside of them:

Sample of Leafs with random room inside each one.
Sample of Leafs with random room inside each one.

As you can see, each Leaf contains a single room with a random size and position. You can play with the values for minimum and maximum Leaf size, and alter how you determine the size and position of each room, to get different effects.

If we remove our Leaf separator lines, you can see that the rooms fill the entire map nicely—there's not a lot of wasted space—and have a slightly more organic feel to them.

Sample of Leafs with a room inside each one, separator lines removed.
Sample of Leafs with a room inside each one, with separator lines removed.

Connecting Leafs

Now, all we need to do is connect each room. Thankfully, since we have the built-in relationships between Leafs, all we have to do is make sure that each Leaf that has child Leafs has a hallway that connects its children.

We'll take a Leaf, look at each of its children Leafs, go all the way through each child until we get to a Leaf with a room, and then connect the rooms together. We can do this at the same time we generate our rooms.

First, we need a new function to iterate from any Leaf into one of the rooms that are inside one of the child Leafs:

Next, we need a function that takes a pair of rooms, picks a random point inside both rooms, and then creates either one or two two-tile-thick rectangles to connect the points together.

Finally, change your createRooms() function to call the createHall() function on any Leaf that has a pair of children:

Your rooms and hallways should now look something like this:

Sample of Leafs filled with random rooms connected via hallways
Example of Leafs filled with random rooms connected via hallways.

As you can see, because we are making sure to connect every Leaf, we're not left with any orphan rooms. Obviously, the hallway logic could be a little more refined to try to avoid running too close to other hallways, but it works well enough.


Finishing Up

That's basically it! We've covered how to create a (relatively) simple Leaf object, which you can use to generate a tree of divided Leafs, generate a random room inside each Leaf, and connect the the rooms via hallways.

Currently, all the objects we created are essentially rectangles, but depending on how you intend to use the resulting dungeon, you can handle them in all sorts of ways.

Now you can use BSP to make any kind of random maps you want, or use it to evenly distribute power ups or enemies across an area... or whatever you want!

Advertisement