基于 Tile 地图的视觉范围生成方法以及实现

作者:eastecho
2015-04-26
53 115 11

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

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

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

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

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

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

t1-1

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

t1-2

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

edges每一个 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 中。

提示:等一下,我们要遍历所有的 Tile,如果我有一个大地图,屏幕上只显示一部分的话,我根本不需要遍历所有的 Tile 吧?没错儿,我们可以将屏幕上显示的这部分地图数据取出来,然后只遍历这一个区域的就可以了。不过,在我们取得这个区域的地图数据之后,记得要在区域再加上一个由 Tile 组成的外圈,这样才不会发生光线跑出屏幕却碰不到图块的情况。

比如这个视觉化后的数据,最外面一圈就是我们添加进去的:

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 由近到远的顺序排序。

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

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

los_p1

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

3、从光源开始发射光线

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

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

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

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

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

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

图解如下:
t3

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

// 注意这不是真正的代码
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) {
		... ...
	}
}

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

los_p2

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

4、连接所有的有用的线

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

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

los_p3

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

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

5、美化

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

los_p4

6、代码

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

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

impact.js 插件

请前往 github 下载 前往 github 下载

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

impact.js 插件

在 indienova 资源库下载 下载

近期点赞的会员

 分享这篇文章

eastecho 

从前的边城浪子,现在的路人乙 

您可能还会对这些文章感兴趣

参与此文章的讨论

  1. 朱大仙 2015-05-09

    噗 真是丰富的代码库。学习了、如果能认识就好了

  2. llq 2016-01-08

    啊嘞嘞,真不错,没想到,这会有js的实现版本,哈哈,踏破铁鞋xxx,得来xxxxx啊,真是。顶个:P

  3. mattins 2016-08-19

    哦哦 挺不错的!

  4. yellow 2017-01-25

    没想到这文章是你写的,我滴神。厉害。

  5. ZackZ 2017-03-07

    没想到Monaco并没有使用GPU加速算法。
    我在考虑我的游戏视野是用C++写这个算法呢……还是弄个GPU加速的版本,GPU加速的话对每个光源应该都要渲染个一维纹理。。

    最近由 ZackZ 修改于:2017-03-07 15:12:17
  6. sloth2d 2017-03-07

    unity有个类似的插件也是这种效果

  7. Wizcas.陈小一 2017-04-27

    超级厉害,好文章,最近正好在研究视野显示的问题,很有启发!

  8. 郭佳谊 2018-04-29

    感谢分享~

  9. ICBITIC 2019-04-20

    非常好又极为及时的好文章,救我于危难之中。但是怎么由edges对画面进行美化钻研了甚久,愣是想不通。

您需要登录或者注册后才能发表评论

登录/注册