Friday, November 23, 2012

Crowd Simulation - Getting Started

Well I am not an expert on crowd simulation, but I have been reading up a lot over the past few weeks. Here I am presenting a list of key readings for someone who wants to get started with it. My main area of interest is behavioral animation so this reading list is geared more towards that.

1. Crowd Simulation by Daniel Thalmann and Soraia Raupp Musse.
I think this is the key text if you wanted to get started with crowd sims. It is like a huge survey paper of what is going on in the field. It is a bit dated now and doesn't include the research from the last 4-5 years, but still is a great starting point.

2. Flocks, Herd and Schools: A Distributed Behavioral Model by Criag Reynolds.
This is where it all started for behavioral animation. The model presented here, however simple, is still very relevant and effective. This is a must read for someone looking to get down and dirty with crowd-sims. Reynold's model works on a premise that if we simulate relatively simple individuals effectively, group behavior will automatically surface. He was able to demonstrate his theory very effectively in the artifact he created.

3. Artiļ¬cial Fishes: Physics, Locomotion, Perception, Behavior by Tu and Terzopoulos 
The model presented by these researchers is based on the same basic premise as Reynolds. However, this is a much more complex and evolved model. The fish in their model have internal states like hunger, libido etc and also some 'habit parameters'. On a second level they have evolved behavior like hunting, mating and schooling. On another level the fish have sensing capabilities and could sense things like temperature for example.

To make this model work there is an algorithm that generates intentions based on internal states and environment variables and produces an output. This output is then passed down to the behavior routines engine and this specify what lower level actions to perform to fulfill the intentions.

This reading is a bit dated but is still relevant as a lot of research in the field has branched out of here. It still remains a key reading for a beginner.

4. Hierarchical Model for Real Time Simulation of Virtual Human Crowds: 
Soraia Raupp Musse and Daniel Thalmann
This paper is a bit advanced and discusses a few more higher level concepts. The main aim of this paper is to come up with a real-time model of crowd simulation. The paper discusses two major points, Crowd Structures and Crowd Behaviours.

Crowds are structured in a hierarchical manner and has 3 levels: Crowd, Group and Individual. The parameters set at a higher level are inherited at the lower level. At the lower level, these parameters can be over-riden. So for example, if we make a crowd 'happy', we can have a group or an individual who is 'sad' and then this entity will behave in a different manner.

In this model, groups are the most complex entity. The individual agents share a decision process and all the information required for this process. The model allows for complex group behaviour like splitting or mutiny.

5. Group Behaviours for Systems with Significant Dynamics by Brogan and Hodgins
This paper mainly talks about something they call 'significant dynamics', i.e., the simulation of crowds where the dynamics of locomotion of the agents is complex enough to impact the behaviour.

The more relevant part of the paper is where they present the algorithm for group behaviour. They divide it into two parts: Perception and Placement. Perception allows the agent to sense the relative position and velocities of other agents and static objects. Placement works by computing a desired position of an entity. All the approaches actually use this higher level algorithm, however, the lower level implementation detail differs.

6. Crowd Simulation for Virtual Heritage: Branislav Ulicny and Daniel Thalmann
The concept presented in this very brief paper is very elegant, although a bit advanced for the beginner. This is a three level system.

On the topmost level there are rules which have two parts. The antecedent part defines which agents are allowed to use which rules and under what circumstances. The consequent part defines the effects of firing the rule which can be change in current agent behaviour, attributes or event triggering.

The current behaviour is performed at the intermediate level. Here every possible behaviour is implemented as a Finite State Machine(FSM)

On the bottom-most level we have algorithms for path planning and collision avoidance etc.

The reading list given above is in now way exhaustive, but will help someone new to crowd simulations to get a hang of what are the major issues and how are they generally handled. It would also help the reader get comfortable with the jargon. From here you can graduate on to newer ideas and more current research.


No comments:

Post a Comment