Homepage > Crowd simulation > List of publications > Paper

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

The Corridor Map Method: A general framework for real-time high-quality path planning

A corridor and resulting path obtained by the Corridor Map Method.

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 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.

References

  • Roland Geraerts and Mark H. Overmars. The Corridor Map Method: A General Framework for Real-Time High-Quality Path Planning. Computer Animation and Virtual Worlds (CAVW), 18:107-119, 2007.

    pdf

  • Roland Geraerts and Mark H. Overmars. The Corridor Map Method: Real-Time High-Quality Path Planning. In IEEE International Conference on Robotics and Automation (ICRA'07), pp. 1023-1028, 2007.

    pdf pptx

  • Roland Geraerts and Mark H. Overmars. Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments. In Computer Animation and Social Agents (CASA'08), pp. 64-71, 2008.

    pdf pptx

  • Mark H. Overmars, Ioannis Karamouzas and Roland Geraerts. Flexible Path Planning Using Corridor Maps. D. Halperin, K. Mehlhorn (Eds): Algorithms - (ESA) 2008, Springer Lecture Notes in Computer Science (LNCS) 5193, pp. 1-12, 2008.

    pdf

  • Roland Geraerts, Arno Kamphuis, Ioannis Karamouzas and Mark H. Overmars. Using the Corridor Map Method for Path Planning for a Large Number of Characters. In Motion in Games (MIG'08), Springer Lecture Notes in Computer Science (LNCS) 5277, pp. 11-22, 2008.

    pdf pptx

The improved version of the Corridor Map structure can be found here: Explicit Corridor Map.

Some applications

The CMM/IRM allows for planning flexible paths.

Results

The Corridor Map Method enables the extraction of high-quality paths within 1 ms cpu time per second traversed time of the path.

Corridor map, corridor and short path in the McKenna environment.

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%.

5000 paths in the City environment.