View source for Crowd simulation

{{Short description|Model of movement}}
{{3D computer graphics}}
'''Crowd simulation''' is the process of simulating the movement (or '''{{vanchor|dynamics|CROWD_DYNAMICS}}''') of a large number of entities or characters.<ref>{{cite book |doi=10.1007/978-3-319-08234-9_69-1 |chapter=Crowd Simulation |title=Encyclopedia of Computer Graphics and Games |pages=1–8 |year=2016 |last1=Thalmann |first1=Daniel |isbn=978-3-319-08234-9 }}</ref> It is commonly used to create [[Virtual cinematography|virtual scene]]s for visual media like films and [[video game]]s, and is also used in crisis training,<ref>{{cite conference |url=http://cc.ist.psu.edu/BRIMS/archives/2007/papers/07-BRIMS-025.pdf |archive-url=https://web.archive.org/web/20161221001136/http://cc.ist.psu.edu/BRIMS/archives/2007/papers/07-BRIMS-025.pdf |archive-date=2016-12-21 |first1=Jérôme |last1=Comptdaer |first2=Emmanuel |last2=Chiva |first3=Stéphane |last3=Delorme |first4=Henri |last4=Morlaye |first5=Jérôme |last5=Volpoët |title=Multi-scale behavioral models for urban crisis training simulation |page=317 |conference=16th Conference on Behavior Representation in Modeling and Simulation 2007 |date=March 2007 }}</ref> architecture and urban planning,<ref>{{cite journal |doi=10.1162/pres.16.3.318 |title=Design and Evaluation of a Real-World Virtual Environment for Architecture and Urban Planning |journal=Presence: Teleoperators and Virtual Environments |volume=16 |issue=3 |pages=318–32 |year=2007 |last1=Drettakis |first1=George |last2=Roussou |first2=Maria |last3=Reche |first3=Alex |last4=Tsingos |first4=Nicolas |url=https://hal.inria.fr/inria-00607261/file/DRRT07.pdf }}</ref> and evacuation simulation.<ref>{{cite journal |doi=10.1016/S0360-1323(98)00057-2 |title=A review of the methodologies used in the computer simulation of evacuation from the built environment |journal=Building and Environment |volume=34 |issue=6 |pages=741–9 |year=1999 |last1=Gwynne |first1=S. |last2=Galea |first2=E.R. |last3=Owen |first3=M. |last4=Lawrence |first4=P.J. |last5=Filippidis |first5=L. |bibcode=1999BuEnv..34..741G }}</ref>

Crowd simulation may focus on aspects that target different applications. For realistic and fast [[rendering (computer graphics)|rendering]] of a crowd for visual media or [[virtual cinematography]], reduction of the complexity of the [[3D scene]] and [[image-based rendering]] are used,<ref>{{cite journal |doi=10.1111/1467-8659.00633 |title=Visualizing Crowds in Real-Time |journal=Computer Graphics Forum |volume=21 |issue=4 |pages=753–65 |year=2002 |last1=Tecchia |first1=Franco |last2=Loscos |first2=Celine |last3=Chrysanthou |first3=Yiorgos }}</ref> while variations (changes) in appearance help present a realistic population.<ref name="Thalmann et al 2009">{{cite book |doi=10.1109/CW.2009.23 |chapter=Challenges in Crowd Simulation |title=2009 International Conference on CyberWorlds |pages=1–12 |year=2009 |last1=Thalmann |first1=Daniel |last2=Grillon |first2=Helena |last3=Maim |first3=Jonathan |last4=Yersin |first4=Barbara |isbn=978-1-4244-4864-7 |url=https://infoscience.epfl.ch/record/159013/files/CW2009.pdf }}</ref><ref name="Maim et al 2009">{{cite journal |doi=10.1109/MCG.2009.129 |pmid=24806782 |title=Unique Character Instances for Crowds |journal=IEEE Computer Graphics and Applications |volume=29 |issue=6 |pages=82–90 |year=2009 |last1=Maim |first1=J. |last2=Yersin |first2=B. |last3=Thalmann |first3=D. }}</ref>

In games and applications intended to replicate real-life [[human]] crowd movement, like in evacuation simulations, simulated agents may need to navigate towards a goal, avoid collisions, and exhibit other human-like behavior. Many crowd steering algorithms have been developed to lead simulated crowds to their goals realistically. Some more general systems are researched that can support different kinds of agents (like cars and pedestrians),<ref>{{cite journal |doi=10.1002/cav.1654 |title=Vehicle-pedestrian interaction for mixed traffic simulation |journal=Computer Animation and Virtual Worlds |volume=26 |issue=3–4 |pages=405–12 |year=2015 |last1=Chao |first1=Qianwen |last2=Deng |first2=Zhigang |last3=Jin |first3=Xiaogang }}</ref> different levels of abstraction (like individual and continuum),<ref>{{cite journal |doi=10.1145/2070781.2024169 |title=Interactive hybrid simulation of large-scale traffic |journal=ACM Transactions on Graphics |volume=30 |issue=6 |page=1 |year=2011 |last1=Sewall |first1=Jason |last2=Wilkie |first2=David |last3=Lin |first3=Ming C. }}</ref> agents interacting with smart objects,<ref>{{cite book |doi=10.1007/978-3-7091-6375-7_6 |chapter=Modeling Objects for Interaction Tasks |title=Computer Animation and Simulation '98 |url=https://archive.org/details/computeranimatio1999poll |url-access=limited |pages=[https://archive.org/details/computeranimatio1999poll/page/n77 73]–86 |series=Eurographics |year=1999 |last1=Kallmann |first1=Marcelo |last2=Thalmann |first2=Daniel |isbn=978-3-211-83257-8 }}</ref> and more complex physical and [[social dynamics]].<ref>{{cite conference |doi=10.2312/SCA/SCA07/099-108 |date=2007 |last1=Pelechano |first1=N. |last2=Allbeck |first2=J.M. |last3=Badler |first3=N.I. |title=Controlling Individual Agents in High-Density Crowd Simulation |conference=Eurographics/Siggraph Symposium on Computer Animation |isbn=978-3-905673-44-9 }}</ref>

== History ==
There has always been a deep-seated interest in the understanding and gaining control of motional and behavior of crowds of people. Many major advancements have taken place since the beginnings of research within the realm of crowd simulation. Evidently many new findings are continually made and published following these which enhance the scalability, flexibility, applicability, and realism of simulations:

In 1987, behavioral animation was introduced and developed by [[Craig Reynolds (computer graphics)|Craig Reynolds]].<ref>{{cite book |doi=10.1145/37401.37406 |chapter=Flocks, herds and schools: A distributed behavioral model |title=Proceedings of the 14th annual conference on Computer graphics and interactive techniques |date=1987 |last1=Reynolds |first1=Craig W. |pages=25–34 |isbn=0-89791-227-6 |url=http://elartu.tntu.edu.ua/handle/lib/43005 }}</ref> He had simulated flocks of birds alongside schools of fish for the purpose of studying group intuition and movement. All agents within these simulations were given direct access to the respective positions and velocities of their surrounding agents. The theorization and study set forth by Reynolds was improved and built upon in 1994 by [[Xiaoyuan Tu]], [[Demetri Terzopoulos]] and Radek Grzeszczuk.<ref>{{cite journal |last1=Terzopoulos |first1=Demetri |last2=Tu |first2=Xiaoyuan |last3=Grzeszczuk |first3=Radek |title=Artificial Fishes: Autonomous Locomotion, Perception, Behavior, and Learning in a Simulated Physical World |journal=Artificial Life |date=July 1994 |volume=1 |issue=4 |pages=327–351 |doi=10.1162/artl.1994.1.4.327 }}</ref> The realistic quality of simulation was engaged with as the individual agents were equipped with synthetic vision and a general view of the environment within which they resided, allowing for a perceptual awareness within their dynamic habitats.

Initial research in the field of crowd simulation began in 1997 with [[Daniel Thalmann]]'s supervision of Soraia Raupp Musse's PhD thesis. They present a new model of crowd behavior in order to create a simulation of generic populations.<ref>{{Cite book|url=https://books.google.com/books?id=3Adh_2ZNGLAC&q=history+of+crowd+simulation&pg=PR8|title=Crowd Simulation|last1=Thalmann|first1=Daniel|last2=Musse|first2=Soraia Raupp|date=2012-10-04|publisher=Springer Science & Business Media|isbn=978-1-4471-4449-6|language=en}}</ref> Here a relation is drawn between the autonomous behavior of the individual within the crowd and the emergent behavior originating from this.<ref>{{cite book |doi=10.1007/978-3-7091-6874-5_3 |chapter=A Model of Human Crowd Behavior : Group Inter-Relationship and Collision Detection Analysis |title=Computer Animation and Simulation '97 |url=https://archive.org/details/computeranimatio1997bode |url-access=limited |pages=[https://archive.org/details/computeranimatio1997bode/page/n46 39]–51 |series=Eurographics |year=1997 |last1=Musse |first1=S. R. |last2=Thalmann |first2=D. |isbn=978-3-211-83048-2 }}</ref>

In 1999, individualistic navigation began its course within the realm of crowd simulation via continued research of Craig Reynolds.<ref>{{Cite web|url=http://www.red3d.com/cwr/papers/1999/gdc99steer.html|title=Steering Behaviors For Autonomous Characters|website=www.red3d.com|access-date=2016-12-17}}</ref> Steering behaviors are proven to play a large role in the process of automating agents within a simulation. Reynolds states the processes of low-level locomotion to be dependent and reliant on mid-level steering behaviors and higher-level goal states and path finding strategies. Building off of the advanced work of Reynolds, Musse and Thalmann began to study the modeling of [[real-time simulation|real time simulation]]s of these crowds, and their applications to human behavior. The control of human crowds was designated as a hierarchical organization with levels of autonomy amongst agents. This marks the beginnings of modeling individual behavior in its most elementary form on humanoid agents or [[virtual humans]].<ref>{{cite journal |doi=10.1109/2945.928167 |title=Hierarchical model for real time simulation of virtual human crowds |journal=IEEE Transactions on Visualization and Computer Graphics |volume=7 |issue=2 |pages=152–64 |year=2001 |last1=Musse |first1=S.R. |last2=Thalmann |first2=D. |url=http://infoscience.epfl.ch/record/98931 |type=Submitted manuscript }}</ref>

Coinciding with publications regarding human behavior models and simulations of group behaviors, Matt Anderson, Eric McDaniel, and Stephen Chenney's proposal of constraints on behavior<ref>{{Cite news|author1=Matt Anderson|author2=Eric McDaniel|author3=Stephen Chenney|title=Constrained animation of flocks|publisher=SCA '03 Proceedings of the 2003 ACM SIGGRAPH/Eurographics symposium on Computer animation |pages= 286–297|date=July 26–27, 2003 |isbn=1-58113-659-5 }}</ref> gained popularity. The positioning of constraints on group animations was presented to be able to be done at any time within the simulation. This process of applying constraints to the behavioral model is undergone in a two-fold manner, by first determining the initial set of goal trajectories coinciding with the constraints, and then applying behavioral rules to these paths to select those which do not violate them.

Correlating and building off of the findings proposed in his work with Musse, Thalmann, working alongside Bratislava Ulicny and Pablo de Heras Ciechomski, proposed a new model which allowed for interactive authoring of agents at the level of an individual, a group of agents and the entirety of a crowd. A brush metaphor is introduced to distribute, model and control crowd members in real-time with immediate feedback.<ref>{{cite book |doi=10.1145/1028523.1028555 |chapter=Crowdbrush |title=Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation – SCA '04 |pages=243–52 |year=2004 |last1=Ulicny |first1=Branislav |last2=Ciechomski |first2=Pablo de Heras |last3=Thalmann |first3=Daniel |isbn=978-3-905673-14-2 |url=http://infoscience.epfl.ch/record/100256 }}</ref>

== Crowd dynamics ==
One of the major goals in crowd simulation is to steer crowds realistically and recreate human dynamic behaviors.

There exists several overarching approaches to crowd simulation and AI, each one providing advantages and disadvantages based on crowd size and time scale. Time scale refers to how the objective of the simulation also affects the length of the simulation. For example, researching social questions such as how ideologies are spread amongst a population will result in a much longer running simulation since such an event can span up to months or years. Using those two characteristics, researchers have attempted to apply classifications to better evaluate and organize existing crowd simulators.<ref>{{cite journal |doi=10.1145/1842722.1842725 |title=Crowd modeling and simulation technologies |journal=ACM Transactions on Modeling and Computer Simulation |volume=20 |issue=4 |pages=1–35 |year=2010 |last1=Zhou |first1=Suiping |last2=Chen |first2=Dan |last3=Cai |first3=Wentong |last4=Luo |first4=Linbo |last5=Low |first5=Malcolm Yoke Hean |last6=Tian |first6=Feng |last7=Tay |first7=Victor Su-Han |last8=Ong |first8=Darren Wee Sze |last9=Hamilton |first9=Benjamin D. |hdl=10149/118022 |url=https://research.tees.ac.uk/ws/files/6477586/Accepted_manuscript.pdf }}</ref>

;Flow-based Approach: Flow based crowd simulations focus on the crowd as a whole rather than its components. As such individuals do not have any distinctive behaviors that occur due to input from their surroundings and behavioral factors are largely reduced.<ref name="Degond">{{cite journal |last1=Degond |first1=Pierre |last2=Navoret |first2=Laurent |last3=Bon |first3=Richard |last4=Sanchez |first4=David |title=Congestion in a Macroscopic Model of Self-driven Particles Modeling Gregariousness |journal=Journal of Statistical Physics |date=February 2010 |volume=138 |issue=1–3 |pages=85–125 |doi=10.1007/s10955-009-9879-x |arxiv=0908.1817 |bibcode=2010JSP...138...85D }}</ref> This model is mainly used to estimate the flow of movement of a large and dense crowd in a given environment. Best used in studying large crowd, short time objectives.

;Entity-based Approach: Models that implement a set of physical, predefined, and global laws meant to simulate social/psychological factors that occur in individuals that are a part of a crowd fall under this category. Entities in this case do not have the capacity to, in a sense, think for themselves. All movements are determined by the global laws being enforced on them. Simulations that use this model often do so to research crowd dynamics such as jamming and flocking. Small to medium-sized crowds with short term objectives fit this approach best.

;Agent-based Approach: Characterized by autonomous, interacting individuals.<ref name="AP">{{cite journal |last1=Shao |first1=Wei |last2=Terzopoulos |first2=Demetri |title=Autonomous pedestrians |journal=Graphical Models |date=September 2007 |volume=69 |issue=5–6 |pages=246–274 |doi=10.1016/j.gmod.2007.09.001 }}</ref> Each agent of a crowd in this approach, is given a degree of intelligence; they can react to each situation on their own based on a set of decision rules. Information used to decide on an action is obtained locally from the agent's' surroundings. Most often, this approach is used for simulating realistic crowd behavior as the researcher is given complete freedom to implement any behaviors.

== Particle systems ==
One way to simulate virtual crowds is to use a [[particle system]]. Particle systems were first introduced in computer graphics by W. T. Reeves in 1983.<ref>{{cite journal |last1=Cohen |first1=Eyal |title=From crowd simulation to airbag deployment: particle systems, a new paradigm of simulation |journal=Journal of Electronic Imaging |date=1997 |volume=6 |issue=1 |page=94 |doi=10.1117/12.261175 |bibcode=1997JEI.....6...94B }}</ref> A particle system is a collection of a number of individual elements or ''particles''. Each particle is able to act autonomously and is assigned a set of physical attributes (such as color, size and velocity).

A particle system is dynamic, in that the movements of the particles change over time.  A particle system's movement is what makes it so desirable and easy to implement. Calculating the movements of these particles takes very little time. It simply involves physics: the sum of all the forces acting on a particle determines its motion. Forces such as gravity, friction and force from a collision, and social forces like the attractive force of a goal.

Usually each particle has a [[velocity vector]] and a [[position vector]], containing information about the particle's current velocity and position respectively. The particles next position is calculated by adding its velocity vector to its position vector. A very simple operation (again why particle systems are so desirable). Its velocity vector changes over time, in response to the forces acting on the particle. For example, a collision with another particle will cause it to change direction.

Particles systems have been widely used in films for effects such as explosions, for water effects in the 2000 movie ''[[The Perfect Storm (film)|The Perfect Storm]]'', and simulated gas in the 1994 film ''[[The Mask (1994 film)|the Mask]]''.

Particles systems, however, do have some drawbacks. It can be a bad idea to use a particle system to simulate agents in a crowd that the director will move on command, as determining which particles belong to the agent and which do not is very difficult.

=== Algorithm by Patil and Van Den Berg ===
This algorithm was designed for relatively simplistic crowds, where each agent in the crowd only desires to get to its own goal destination while also avoiding obstacles.<ref>{{cite journal |doi=10.1109/TVCG.2010.33 |pmid=21149879 |title=Directing Crowd Simulations Using Navigation Fields |journal=IEEE Transactions on Visualization and Computer Graphics |volume=17 |issue=2 |pages=244–54 |year=2011 |last1=Patil |first1=Sachin |last2=Van Den Berg |first2=Jur |author-link2= Jur P. van den Berg|last3=Curtis |first3=Sean |last4=Lin |first4=Ming C |last5=Manocha |first5=Dinesh }}</ref> This algorithm could be used for simulating a crowd in Times Square.

Patils algorithm's most important and distinctive feature is that it utilizes the concept of ''navigation fields'' for directing agents. This is different from a guidance field; a guidance field is an area around the agent in which the agent is capable of "seeing"/detecting information. Guidance fields are typically used for avoiding obstacles, dynamic obstacles (obstacles that move) in particular. Every agent possesses its own guidance field. A navigation field, on the other hand, is a vector field which calculates the minimum cost path for every agent so that every agent arrives at its own goal position.

The navigation field can only be used properly when a path exists from every free (non-obstacle) position in the environment to one of the goal positions. The navigation field is computed using coordinates of the static objects in the environment, goal positions for each agent, and the guidance field for each agent. In order to guarantee that every agent reaches its own goal the navigation field must be free of local minima, except for the presence of sinks at the specified goals.

the algorithm is only dependent on the grid resolution and not dependent on the number of agents in the environment. However, this algorithm has a high memory cost.

=== Individual behavior modelling ===
One set of techniques for AI-based crowd simulation is to model crowd behavior by advanced simulation of individual agent motivations and decision-making. Generally, this means each agent is assigned some set of variables that measure various traits or statuses such as stress, personality, or different goals. This results in more realistic crowd behavior though may be more computationally intensive than simpler techniques.

==== Personality-based models ====
One method of creating individualistic behavior for crowd agents is through the use of personality traits.<ref>{{cite book |doi=10.1145/2019406.2019413 |chapter=Simulating heterogeneous crowd behaviors using personality trait theory |title=Proceedings of the 2011 ACM SIGGRAPH/Eurographics Symposium on Computer Animation – SCA '11 |pages=43–52 |year=2011 |last1=Guy |first1=Stephen J. |last2=Kim |first2=Sujeong |last3=Lin |first3=Ming C. |last4=Manocha |first4=Dinesh |isbn=978-1-4503-0923-3 }}</ref> Each agent may have certain aspects of their personality tuned based on a formula that associates aspects such as aggressiveness or impulsiveness with variables that govern the agents' behavior. One way this association can be found is through a subjective study in which agents are randomly assigned values for these variables and participants are asked to describe each agent in terms of these personality traits. A regression may then be done to determine a correlation between these traits and the agent variables. The personality traits can then be tuned and have an appropriate effect on agent behavior.

The [[Big Five personality traits|OCEAN personality model]] has been used to define a mapping between personality traits and crowd simulation parameters. Automating crowd parameter tuning with personality traits provides easy authoring of scenarios with heterogeneous crowds.<ref>{{cite journal|last1=Durupinar|first1=Funda|last2=Pelechano|first2=Nuria|last3=Allbeck|first3=Jan|last4=Gudukbay|first4=Ugur|last5=Badler|first5=Norman I.|title=How the Ocean Personality Model Affects the Perception of Crowds|journal=IEEE Computer Graphics and Applications|date=2011|volume=31|issue=3|pages=22–31|doi=10.1109/MCG.2009.105|pmid=24808089|hdl=11693/11800 |hdl-access=free}}</ref>

==== Stress-based model ====
The behavior of crowds in high-stress situations can be modeled using [[General adaptation syndrome|General Adaptation Syndrome]] theory.<ref>{{cite book |doi=10.1145/2159616.2159626 |chapter=Interactive simulation of dynamic crowd behaviors using general adaptation syndrome theory |title=Proceedings of the ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games – I3D '12 |pages=55–62 |year=2012 |last1=Kim |first1=Sujeong |last2=Guy |first2=Stephen J. |last3=Manocha |first3=Dinesh |last4=Lin |first4=Ming C. |isbn=978-1-4503-1194-6 }}</ref> Agent behavior is affected by various stressors from their environment categorized into four prototypes: time pressure, area pressure, positional stressors, and interpersonal stressors, each with associated mathematical models.

''Time pressure'' refers to stressors related to a time limit in reaching a particular goal. An example would be a street crossing with a timed walk signal or boarding a train before the doors are closed.

''Area pressure'' refers to stressors as a result of an environmental condition. Examples would be noise or heat in an area. The intensity of this stressor is constant over a particular area.

''Positional stressors'' refer to stressors associated with a local source of stress. The intensity of this stressor increases as an agent approaches the source of the stress. An example would be a fire or a dynamic object such as an assailant. 


Examples of notable crowd AI simulation can be seen in [[New Line Cinema]]'s ''[[The Lord of the Rings (film series)|The Lord of the Rings]]'' films, where AI armies of thousands of characters battle each other. This crowd simulation was done using [[Weta Digital]]'s [[Massive (software)|Massive software]].

=== Sociology ===
''Crowd simulation'' can also refer to simulations based on [[group dynamics]], [[crowd psychology]], and even social [[etiquette]].<ref name="Huang">{{cite journal |last1=Huang |first1=Wenjia |last2=Terzopoulos |first2=Demetri |title=Door and Doorway Etiquette for Virtual Humans |journal=IEEE Transactions on Visualization and Computer Graphics |date=March 2020 |volume=26 |issue=3 |pages=1502–1517 |doi=10.1109/TVCG.2018.2874050 |pmid=30295624 }}</ref> In this case, the focus is on the behavior of the crowd, not necessarily on the visual realism of the simulation. Crowds have been studied as a scientific interest since the end of the 19th century. A lot of research has focused on the collective social behavior of people at social gatherings, assemblies, protests, rebellions, concerts, sporting events and religious ceremonies. Gaining insight into natural human behavior under varying types of stressful situations will allow better models to be created which can be used to develop crowd controlling strategies, often in public safety planning.

''Emergency response teams'' such as policemen, the National Guard, military and even volunteers must undergo some type of crowd control training. Using researched principles of human behavior in crowds can give disaster training designers more elements to incorporate to create realistic simulated disasters. Crowd behavior can be observed during both panic and non-panic conditions. Military programs are looking more towards simulated training involving emergency responses due to their cost-effective technology, as well as how effective the learning can be transferred to the real world.{{Citation needed|date=October 2012}} Many events that may start out controlled can have a twisting event that turns them into catastrophic situations, where decisions need to be made on the spot. It is these situations in which crowd dynamical understanding could play a vital role in reducing the potential for chaos.

''Modeling'' techniques of crowds vary from holistic or network approaches to understanding individualistic or behavioral aspects of each agent. For example, the Social Force Model describes a need for individuals to find a balance between social interaction and physical interaction. An approach that incorporates both aspects, and is able to adapt depending on the situation, would better describe natural human behavior, always incorporating some measure of unpredictability. With the use of multi-agent models understanding these complex behaviors has become a much more comprehensible task. With the use of this type of software, systems can now be tested under extreme conditions, and simulate conditions over long periods of time in the matter of seconds.

In some situations, the behavior of swarms of non-human animals can be used as an experimental model of crowd behavior. The panic behavior of ants when exposed to a [[Insect repellent|repellent]] chemical in a confined space with limited exit routes has been found to have both similarities and differences to equivalent human behavior.<ref>{{cite journal |last1=Shiwakoti |first1=Nirajan |last2=Sarvi |first2=Majid |last3=Rose |first3=Geoff |last4=Burd |first4=Martin |title=Animal dynamics based approach for modeling pedestrian crowd egress under panic conditions |journal=Procedia - Social and Behavioral Sciences |date=2011 |volume=17 |pages=438–461 |doi=10.1016/j.sbspro.2011.04.526 }}</ref><ref>{{cite journal |last1=Wang |first1=Shujie |last2=Lv |first2=Wei |last3=Song |first3=Weiguo |title=Behavior of Ants Escaping from a Single-Exit Room |journal=PLOS ONE |date=30 June 2015 |volume=10 |issue=6 |article-number=e0131784 |doi=10.1371/journal.pone.0131784 |doi-access=free |pmid=26125191 |pmc=4488427 |bibcode=2015PLoSO..1031784W }}</ref>

=== Modeling individual behaviors ===

Hacohen, Shoval and Shvalb<ref>{{cite journal |last1=Hacohen |first1=Shlomi |last2=Shvalb |first2=Nir |last3=Shoval |first3=Shraga |title=Dynamic model for pedestrian crossing in congested traffic based on probabilistic navigation function |journal=Transportation Research Part C: Emerging Technologies |date=January 2018 |volume=86 |pages=78–96 |doi=10.1016/j.trc.2017.10.024 |bibcode=2018TRPC...86...78H }}</ref> formulated the drivers-pedestrians dynamics at congested conflict spots. In such scenarios, the drivers and/or pedestrians do not closely follow the traffic laws. The model is based on the Probabilistic [[Navigation function]] (PNF), which was originally developed for robotics motion planning. The algorithm constructs a trajectory according to the probability for collision at each point in the entire crossing area. The pedestrian then follow a trajectory that locally minimizes their perceived probability for collision.

Helbing proposed a model based on physics using a particle system and socio-psychological forces in order to describe human crowd behavior in panic situation, this is now called the Helbing Model. His work is based on how the average person would react in a certain situation. Although this is a good model, there are always different types of people present in the crowd and they each have their own individual characteristics as well as how they act in a group structure. For instance, one person may not react to a panic situation, while another may stop walking and interfere in the crowd dynamics as a whole. Furthermore, depending on the group structure, the individual action can change because the agent is part of a group, for example, returning to a dangerous place in order to rescue a member of that group. Helbing's model can be generalized incorporating individualism, as proposed by Braun, Musse, Oliveira and Bodmann.<ref name=":0" />

In order to tackle this problem, individuality should be assigned to each agent, allowing to deal with different types of behaviors. Another aspect to tackle this problem is the possibility to group people, forming these group causes people to change their behavior as a function of part of the group structure. Each agent (individual) can be defined according to the following parameters:

# Id – Agent identifier
# IdFamily – Identifier of the family. A family is a predefined group formed by agents who know each other
# DE – Dependence level of the agent which mimics the need for help. Values [0,1]
# AL – Altruism level representing the tendency to help other agents. Values [0,1]
# v<sub>i</sub> – Speed of the agent

To model the effect of the dependence parameter with ''individual agents.''

When evaluating the speed of the agent, it is clear that if the value of the dependence factor, DE, is equal to one, then the person would be fully disabled making him unable to move. If the dependence factor is equal to zero, then the person is able to run at his max speed.

[[Group formation]] is related to the Altruism force which is implemented as an interaction force between two or more agents who are part of the same family.

The places where this would be helpful would be in an evacuation scenario. Take for example, an evacuation of a building in the case of a fire. Taking into account the characteristics of individual agents and their group performances, determining the outcome of how the crowd would exit the building is critically important in creating the layout of the building.<ref name=":0">{{cite book |doi=10.1109/CASA.2003.1199317 |chapter=Modeling individual behaviors in crowd simulation |title=Proceedings 11th IEEE International Workshop on Program Comprehension |pages=143–8 |year=2003 |last1=Braun |first1=A. |last2=Musse |first2=S.R. |last3=De Oliveira |first3=L.P.L. |last4=Bodmann |first4=B.E.J. |isbn=978-0-7695-1934-0 }}</ref>

=== Leader behavior during evacuation simulations ===
As described earlier, the '''Helbing Model''' is used as the basics for crowd behavior. This same type of behavior model is used for evacuation simulations.

In general, the first thing that has to be assumed is that not everyone has knowledge about the environment or where there are and aren't hazards. From this assumption we can create three types of agents. The first type is a trained leader, this agent knows about the environment and is able to spread knowledge to other agents so they know how to exit from an environment. The next type of agent is an untrained leader, this agent does not know about the environment, however, as the agent explores the environment and gets information from other types of leaders, the agent is able to spread the knowledge about the environment. The last type of agent is a follower, this type of agent can only take information from other leaders and not be able to share the information with other agents.

The implementation of these types of agents is fairly straightforward. The leaders in the environment have a map of the environment saved as one of their attributes. An untrained leader and followers will start out with an empty map as their attribute. Untrained leaders and followers will start exploring an environment by themselves and create a map of walkable and unwalkable locations. Leaders and untrained leaders (once they have the knowledge), will share information with other agents depending on their proximity. They will share information about which points on the grid are blocked, the local sub-graphs and the dangers in the area.

There were two types of searching algorithms tried out for this implementation. There was the random search and the depth first search. A random search is where each of the agents go in any direction through the environment and try to find a pathway out. The depth first search is where agents follow one path as far as it can go then return and try another path if the path they traversed does not contain an exit. If was found that depth first search gave a speed up of 15 times versus a random search.<ref>{{cite journal |doi=10.1109/MCG.2006.133 |pmid=17120916 |title=Modeling Crowd and Trained Leader Behavior during Building Evacuation |journal=IEEE Computer Graphics and Applications |volume=26 |issue=6 |pages=80–6 |year=2006 |last1=Pelechano |first1=Nuria |last2=Badler |first2=Norman |hdl=2117/10047 |url=https://repository.upenn.edu/cis_papers/272 |hdl-access=free }}</ref>

=== Scalable simulations ===
There are many different case situations that come into play in crowd simulations.<ref>{{cite book |doi=10.1109/ICPP.2008.20 |chapter=A Scalable Architecture for Crowd Simulation: Implementing a Parallel Action Server |title=2008 37th International Conference on Parallel Processing |pages=430–7 |year=2008 |last1=Vigueras |first1=G. |last2=Lozano |first2=M. |last3=Pérez |first3=C. |last4=Orduña |first4=J.M. }}</ref> Recently, crowd simulation has been essential for the many virtual environment applications such as education, training, and entertainment.  Many situations are based on the environment of the simulation or the behavior of the group of local agents.  In virtual reality applications, every agent interacts with many other agents in the environment, calling for complex real-time interactions.  Agents must have continuous changes in the environment since agent behaviors allow complex interactions.  Scalable architecture can manage large crowds through the behavior and interactive rates.  These situations will indicate how the crowds will act in multiple complex scenarios while several different situations are being applied.  A situation can be any circumstance that has typical local behaviors.  We can categorize all situations into two different kinds.

''Spatial situation'' is a situation that has a region where the environment affects the local agents.  For instance, a crowd waiting in line for a ticket booth would be displaying a spatial situation. Other examples may be a bus stop or an ATM where characters act upon their environment.  Therefore, we would consider 'bus stop' as the situation if the behavior of the agents are to be getting on or off a bus.

''Non-Spatial situation'' has no region in the environment because this only involves the behavior of the crowd.  The relationship of the local agents is an important factor to consider when determining behavior.  An example would be a group of friends walking together.  Typical behavior of characters that are friends would all move along with each other. This means that 'friendship' would be the situation among the typical behavior of walking together.

The structure of any situation is built upon four components, Behavior functions, Sensors, States, and Event Rules.  Behavior functions represent what the characters behaviors are specific to the situation.  Sensors are the sensing capability for agents to see and respond to events.  States are the different motions and state transitions used only for the local behaviors.  Event rule is the way to connect different events to their specific behaviors.  While a character is being put into a situation, these four components are considered at the same time.  For spatial situations,  the components are added when the individual initially enters the environment that influences the character.  For non-spatial situations, the character is affected only once the user assigns the situation to the character.  The four components are removed when the agent is taken away from its situations region or the situation itself is removed.  The dynamic adding and removing of the situations lets us achieve scalable agents.

== Human-like behaviors and crowd AI ==
[[File:Crowd simulation, Covent Garden.jpg|thumb|A crowd simulation of [[Covent Garden square]], London, showing a crowd of pedestrian agents reacting to a street performer]]
{{Main|Swarm intelligence}}
To simulate more aspects of human activities in a crowd, more is needed than path and motion planning. Complex social interactions, smart object manipulation, and hybrid models are challenges in this area. Simulated crowd behavior is inspired by the flow of real-world crowds. Behavioral patterns, movement speeds and densities, and anomalies are [[crowd analysis|analyzed]] across many environments and building types. Individuals are [[crowd tracking|tracked]] and their movements are documented such that algorithms can be derived and implemented into crowd simulations.

Individual entities in a crowd are also called [[Software agent|agents]]. In order for a crowd to behave realistically each agent should act autonomously (be capable of acting independently of the other agents). This idea is referred to as an ''agent-based model.'' Moreover, it is usually desired that the agents act with some degree of intelligence (i.e. the agents should not perform actions that would cause them to harm themselves). For agents to make intelligent and realistic decisions, they should act in accordance with their surrounding environment, react to its changes, and react to the other agents. [[Demetri Terzopoulos|Terzopoulos]] and his students have pioneered agent-based models of pedestrians, an approach referred to as multi-human simulation to distinguish it from conventional crowd simulation.<ref name=AP/><ref name="Yu">{{cite conference |doi=10.2312/SCA/SCA07/119-128 |date=2007 |last1=Yu |first1=Qinxin |last2=Terzopoulos |first2=Demetri |title=A Decision Network Framework for the Behavioral Animation of Virtual Humans |conference=Eurographics/Siggraph Symposium on Computer Animation |isbn=978-3-905673-44-9 }}</ref><ref name=Huang/>

=== Rule-based AI ===
[[File:MaslowsHierarchyOfNeeds.svg|alt=Maslow's Hierarchy of Needs|thumb|Maslow's Hierarchy of Needs]]
In rule-based AI, virtual agents follow scripts: "if this happens, do that". This is a good approach to take if agents with different roles are required, such as a main character and several background characters. This type of AI is usually implemented with a hierarchy, such as in [[Maslow's hierarchy of needs]], where the lower the need lies in the hierarchy, the stronger it is.{{fact|date=February 2025}}

For example, consider a student walking to class who encounters an explosion and runs away. The theory behind this is initially the first four levels of his needs are met, and the student is acting according to his need for self-actualization. When the explosion happens his safety is threatened which is a much stronger need, causing him to act according to that need.{{fact|date=February 2025}}

This approach is scalable, and can be applied to crowds with a large number of agents. Rule-based AI, however, does have some drawbacks. Most notably the behavior of the agents can become very predictable, which may cause a crowd to behave unrealistically.{{fact|date=February 2025}}

=== Learning AI ===
In learning AI, virtual characters behave in ways that have been tested to help them achieve their goals.  Agents experiment with their environment or a sample environment which is similar to their real one.{{fact|date=February 2025}}

Agents perform a variety of actions and learn from their mistakes. Each agent alters its behavior in response to rewards and punishments it receives from the environment. Over time, each agent would develop behaviors that are consistently more likely to earn high rewards.{{fact|date=February 2025}}

If this approach is used, along with a large number of possible behaviors and a complex environment agents will act in a realistic and unpredictable fashion.{{fact|date=February 2025}}

==== Algorithms ====
There are a wide variety of machine learning algorithms that can be applied to crowd simulations.{{fact|date=February 2025}}

Q-Learning is an algorithm residing under machine learning's sub field known as reinforcement learning. A basic overview of the algorithm is that each action is assigned a Q value and each agent is given the directive to always perform the action with the highest Q value. In this case learning applies to the way in which Q values are assigned, which is entirely reward based. When an agent comes in contact with a state, s, and action, a, the algorithm then estimates the total reward value that an agent would receive for performing that state action pair. After calculating this data, it is then stored in the agent's knowledge and the agent proceeds to act from there.{{fact|date=February 2025}}

The agent will constantly alter its behavior depending on the best Q value available to it. And as it explores more and more of the environment, it will eventually learn the most optimal state action pairs to perform in almost every situation.

The following function outlines the bulk of the algorithm:

<math>Q(s,a) \leftarrow r + \max_{a'} Q(s',a')</math>

Given a state <math>s</math> and action <math>a</math>, <math>r</math> and <math>s'</math> are the reward and state after performing a given action. Based on this algorithm, <math>a'</math> ranges over all actions taken.<ref>{{cite journal |last1=Torrey |first1=Lisa |title=Crowd Simulation Via Multi-Agent Reinforcement Learning |journal=Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment |date=10 October 2010 |volume=6 |issue=1 |pages=89–94 |doi=10.1609/aiide.v6i1.12390 }}</ref>

== Crowd rendering and animation ==
Rendering and animating a large number of agents realistically, especially in real time, is challenging. To reduce the complexity of 3D rendering of large-scale crowds, techniques like culling (discarding unimportant objects), impostors (image-based rendering) and decreasing levels of detail have been used.<ref>{{cite journal |doi=10.1109/76.825720 |title=Real-time display of virtual humans: Levels of details and impostors |journal=IEEE Transactions on Circuits and Systems for Video Technology |volume=10 |issue=2 |pages=207–17 |year=2000 |last1=Aubel |first1=A. |last2=Boulic |first2=R. |last3=Thalmann |first3=D. }}</ref>
Variations in appearance, body shape and size, accessories and behavior (social or cultural) exist in real crowds, and lack of variety affects the realism of visual simulations. Existing systems can create virtual crowds with varying texture,<ref name="Maim et al 2009"/> color,<ref>{{cite book |last1=Gosselin |first1=David R. |last2=Sander |first2=Pedro V. |last3=Mitchell |first3=Jason L. |chapter=Drawing a Crowd |editor1-first=Wolfgang |editor1-last=Engel |title=ShaderX3: Advanced Rendering Techniques in DirectX and OpenGL |url=https://archive.org/details/shaderxadvancedr00enge_759 |url-access=limited |publisher=Charles River Media |location=Cambridge, MA |year=2004 |pages=[https://archive.org/details/shaderxadvancedr00enge_759/page/n498 505]–17 |isbn=978-1-58450-357-6 }}</ref> size, shape and animation.<ref name="Thalmann et al 2009"/>

== Real world applications ==

=== Virtual cinematography ===
Crowd simulations have been used widely across films as a cost-effective and realistic alternative from hiring actors and capturing shots that would otherwise be unrealistic. A significant example of its use lies in [[The Lord of the Rings (film series)]]. One of the most glaring problems for the production team in the initial stages were large-scale battles, as the author of the novels, J. R. R. Tolkien,  envisioned them to have at least 50,000 participants. Such a number was unrealistic had they decided to only attempt to hire real actors and actresses. Instead they decided to use CG to simulate these scenes through the use of the Multiple Agent Simulation System in a Virtual Environment, otherwise known as MASSIVE. The Human Logic Engine based [[Autodesk Maya|Maya]] plugin for crowd simulation, [[Miarmy]], was used for the development of these sequences. The software allowed the filmmakers to provide each character model an agent based A.I. that could utilize a library of 350 animations. Based on sight, hearing, and touch parameters generated from the simulation, agents would react uniquely to each situation. Thus each simulation of the scene was unpredictable. The final product clearly displayed the advantages to using crowd simulation software.<ref>http://people.ucalgary.ca/~far/Lectures/SENG697/PDF/tutorials/2002/Multiple_Agent_Simulation_System_in_a_Virtual_Environment.pdf Davis Guy. Multiple Agent Simulation System in a Virtual Environment.{{self-published inline|date=February 2025}}</ref>

=== Urban planning ===
The development of crowd simulation software has become a modern and useful tool in designing urban environments. Whereas the traditional method of urban planning relies on maps and abstract sketches, a digital simulation is more capable of conveying both form and intent of design from architect to pedestrian. For example, street signs and traffic lights are localized visual cues that influence pedestrians to move and behave accordingly. Following this logic, a person is able to move from point A to point B in a way that is efficient and that a collective group of people can operate more effectively as a result. In a broader sense, bus systems and roadside restaurants serve a spatial purpose in their locations through an understanding of human movement patterns.<ref>{{cite conference |last1=Aschwanden |first1=Gideon |last2=Halatsch |first2=Jan |last3=Schmitt |first3=Gerhard |title=Crowd Simulation for Urban Planning |conference=26th Conference on Education and Research in Computer Aided Design in Europe (eCAADe 2008) |date=September 2008 |pages=493–500 |url=http://papers.cumincad.org/data/works/att/ecaade2008_160.content.pdf }}</ref> The [[SimCity]] video game series exemplifies this concept in a more simplistic manner. In this series, the player assigns city development in designated zones while maintaining a healthy budget. The progression from empty land to a bustling city is fully controlled by the player's choices and the digital citizens behave as according to the city's design and events.

=== Evacuation and riot handling ===
Simulated realistic crowds can be used in training for riots handling, architecture, safety science (evacuation planning).{{fact|date=February 2025}}

=== Military ===
Being that crowd simulations are so prevalent in use for public planning and general order with regards to chaotic situations, many applications can be drawn for governmental and military simulations. Crowd modeling is essential in police and military simulation in order to train officers and soldiers to deal with mass gatherings of people. Not only do offensive combatants prove to be difficult for these individuals to handle, but noncombatant crowds play significant roles in making these aggressive situations more out of control. Game technology is used in order to simulate these situations for soldiers and technicians to practice their skills.<ref>{{cite journal |doi=10.1177/1046878107308092 |title=Integrating crowd-behavior modeling into military simulation using game technology |journal=Simulation & Gaming |volume=39 |pages=10–38 |year=2007 |last1=McKenzie |first1=F. D. |last2=Petty |first2=M. D. |last3=Kruszewski |first3=P. A. |last4=Gaskins |first4=R. C. |last5=Nguyen |first5=Q.-A. H. |last6=Seevinck |first6=J. |last7=Weisel |first7=E. W. }}</ref>

=== Sociology ===
The behavior of a modeled crowd plays a prominent role in analytical matters. These dynamics rely on the physical behaviors of individual agents within a crowd rather than the visual reality of the model itself. The social behaviors of people within these constructs have been of interest for many years, and the sociological concepts which underpin these interactions are constantly studied. The simulation of crowds in different situations allows for sociological study of real life gatherings in a variety of arrangements and locations. The variations in human behavior in situations varying in stress-levels allows for the further development and creation of crowd control strategies which can be more specifically applied to situations rather than generalized.{{fact|date=February 2025}}

== See also ==

* [[3D computer graphics]]
* [[Artificial intelligence]]
* [[Crowd analysis]]
* [[Emergent behavior]]
* [[Multi-agent system]]
* [[Particle system]]

== References ==
{{Reflist|30em}}

== External links ==
<!-- wikipedia is not a directory of external links for companies or products -->
* [https://web.archive.org/web/20130627102118/http://steersuite.cse.yorku.ca/ SteerSuite], An open-source framework for developing and evaluating crowd simulation algorithms
* {{cite journal |doi=10.1111/j.1467-8659.2004.00783.x |title=Scalable behaviors for crowd simulation |journal=Computer Graphics Forum |volume=23 |issue=3 |pages=519–28 |year=2004 |last1=Sung |first1=Mankyu |last2=Gleicher |first2=Michael |last3=Chenney |first3=Stephen }}

{{Animation}}
{{collective animal behaviour}}

[[Category:Crowds]]
[[Category:Computer animation]]
[[Category:3D computer graphics]]
[[Category:Social physics]]