This post is the first of a series about crowd simulation. “Why crowd simulation specifically ?” one might ask. And I say it’s because I studied crowd simulation for several years and, although I do not work on this subject anymore, I do like to talk about it.
In this article, I will give an overview about crowd simulation (no code this time), but in the following articles in this series I will focus mostly on crowd navigation.
But first, what is crowd simulation about ?
Crowd simulation is a multidisciplinary field that focuses on simulating the behavior of several entities (let’s call them ‘agents’) as well as the interactions among them that might emerge naturally. These agents not necessarily represent humans, they can be fishes, birds, robots or whatever you want. Consequently, we are not limited to simulating walking behavior but also flying or swimming, example.
Simulating a crowd is challeging because it involves not only steering the agents (what itself is complex enough), but also making them look visually different and having different animations. Not to mention the need of rendering several of them (sometimes in realtime).
Application
There are different applications for crowd simulators. They can be used in videogames, such as we have seen in Kameo, Assassin’s creed series and Dead rising series, for example. The following videos show footages of Assassin’s Creed Unity and the recent Planet Coaster (check this gamasutra article).
They are also useful in the architectural engineering field. When designing a stadium, for example, one need to place exit doors in order to optimize the evacuation of people in an emergency situation. Crowd simulators can be used to help this kind of design. Some simulators can even give information about the build up pressure when human traffic jams happen.
Some crowd simulators are intended to study the human behavior and try to faithfully replicate it from ground truth. Several emerging patterns can be observed within real crowds interactions and these simulators try to reach that.
Finally, crowd simulators can be used in movies and TV series, of course. Lord of the rings, world war z, the walking dead, game of thrones, just to cite a few examples.
Trivia: the Massive software was specially developed for Lord of the rings.
Trivia 2: Golaem is the Maya plugin used in TV series like Game of Thrones and The Walking Dead.
The demands for a simulator will depend on its objective. For movies, both visuals and behaviors have to have a high quality, whereas real-time execution is not expected. Human behavior studies and civil engineering applications expect “realistic” behavior, real-time execution, but not much from visuals. In games, we need real-time interaction, pleasant visual and pleasant (but not necessarily realistic) behavior.
Realism is subjective, that’s why I used the quotation marks when saying “realistic” behavior. A simulator can have a perfect execution, organizing everybody in a beatiful flow, where everybody avoids collision with each other, forming lanes in the counterflow. Is that realistic? It might be, if we are simulating an army, for example; and it is not if we are trying to simulate the Shibuya crossing (Tokyo, Japan).
Navigation
Perhaps the most important, and consequently the most investigated, part of a crowd simulator is the navigation system. A simulator needs to be able to make agents reach their goals while traversing complex environments and avoiding collisions with other agents or obstacles. We can separate the navigation in two categories: global and local.
The global navigator is responsible for managing the global goals of the agents. For example, an agent starts at A and has to go to B, once it gets to B the global navigator update its objective and now the agent knows that it has to go to C, and so on. You probably already heard about the algorithm A*, it is a extended Djikstra broadly used for global navigation or at least used as inspiration for some other algorithms. If instead of moving point-to-point we are interested in moving from a set of points within an area to another set of points, we can resort then to a navigation mesh, that represents the navigable space within an environment and this way provides more options of movement.
Difference of paths when moving between waypoints and using a navigation mesh (found this image here).
A local navigator is responsible for making the agent move safely from A to B. The main task here is to avoid collisions with static and dynamic obstacles. There are several approaches to solve this, agents can: be endowed with cooperative rules, be treated as particles in a particle system, move according flow fields, react according to their synthetic vision, adjust their velocities reciprocally, among many others approaches that you can find the literature.
Engines
Both Unity and Unreal come with global and local navigators. For global navigation, they use navigation meshes and for local navigation they use a model of reciprocal collision avoidance (RVO) (Unreal also comes with Detour crowd) (Unity’s doc and some info from Unreal).
Conclusion
This was a brief introduction to crowd simulation, not very deep but with some useful information to start. The next posts in this series will be related to navigation, I’ll start with global navigators and then move to the local ones (this order might change or this might never happen as well :P).
Here are some references for those that want more info about this field.
Books
Simulating Heterogeneous Crowds with Interactive Behaviors
Articles
Flocks, Herds, and Schools: A Distributed Behavioral Model (All started here)
Social force model for pedestrian dynamics
Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation
Gradient-based steering for vision-based crowd simulation algorithms (my last work on crowds)
