# How to Use BSP Trees to Generate Game Maps

Difficulty:IntermediateLength:MediumLanguages:

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).

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:

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`:

## 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:

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.

## 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:

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!