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

• 作者: 刘黎志 朱昌龙
• 来源期刊: 软件导刊
• 学科: 工学
• 关键词: A*算法 Delaunay三角 多边形导航网格 平滑路径 漏斗算法
• 年，卷（期）: 2019,（1）
• 所属期刊栏目: 人工智能
• 页码范围: 17-21
• 页数: 5页
• 分类号: TP301
• 字数: 4491字
• 语种: 中文
• DOI: 10.11907/rjdk.181825

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘黎志	武汉工程大学智能机器人湖北省重点实验室	26	78	4.0	8.0
5	朱昌龙	武汉工程大学智能机器人湖北省重点实验室	3	2	1.0	1.0