  Exploiting the efficiency and stability of Position-Based Dynamics (PBD), we
introduce a novel crowd simulation method that runs at interactive rates for
hundreds of thousands of agents. Our method enables the detailed modeling of
per-agent behavior in a Lagrangian formulation. We model short-range and
long-range collision avoidance to simulate both sparse and dense crowds. On the
particles representing agents, we formulate a set of positional constraints
that can be readily integrated into a standard PBD solver. We augment the
tentative particle motions with planning velocities to determine the preferred
velocities of agents, and project the positions onto the constraint manifold to
eliminate colliding configurations. The local short-range interaction is
represented with collision and frictional contact between agents, as in the
discrete simulation of granular materials. We incorporate a cohesion model for
modeling collective behaviors and propose a new constraint for dealing with
potential future collisions. Our new method is suitable for use in interactive
games.
