Autonomous and robust navigation for simulated humanoid characters in virtual environments

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