二叉空间分割 (Binary space partitioning，简称BSP)是一种通过使用超平面作为分割，递归细分空间为两凸集的算法。

BSP Tree

二叉空间分割 (Binary space partitioning，简称BSP)是一种通过使用超平面作为分割，递归细分空间为两凸集的算法。
这个过程将空间细分转化为了树结构，即所谓的二叉空间分割树（BSP树）。1993年， 毁灭战士(DOOM) 是John Carmack首次在游戏中使用二叉空间分割算法

图源wiki

构建BSP Tree

首先选取一块矩形空间作为地图的最大边界，接下来对地图进行递归的分割，直到每个单独的小空间不能再进行划分为止。

划分算法可分为以下步骤：

选择划分方向：横向还是纵向
选择划分位置
将空间分割为两个子空间

第一次划分结果

第二次划分结果
注意当选择划分位置的时候，分割线不能离空间边界太近，必须保证最后的每个空间都能放下一个预设房间的大小。重复划分直到最低层的空间（叶子节点）达到我们想要的近似预设空间的大小。

第四次划分结果

不同的划分位置选择会造成不同的生成结果，如果把分割线规定在0.4f - 0.5f 的范围内，最后会形成比较一个比较规整的地图，所有房间大小相近。如果把分割线规定在0.1f - 0.9f的范围内，就会形成一个比较混乱的地图，房间大小不一。

BSP节点生成伪代码：

while (迭代次数 < 最大迭代次数 && graph.Count>0)    // graph 为待检查节点队列
        {
            迭代次数++;
            RoomNode 当前节点 = graph.Dequeue();
            if(当前节点 仍然可以分割)
            {
                根据房间最小宽度和长度 获取分割线(Line)位置(Coordinate)和方向(Orientation);
                依据分割线生成两个新的子节点;
                将新生成的子节点加入节点集合和graph中;
            }
        }

创建房间

创建好BSP Tree之后，即可创建房间了。为了创建房间，首先需要遍历BSP树找到所有叶子节点，也就是对BSP树进行按层遍历。

查找叶子节点主要代码

while (nodesToCheck.Count > 0)
        {
            var currentNode = nodesToCheck.Dequeue();   // 当前检查的节点
            if (currentNode.ChildrenNodeList.Count == 0)    // 没有子节点即为叶子节点，加入叶子节点列表
            {
                listToReturn.Add(currentNode);
            }
            else        // 如果有叶子节点，将该节点的子节点入队，等待遍历
            {
                foreach (var child in currentNode.ChildrenNodeList)
                {
                    nodesToCheck.Enqueue(child);
                }
            }
        }

查找到所有的叶子节点后，即可在节点中生成房间。

房间生成结果

创建走廊

为了创建走廊，需要遍历所有的叶子节点，连接每个节点至它的兄弟节点。如果两个房间有面对面的墙，即可直接直线连接，如果没有的话，只能使用一个Z型的走廊来连接。

连接第四层兄弟节点

下一步重复以上的步骤对上一层（第三层）进行处理。由于第四层的房间已经相互连接起来，所以在连接第三层的时候可以有以下几种连接方式：

两个房间进行连接
房间与走廊连接
走廊与走廊连接

连接第三层兄弟节点
重复以上步骤直到A和B节点连接到一起
走廊生成部分主要代码：

// 连接两个相对位置为左右关系的节点
    private void ProcessRoomInRelationRightOrLeft(Node structure1, Node structure2)
    {
        Node leftStructure = null;
        // 获取左半部分叶子节点
        List<Node> leftStructureChildren = StructureHelper.TraverseGraphToExtractLowestLeafes(structure1);
        Node rightStructure = null;
        // 获取右半部分叶子节点
        List<Node> rightStructureChildren = StructureHelper.TraverseGraphToExtractLowestLeafes(structure2);

        // 将左侧叶子节点按照x坐标递减的顺序排列
        var sortedLeftStructure = leftStructureChildren.OrderByDescending(child => child.TopRightAreaCorner.x).ToList();
        if (sortedLeftStructure.Count == 1)
        {
            leftStructure = sortedLeftStructure[0];
        }
        else
        {
            // 在左侧叶子节点中 随机选取一个节点与右侧进行连接，该结点的x坐标与x坐标的最大值相距不能超过10
            int maxX = sortedLeftStructure[0].TopRightAreaCorner.x;
            sortedLeftStructure = sortedLeftStructure.Where(children => Math.Abs(maxX - children.TopRightAreaCorner.x) < 10).ToList();
            int index = UnityEngine.Random.Range(0, sortedLeftStructure.Count);
            leftStructure = sortedLeftStructure[index];
        }

        // 根据选中的左侧节点 在右侧的叶子节点中找到能够与之相连接的节点
        var possibleNeighboursInRightStructureList = rightStructureChildren.Where(
            child => GetValidYForNeighourLeftRight(
                leftStructure.TopRightAreaCorner,
                leftStructure.BottomRightAreaCorner,
                child.TopLeftAreaCorner,
                child.BottomLeftAreaCorner
                ) != -1
            ).OrderBy(child => child.BottomRightAreaCorner.x).ToList();

        // 在右侧可用的节点中选取一个
        if (possibleNeighboursInRightStructureList.Count <= 0)
        {
            rightStructure = structure2;
        }
        else
        {
            rightStructure = possibleNeighboursInRightStructureList[0];
        }

        // 计算出左侧房间和右侧房间能够连接的有效y坐标（y值坐标会被用作走廊左下角顶点的y值）
        int y = GetValidYForNeighourLeftRight(leftStructure.TopLeftAreaCorner, leftStructure.BottomRightAreaCorner,
            rightStructure.TopLeftAreaCorner,
            rightStructure.BottomLeftAreaCorner);

        // 当无法找到有效的y值连接点时，并且左侧叶子节点数量大于1时，进入以下循环
        while(y==-1 && sortedLeftStructure.Count > 1)
        {
            // 从左侧叶子节点中重新选择一个有效节点
            sortedLeftStructure = sortedLeftStructure.Where(
                child => child.TopLeftAreaCorner.y != leftStructure.TopLeftAreaCorner.y).ToList();
            leftStructure = sortedLeftStructure[0];
            // 重新计算有效的y值坐标
            y = GetValidYForNeighourLeftRight(leftStructure.TopLeftAreaCorner, leftStructure.BottomRightAreaCorner,
            rightStructure.TopLeftAreaCorner,
            rightStructure.BottomLeftAreaCorner);
        }

        // 求出走廊的左下角坐标和右上角坐标
        BottomLeftAreaCorner = new Vector2Int(leftStructure.BottomRightAreaCorner.x, y);
        TopRightAreaCorner = new Vector2Int(rightStructure.TopLeftAreaCorner.x, y + this.corridorWidth);
    }

以上代码展示的是两个兄弟结点的分割方式为 纵向(Vertical) 的时候， 横向(Horizontal) 分割方式同理。

地图生成结果

Unity Showcase

Reference

http://www.roguebasin.com/index.php?title=Basic_BSP_Dungeon_generation
https://en.wikipedia.org/wiki/Binary_space_partitioning
https://youtu.be/VnqN0v95jtU?list=PLcRSafycjWFfEPbSSjGMNY-goOZTuBPMW

Sqrt9

Unity 使用BSP程序化生成地图