Motion Planning for Human Crowds: from Individuals to Groups of Virtual Characters

Virtual worlds, to become more lively and appealing, are typically populated by large crowds of virtual characters. One of the fundamental tasks that these characters have to perform is, on one hand, to plan their paths between different locations in the world and, on the other hand, to move toward their desired locations in a human-like manner avoiding collisions with each other and with the environment. This is the main topic of this thesis. Although the path planning problem has received considerable attention over the past thirty years, most path planning algorithms originate from robotics aiming at creating short and collision-free paths for one or a few robots having many degrees of freedom. In interactive virtual worlds, though, the requirements are different. Paths for hundreds of characters through complex environments should be planned simultaneously and in real-time using only a small percentage of the CPU time. In addition to being collision-free, the paths followed by the characters must also look plausible in order to retain the suspension of disbelief of the viewer. Such paths typically follow smooth curves, are short and keep a certain amount of clearance to obstacles. To address the aforementioned issues, in the first part of the thesis, we introduce the Indicative Route Method as a new path planning approach in interactive virtual worlds and games. We further combine the Indicative Route Method with techniques from Linear Programming to efficiently choreograph through space-time the motions of large heterogeneous groups of virtual characters. We also present simple techniques for creating variants of homotopic paths that virtual characters can follow given a path planning query. Such variation not only provides a more challenging and less predictable opponent for the user in a (serious) game, but also enhances the realism of a simulation allowing the characters to spread over the environment and take alternative routes. Besides demonstrating believable path planning behavior, the virtual characters should also be able to adapt their motions resolving a bewildering amount of local interactions and avoiding collisions with each other. This problem is very challenging, since real humans exhibit behaviors of enormous complexity and subtlety making their simulation a rather difficult task. In the second part of the thesis, we try to address some of these challenges. We first propose a physically-based model for solving interactions between virtual pedestrians that have converging trajectories. The proposed method is extremely fast, simple to implement and captures the emergence of self-organization phenomena allowing interactions to be solved more efficiently at a global scale. We also address the issue of realistic collision avoidance among virtual humans by exploiting experimental interactions data between real pedestrians. In the derived model, virtual characters take early and effort-efficient actions to avoid collisions by slightly adapting their directions and speeds. We further extend this technique to simulate the walking behavior of small groups of virtual pedestrians. Here, a novel algorithm is introduced ensuring that the group members will safely navigate toward their goals, while forming walking patterns similar to the ones observed in real-life