Aggregate Dynamics for Dense Crowd Simulation

Published on .

Ming C.Lin's lab latest work in crowd simulation has been featured in two recent publications from MIG (International workshop on Motion In Games) 2009 and SIGGRAPH Asia 2009 (the article is already published on the author's website). The method presented int those articles, particularly the latter one, is designed to simulate the navigation behaviors of tens of thousand pedestrians at interactive rates. Let's see first the eye candy !

Open on YouTube

Impressed ? So do I, let's see how it works. This approach combines microscopic goals with macroscopic flow simulation:

  • Each agent is described by its position and its current velocity;
  • A desired velocity is computed by a global planner (roadmap based path planning for example) for each agent;
  • The navigable space is divided in cells, in each cells a flow of particles is computed using the current velocity of the agents in the cell and their density;
  • Given those initial computed velocities the global particle flow is solved at the grid level computing new velocities for each cell;
  • For each pedestrian, a new velocity is computed taking into account the desired velocity and the flow velocity weighted by the local density (The more dense the flow is, the morethe agent's velocity is influenced by the flow's);
  • Finally a simple collision detection and resolution is applied.

Both the visual results and the computation times are really interesting ! Two major problems are still not addressed: no collision prediction (two groups heading towards each other won't try to avoid before collision detection) and no way to add social convention to the avoidance behavior (favor one side of collision avoidance, avoid splitting groups...). This method should be great for dense crowds and/or used as a low LOD for navigation behaviors (this will be the topic of the next article !).

Bibliography