寻路算法的研究与应用主要集中在路网寻路、避难救灾等领域,随着互联网技术的进一步发展、虚拟技术和智能车行业的兴起、人工智能热度的提高,相应的也将寻路算法的研究热度提升上来。传统路网寻路算法的研究主要针对静态网格的进行寻路研究,而在智能车以及虚拟技术领域上,随着数据获取能力的显著提升,将移动过程中处于变化的路况信息加入到算法中的需求也愈来越高。论文以NavMesh技术作为研究的基点,NavMesh寻路算法是目前使用率最高的开源寻路算法,该算法由Recast算法和Detour算法组成,Recast算法实现对静态网格的数据格式化处理工作,Detour算法实现在经预处理后的地图网格上实现寻路的工作。NavMesh算法在实际应用中仍有不足之处,论文主要关注NavMesh在应用过程中遇到的几个关键问题,包括拥塞问题、路径调整问题、阻挡检测问题以及交通路径变化问题。论文使用新的估价函数F(n)=B*G(n)+H(n)来解决虚拟场景运行态下的动态寻路问题,在不改变NavMesh工程原本的预处理机制的情况下结合避所算法以及动态交通管理算法实现虚拟场景运行态下动态寻路。以下四点是论文针对NavMesh算法实际应用过程中出现的四个相对严重的问题的改进措施以及改进成果说明:1)拥堵问题。通过实验证明,NavMesh工程使用的CritterAI寻路算法多次寻路得到的结果是相同的,论文改进算法引入RoadSection数据结构,将地图分为不同的RoadSection,然后计算RoadSection的饱和度,通过影响估价函数的方式对算法寻路的结果产生影响,从而在不同拥堵状态下得到不同的路径,达到了解决拥堵问题的目的;2)路径自我调整问题。NavMesh寻路算法由于多次寻路得到的结果是相同的,所以寻路单位移动过程中无法实现路径的自我调整,论文改进算法则解决了这个问题。依据饱和度的动态性,实现了移动单位依据实际情况重新规划自己的移动路径;3)路径阻挡检测问题。由于加入饱和度的概念,当一个RoadSection出现特殊情况导致不可通行时可以直接访问对应RoadSection,通过接口修改其饱和度,达到将该路径设为不可通行,这也就解决了路径阻挡检测的问题;4)道路交通变化问题。当新的路径产生或者旧的路径被修改甚至删除时,算法需要重构预处理操作实现重新规划,这和目前所有的交通规划方案相同,动态算法并没有使这个问题变得更复杂。通过对上述四个问题的研究,论文验证了引入饱和度以及新的估价函数改进算法的可行性,实现了动态寻路的基本要求。