上篇教程结束，可以得到一个处理过的地下城map数组，拥有多个房间以及房间之间的两个最短连接点，如下图所示：
要连通整个地下城，需要在房间之间创建路径，既然我们已经有了路径的首尾两点，那问题就变成了如何在一个二维像素网格中，给定两个点，点出连接两点的线段：
可能在上个世纪人们造像素显示器的时候就面临过这个问题，也留下了一个很经典的算法：布雷森漢姆直線演算法。
从最简单的情况开始，假设我们有两点p1(x1, y1)，p2(x2, y2)，p2在p1的右上方。可以算出斜率delta为(y2 - y1) / (x2 - x1)。设定一个误差值error，初始设为0。
版本1:
- 从x1开始，顺序遍历从x1到x2的点x，y从y1开始先保持不变。
- 填充点(x, y)。
- x每增加1，error就增加斜率delta。
- 当error值大于0.5的时候，说明这时候偏差更偏向于y，y增加1，error值减去1。
- 重复步骤2，直到x遍历结束。
连线后的结果如图所示：
上面的基础算法只适用于p2在p1右上角，且斜率delta小于1的情况，可以稍微修改下以适用于一般情况：
版本2:
- 如果斜率delta大于1，则交换x1，y1和交换x2，y2，相当于旋转坐标系90度。
- 如果p2在p1左边(x2 < x1)，则交换起始点。
- 如果p2在p1下边(y2 < y1)，则当error值大于0.5时，y减去1。
考虑到浮点数的运算效率比较慢，还可以把error和delta变为整数进行运算：
版本3:
- error值初始设置为(int)((x2 - x1)/2)
- deltaY值设置为abs(y2 - y1)，deltaX值设置为(x2 - x1)
- 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，戳我直达
