| abstract | In many virtual environment applications, paths have to be planned for characters to
traverse from a start to a goal position in the virtual world while avoiding obstacles.
Contemporary applications require a path planner that is fast (to ensure real-time
interaction with the environment) and flexible (to avoid local hazards such as small and
dynamic obstacles). In addition, paths need to be smooth and short to ensure natural
looking motions.
Current path planning techniques do not obey these criteria simultaneously. For example,
A* approaches generate unnatural looking paths, potential field-based methods are too
slow, and sampling-based path planning techniques are inflexible.We propose a new
technique, the Corridor Map Method (CMM), which satisfies all the criteria. In an off-line
construction phase, the CMM creates a system of collision-free corridors for the static
obstacles in an environment. In the query phase, paths can be planned inside the corridors
for different types of characters while avoiding dynamic obstacles. Experiments show that
high-quality paths for single characters or groups of characters can be obtained in real-time. |
