Interactive Formation Control in Complex Environments

Henry, Joseph; Shum, Hubert P.H.; Komura, Taku

Abstract

The degrees of freedom of a crowd is much higher than that provided by a standard user input device. Typically, crowd-control systems require multiple passes to design crowd movements by specifying waypoints, and then defining character trajectories and crowd formation. Such multi-pass control would spoil the responsiveness and excitement of real-time control systems. In this paper, we propose a single-pass algorithm to control a crowd in complex environments. We observe that low-level details in crowd movement are related to interactions between characters and the environment, such as diverging/merging at cross points, or climbing over obstacles. Therefore, we simplify the problem by representing the crowd with a deformable mesh, and allow the user, via multitouch input, to specify high-level movements and formations that are important for context delivery. To help prevent congestion, our system dynamically reassigns characters in the formation by employing a mass transport solver to minimize their overall movement. The solver uses a cost function to evaluate the impact from the environment, including obstacles and areas affecting movement speed. Experimental results show realistic crowd movement created with minimal high-level user inputs. Our algorithm is particularly useful for real-time applications including strategy games and interactive animation creation.

Citation

Henry, J., Shum, H. P., & Komura, T. (2014). Interactive Formation Control in Complex Environments. IEEE Transactions on Visualization and Computer Graphics, 20(2), 211-222. https://doi.org/10.1109/tvcg.2013.116

• Journal Article Type: Article
• Acceptance Date: Aug 1, 2013
• Online Publication Date: Aug 16, 2013
• Publication Date: 2014-02
• Deposit Date: Sep 1, 2020
• Journal: IEEE Transactions on Visualization and Computer Graphics
• Print ISSN: 1077-2626
• Electronic ISSN: 1941-0506
• Publisher: Institute of Electrical and Electronics Engineers
• Volume: 20
• Issue: 2
• Pages: 211-222
• DOI: https://doi.org/10.1109/tvcg.2013.116
• Public URL: https://durham-repository.worktribe.com/output/1293691