binary space partitioning往往较多的在渲染中被提到，用于实现场景管理。这里我们说说用BSP实现的过程生成。
现在假设要生成一个由很多小房间组成的地形。我们假设用笨办法，不断地生成一个房间，然后不断挪动，把它放到能放的位置，接着再生成下一个……
这个办法看上去没什么问题，但是实际上如何让生成的房间排列的看起来比较正常，是很让人头疼的问题。
而我们使用BSP生成的话，问题便迎刃而解了。
方法很简单：先用BSP做随机的空间划分，然后在所有划分的最小格里放上一个房间即可，房间的位置大小根据需求来。
上文参考中做的空间划分
根据BSP如何进行“随机的划分”，最终结果可以变得非常有序，也可以“随心所欲”。
往划好的格子里填房间
在参考文中的最后建立连通性时，他通过空间和子空间的关系确定建立哪些连接来让房间连通。在我自己的实现中我还是用了传统的最小生成树的办法。
不过这里要提到一点是，在游戏中我们往往不需要寻求最优解或者是正确解，比如上一篇中提到的官方教程的代码的小错误，反而让结果变得更好。我在实现最小生成树连通时，给了一定的阈值，使得不属于最小生成树的一些边也会加入到图中，使最终的结果看起来更自然。
最小生成树生成的连通性
加入一点“额外允许”
代码部分。核心的划分规则和参考文中的差不多。只包括bsp生成，没有连通构造。
using UnityEngine;
using System.Collections;
namespace CS.MapGeneration {
public class Leaf {
public Leaf[] childLeaf = new Leaf[2];
public Leaf leftLeaf {
get {
return childLeaf[0];
}
set {
childLeaf[0] = value;
}
}
public Leaf rightLeaf {
get {
return childLeaf[1];
}
set {
childLeaf[1] = value;
}
}
public int width;
public int height;
public int x;
public int y;
public Room room;
public Leaf(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public Leaf() {
}
}
public class Room {
public int width;
public int height;
public int x;
public int y;
public Room(int x, int y, int width, int height) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
}
public Room() {
}
}
[System.Serializable]
public class BspGenrator {
public MapseedRandom random;
public Leaf Genrate(int width, int height) {
Leaf start = new Leaf(0, 0, width, height);
Split(start);
return start;
}
public int minSplitSize = 5;
public float stopSplitChance = 0.3f;
private void Split(Leaf leaf) {
bool splitH = random.GetNext() > 0.5f;
if ((float)leaf.width / leaf.height >= 1.25f)
splitH = false;
else if ((float)leaf.height / leaf.width >= 1.25f) {
splitH = true;
}
var max = (splitH ? leaf.height : leaf.width) - minSplitSize;
if (max <= minSplitSize || random.GetNext() < stopSplitChance)
return;
var split = (int)(random.GetNext() * (max - minSplitSize + 1) + minSplitSize);
if (splitH) {
leaf.leftLeaf = new Leaf(leaf.x, leaf.y, leaf.width, split);
leaf.rightLeaf = new Leaf(leaf.x, leaf.y + split, leaf.width, leaf.height - split);
} else {
leaf.leftLeaf = new Leaf(leaf.x, leaf.y, split, leaf.height);
leaf.rightLeaf = new Leaf(leaf.x + split, leaf.y, leaf.width - split, leaf.height);
}
Split(leaf.leftLeaf);
Split(leaf.rightLeaf);
}
}
[System.Serializable]
public class BspRoomGenerator {
public MapseedRandom random;
public int minGap = 1;
public int minRoomSize = 5;
public void SetRoom(Leaf leaf) {
bool doSet = true;
if (leaf.leftLeaf != null) {
SetRoom(leaf.leftLeaf);
doSet = false;
}
if (leaf.rightLeaf != null) {
SetRoom(leaf.rightLeaf);
doSet = false;
}
if (!doSet)
return;
if (leaf.width < minRoomSize + minGap || leaf.height < minRoomSize + minGap)
return;
var width = (leaf.width - minRoomSize - minGap + 1) * random.GetNext() + minRoomSize;
var height = (leaf.height - minRoomSize - minGap + 1) * random.GetNext() + minRoomSize;
var x = leaf.x + (leaf.width - minGap - width + 1) * random.GetNext();
var y = leaf.y + (leaf.height - minGap - height + 1) * random.GetNext();
leaf.room = new Room((int)x, (int)y, (int)width, (int)height);
}
}
}