Autonomous and robust navigation for simulated humanoid characters in virtual environments

An important task for virtual characters is autonomous navigation in a virtual environment. The task is to find a way through the environment leading to a certain goal, avoiding obstacles such as walls, or surfaces not suitable for walking. This paper invents an algorithm that analyzes a given scene database in a preprocessing phase fully automatically. It identifies storeys, rooms and stairs without the need of user-guidance. During runtime, the path planning itself works on data generated during the preprocessing phase working in realtime today's PC hardware.