软件导刊2019，Vol.18Issue(1)：17-21,5.DOI:10.11907/rjdk.181825
基于多边形导航网格地图的改进A*算法
Research on Improved A-Star Algorithm Based on Polygon Navigation Mesh Map
摘要
Abstract
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 Unity3 d 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.关键词
A*算法/Delaunay三角/多边形导航网格/平滑路径/漏斗算法Key words
A-Star/Delaunay triangulation/polygon navigation mesh/smoothing path/funnel algorithm分类
信息技术与安全科学引用本文复制引用
朱昌龙,刘黎志..基于多边形导航网格地图的改进A*算法[J].软件导刊,2019,18(1):17-21,5.基金项目
湖北省自然科学基金项目(2014CFB791) （2014CFB791）
湖北省高等学校优秀中青年科技创新团队计划项目(T201206) （T201206）
