NavMesh 与常见寻路算法

寻路问题一般可以形式化为求从起点到终点最短或较短路径的问题。

NavMesh 导航网格

NavMesh（导航网格）是为了作为一种寻路算法运行而生的技术。其大致流程是根据表面生成特殊的图结构（也就是网格），图中每一个点都是可以参与寻路算法计算的路径点。

通过 NavMesh 构建出来的网格图，可以在其上运行不同寻路算法来获得所需要的路径。

最简单的办法就是使用广度优先搜索从起点进行遍历图，直到遍历到终点便停止，此时遍历到终点的路径就是最短路径。

但 BFS 的问题是如果网络节点很多（例如 NavMesh 节点较为密集的时候），遍历起来会花不少时间。

Dijkstra 也是经典寻路算法。Dijkstra 在 BFS 方法的基础上加入了对移动代价的考虑，以便适应复杂寻路问题中移动代价不同的条件（例如山和平地移动速度不同）。

为此，Dijkstra 在进行遍历的时候引入了优先队列进行遍历，同时也在不断计算遍历到的当前节点的移动代价——也就是从起点到当前节点的移动代价。

Dijkstra 同样在遍历到终点的时候停止遍历，得到最短路径。

最佳优先搜索同样也使用了优先队列来进行遍历，但和 Dijkstra 不同的是，其队列优先级来源是当前节点距离终点的距离。

由此每次遍历新节点的时候，选择的都是距离终点最近的节点进行遍历。

最佳优先搜索是一种启发式算法，所以并不能保证得到的是最短路径，而是尽量得到一条较短路径。

A-star 同样是一种启发式算法，其结合了上述算法的特点，将其表达为一个优先级函数（又被称为代价函数）：

其中，是节点距离起点的代价，是节点和终点的距离。

可以看到，就是 Dijkstra 的部分，则是最佳优先搜索的部分，通过加法将二者融合得到最终的遍历优先级，从最小的节点开始遍历，便可以较快地遍历出一条较短的路径。

小知识：此外还有一种常见的变体，加权 A-star 算法。加权 A-star在 A-star 算法上对代价公式进行了加权。例如在 Minecraft 中，Mojang 使用了作为代价函数来为生物寻路。