Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments

A central problem in interactive virtual environments is planning high-quality paths for characters avoiding obstacles in the environment. Current applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards). In addition, paths need to be natural, i.e. smooth and short. To satisfy these requirements, we need an adequate representation of the free space stored in a convenient data structure, a fast mechanism for querying this data structure, and an algorithm that constructs natural paths for the characters. We improve an existing data structure, the Corridor Map, which represents the free space by a graph whose edges correspond to collision-free corridors. We show that this structure, together with a kd-tree, can be used for fast querying, resulting in a corridor that guides the global path of the character. Its local motions are controlled by force functions, providing the desired flexibility. Experiments show that the improvements lead to a method which can steer a crowd of approximately 10,000 characters in real-time.