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