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

Research on Improved A-Star Algorithm Based on Polygon Navigation Mesh Map

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

Regarding the A-Star algorithm shortcomings of excessive searching nodes of path and inefficiency of searching in large tradition grid map,this paper propose an improved A-Star algorithm based on polygon navigation mesh map.Firstly,the obstacles are eliminated by using the modeling tool in the map to generate a polygonal navigation mesh for the walking domain.Secondly,a triangular navigation mesh is generating by using Delaunay triangulation on polygonal meshes,the data structure of A-Star algorithm is optimized by a binary heap,and the navigation mesh is precompted by goal bounding method and then the heuristic function of the A-Star algorithm is modified to apply to the polygonal navigation mesh,and then the path generated by the polygon navigation mesh is smoothed by funnel algorithm to generate the actual optimal path.Finally,building map-finding path comparative experimental platform is buitt by using the Unity3d game engine to compare analysis the performance gap of the algorithm.Experiments show that the search efficiency of improved A-Star algorithm based on polygon navigation mesh is significantly higher than that based on the traditional grid map A-Star algorithm in large maps.