基于半边数据结构的A-star路径规划算法及实现

摘要：

针对 3D游戏地形的路径搜索问题,提出基于半边数据结构的具有避障能力的A-star最短路径搜索算法.算法利用三角面与邻接边的拓扑关系建立半边数据结构,并以三角面邻接边中点作为路径节点,对比传统的以欧氏距离为预估代价计算模型,提出一种新的预估代价计算模型的A-star算法(HEAS),算法可有效规避障碍并找到最优路径.实验表明,HEAS算法可适用于不同三维地形,并可确保在较短的时间内找到最优路径.实际上,HEAS算法不仅可应用于 3D游戏场景下的最优路径搜索,亦可应用于实际三维地形图的最优路径规划问题.

关键词：半边数据结构、A-star算法、路径规划、邻接边中点、3D游戏

所属期刊栏目：13

分类号：TP391(计算技术、计算机技术)

资助基金：佛山科学技术学院国家级大学生创新创业训练计划项目202211847004

在线出版日期：2023-11-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：34-37,45