提出背景：
长距离寻路会出现掉帧现象，为了提高寻路速度，并为3D环境中的寻路方案提供基础算法实现。
目前状况：
由于3D游戏对帧率要求很高，而在游戏中进行一次长距离的寻路可能要花费8-10帧的时间，在地图复杂的情况下寻路时间甚至可能会更严重，而在这段时间，渲染循环会暂停渲染并等待寻路结果。会给玩家带来不流畅的操作体验。
特别是3D游戏中地图比较复杂，地图规模比较大，对于一张600*600的地图，寻路的搜索空间的节点数目有可能达到数十万之多，这给传统的A*寻路算法提出了挑战，如果地图比较复杂，直接在这些节点上直接寻路的时间可能会以秒来计算。
解决方案：
解决上述问题的方法，可以通过生成导航网格来减少寻路算法的搜索空间。这也是3D世界中最常用的寻路解决方案。
常见的导航网格生成方法有两种，一种是通过手工创建，这需要专门的人员很细心的花费一定的时间来创建。另外一种是通过程序来自动生成，不过稍微复杂一点。这次创新采用了自动生成导航网格的方法。可以通过我们自己的AStarExplore工具，在不改变现有资源的情况下自动生成导航网格。
DK Online 中枫林片区地图为例，可通过节点55616个，如下图：
上图为一张435*310的地图，可通过节点55616个
通过我们自己的工具自动生成的导航网格(不需要人工手动创建)，可通过寻路节点仅为2238个，生成算法采用了Hertel-Mehlhorn算法和3-2Merging算法。
自动生成的导航网格。节点数为2238个
生成结果显示：可通过节点由原先的55616个节点合并成为了2238个节点。大大减少了寻路时的搜索空间，为更快，更远的路径搜索提供了可能性。
3D空间中的导航网格
A*寻路优化：
1、 内存优化：
寻路中，搜索路径耗费的时间并不是最主要的损耗，而是寻路开始时的内存重置，或者是内存的不断分配和释放。由于节点数目的减少，在寻路之前就建立了节点的数组（只占用100-200K内存），使用一个bool的一维数组来标识这些节点是否被搜索过，每次寻路结束之后只需重置这个bool数组即可。
2、 使用二叉堆优化Open表：
使用二叉堆可使最优的节点一直处于堆的顶部，而不用消耗太多的时间在对Open表的排序上，或者遍历Open表查找最优节点上。
一次中短距离寻路对比：
游戏中实际距离如图A到B的距离。
掩码寻路结果 导航网格寻路结果
掩码寻路耗费时间 导航网格耗费时间
通过对比：一次中短距离的基于原始节点的寻路，寻路时间为1.615ms，遍历节点数284个。而一次基于导航网格的寻路，遍历节点仅为58个，寻路时间只有0.0711毫秒。
一次中距离寻路对比：
游戏中实际距离如图A到B的距离。
实际寻路时间：
掩码寻路结果 导航网格寻路结果
通过对比：一次中距离的基于原始节点的寻路，寻路时间为69ms，遍历节点数8393个。而一次基于导航网格的寻路，遍历节点仅为522个，寻路时间只有0.38毫秒。
一次长距离的寻路对比:
游戏中实际距离如图A到B的距离，寻了一个对角长度。
掩码寻路结果 导航网格寻路结果
通过对比：一次长距离的基于原始节点的寻路，寻路时间为468ms，遍历节点数46636个。而基于导航网格的寻路，遍历节点仅为2198个，寻路时间只有1.604毫秒。
扩展：
由于生成导航网格的算法是完全基于3D空间的多边形，可将此算法应用到场景面片当中，生成基于实际场景的导航网格，从而可实现分层寻路。如下图。
参考文献：参考《Ai Game Programming Wisdom》中《建立接近最优的导航网格》文献。
采用了Hertel-Mehlhorn算法和3-2Merging算法建立接近最优的导航网格。
Hertel-Mehlhorn算法
3-2Merging算法
寻路算法仍然采用A*算法，但搜索空间变成了导航网格。启发函数的计算公式有所改变。
G值 = 穿入边中点与穿出边中点的距离。
H值 = 多边形中点到目标点的直线距离。
F值 = G值 + H值。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
