Crowd Simulation with Arrival Time Constraints

Abstract

Finding collision-free paths for crowd simulation has been a core technique in video games and the film industry; it has drawn a great deal of attention from computer animation researchers for several decades. Additionally, theoretical modeling of pedestrian has been a hot topic in physics as well because it allows us to predict any architectural failure of buildings and many city planning problems. However, the existing studies for path planning cannot guarantee the arrival order, which is critical in many cases, such as arrival symmetry of the characters within video games or films. To resolve this issue, a path planning algorithm has been developed with a novel method for satisfying the arrival-order constraints. The time constraint we suggest is the temporal duration for each character, specifying the order in which they arrive at their target positions. In addition to the algorithm that guarantees the arrival order of objects, a new user interface is suggested for setting up the arrival order. Through several experiments, the proposed algorithm was verified, and can successfully find collision-free paths, while satisfying the time constraint set by the new user interface. Given the available literature, the suggested algorithm and the interface are the first that support arrival order, and their usability is proven by user studies.

Keywords

• computer animation
• crowd simulation
• multi-agent simulation
• time constraints