Virtual crowds
New techniques to populate virtual worlds with thousands of characters
Contrary to real worlds, many game worlds contain only very few people. As a result the worlds feel uninhabited. To give game worlds a lively feeling we need to simulate large crowds of virtual characters. New techniques have been developed for this that are efficient and lead to natural crowd behavior.

A basic operation that virtual characters must perform is navigating from their current location in the virtual world to a desired new location. This problem is called the path planning problem. Often multiple characters move in large groups or crowds in the same environment, in which case we talk about crowd simulation. Path planning and crowd simulation play an important role in the immersion that a player experiences in a game. Existing real-time crowd simulation approaches fail to deliver motions that are natural. This project studies new, practical path planning and crowd simulation algorithms that efficiently generate convincing paths.

We developed a new approach to path planning that is very fast and flexible. During a preprocessing phase we compute a network of routes through the environment, similar to waypoint graphs that are often used in games. But we do not follow these routes directly! The paths are only used as an indication. With each route we store a collision-free corridor. This corridor gives the character flexibility to choose its path. While it globally follows the indicative route to its goal, locally it can deviate from the path, as long as it stays within the corridor. This approach can plan thousands of paths simultaneously with little CPU usage. We use this approach as the basis for our crowd simulation technique. While characters globally follow their indicative routes they must avoid other characters. We developed a new approach for character avoidance based on observations of behavior of real people. The characters predict collisions and take early action to avoid them by making small changes to their direction and speed. Recently we extended this to characters walking in pair and triples. The resulting motions are much more natural and we can simulate crowds of thousands of people at interactive frame rates.

In different situations crowds of people behave differently. For example, in a railway station many people stand still while others run. But in a shopping center people tend to wander around slowly. We currently investigate these different types of behavior and we will design algorithms to simulate different types of crowds. Also the personality, mood, and age of people strongly influence their walking behavior. Angry people walk faster and are less willing to deviate from their path. People that are distracted, for example when using a mobile phone, walk slowly and pay little attention to other people. We will construct a general framework to deal with these different types of people in a crowd. Finally we will study replanning, which is required when a path that is chosen by a character is blocked. Integrating all these elements will lead to much improved and more generic crowd simulation software.

Workpackage
2.3 Natural paths for virtual entities

Partners
Utrecht University

Key Publications
I. Karamouzas et al. (2008). Adding variation to path planning. Computer Animation and Virtual Worlds 19, pp. 283-293.
I. Karamouzas et al. (2009). Indicative routes for path planning and crowd simulation. Proc. fourth international conference on Foundations of Digital Games, pp. 113-120.
I. Karamouzas et al. (2009). A predictive collision avoidance model for pedestrian simulation. Proc. Motion in Games, pp. 41-52.
More publications.

Contact details
Frank van der Stappen, Utrecht University
A.F.vanderStappen(at)uu.nl