作者：Timothy Hely
当用对象随机填充某个区域如地下城中的房间时，你可能会遇到的问题是太过随机，导致分布疏密不均或混乱。在本教程中，我将告诉大家如何使用二进制空间划分法（游戏邦注：即Binary Space Partitioning，简称为BSP，这种方法每次将一实体用任一位置和任一方向的平面分为二部分。）来解决这个问题。
我将分成几个步骤教你如何使用BSP来制作一个简单的2D地图，这个方法可以用于布局游戏中的地下城。我将教你如何制作一个基本的Leaf对象，我们将用它把区域划分成几个小分区；如何在各个Leaf中生成随机房间；如何用走廊把各个房间接通。
注：虽然这里使用的代码是AS3写的，但你应该可以把它转换成其他语言。
样本项目
我已经制作了一个能够证明BSP的强大的样本程序。这个样本是用免费的开源AS3库Flixel写的。
当你点击Generate按钮时，它就会运行相同的代码生成一些Leaf，然后把它们绘制到BitmapData对象，并显示出来（按比例以填满屏幕）。
Binary_Space_Partitioning_for_Maps_Gamedev_Screen-Demo（from tutsplus）
生成随机地图
当你点击Play按钮，它就会把生成的地图Bitmap传给FlxTilemap对象，后者再生成一个可玩的瓷砖地图，并把它显示在屏幕上：
Binary_Space_Partitioning_for_Maps_Gamedev_Screen-Demo（from tutsplus）
显示地图
使用方向键移动。
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 Leafpublic var rightChild:Leaf; // the Leaf’s right child Leafpublic var room:Rectangle; // the room that is inside this Leafpublic var halls:Vector.; // hallways to connect this Leaf to other Leafs
public function Leaf(X:int, Y:int, Width:int, Height:int){// initialize our leafx = X;y = Y;width = Width;height = Height;}
public function split():Boolean{// begin splitting the leaf into two childrenif (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 randomlyvar 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 widthif (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 splitif (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的案例：
Binary_Space_Partitioning_for_Maps_Gamedev_Screen（from tutsplus）
用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 leafsif (leftChild != null){leftChild.createRooms();}if (rightChild != null){rightChild.createRooms();}}else{// this Leaf is the ready to make a roomvar 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的案例：
Binary_Space_Partitioning_for_Maps_Gamedev_Screen（from tutsplus）
如你所见，每个Leaf都包含一个房间，大小和位置是随机的。你可以调整Leaf的大小和位置，以得到不同的布局。
如果我们移除Leaf的分隔线，你可以看到房间充满整个地图—-浪费了很多空间，并且显得太过条理。
Binary_Space_Partitioning_for_Maps_Gamedev_Screen（from tutsplus）
带房间的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;elsereturn 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 leafsif (leftChild != null){leftChild.createRooms();}if (rightChild != null){rightChild.createRooms();}
// if there are both left and right children in this Leaf, create a hallway between themif (leftChild != null && rightChild != null){createHall(leftChild.getRoom(), rightChild.getRoom());}
}else{// this Leaf is the ready to make a roomvar 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);}}
现在你的房间和走廊应该如下图所示：
Binary_Space_Partitioning_for_Maps_Gamedev_Screen（from tutsplus）
房间被走廊沟通的Leaf案例
正如你所见，所有Leaf都是相互沟通的，不留任何一个孤立的房间。显然，走廊逻辑可以更精确一点，避免太接近其他走廊，但现在这样已经够好了。
总结
以上！我介绍了如何生成（比较）简单的Leaf对象，你可以用它生成分区Leaf和生成各个Leaf内的随机房间，最后用走廊沟通所有房间。
目前我们制作的所有对象都是矩形的，但根据你将如何使用地下城，你可以对它们进行其他处理。
现在你可以使用BSP制作任何一种你需要的随机地图，或使用它平均分布区域内的增益道具或敌人。
在游戏邦看到一篇不错的贴子，转一下。备用。
转载于:https://www.cnblogs.com/pelephone/p/bsp-tree-game.html
相关资源：linux自动删除文件