The latest generation of consoles presents an opportunity for studios to opt for quantity over quality, by adding many more characters in their games than was previously possible. These crowds can have a dramatic impact on both gameplay and the overall experience. This article looks at how you can simulate large numbers of NPCs in a game, including practical advice, white papers and their videos.
This article is based on a question by James Hull who writes:
“I was wondering if you have ever looked at Crowd Dynamics. I can only think of one game (Assassin’s Creed) that has truly used crowd simulation as a game character. I would be really interested to know how they achieved what they did.”
Although game developers don’t often focus their efforts on crowd simulations, there’s a huge amount of research to draw from when necessary. I’ve collected almost a dozen papers about simulating groups of people, ranging from low-level animation details to modeling the flow of game actors as particles. See the White Paper section of the forums (registration and introduction required) for references to all the papers, or read on for a selection of the best and most appropriate.
The first thing to realize is that crowds are made of individual people, obviously! But if you model individual actors and give them a basic ability to avoid other people, then you can get pretty impressive crowd behaviors that emerge from the sheer numbers, as in the game Dead Rising. In fact, this is probably the best ratio of implementation cost to results obtained, as it requires only simple techniques that game developers are already very comfortable with.
In practice, what you need are reactive navigation techniques as used in the field of robotics for decades. In the context of games, this research was epitomized by Craig Reynolds‘ steering behaviors — which express movement as simple equations that you can implement directly into your code.
Screenshot 1: Large crowds in Dead Rising (Large)
Animations for Bumping into People
In a first- or third-person game, the feel of a crowd is portrayed primarily by the character animations. In Assassin’s Creed for example, the developers spent a lot of time working on animation technology for bumping into characters. When the player (or another aggressive NPC) rushes through the crowd, this makes a big difference.
Technically, there are a few ways to achieve this, but the best solution is to select an appropriate reaction from a motion-capture database. There doesn’t have to be many clips for this to work, just four “bumping” animations for each cardinal direction. If you have more animations, then you can do some blending into parametric animations — but it’ll cut into your computational budget very quickly.
Dynamic Response for Motion Capture Animation Victor Zordan, Anna Majkowska, Bill Chiu, Matthew Fast ACM Transactions on Graphics, SIGGRAPH 2005. Download PDF (9.1 Mb)
This first white paper applies primarily to close combat, but you can also use it for simulating directional bumps in a crowd. The second paper below is also quite similar, which goes to show how generic and versatile this technique can be!
Animating Reactive Motion Using Momentum-based Inverse Kinematics and Captured Motion Taku Komura, Ho Shu Lim, Rynson W. H. Lau Computer Animation and Virtual Worlds Journal, 2005. Download PDF (518 Kb)
Combining Individual Behaviors
Individual reactive behaviors with high-quality animations will only get you so far. To improve the behavior crowd, you’ll also need to model small groups. In Assassin’s Creed for example, there are groups of similar characters that wander around together. This not only looks great, but it also provides an additional gameplay element since the player can merge into these groups to hide.
Technically, you can implement groups using very similar techniques than the individuals:
Use high-level goals and destinations for the group only.
Apply the pathfinder for the group as a whole.
Let each individual follow the path reactively.
You can also use loose formations to provide a bit more structure to the group. Think of a formation as a shape following a path, and attach individual actors to each point in the shape. This is a good way to implement columns of monks, to take an example from Assassin’s Creed.
Screenshot 2: Crowd simulation in Assassin’s Creed (Large)
Flocking vs. Flow Modeling
Taking the crowd behaviors beyond groups involves modeling the dynamic patterns that occur naturally when individuals get together in the real world. This includes the formation of pedestrian lanes which help increase the flow within a crowd. To implement this, you have two options:
Use flocking behaviors from Craig Reynolds. This is the simplest solution; get each individual to move based on others nearby, for example adjusting direction and velocity dynamically. The result can end up looking pretty good despite the simplicity of the code.
For a better quality simulation, you’ll need to explicitly model the crowd’s flow using continuum dynamics for example. This involves writing a simple physical simulation that treats characters as particles moving around. The results look very impressive, and it’s the kind of code you can parallelize with little effort.
See an example of the flow modeling in this paper:
Continuum Crowds A. Treuille, S. Cooper, Z. Popovi? ACM Transactions on Graphics, SIGGRAPH 2006. Download PDF (3.2 Mb)
Crowds can be a very effective way to add depth to a game. These behaviors can emerge by plugging together surprisingly simple techniques. Try to start simple and build up the features of your simulation, roughly in the order of this article.
If your game engine can render large numbers of characters, you won’t need too much AI to get a pretty descent crowd. Focus on reactive behaviors that take into account nearby actors first, then improve your animation to make sure the interactions look good enough.
Beyond that, simulating groups can be a very effective way to make the crowds seem more structured. Groups can be implemented using the very same navigation as individual characters (both path-finding and reactive locomotion), so try to use them whenever appropriate. Techniques like flocking can improve the flow of the crowd locally, but consider doing a full physical simulation if you’re after the best quality results.
In what games have you seen good crowd simulations? What behaviors would you like to see in such crowds?