Coordinated Crowd Simulation With Topological Scene Analysis
Open Access
- 26 October 2015
- journal article
- research article
- Published by Wiley in Computer Graphics Forum
- Vol. 35 (6) , 120-132
Abstract
This paper proposes a new algorithm to produce globally coordinated crowds in an environment with multiple paths and obstacles. Simple greedy crowd control methods easily lead to congestion at bottlenecks within scenes, as the characters do not cooperate with one another. In computer animation, this problem degrades crowd quality especially when ordered behaviour is needed, such as soldiers marching towards a castle. Similarly, in applications such as real‐time strategy games, this often causes player frustration, as the crowd will not move as efficiently as it should. Also, planning of building would usually require visualization of ordered evacuation to maximize the flow. Planning such globally coordinated crowd movement is usually labour intensive. Here, we propose a simple solution that is easy to use and efficient in computation. First, we compute the harmonic field of the environment, taking into account the starting points, goals and obstacles. Based on the field, we represent the topology of the environment using a Reeb Graph, and calculate the maximum capacity for each path in the graph. With the harmonic field and the Reeb Graph, path planning of crowd can be performed using a lightweight algorithm, such that any blocking of one another's paths is minimized. Comparing to previous methods, our system can synthesize globally coordinated crowd with smooth and efficient movement. It also enables control of the crowd with high‐level parameters such as the degree of cooperation and congestion. Finally, the method is scalable to thousands of characters with minimal impact to computation time. It is best applied in interactive crowd synthesis systems such as animation designs and real‐time strategy games.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/M002632/1)
This publication has 32 references indexed in Scilit:
- Pedestrian Reactive Navigation for Crowd Simulation: a Predictive ApproachComputer Graphics Forum, 2007
- The corridor map method: a general framework for real‐time high‐quality path planningComputer Animation and Virtual Worlds, 2007
- Continuum crowdsACM Transactions on Graphics, 2006
- Real‐time navigating crowds: scalable simulation and renderingComputer Animation and Virtual Worlds, 2006
- Harmonic functions for quadrilateral remeshing of arbitrary manifoldsComputer Aided Geometric Design, 2005
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Anisotropic polygonal remeshingACM Transactions on Graphics, 2003
- Probabilistic roadmaps for path planning in high-dimensional configuration spacesIEEE Transactions on Robotics and Automation, 1996
- Flocks, herds and schools: A distributed behavioral modelACM SIGGRAPH Computer Graphics, 1987
- On the fluid mechanics of human crowd motionTransportation Research, 1974