我们之前曾经介绍过关于视觉范围的算法，比如针对任意形状的《视线和光线：如何创建 2D 视觉范围效果》。那么，今天我们再来了解另外一种算法，它是基于 TileSet 图块的，也就是说：我们将会学习如何实现在一个 Tile-Based 的游戏环境中实现视觉范围。我们会介绍基本方法，以及一些实现的例子供大家参考。

本文是参考了著名独立游戏《Monaco 摩纳哥：你的就是我的》的作者的文章：Line of Sight in a Tile Based World（Facebook，需要翻墙）。这篇文章介绍了 Monaco 的视线范围的实现方法，但是说的都是要点，具体实现方法就很不详细，需要开发者自己研究。我希望能够将这个算法清晰的介绍给大家，以便能够用在自己的游戏里面。

开始这篇教程之前，有几个设定事先说明：

1. 游戏系统是 Tile Based；
2. 假定玩家的角色永远处在屏幕中央；（这个一般都是这样）
3. 假定光线的发射点（光源／观察者）是玩家，也就是在屏幕中央。（这个一般也都是这样。当然在实际的游戏当中，光源可能是固定的灯，或者运动的子弹等等。在教程中我们只有一个光源，并且位于屏幕中央）

1、找到面向光源的面边缘

因为我们假定光源在屏幕中央，那么它会向四面八方发射光线。当然这个光线遇到表面就会停下来，但是我们并不知道光线会到达哪些表面，所以，先要将面向光源的表面（边缘）全部找出来。

如上图所示，地图上单个 Tile 面向玩家的面无外乎这两种情况，因为再厉害的光线也跑不到后面去。特殊情况会出现在图块连接的时候，这时候，有些原本是面向光源的面被挡住了，所以也就不计算了。那么，粗黑色的线就是面向光源的面，也是我们要记录下来的边缘数据。（这里你可能会有疑问：有些面虽然是面向光源的，可是它们和光源之间还有遮挡，不可能会被照射到，那么我有必要记录它么？当然需要，因为我们并不能确定这些边缘是否能被照射到，随后我们都需要计算。）

至于如何找到这些面的数据，我们只需要遍历一下地图处理每一个 Tile 就可以了。

每一个 Tile 都有自己的坐标（四个顶点坐标），我们根据光源的 x, y 和 Tile 边缘的坐标 { x1, y1, x2, y2 } 来判断，就知道该保留哪些边缘了。值得注意的一点是，为了后面的计算，我们需要将取到的边缘按照顺时针方向来保存，这样每次计算的时候都能保证这些边缘能够正常相连。

就像右边这张图所示，坐标方向要按照顺时针来排列。比如，如果左边缘是可见的，那么它的坐标描述就应该是 x3,y3 -> x1,y1，如果右边缘是可见的，那么它的坐标描述就应该是 x2,y2 -> x4,y4。

我们找到这些边缘之后，要将它们存储起来，以便后面使用，每一个边缘都是具有这样属性的一个对象：

p1 : { x:0, y:0 },	// 边缘起始点
p2 : { x:0, y:0 },	// 边缘结束点
prev: -1,		// 上一条相连接的边缘
next: -1,		// 下一条相连接的边缘
distance: 0		// 距离光源的距离

我们现在已经可以取得边缘起始点 p1 和边缘结束点 p2 了，生成一个新对象，并且将它放到边缘数组 edges 中。

0000  # # # # # # # # # # # # # # # # # # 
0001  # # . . . . . # # # # # # # # . # # 
0002  # . . . . . . # . . . . . . . . # # 
0003  # . . . . . . # . . . . . . . . # # 
0004  # . . . . . . # . . . . . . . . # # 
0005  # # # # # # # # # . # # # . # # # # 
0006  # . . . . . . . . . . . . . . # . # 
0007  # . . . # # . . . 0 . . . . . # . # 
0008  # . . . # # . . . . . . . . . # . # 
0009  # . . . . . . . . # # . # # # # . # 
0010  # . . . . . . . . # . . . # . . . # 
0011  # . . # # # . . . # . . . # . . . # 
0012  # . . # # # . . . # . . . . . . # # 
0013  # # # # # # # # # # # # # # # # # #

2、将这些面连接起来，并排序

从边缘数据结构可以见到，我们取得边缘数据后，还没有结束。我们将这些数据装在一个数组中，然后遍历这个数组，这一次我们要做的工作有三个：

1. 计算这个边缘到光源的距离，放到 distance 里面；（我是通过计算光源到边缘中心点的距离得到的这个数值）
2. 循环寻找相连的边缘，只要这条边缘的 p1 等于另外一条边缘的 p2，那么，这条边缘的 id 就是另外一条边缘的 next（下一条），同时，这条边缘的 prev（上一条）就是另外一条边缘的 id（现在知道为什么我们要给这些边缘的数据带有方向顺序了吧？）。然后将这些边缘的 id（数组下标）对应的放到 next（下一条）和 prev（上一条）里。如果这个边缘没有上一条或者下一条边缘可以相连，那么就留着值为 -1 就好了，后面正好要用上；
3. 前面两项工作做完之后，按照 distance 由近到远的顺序排序。

好了，我们的准备工作完成了！现在，所有有关边缘的数据都妥妥的装载数组里面了，我们可以准备做下一步了。

当然，我们可以先将这些面绘制出来，如下所示：

我们还特地将这完成的一步做了出来，您可以在地图上行走，看看这些面的实时变化：

3、从光源开始发射光线

现在，关键也是最复杂的一步到来了，我们要从光源开始发射光线了。

对已找到的边缘，我们开始寻找那些 next（下一条）或者 prev（上一条）为 -1 的，这代表这个边缘没有完整连接。

这条边缘缺少同其它边缘的连接，那么我们就从光源处发出一条射线，这条射线要经过这条边缘的缺失连接的那个点。比如，如果这条边缘缺少 next（下一条），那么我们就发出一条经过光源 x, y 和这条边缘的 p2 点，这样我就得到一条射线。

然后用这条射线按照数组的顺序（我们已经按照距离排好序了）寻找与其它边缘的交点。如果完全找不到，那么说明这条边缘无意义，我们也只能放弃它了。如果找到的话，那么我们就要更改一下数据了。

我们设置当前边缘为 edgeStart，找到的那条边缘为 edgeToBeSliced，交点为 p，那么我们要对边缘的连接关系做一下更新，并且切割另外一条边缘（交点 p 就是新的 p1），丢弃掉一部分：

edgeStart.next = targetEdgeID;	// 当前边缘的下一条设为找到的那条边缘
edgeToBeSliced.p1 = p;		// 将找到的那条边缘的起始点重新设置为切割点
edgeToBeSliced.prev = edgeID;	// 找到的那条边缘的上一条设为当前边缘

图解如下：

这样，我们原本没有连接的两个边缘被射线连接起来了。即使交点上的那条边缘之前有其它的连接，也都废弃不用了，被更新成了当前这条边缘。这是很关键的一步，我们将这个流程做一下描述：

// 注意这不是真正的代码
for i = 0 to count(edges) {
	e = edges[i]
	// 如果没有下一条
	if (e.next == -1) {
		// 寻找和其它边缘交点
		intersection = checkIntersection(e)
		if (intersection) {
			// 更新边缘数据，就像前面那段代码写到的那样
			updateEdges(e, intersectionEdge, intersectionPoint)
			// 然后跳出，不再寻找了，因为按照顺序已经找到最近一条有交点的，其它忽略
			break
		}
	}
	// 如果没有上一条
	if (e.prev == -1) {
		... ...
	}
}

循环完毕之后，其实我们的工作就完成了。这个时候如果我们再尝试着绘制边缘，那么就会看到如下的情况：

会发现有些边缘已经残缺不全了，因为射线将它切割了，失掉的部分是不可见的，这是正确的。

4、连接所有的有用的线

现在我可以做有趣的部分了：将有用的边缘连接起来！

我们还是从边缘数组的第一个边缘开始，绘制这条边缘，然后找到它的下一条，绘制下一条，然后再寻找下一条的下一条……这样继续下去，直到回到第一条，也就是我们出发的那条。效果会怎样呢？请看：

怎么样，我们就这样完成它了。

那么还能做些什么呢？当然是各种美化啦！

5、美化

下面是一个美化的例子，您当然可以自己做出各种效果啦：

6、代码

我将这个视觉跟踪的方法在 iOS 和 JavaScript 里面都有实现。

目前已经将实现完成的 impact.js 插件上传到 Github，如果您使用 impact.js，请到这里查看：

另外本站的资源站也有相关链接：