Real‐time density‐based crowd simulation
Authors:
- 9 February 2012
- journal article
- research article
- Published by Wiley in Computer Animation and Virtual Worlds
- Vol. 23 (1) , 59-69
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 two‐dimensional (2‐D) or multilayered three‐dimensional (3‐D) 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 is equal to the area occupied by all the 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. Copyright © 2012 John Wiley & Sons, Ltd.Keywords
This publication has 16 references indexed in Scilit:
- Navigation meshes for realistic multi-layered environments2011
- Graph-based approaches for simulating pedestrian dynamics in building models2010
- Directing Crowd Simulations Using Navigation FieldsIEEE Transactions on Visualization and Computer Graphics, 2010
- Aggregate dynamics for dense crowd simulationACM Transactions on Graphics, 2009
- Modeling crowd evacuation of a building based on seven methodological approachesBuilding and Environment, 2009
- A Predictive Collision Avoidance Model for Pedestrian Simulation2009
- Real-time crowd motion planningThe Visual Computer, 2008
- The visibility–Voronoi complex and its applicationsComputational Geometry, 2007
- Continuum crowdsACM Transactions on Graphics, 2006
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996