# How to Use BSP Trees to Generate Game Maps

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.

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

public class Leaf { private const MIN_LEAF_SIZE:uint = 6; public var y:int, x:int, width:int, height:int; // the position and size of this Leaf public var leftChild:Leaf; // the Leaf's left child Leaf public var rightChild:Leaf; // the Leaf's right child Leaf public var room:Rectangle; // the room that is inside this Leaf public var halls:Vector.; // hallways to connect this Leaf to other Leafs public function Leaf(X:int, Y:int, Width:int, Height:int) { // initialize our leaf x = X; y = Y; width = Width; height = Height; } public function split():Boolean { // begin splitting the leaf into two children if (leftChild != null || rightChild != null) return false; // we're already split! Abort! // determine direction of split // if the width is >25% larger than height, we split vertically // if the height is >25% larger than the width, we split horizontally // otherwise we split randomly var splitH:Boolean = FlxG.random() > 0.5; if (width > height && height / width >= 0.05) splitH = false; else if (height > width && width / height >= 0.05) splitH = true; var max:int = (splitH ? height : width) - MIN_LEAF_SIZE; // determine the maximum height or width if (max <= MIN_LEAF_SIZE) return false; // the area is too small to split any more... var split:int = Registry.randomNumber(MIN_LEAF_SIZE, max); // determine where we're going to split // create our left and right children based on the direction of the split if (splitH) { leftChild = new Leaf(x, y, width, split); rightChild = new Leaf(x, y + split, width, height - split); } else { leftChild = new Leaf(x, y, split, height); rightChild = new Leaf(x + split, y, width - split, height); } return true; // split successful! } }

Now, you need to actually create your `Leafs`

:

const MAX_LEAF_SIZE:uint = 20; var _leafs:Vector<Leaf> = new Vector<Leaf>; var l:Leaf; // helper Leaf // first, create a Leaf to be the 'root' of all Leafs. var root:Leaf = new Leaf(0, 0, _sprMap.width, _sprMap.height); _leafs.push(root); var did_split:Boolean = true; // we loop through every Leaf in our Vector over and over again, until no more Leafs can be split. while (did_split) { did_split = false; for each (l in _leafs) { if (l.leftChild == null && l.rightChild == null) // if this Leaf is not already split... { // if this Leaf is too big, or 75% chance... if (l.width > MAX_LEAF_SIZE || l.height > MAX_LEAF_SIZE || FlxG.random() > 0.25) { if (l.split()) // split the Leaf! { // if we did split, push the child leafs to the Vector so we can loop into them next _leafs.push(l.leftChild); _leafs.push(l.rightChild); did_split = true; } } } } }

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:

public function createRooms():void { // this function generates all the rooms and hallways for this Leaf and all of its children. if (leftChild != null || rightChild != null) { // this leaf has been split, so go into the children leafs if (leftChild != null) { leftChild.createRooms(); } if (rightChild != null) { rightChild.createRooms(); } } else { // this Leaf is the ready to make a room var roomSize:Point; var roomPos:Point; // the room can be between 3 x 3 tiles to the size of the leaf - 2. roomSize = new Point(Registry.randomNumber(3, width - 2), Registry.randomNumber(3, height - 2)); // place the room within the Leaf, but don't put it right // against the side of the Leaf (that would merge rooms together) roomPos = new Point(Registry.randomNumber(1, width - roomSize.x - 1), Registry.randomNumber(1, height - roomSize.y - 1)); room = new Rectangle(x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y); } }

Then, after you've created your `Vector`

of `Leafs`

, call our new function from your root `Leaf`

:

_leafs = new Vector<Leaf>; var l:Leaf; // helper Leaf // first, create a Leaf to be the 'root' of all Leafs. var root:Leaf = new Leaf(0, 0, _sprMap.width, _sprMap.height); _leafs.push(root); var did_split:Boolean = true; // we loop through every Leaf in our Vector over and over again, until no more Leafs can be split. while (did_split) { did_split = false; for each (l in _leafs) { if (l.leftChild == null && l.rightChild == null) // if this Leaf is not already split... { // if this Leaf is too big, or 75% chance... if (l.width > MAX_LEAF_SIZE || l.height > MAX_LEAF_SIZE || FlxG.random() > 0.25) { if (l.split()) // split the Leaf! { // if we did split, push the child Leafs to the Vector so we can loop into them next _leafs.push(l.leftChild); _leafs.push(l.rightChild); did_split = true; } } } } } // next, iterate through each Leaf and create a room in each one. root.createRooms();

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`

:

public function getRoom():Rectangle { // iterate all the way through these leafs to find a room, if one exists. if (room != null) return room; else { var lRoom:Rectangle; var rRoom:Rectangle; if (leftChild != null) { lRoom = leftChild.getRoom(); } if (rightChild != null) { rRoom = rightChild.getRoom(); } if (lRoom == null && rRoom == null) return null; else if (rRoom == null) return lRoom; else if (lRoom == null) return rRoom; else if (FlxG.random() > .5) return lRoom; else return rRoom; } }

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.

public function createHall(l:Rectangle, r:Rectangle):void { // now we connect these two rooms together with hallways. // this looks pretty complicated, but it's just trying to figure out which point is where and then either draw a straight line, or a pair of lines to make a right-angle to connect them. // you could do some extra logic to make your halls more bendy, or do some more advanced things if you wanted. halls = new Vector<Rectangle>; var point1:Point = new Point(Registry.randomNumber(l.left + 1, l.right - 2), Registry.randomNumber(l.top + 1, l.bottom - 2)); var point2:Point = new Point(Registry.randomNumber(r.left + 1, r.right - 2), Registry.randomNumber(r.top + 1, r.bottom - 2)); var w:Number = point2.x - point1.x; var h:Number = point2.y - point1.y; if (w < 0) { if (h < 0) { if (FlxG.random() * 0.5) { halls.push(new Rectangle(point2.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); } else { halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point2.y, 1, Math.abs(h))); } } else if (h > 0) { if (FlxG.random() * 0.5) { halls.push(new Rectangle(point2.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point1.y, 1, Math.abs(h))); } else { halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); } } else // if (h == 0) { halls.push(new Rectangle(point2.x, point2.y, Math.abs(w), 1)); } } else if (w > 0) { if (h < 0) { if (FlxG.random() * 0.5) { halls.push(new Rectangle(point1.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point2.y, 1, Math.abs(h))); } else { halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); } } else if (h > 0) { if (FlxG.random() * 0.5) { halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); halls.push(new Rectangle(point2.x, point1.y, 1, Math.abs(h))); } else { halls.push(new Rectangle(point1.x, point2.y, Math.abs(w), 1)); halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); } } else // if (h == 0) { halls.push(new Rectangle(point1.x, point1.y, Math.abs(w), 1)); } } else // if (w == 0) { if (h < 0) { halls.push(new Rectangle(point2.x, point2.y, 1, Math.abs(h))); } else if (h > 0) { halls.push(new Rectangle(point1.x, point1.y, 1, Math.abs(h))); } } }

Finally, change your `createRooms()`

function to call the `createHall()`

function on any `Leaf`

that has a pair of children:

public function createRooms():void { // this function generates all the rooms and hallways for this Leaf and all of its children. if (leftChild != null || rightChild != null) { // this leaf has been split, so go into the children leafs if (leftChild != null) { leftChild.createRooms(); } if (rightChild != null) { rightChild.createRooms(); } // if there are both left and right children in this Leaf, create a hallway between them if (leftChild != null && rightChild != null) { createHall(leftChild.getRoom(), rightChild.getRoom()); } } else { // this Leaf is the ready to make a room var roomSize:Point; var roomPos:Point; // the room can be between 3 x 3 tiles to the size of the leaf - 2. roomSize = new Point(Registry.randomNumber(3, width - 2), Registry.randomNumber(3, height - 2)); // place the room within the Leaf, but don't put it right against the side of the leaf (that would merge rooms together) roomPos = new Point(Registry.randomNumber(1, width - roomSize.x - 1), Registry.randomNumber(1, height - roomSize.y - 1)); room = new Rectangle(x + roomPos.x, y + roomPos.y, roomSize.x, roomSize.y); } }

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!