RTS流场寻路算法详解

2022-10-14 16:55 作者:游戏开发RAIN 0人读过 | 我要投稿

RTS里面经常会有很多角色，群体一起寻路到目的地附近，这种寻路是如何实现的，今天给大家详细的讲解基于流场寻路的算法。在本教程中，我将解释向量场寻路及其相对于Dijkstra等传统寻路算法的优势。对Dijkstra算法和势场的基本理解将有助于理解本文，但不是必需的。

寻路的问题有很多种解决方案，如AStar等, 每种寻路的方案都各有优缺点，大部分的寻路，都是角色要从A点走到B点，然后调用寻路算法找出一条路径出来。通常情况下这样是不会有问题的，但是对于像RTS这种游戏需要做群体寻路，从A点到B点一群角色走过去，如果每个角色都单独寻路，这样性能开销会比较大，所以今天我们为了解决这个问题，介绍基于流场向量的寻路。它的原理是把目标点的流场计算出来，所有移动的目标共用这个流量场。接下来本文讲详细的介绍流场寻路的核心技术与步骤。(本文是将地图基于网格来讲解的，你也可以用到其它的地方，不限于网格)。

生成Heatmap

Heatmap 是指从目标点到地图上每个图块的路径距离。路径距离不同于欧几里德距离，它是通过可穿越地形的最短的两点之间距离来计算。如下图，你可以看到从目标点（用红色标记）到地图任意的点（用粉色标记）的路径距离和线性距离之间的差异。不可行走的块以绿色绘制。如图，路径距离（以黄色显示）为9，而线性距离（以浅蓝色显示）约为4.12。每个图块左上角的数字显示由Heatmap生成算法计算出的到目标的路径距离。注意两点之间可能有一个以上的路径距离, 我们只算最短的那个距离。经过算法第一步，我们把地图上的每个块到目的地的最短距离都计算了出来，生成了Heatmap。