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

朱昌龙 刘黎志

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

关键词：A*算法;Delaunay三角;多边形导航网格;平滑路径;漏斗算法

DOI：10. 11907/rjdk. 181825

中图分类号：TP301文献标识码：A文章编号：1672-7800（2019）001-0017-05

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 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.

Key Words： A-Star;Delaunay triangulation; polygon navigation mesh; smoothing path; funnel algorithm

0 引言

路径搜索一直是人工智能领域研究的热点，高效性和真实性一直是判断寻路算法性能的指标[1-3]。在人工智能路径搜索方面，运用最多的是A*算法[4]。相关领域研究者在A*算法基础上，进行了寻路算法的优化和改进，提高了寻路算法的性能。例如Daniel Harabor[5]提出JPS算法，利用跳点搜索的方法解决了传统等价方格地图中存在的对称性搜索结点问题，从而提高了搜索效率。但是目前大多数A*算法优化都是基于具有对称性的方格地图进行的，方格地图在大型地图中寻路网格结点较多，占用系统资源过多，从而导致搜索效率过慢。……