Article
files/questions/crowd-icon

Simulating Crowd Dynamics: Flow Lanes and Character Animation

Alex J. Champandard on April 25, 2008

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.

Fridays at AiGameDev.com (RSS) are typically dedicated to answering emails from readers. If you have any questions on the topic of artificial intelligence in games, be sure to send them in!

Self-Absorbed Pedestrians

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 Reynoldssteering behaviors — which express movement as simple equations that you can implement directly into your code.

Large Crowds in Dead Rising

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.

Crowd Simulation in 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:

  1. 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.

  2. 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)

Conclusion

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?

Discussion 6 Comments

JonBWalsh on April 26th, 2008

It's really interesting to see how much something like a crowd can simulate other things in nature (such as the flow of a liquid). One thing that I'd really like to see in crowd simulations is a combination of the crowd behavior and intelligence at a per agent level. In most large crowd simulations the results are pretty impressive but they also seem to still have a long way to go. The simulations tend to treat each agent as independently moving. In a realistic crowd however you often have groups of people moving together that won't separate (they have a relationship with each other such as being friends). This can change the way part of the crowd moves. Agents may slow down to wait for someone to catch up or form wider 'lanes' so they can walk abreast. Another behavior that I think would really help to make the simulations look more realistic is giving the agents the right-side (or left-side in non US countries maybe) as we walk down something like a hallway or sidewalk. Rarely do you see large groups of people forming 3 lanes when doing something like walking down a hallway/sidewalk so it's a little strange to see the agents do just that in a simulation.

Andrew on April 26th, 2008

Nice lot of information, I should read through it all at some point, crowds are the new "in" :) Since Dead Rising was zombies, and Assassins Creed medieval, I want to see GTA4 and see if that has decent modern-day-alive-people crowds. Also, like I noted on the [URL="http://www.aarmstrong.org/journal/2008/02/28/gdc08-notes-streaming-open-world-pathfinding"]Streaming Open World Pathfinding[/URL] presentation, a good optimisation is having reliable crowd avoidance and removing all collision detection for NPC's for some games. I hope it works practically in Saboteur, to get a good example we can look at :D

zoombapup on April 27th, 2008

Nice post. Might I also note that there is a lot of research into REAL crowds out there. I've only skimmed it so far myself, but clearly researching the real human side of crowds can help you simulate the behavior. One other thing I find relevent and also with sparkly animation, is the work by AISeek in doing crowd simulation. [url]http://uk.youtube.com/results?search_query=aiSeek&search_type=&aq=f[/url] Check out a youtube search for aiSeek and marvel at the fun you can have. Another thing to check out, if you're interested in this area (I am btw), is the work on "massive", the AI engine used in a lot of movies for doing crowd battle scenes. I'll try and find some links later. Its an interesting area of research for me, in fact AI for "humans" is an interesting area of research really. All sorts of things come into play, as many of us have noted.

Dmitriy Iassenev on April 28th, 2008

great portion of information, Alex adding crowds to the game adds restrictions to the NPCs (simplistic AI, playing the same animations to minimize skinning time, what would be with the game if each pedestrian will have a gun and can use it?) Therefore, in the game you may have lots of simple characters or little of advanced ones (with advanced animations, AI, dynamic motion synthesis and so on). What option to choose - it's up to the game you're working on :-)

SilentBob on April 29th, 2008

Interesting read and very relevant to what I'm working on now. I'm getting good results by simply applying attractive and repulsive forces to the crowd agents. It works great for open spaces with few obstacles, but there are some problems in close, confined areas...

bigfellahull on May 1st, 2008

Great! Thanks for answering my question. Very helpful collection of information. I can see from the comments that we all pretty much agree that this field has a long way to go. I was investigating modelling crowds (which sparked my question in the first place) and have been thinking about including some psychology into the crowd... stopping, bunching etc. http://en.wikipedia.org/wiki/Crowd_psychology I like SilentBob's forces between each agent. I can imagine varying the intensity of the forces throughout the crowd could produce some interesting results.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!