The purpose of this project was to see how crowds behave in different environments using a simulation that took stress of each individual crowd member into account. In addition, this project allows the user to interactively alter the environment to see real time changes in crowd behavior.

The crowd movement algorithm combines the "Boids" algorithm [1] (a common and older flocking algorithm) and some stress based models based off newer research [2].

Simulation running with Interactivity

Environment Layout


"Subway" Map

For testing purposes a "map" was created with ability to add further maps later on to run the simulationt through different preplanned environments.

Each map consists of 3 main components described below.

  • Start: area where new "persons" spawn from at a restricted random rate with random starting velocity. Represented by blue circle

  • Goal: Area where each "person" is trying to reach. When a person reaches the goal area they are removed from the map and the crowd. Represented by a red circle

  • Obstacles: Areas where persons can not go through or enter. Can either be rectangles or circles. Represented by black shape
  • By clicking on the map one can create a new obstacle at the mouse location. By dragging the clicked mouse one can create walls and any desired shape.

    By right clicking one cam remove any obstacles. By right clicking and dragging one can remove a large area at once if desired.

    This allows the user to change the environment and could be used to simulate something like an emergency situation where the environment can rapidly change. Stress based simulations like this one are very useful for emergency situations and similar high stress situations since it takes the chaos and disorganization into account [3].


Boids


Persons (boids) moving around without any stress added behavior

The popular "Boids" flocking algorithm was used as a basis for the crowd movement. The Boids algorothm models each "boid" (from here on referred to as person) individually and uses three rules to compute it's movement. A brief description is listed below

  • Seperation: Adds an acceleration vector to the person to steer it away from nearby neighbor persons

  • Alignment: Adds an accelearation vector to the person to steer it in the same direction as neighboring persons

  • Cohesion: Adds an accelearation vector to the person to steer it towards the center of mass of neighboring persons
  • In addition to these three rules, for the purpose of this project, another acceleration vector was added that directed the person to a goal. The goal was chosen randomly for each person from all the goals in the environment.

    Using these simple rules, interesting emergent behavior develops in the crowd such as people grouping together with a couple of them occasionally leaving to join another group. This gives a good basis for crowd movement but is of course not complex enough to simulate as to how actual people behave.


Stress Based Behavior


Various levels of stress

To more accurately simulate how an actual crowd might behave, a stress based behavioral model was added to the crowd movement algorithm. Each person had an individual random stress starting level.

Effect

Stress affects all components of the boids moving algorithm talked about previous. It lowers magnitude of the cohesion and alignment acceleartion vectors and raises the magnitude of the seperation vector. In addition, each individual person has a different stress tolerance. Once that tolerance is surpassed, that person would stop moving altogether.

The level of stress of a person is represented in the simulation by the shade of red that each person is rendered as. A person whose stress tolerance has ben surpassed is rendered as black.

Calculation

The stress was calculated every frame for each person by taking two factors, time taken and density of crowd, into account.

Each person was spawned with a constricted random value for the amount of time in which they want to reach their goal. If a person was "alive" for longer than their desired time then their stress would be linearly increased by the amount of time over their desired time they still hadn't reached their goal. So that the time stress level could be calculated by S * max(timeAlive - desiredTime, 0) whee S is some scalar.

Each person was also spawned with a constricted random amount of people they feel "comfortable" around. If the number of neighbors (other persons in some radius) exceeded this amount then the stress would increase linearly. So that the density stress level could be calculated by S * max(desiredNeighbors - numberOfNeighbors, 0) where S is some scalar.

Once these individual stress levels were calculated they were simply added together to determine the stress level of that person.


Measurable Results

In order to measure how the environment changes affect the crowd in a scientific fashion some information is displayed at the bottom right in the simulation which updates live.

This includes the number of people in the crowd currently being rendered on the display (crowd size) and the average stress of the entire crowd. This can be a good indicator as to how changing the environment affects the stress of the crowd and should try to be minimized.

Finally, there is also a display of the average time of a person to reach their destination from their start. This is generated by taking the average of the time alive of all the people who reached the destination in one second. This is why this value updates every second.

Lesson's Learned

There are many lessons I learned through doing this project.

One of the main ones was that changing some variable (such as the amount of seperation or the radius of which people would be considered neighbors) even by a tiny amount would have huge effects on the crowd. I played around quite a bit to scale each effect differently to have the crowd be both able to reach it's goal but still be similar to real people and not move like physics particles.

Another thing I learned about crowd simulation is that there is a very interesting problem of balancing path planning and human behavior. I have in the past worked with writing efficient path planning algorithms that would find an optimal path. However, humans don't move like this and sometimes a person who is in a hurry somewhere will still stop and be distracted by seeing someone they know and saying hello. These interactions make an accurate crowd simulation incredibly complex.


Future Goals

There are several things I would like to add and improve on in the program in the future. These include both making the crowd flocking algorithm more realistic and making more interesting maps and environments to run the simulations through.

One idea I had which I didn't have time to implement in this version of the program was to have an abstract "person" that would act as a leader and find an efficient path to the goal. Each group of people would follow slightly this person instead of trying to get directly to the goal (which often leads in people getting stuck running against a wall). For the "leader" I was planning on using the RRT* algorithm as it is able to process complex moving obstacles, starts, and goals. I had previously already written an RRT* algorithm example as can be seen below. I think it would be interesting to implement this into my current program.


In addition, to this more maps could be generated to show real life environments that have a high frequency high density amount of people having to traverse through it (e.g. subway stations, sport arena entrances, etc.)

Finally there are many other social forces that could be taken into account into the current algorithm. There are several papers that have proposed different social models such as creating different personalities for each person from a group of common social behaviors that the personality type causes.

References

[1] Craig W. Reynolds. 1987. Flocks, herds and schools: A distributed behavioral model. SIGGRAPH Comput. Graph. 21, 4 (August 1987), 25-34. DOI: https://doi.org/10.1145/37402.37406

[2] Sujeong Kim, Stephen J. Guy, Dinesh Manocha, and Ming C. Lin. 2012. Interactive simulation of dynamic crowd behaviors using general adaptation syndrome theory. In Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games (I3D '12), Stephen N. Spencer (Ed.). ACM, New York, NY, USA, 55-62. DOI=http://dx.doi.org/10.1145/2159616.2159626

[3] D. Helbing, I. Farkas, P. Molnàr, T. Vicsek. Simulation of pedestrian crowds in normal and evacuation situations In Pedestrian and Evacuation Dynamics (2002), pp. 21-58