摘要
以3D游戏中智能体的路径规划为研究背景,对于如何生成3D游戏的地形网格以及如何进行高速、准确的路径规划进行了研究。提出了一种分层的解决方案,首先通过建立导航网格划分状态空间;接着使用引入地形估价因子的算法进行网格寻路,并通过拐角点法生成路径,同时对算法的OPEN表进行了二叉堆的优化;最后介绍了基于射线透射的局部算法对动态障碍物的处理。实验分析表明该算法的有效性。
This paper focuses on how to generate a 3D navmesh and implement high-speed path-finding for autonomous characters in 3D games. We proposed a hierarchical solution to meet the requirement. Firstly, a navmesh is used to divide the state space. Then we used the A＊ algorithm to find the path of the navmesh with making use of binary heaps to optimize the OPEN table. We also proposed a method of corner points to find the final path. At last, we used ray transmission to detect the dynamic obstacles. The initial experimentation shows that our solution is able to be used in some 3D games.
出处
《电子设计工程》
2014年第14期37-39,42,共4页
Electronic Design Engineering
关键词
导航网格
算法
地形因子
二叉堆
拐角点法
射线透射
navmesh
A＊ Algorithm
terrain factor
binary heaps
corner points
ray transmission
