Real-Time Path Planning in Virtual Environments
|
Abstract
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.
Reference
Roland Geraerts and Mark Overmars. Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments.In Computer Animation and Social Agents (CASA), pp. 64-71, 2008. Full text: [pdf] Presentation: [ppt]
Construction of a high-quality corridor map.
NB The improved version of the Corridor Map structure can be found here: Explicit Corridor Map.
Test environments
We used the following two test environments in our experiments (click on
a picture to enlarge):
Results (Corridor map)
We used our new approach to create the following two high-quality Corridor Maps. These maps were created in 0.05 and 0.64 seconds, respectively.
Results (Crowd simulation)
Experiments showed that the improvements led to a method steering a crowd of
approximately 10,000 characters in real-time (using one cpu running at 2.4Ghz):
The picture below gives an impression of 5000 paths, each traversed by a character having its own long term goal. All characters avoid each other in real time. The cpu-load of this simulation was 40%.
|
||||||||||||||||||||||||||||||||||||||||||||||
