Real-time motion planning, navigation, and behavior for large crowds of virtual humans

Simulating crowds in real time is a challenging problem that touches many different aspects of Computer Graphics: rendering, animation, path planning, behavior, etc. Our work has mainly focused on two particular aspects of real-time crowds: motion planning and behavior. Real-time crowd motion planning requires fast, realistic methods for path planning as well as obstacle avoidance. The difficulty to find a satisfying trade-off between efficiency and believability is particularly challenging, and prior techniques tend to focus on a single approach. We have developed two approaches to completely solve crowd motion planning in real time. The first one is a hybrid architecture able to handle the path planning of thousands of pedestrians in real time, while ensuring dynamic collision avoidance. The scalability of this architecture allows to interactively create and distribute regions of varied interest, where motion planning is ruled by different algorithms. Practically, regions of high interest are governed by a long-term potential field-based approach, while other zones exploit a graph of the environment and short-term avoidance techniques. Our architecture also ensures pedestrian motion continuity when switching between motion planning algorithms. Tests and comparisons show that our architecture is able to realistically plan motion for thousands of characters in real time, and in varied environments. Our second approach is based on the concept of motion patches [Lee et al., 2006], that we extend to densely populate large environments. We build a population from a set of blocks containing a pre-computed local crowd simulation. Each block is called a crowd patch. We address the problem of computing patches, assembling them to create virtual environments (VEs), and controlling their content to answer designers' needs. Our major contribution is to provide a drastic lowering of computation needs for simulating a virtual crowd at runtime. We can thus handle dense populations in large-scale environments with performances never reached so far. Our results illustrate the real-time population of a potentially infinite city with realistic and varied crowds interacting with each other and their environment. Enforcing intelligent autonomous behaviors in crowds is a difficult problem, for most algorithms are too computationally expensive to be exploited on large crowds. Our work has been focused on finding solutions that can simulate intelligent behaviors of characters, while remaining computationally inexpensive. We contribute to crowd behaviors by developing situation-based behaviors, i.e., behaviors triggered depending on the position of a pedestrian. We have also extended our crowd motion planning architecture with an algorithm able to simulate group behaviors, which much enhances the user perception of the watched scene.