程序生成地下城洞穴(3)

上篇教程结束，可以得到一个处理过的地下城map数组，拥有多个房间以及房间之间的两个最短连接点，如下图所示：

要连通整个地下城，需要在房间之间创建路径，既然我们已经有了路径的首尾两点，那问题就变成了如何在一个二维像素网格中，给定两个点，点出连接两点的线段：

可能在上个世纪人们造像素显示器的时候就面临过这个问题，也留下了一个很经典的算法：布雷森漢姆直線演算法。

从最简单的情况开始，假设我们有两点p1(x1, y1)，p2(x2, y2)，p2在p1的右上方。可以算出斜率delta为(y2 - y1) / (x2 - x1)。设定一个误差值error，初始设为0。

版本1:

1. 从x1开始，顺序遍历从x1到x2的点x，y从y1开始先保持不变。
2. 填充点(x, y)。
3. x每增加1，error就增加斜率delta。
4. 当error值大于0.5的时候，说明这时候偏差更偏向于y，y增加1，error值减去1。
5. 重复步骤2，直到x遍历结束。

连线后的结果如图所示：

上面的基础算法只适用于p2在p1右上角，且斜率delta小于1的情况，可以稍微修改下以适用于一般情况：

版本2:

1. 如果斜率delta大于1，则交换x1，y1和交换x2，y2，相当于旋转坐标系90度。
2. 如果p2在p1左边(x2 < x1)，则交换起始点。
3. 如果p2在p1下边(y2 < y1)，则当error值大于0.5时，y减去1。

考虑到浮点数的运算效率比较慢，还可以把error和delta变为整数进行运算：
版本3:

1. error值初始设置为(int)((x2 - x1)/2)
2. deltaY值设置为abs(y2 - y1)，deltaX值设置为(x2 - x1)
3. x每增加1，error值就减去deltaY，如果error小于0，y发生变化，error加上deltaX。

最终版本的两点画线代码如下：

List<Coord> GetLine(Coord from, Coord to) {
    List<Coord> line = new List<Coord>();

    int x = from.tileX;
    int y = from.tileY;
    int dx = to.tileX - from.tileX;
    int dy = to.tileY - from.tileY;

    bool inverted = false;
    int step = Math.Sign(dx);
    int gradientStep = Math.Sign(dy);

    int longest = Math.Abs(dx);
    int shortest = Math.Abs(dy);

    if (longest < shortest) {
        inverted = true;

        step = Math.Sign(dy);
        gradientStep = Math.Sign(dx);

        longest = Math.Abs(dy);
        shortest = Math.Abs(dx);
    }

    int gradientAccumulation = longest / 2;

    for (int i = 0; i < longest; i++) {
        line.Add(new Coord(x, y));
        if (inverted) {
            y += step;
        } else {
            x += step;
        }

        gradientAccumulation += shortest;
        if (gradientAccumulation >= longest) {
            if (inverted) {
                x += gradientStep;
            } else {
                y += gradientStep;
            }

            gradientAccumulation -= longest;
        }
    }

    return line;
}

在CreatePassage函数中：

void CreatePassage(Room roomA, Room roomB, Coord tileA, Coord tileB) {
    Room.ConnectRooms(roomA, roomB);
    //Debug.DrawLine (CoordToWorldPoint (tileA), CoordToWorldPoint (tileB), Color.green, 100);
    List<Coord> line = GetLine(tileA, tileB);
    foreach (Coord c in line) {
        DrawCircle(c, 2);
    }
}

获取路径点集合后，通过DrawCircle方法在路径点周围清除map，确保路径畅通。

最终效果如图所示：

源代码可参考SebLague小哥的Github，戳我直达