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

Planning Short Paths with Clearance using Explicit Corridors

A smooth, short path with clearance inside an Explicit Corridor.

Abstract

A central problem of applications dealing with virtual environments is planning a collision-free path for a character. Since environments and their characters are growing more realistic, a character's path needs to be visually convincing, meaning that the path is smooth, short, has some clearance to the obstacles in the environment, and avoids other characters. Up to now, it has proved difficult to meet these criteria simultaneously and in real-time.

We introduce a new data structure, i.e. the Explicit Corridor Map, which allows creating the shortest path, the path that has the largest amount of clearance, or any path in between. Besides being efficient, the corresponding algorithms are surprisingly simple. By integrating the data structure and algorithms into the Indicative Route Method, we show that visually convincing short paths can be obtained in real-time.

Reference

  • Roland Geraerts. Planning Short Paths with Clearance using Explicit Corridors. In IEEE International Conference on Robotics and Automation (ICRA'10), pp. 1997-2004, 2010.

    pdf pptx YouTube
    A smooth, short path with clearance inside an Explicit Corridor.

Movie

The steps of our algorithm are visualized in the movie below.

Visualized steps in the algorithm that creates short paths.

The Explicit Corridor

Explicit Corridors facilitate creating the shortest path with a certain amount of minimum clearance.

Experiments (a selection)

We extracted 1,000 random corridors from the map. The average running time for extracting an Explicit Corridor was 1.19ms. Shrinking the corridor added 0.54ms. Triangulating this corridor and computing the shortest path added another 1.83ms. Hence, on average, the total time for computing the shortest (minimum-clearance) path in a corridor was 3.56ms. By using the resulting shortest paths as control paths, smooth paths were obtained, increasing the total time to 4.14ms. By having an average traveled distance of 321m, the CPU-load was 0.002% for steering a single character. Consequently, the approach is suitable for steering many characters simultaneously, as occurs in a large crowd.