Abstract: This paper presents an efficient path planning algorithm for quickly generating global motion paths from navigation goals for a human model in very complex 3D obstacles environments,which is based on the representation of virtual environments.First,all obstacle geometry within the height range of the character is projected to a discretized 2D bitmap grid;the projected obstacles are “grown”.Then,the path planning algorithm presented in this paper is used to find an optimal path from an original position to an aim,directing virtual human walkthrough in environments.This method can quickly plan the optimal path from the position of virtual human now to the goal position within low memory requirements and computational cost.The feasibility and effectiveness of the algorithm are demonstrated by experiments.

Key words: virtual human, path planning, goal-directed motion

摘要： 提出了一种虚拟人在复杂的3D障碍环境中根据导航目标快速进行最优路径规划的算法,该算法以使用栅格法表示虚拟环境为基础。首先,将虚拟环境中虚拟人高度范围内所有障碍物的几何形状映射到一个离散的2D位图,并对障碍物进行“膨胀”;然后,使用提出的算法规划出一条从初始位置到目标位置的最优路径,引导虚拟人在虚拟环境中进行导航运动。该方法可以在较少的内存代价和计算代价的情况下,快速规划出从虚拟人目前位置到目标位置的最优路径,算法的可行性和有效性经过实验验证。

关键词: 虚拟人, 路径规划, 目标导航