教程翻译-理解基于矢量场寻路算法

标签：grid   效果   方法   对比   inf   algo   热力图   out   front   

这个教程中我会解释向量场寻路(vector field pathfinding)以及它对比其他传统的寻路的优点，比如Dijkstra‘s算法。对于 Dijkstra‘s算法和势场（potential fields）概念的理解可以帮助你更好的理解本文，但这不是必要条件。

简介

寻路问题有多种方案，每种方案都有其优缺点。很多寻路算法为每一个寻路个体执行路径计算，这就意味着寻路开销会随着寻路个体成倍增加而增加。在很多情况下是可以接受的，但如果有几百个寻路个体的情况下，需要有更高效的方法。

向量场寻路方法计算从寻路的终点到图中的每一个节点的路径。为了更充分地对向量场寻路的解释，我会用我个人的实现版本作为例子。

注:向量场通常可以用节点或者图；这里我使用tile和grid并不意味这这个算法仅限于基于tile的世界！

视频预览

向量场算法由三个步骤组成。
1.生成热力图，用来确定地图中任意块/节点到终点的路径距离
2.为每一个节点生成指向到达终点方向的矢量域
3.每个正在搜索共享终点的粒子使用矢量域导航到终点

这个视频展示了最终的效果，为你展示完整教程的总体概念：
https://youtu.be/Bspb9g9nTto

生成热力图

热力图保存了从终点到地图上每一个点的寻路距离。寻路距离区别于欧式距离，它计算了2点之间能通过的地形的距离。这就好比是GPS总是只计算地图上能通过的道路的路径距离。

下图中你可以看出从终点（这里标记为红色）到任意一点（标记为粉色）的路径距离和直线距离的区别。不可通过的tile被染成绿色。你可以看到，路径距离（黄色）是9，直线距离（浅蓝）大约是4.12。

通过热力图生成算法，每一个Tile的左上角的数字显示了到达终点的路径距离。请注意2点之间有多条路径；本文中我们只关心最短路径。

热力图生成算法是一种波面算法（wavefront algorithm）。算法从终点开始，标记值为0，最后像波浪一样扩散，填满整个可以通过的区域。波面算法包含2个步骤：
1.算法从终点开始，用0标记终点的路径长度。
2.标记每一个未被标记的相邻tile，赋值为前一个路径长度 + 1
3.继续算法之道地图中每一个可达的tile都被标记完成

注：波面算法是在grid上使用广度优先算法，并保存从终点到每个tile的路径需要花费多少步。这个算法有时也被称为森林火灾算法。

生成矢量场

既然每个tile到达终点的路径长度已经计算完毕了，我们可以很简单的确定如何接近终点的路径。

教程翻译-理解基于矢量场寻路算法

标签：grid   效果   方法   对比   inf   algo   热力图   out   front   

原文地址：https://www.cnblogs.com/terrynoya/p/13206962.html