作者：Timothy Hely

当用对象随机填充某个区域如地下城中的房间时，你可能会遇到的问题是太过随机，导致分布疏密不均或混乱。在本教程中，我将告诉大家如何使用二进制空间划分法（游戏邦注：即Binary Space Partitioning，简称为BSP，这种方法每次将一实体用任一位置和任一方向的平面分为二部分。）来解决这个问题。

我将分成几个步骤教你如何使用BSP来制作一个简单的2D地图，这个方法可以用于布局游戏中的地下城。我将教你如何制作一个基本的Leaf对象，我们将用它把区域划分成几个小分区；如何在各个Leaf中生成随机房间；如何用走廊把各个房间接通。

注：虽然这里使用的代码是AS3写的，但你应该可以把它转换成其他语言。

样本项目

我已经制作了一个能够证明BSP的强大的样本程序。这个样本是用免费的开源AS3库Flixel写的。

当你点击Generate按钮时，它就会运行相同的代码生成一些Leaf，然后把它们绘制到BitmapData对象，并显示出来（按比例以填满屏幕）。

生成随机地图

当你点击Play按钮，它就会把生成的地图Bitmap传给FlxTilemap对象，后者再生成一个可玩的瓷砖地图，并把它显示在屏幕上：

显示地图

使用方向键移动。

BSP是什么？

BSP是一种将区域分成更小的分区的方法。

基本做法就是，你把一个叫作Leaf的区域水平或竖直地分成两个更小的Leaf，然后在这两个Leaf上重复这个步骤，直到得到所需的房间数量。

完成上述步骤后，你就得到一个分区的Leaf，你可以在它上面布局对象。在3D图像中，你可以使用BSP分类哪些对象对玩家可见，或用于更小的空间中的碰撞检测。

为什么使用BSP生成地图？

如果你想生成随机地图，你可以使用的办法有很多种。你可以写一个简单的逻辑在随机地点生成随机大小的矩形，但这可能导致生成的地图出现大量重叠、集群或奇怪的房间。此外，增加了沟通房间的难度，且难以保证没有遗漏的房间未连上。

而使用BSP，可以保证房间布局平均，且所有房间都联系在一起。

生成Leaf

第一步是生成Leaf类。Leaf基本上是矩形的，具有一些额外的功能。各个Leaf都包含一对子Leaf或一对Room及一两个走廊。

我们的Leaf如下所示：

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!
}
}

现在才是真正生成Leaf：

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;
}
}
}
}
}

这个循环结束后，你的所有Leaf中都会包含一个Vector（一种集合）。

以下是分区的Leaf的案例：

用Leaf分区的案例

生成房间

你的Leaf做好后，我们就可以制作房间了。我们想要一种“涓流效果”，也就是从最大的“根”Leaf开始，一直划分到没有子项的最小的Leaf，然后在每个Leaf中做出房间。

把以下功能添加到Leaf类中：

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);
}
}

然后，制作好Leaf的Vector后，从你的根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();

以下是还有房间的Leaf的案例：

如你所见，每个Leaf都包含一个房间，大小和位置是随机的。你可以调整Leaf的大小和位置，以得到不同的布局。

如果我们移除Leaf的分隔线，你可以看到房间充满整个地图—-浪费了很多空间，并且显得太过条理。

带房间的Leaf，移除了分隔线。

沟通Leaf

现在，我们需要做的是沟通各个房间。幸好各个Leaf之间存在内部关系，我们只需要保证各个Leaf都能够与其子leaf相互连接。

我们把各个子Leaf内的房间连接起来。我们在生成房间时可以同时做沟通的工作。

首先，我们需要一个从所有Leaf开始迭代到各个子Leaf中的房间的新功能：

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;
}
}

然后，我们需要一个功能，它将选取一对房间并在二者内选中随机点，然后生成一两个两片瓷砖大小的矩形把点连接起来。

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)));
}
}
}

最后，改变createRooms()功能，以调用所有具有一对子Leaf的Leaf的createHall()功能：

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);
}
}

现在你的房间和走廊应该如下图所示：

房间被走廊沟通的Leaf案例

正如你所见，所有Leaf都是相互沟通的，不留任何一个孤立的房间。显然，走廊逻辑可以更精确一点，避免太接近其他走廊，但现在这样已经够好了。

总结

以上！我介绍了如何生成（比较）简单的Leaf对象，你可以用它生成分区Leaf和生成各个Leaf内的随机房间，最后用走廊沟通所有房间。

目前我们制作的所有对象都是矩形的，但根据你将如何使用地下城，你可以对它们进行其他处理。

现在你可以使用BSP制作任何一种你需要的随机地图，或使用它平均分布区域内的增益道具或敌人。

（本文为游戏邦/gamerboom.com编译，拒绝任何不保留版权的转载，如需转载请联系：游戏邦）

How to Use BSP Trees to Generate Game Maps

By Timothy Hely

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

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:

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:

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:

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:

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:

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

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:

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!(source:tutsplus)