基于多边形导航网格地图的改进A*算法

针对A*寻路算法在大型地图中搜索路径结点过多、搜索效率过低的问题，提出一种基于多边形导航网格的改进A*算法。首先利用建模工具对地图中障碍物进行剔除，生成可行走域的多边形导航网格；其次对多边形网格进行Delaunay三角剖分，形成三角导航网格，利用二叉堆对A*算法所使用的数据结构进行优化，采用目标范围界限方法对导航网格进行预处理，并将处理A*算法的启发函数进行改进以适用于多边形导航网格，对多边形导航网格生成路径利用漏斗算法进行路径平滑处理，生成实际最优路径；最后利用Unity3d游戏引擎搭建地图寻路实验平台，对比分析算法的性能差距。实验证明，基于多边形导航网格改进A*算法在大型地图中的搜索效率明显高于基于传统方格地图A*算法。