Real-time motion planning of multiple formations in virtual environments: Flexible virtual structures and continuum model

We present a novel approach for real-time motion planning of multiple formations in virtual environments with dynamic obstacles. Our algorithm is based on the continuum model for crowd simulation and our flexible virtual structure approach for formation control in virtual environments. Simulations created with our algorithm run at interactive rates in quite complex environments. In addition, each formation can be deformed in real-time and the deformation is triggered either automatically (e.g., when the formationpsilas path is blocked by dynamic obstacles) or manually. Via simulations, we show that we can plan at least four formations, each with tens of agents, in real-time on a PC.