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

Real-Time Density-Based Crowd Simulation

When density information is considered, the characters will naturally spread out among the available routes.

Abstract

Virtual characters in games and simulations often need to plan visually convincing paths through a crowded environment. This paper describes how crowd density information can be used to guide a large number of characters through a crowded environment. Crowd density information helps characters avoid congested routes that could lead to traffic jams. It also encourages characters to use a wide variety of routes to reach their destination.

Our technique measures the desirability of a route by combining distance information with crowd density information. We start by building a navigation mesh for the walkable regions in a polygonal 2D or multi-layered 3D environment. The skeleton of this navigation mesh is the medial axis. Each walkable region in the navigation mesh maintains an up-to-date density value. This density value equals the area of all characters inside a given region divided by the total area of this region. These density values are mapped onto the medial axis to form a weighted graph. An A* search on this graph yields a backbone path for each character, and forces are used to guide the characters through the weighted environment. The characters periodically replan their routes as the density values are updated. Our experiments show that we can compute congestion-avoiding paths for tens of thousands of characters in real-time.

References

  • Wouter G. van Toll, Atlas F. Cook IV and, Roland Geraerts. Real-Time Density-Based Crowd Simulation. Computer Animation and Virtual Worlds (CAVW), 23(1):59-69, 2012.

    Full text

  • Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Realistic Crowd Simulation with Density-Based Path Planning. ASCI - IPA - SIKS tracks, ICT.OPEN (ICT.OPEN 2012), pp. 3-9, 2012. This paper has received the best presentation award ASCI 2012.

    pdf poster pptx

Movie

The method is demonstrated in the following movie.

Adding Sociality to Virtual Pedestrian Groups.

Results

Although it is common to steer characters along short paths to their destinations, high congestion can lead to traffic jams that seem unnatural when many routes are underutilized in an environment. To improve the realism of our simulations, we used crowd density information to guide a large number of characters along a wide variety of routes. We did this by building a navigation mesh and weighting the desirability of routes based on the crowd density along the path. Our technique can guide tens of thousands of characters through a polygonal 2D or multi-layered 3D environment in real-time. The movie highlights the effectiveness of these techniques in both 2D and 2.5D environments.