Home Research Publications Software Teaching Resume Gallery Japan

Goal-Directed Navigation for Animated Characters
Using Real-Time Path Planning and Control

James Kuffner, Jr.

Robotics Laboratory
Department of Computer Science
Stanford University
Stanford, CA 94305, USA



This paper presents a new technique for computing collision-free navigation motions from task-level commands for animated human characters in interactive virtual environments. The algorithm implementation utilizes the hardware rendering pipeline commonly found on graphics accelerator cards to perform fast 2D motion planning. Given a 3D geometric description of an animated character and a level-terrain environment, collision-free navigation paths can be computed between initial and goal locations at interactive rates. Speed is gained by leveraging the graphics hardware to quickly project the obstacle geometry into a 2D bitmap for planning. The bitmap may be searched by any number of standard dynamic programming techniques to produce a final path. Cyclic motion capture data is used along with a simple proportional derivative controller to animate the character as it follows the computed path. The technique has been implemented on an SGI Indigo2 workstation and runs at interactive rates. It allows for real-time modification of the goal locations and obstacle positions for multiple characters in complex environments composed of more than 15,000 triangles.

Keywords: Real-Time Motion Planning, Goal-Directed Navigation, Virtual Humans, Task-Level Animation, Motion Capture Synthesis, Interactive Virtual Environments


1997 - 2006 © James Kuffner, Jr.