TY - JOUR
T1 - Interactive formation control in complex environments
AU - Henry, Joseph
AU - Shum, Hubert P. H.
AU - Komura, Taku
PY - 2014/2/1
Y1 - 2014/2/1
N2 - 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 multi-touch 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 minimise 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.
AB - 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 multi-touch 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 minimise 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.
KW - Animation
KW - Artificial Intelligence
KW - computer graphics
KW - computing methodologies
KW - distributed artificial intelligence
KW - games
KW - gaming
KW - H.5.2.h input devices and strategies
KW - information interfaces and representation (HCI)
KW - intelligent agents
KW - interaction techniques
KW - modeling
KW - multiagent systems
KW - simulation
KW - three-dimensional graphics and realism
KW - types of simulation
KW - user interfaces and visualization
U2 - 10.1109/TVCG.2013.116
DO - 10.1109/TVCG.2013.116
M3 - Article
SN - 1077-2626
VL - PP
SP - 1
JO - IEEE Transactions on Visualization and Computer Graphics
JF - IEEE Transactions on Visualization and Computer Graphics
IS - 99
ER -