The second dimension of the crowd simulation problem is the control granu-larity, that is, how to control the movements of our different characters. The control granularity axis can go from computing only a reactive and local
mo-2.3. CONTROL GRANULARITY
2.3.1 . Reactive and Local Motion
We callsteeringthe behavior of an agent when simulating motion at local level.
Basically that is to compute the velocity vector, with speed and direction of movement, that has the agent, and to modify it accordingly by reacting to the surrounding events such as possible collisions or pushes. The orientation of the agent is also important if we want to distinguish the direction of movement and the direction that the agent is facing. Adding orientation to the simulation might also imply simulate rotation, turns, pivoting actions and torques. The interactions that might happen at this level are purely reactive and may go from collision avoidance forces to pushes, forming queues, waiting, and even physical reactions.
An important distinction we should mention at this level is about how do we represent the surface or space where agents are moving: as a discrete local space or as a continuous space. Adiscretizationof the local space, such as having a grid, reduces somehow the dimensionality of the problem as we can work on fixed units. We can easily know, for example, if a same unit of space is already occupied and collisions can be avoided. The problem of using a discrete space is that, depending on its granularity we do not allow agents to really get in contact. A continuous space might have a higher computational cost to be used, but it is more suitable to obtain effects such as pushes between agents as its movements are not limited (see Figure2.5).
2.3.2 . Planning and Global Motion
The terms planning and global motion apply to a series of simulation algo-rithms that take place on a bigger scale than reactive and local motion. First of all as the termplanningitself states, they plan a series of actions to be per-formed over time. These actions may come determined by the current state, a desired goal state, and the environment as well as other possible events. There-fore they usually take into consideration an abstract model of the environment such as a grid composed of cells or navigation meshes.
Space Space
Figure 2.5: Continuous Vs. Discretized Local Space. With continuous space real contact and interactions like pushing behaviors can be possible
2.3.2 . Navigation Meshes
The agents of crowd simulations move around in a virtual environment, which is usually modeled in 3D. From the 3D mesh of the scene we can manually or automatically extract features such as rooms, doors, or moreover a navigation graphcontaining cells and portals, indicating the space where agents can walk over. Thenavigation meshis this graph, and it is necessary to have it in order to efficiently compute plans to navigate from one place of the environment to another. The applied algorithms to plan are usually pathfinding algorithms, such as the well known A*. For example, our navigation mesh is composed of polygons, and an agent might need to go from its current position to another one. The planner will detect the polygons where those points lie into, and then use a pathfinding algorithm to output a sequence of polygons, or waypoints, conforming the plan or path of the agent (see Figure2.6).
2.3.2 . Planner
A formal description of aplannerrequires that it works over agraphcomposed of states and transitions. The states can be the nodes of a navigation mesh
2.3. CONTROL GRANULARITY
Figure 2.6:An example of a navigation mesh and a plan computed over it.
the planner these might go from moving to an adjacent cell to execute some action or playback an animation clip. But the algorithms are always essentially pathfindingalgorithms trying to reach one state from another one by executing actions.
These algorithms usually work by and exploring the search space while expand-ing nodes, applyexpand-ing different transitions. Explored nodes are evaluated with a cost function, determining how much effort it takes to get to that specific state.
Anheuristicfunction is then needed to estimate the necessary cost to get to the final goal state. Heuristics can be as simple as an euclidian distance function, to any complex and high costly function.
2.3.2 . Prediction
When planning at a local level, only with a reactive behavior, an agent can pre-dict the future position of an agent just by using its current velocity, and maybe other forces interacting with it. But it can not foresee abrupt changes in the di-rection, neither it can predict decelerations or accelerations. When planning at a global level we can compute the plans of all agents. Since a planner can have access to the other agent, it makes sense that it can access to their plans too.
Therefore we can foresee and predict possible collisions between agents. Such a planner should be able to modify plans in order to avoid predicted collisions (see Figure2.7). Interactions between agents can then emerge at a collaborative level, like wait for someone to come across, help another agent to perform an action, etc.
Prediction with a reactive local movement
Prediction with access to the global plan of other
agents
Figure 2.7: A collision prediction only by estimating the future position of an agent using its velocity vector, like in a purely reactive behavior (left). With global planning, agents can access to the real plan of other agents and make a
more accurate collision prediction to modify their own plan (right).
2.3.3 . Behavior
Behaviorrefers to the decisions and the set of actions or reactions that agents can do or have in different situations. Simulating the behavior of a character is a higher level AI than just planning for a specific goal or reacting to some-thing. It implies a mind state, a more complex goal and even strategies. Interac-tions between agents at this stage can be also more complex, with collaborative strategies for a common goal.
2.3.4 . Complete Control
A crowd simulation system can work with agents having just a local reactive motion, but they will lack the efficiency to find shortest paths to get a specific goal, and the exhibition of a a specific behavior. Depending on how the global planning is designed, including predictions and collision avoidance, a local mo-tion might not be necessary. Although if we just plan waypoints to go through different cells, a local steering behavior is sufficient to navigate within those cells. A behavior simulation is needed when we want to give agents specific