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

作　　者：古天驰 李晓东[1] 苏龙生 

机构地区：[1]佛山科学技术学院计算机系,广东佛山528225

出　　处：《科技创新与应用》2023年第30期34-37,45,共5页Technology Innovation and Application

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

摘　　要：针对3D游戏地形的路径搜索问题,提出基于半边数据结构的具有避障能力的A-star最短路径搜索算法。算法利用三角面与邻接边的拓扑关系建立半边数据结构,并以三角面邻接边中点作为路径节点,对比传统的以欧氏距离为预估代价计算模型,提出一种新的预估代价计算模型的A-star算法(HEAS),算法可有效规避障碍并找到最优路径。实验表明,HEAS算法可适用于不同三维地形,并可确保在较短的时间内找到最优路径。实际上,HEAS算法不仅可应用于3D游戏场景下的最优路径搜索,亦可应用于实际三维地形图的最优路径规划问题。Aiming at the path search problem of 3D game terrain,an A-star shortest path search algorithm with obstacle avoidance ability based on half-edge data structure is proposed.The algorithm uses the topological relationship between the triangular surface and the adjacent edge to establish a half-edge data structure,and takes the midpoint of the adjacent edge of the triangular surface as the path node.Compared with the traditional calculation model based on Euclidean distance,a new predictive cost calculation model A-star algorithm(HEAS)is proposed,which can effectively avoid obstacles and find the optimal path.The experimental results show that the HEAS algorithm can be applied to different 3D terrain and can ensure that the optimal path can be found in a short time.In fact,HEAS algorithm can be applied not only to the optimal path search in 3D game scenes,but also to the optimal path planning of practical 3D topographic maps.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]