欢迎光临散文网 会员登陆 & 注册

像《红警》里的大兵那样找路(上)——全局向量场寻路

2022-09-23 16:24 作者:皮皮关做游戏  | 我要投稿

前前言

之前未接触过游戏开发但又对其感兴趣的朋友,可以参与咱们的网易游戏开发3天集训营,体验一次激动人心的游戏开发过程——提出需求、思考原理、实现功能、定位bug、设计关卡、更换美术资源......麻雀虽小五脏俱全。只需添加如下网易小伙伴联系方式(注明B站)就能轻松报名:

(本文作者 @沈琰)

前言

最初是因为偶然看到的视频(注1) ,对其中游戏的演示涉及的技术产生了兴趣:


对于游戏开发有些了解的人来说,寻路算法应该都不会陌生。但对于类似这种RTS类型游戏里集群寻路的实现方法可能就不是太清楚,这次的目的就是探索其背后的思路和实现方法。



向量场

向量场(vector field),视频里也称之为流场(flow field),有些其他的教程里或者会称为势场(potential field),这些说的都是一个概念。至于为什么使用向量场作为基础,可能基于一个很朴素的想法:

先假设这么一个场景:RTS游戏中的场景里有成百上千的单位,而你大手一框F2A。 如果是基于之前学习的寻路方法,不管是A*还是别的其他寻路算法,那么接下来要做的总归是每个单位要基于目标点在地图上计算并生成一条路径,成百上千个单位就是成百上千次计算,这还没有考虑目标是一个移动中的单位,路径还需要实时更新的情况。此时哪怕使用的寻路算法效率再高,基数的量级就已经摆在那里了,总效率肯定高不起来。 使用向量场寻路的逻辑则是:由目标点计算出一个覆盖整个地图的全局向量场,每个单位只需要根据当时所在位置的向量走就行,在不考虑其他功能的情况下,效率差不多就是O(1)和O(n)的区别。

简而言之,对于多目标寻路来说,提高效率的方式可能不再是抠寻路算法的细节,而是以减少计算次数这个思路出发。使用向量场就是这个目的,相当于用一种可以复用的方式保存了路径,避免重复计算。

生成向量场

按照教程(注2)的方法,构建向量场分三步:

  1. 划分网格

  2. 生成热力图(Heatmap)

  3. 计算向量

现在按照这个步骤来实现。

构建网格

这里网格可以是任意规则形状的,如四边形六边形之类的,取决于需要,关键是世界坐标到网格坐标的映射转换正确即可。这里使用用普通的矩形网格。


生成热力图

所谓热力图,即图中的每一格都表示到目标距离的远近程度,换句话说就是DistanceMap,或者CostMap。 具体怎么计算距离,则根据需要来。

以我们现在的目的为例,一般矩形网格寻路只计算上下左右四个方向,而RTS不是战棋游戏,路使可以斜着走的,所以相邻节点要计算八个方向的距离。接下来遍历一遍所有格子计算到目标的距离,这里可以再加上一个梯度颜色字段,让单元格根据距离显示,使得热力图这个名字名副其实。

这里使用广度优先搜索算法(BFS)从目标点遍历所有格子,相应的,距离值的计算就直接计算实际距离,也叫欧几里得距离(注3) ,即正方向的距离加 1 ,斜方向的距离加%5Csqrt%7B2%7D%20

矩形网格的八方向BFS比起一般用的四方向要多注意一个地方:视遍历周围单元格的方法不同,可能会有方向的距离计算出错,需要打个“补丁”。 举个例子,假设沿着正右边顺时针遍历格子:

那么继续顺着这个逻辑遍历会有两处计算错误,本该算直线距离的位置会算成两个斜线距离,因此记得对已访问的单元格重新计算一次距离,取其中的最小值。



向量计算

接下来根据距离计算每个格子的向量,这里可以变化的点就很多。

简单点的想法就是向量指向周围格子里距离最小的那个,这个方法很适合用BFS生成的距离图,但对于实际情况来说,相当于把偏转的倾向特征抹掉了。


这里我的思路参考这个视频 [注4] ,用卷积核的方式计算周围每个相邻格子的权重。简单来说就是:生成八根从当前格指向相邻格的标准化向量,如果把指向最短距离格的向量长度视为 1,那么其他方向的向量的长度就是 1/distance,然后把8跟向量加起来再标准化,这样做的好处是可以充分考虑到各个方向的距离对整体权重影响,形成的向量场不再那么“直”,而是有一些弧度。

现在看起来好像没问题,但在把障碍物加进去后问题会变得更复杂一些。对于障碍物的格子的处理方法和边界一样,即在计算向量时不考虑这个方向上的权重。

先随机生成一些障碍物运行看看效果,会发现下面两个问题:

1.处于对角的障碍物的计算问题。


严格来说这并不是向量计算的问题,因为权重是按八方向取的均值,所以计算的时候认为斜角有路是理所应当的,解决的方法应该是不允许生成这样对角排布的障碍,只要发现斜对角的障碍物相邻,那么有一边整体都算障碍物。

2.与目标接近同一直线的情况下的障碍物附近的权重计算问题:


这个问题的解决思路是把与障碍物相邻的格子的权重向量单独计算,不再按照上面的规则。因为对于与障碍相邻的格子来说仅仅是不计算障碍物方向的权重,影响力是不够的。最直接的办法是障碍物边上的单元格,按之前的方法,量直接指向最小周围最小距离值的单元格,这也就是视频[注4] 中最后的优化组合算法:

进一步优化向量计算

到这里还有优化空间,现在的目标是希望计算出的向量场在遇到障碍物时稍微避开一些,不要贴着障碍物走。

现在网格图里计算向量的单元格分成两类:普通的单元格和障碍物旁边的单元格。思路是这样:

对于普通单元格,在发现其中一个方向的相邻单元格是在障碍物旁边的话,可以稍微减少一点这个方向的计算权重。

对于自身就在障碍物边上的单元格,可以在发现相邻单元格是障碍物时考虑这个方向的权重,给一个较小的反向的分量。

移动

向量的计算不可能尽善尽美,总会有些瑕疵,比如指向障碍物之类。但是向量的指向并不一定是移动方向,只是在当前单元格内的倾向于走的方向,换句话说就是力的施加方向。


写一个简单的移动脚本,每一帧获取当前脚下单元格的向量作为加速度方向参与速度计算,然后根据当前的速度移动,为防止穿墙,给移动角色加上刚体并在障碍物上加上碰撞盒,效果如图:


单个的角色移动问题不大,由于向量是作为加速度计算,所以移动轨迹会比较平滑。但直接多角色移动的效果并不好,由于碰撞的存在会使得移动显得很生硬,但这就不是继续优化向量计算能解决的问题了。限于篇幅,具体的群体移动逻辑放在下一篇文章。



结束

现在回过头从整体来看向量场寻路的优缺点:

优点是多目标寻路时比较节省计算资源,从这个角度来说,向量场寻路更适合的游戏类型是塔防游戏,只用一次计算就能整场复用寻路。

缺点则是在地图比较大的时候,每一次更新向量场信息都要全局更新,会有较高的性能热点。不过在实际的游戏中会用诸如分块的方法优化这个缺点。

下一期文章我们来研究一下转向行为(steering behaviors),让向量场导航显得更生动拟真。

工程地址:https://pan.baidu.com/s/1FbZ5mtE-g9Bfz4pjtQhp9A?pwd=bfdx

注1 :https://v.youku.com/v_show/id_XMTU0ODM4Njk2.html

注2:https://gamedevelopment.tutsplus.com/tutorials/understanding-goal-based-vector-field-pathfinding--gamedev-9007

注3:https://baike.baidu.com/item/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E5%BA%A6%E9%87%8F?fromtitle=%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E8%B7%9D%E7%A6%BB&fromid=2701459

注4:https://www.youtube.com/watch?v=ZJZu3zLMYAc

像《红警》里的大兵那样找路(上)——全局向量场寻路的评论 (共 条)

分享到微博请遵守国家法律