Combining GPU-generated linear trajectory segments to create collision-free paths for real-time ambient crowds

Ambient crowds are used widely in today's computer games and movies. In this study, a real-time steering-free ambient crowd navigation technique is presented, which combines linear and constant-speed trajectory segments end-to-end to provide collision-free paths to simulated agents. This method seeks spatio-temporal space to find such trajectory segments by utilizing specialized features of the GPU. Each segment is required to come one after another, and at the transition points, the segments are restricted to have direction and/or speed changes within certain limits. Experiments revealed that the proposed multi-segment path technique can create denser crowds by simulating more agents (up to 53% on average and up to 44% as a maximum) than the single-segment path method existing in the literature. It is also shown in the experiments that the presented technique requires less time per navigated agent per time step (up to 98%) than a popular velocity-based microscopic method.