Crowd simulation

The Utrecht University Crowd Simulation (UUCS) Framework creates high-quality navigation meshes and uses them for path planning and crowd simulation. On this page we describe the features and technical properties of our framework.

For some examples, please refer to our case studies. We do not license the plugin, but we are open for collaboration in research projects. Please contact Roland Geraerts for more information or visit the website of our academic spin-off uCrowds.

Many people have contributed to this software, including my PhD students, Arne Hillebrand, Wouter van Toll, Norman Jaklin, and many other people, including Angelos Kremyzas, Ioannis Karamouzas, Arthur van Goethem, Mihai Polak, Jordi Vermeulen, Martijn Koenis, Marijn van der Zwan, Mark tibboel and Andrei Cibotaru.

References

The framework is described on our research page and is based on the following paper:

• Wouter G. van Toll, Norman S. Jaklin and, Roland Geraerts. Towards Believable Crowds: A Generic Multi-Level Framework for Agent Navigation. In ICT.OPEN 2015 (ICT.OPEN 2015).
  

  

  

The framework heavily relies on the multi-layered Explicit Corridor Map data structure. You may read about this structure and its performance in the following paper:

• Wouter G. van Toll, Atlas F. Cook IV, Marc J. van Kreveld and Roland Geraerts. The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh. ACM Transactions on Spatial Algorithms and Systems. Vol. 4, No 1. pages 2:1-2:34. May 2018.

  

  

Features of our framework

The framework generates a compact but complete representation of the navigable areas in an environment. This representation is a navigation mesh suitable for representing the walkable areas in a 2D environment (such as a city with a footprint that represents buildings) or a 3D multi-layered 3D environment, such as a train/metro station, or a soccer stadium.

A simple multi-layered environment with a continuous, exact navigation mesh. An agent can move under a ramp as well as over it.

This representation can be updated in real-time and dynamically when obstacles are inserted, deleted, or moved.

Crowds can be simulated in real-time given the above representation. This includes:

• Planning global paths for agents, based on their personal goals, properties (such as their size and preferred minimum distance to obstacles), and terrain preferences (such as road, grass, dangerous area).
• Letting the agents smoothly follow an indicative route through the environment.
• Letting the agents avoid collisions with other agents while following their route.
• Letting the crowd react on dynamic changes and visibility in the environment.
• Coordination of the motions when it is getting more crowded.
• Planning paths and local motions for individuals as well as social groups.

Our system is rather fast, allowing for many case-studies to be performed in a reasonable amount of time. Our framework

• simulates in real-time 200.000 agents on an 8-core Dell XPS laptop, 314.159 agents on a 12-core 3900x PC and 600.000 agents on a 64-core ThreadRipper PC.
• handles more than 1 million agents on 1 PC (not in real-time).
• handles environments measuring many squared kilometers at millimeter precision.

These features are demonstrated on our YouTube channel on crowd simulation. You can find, for instance, a movie that demonstrates how we handle coordination between agents:

Technical properties

The Explicit Corridor Map (ECM) navigation mesh has a number of useful properties, including the following:

• Automatic construction. Given a set of obstacles and a bounding box, our framework uses the exact algorithms to compute the ECM navigation mesh efficiently and automatically.
• Multi-layered environments. The ECM is also defined for environments that consist of multiple 2D layers connected by line segments. (For example, imagine a building with multiple floors and staircases.) For such a multi-layered environment, our framework builds a continuous graph with the same properties as the 2D version. Hence we can perform path planning and crowd simulation in so-called 2.5D environments. See Figure (c) below.
• Compactness. The ECM is based on the medial axis, which is a sparse graph of O(n) complexity, where n is the number of obstacle vertices in the environment. The graph only splits up wherever multiple homotopic routes appear. Informally, this means that an agent can only choose between 'left' and 'right' if there is an obstacle in-between. Because of this low complexity, the ECM has a small memory footprint, and path planning is more efficient on the ECM than on a grid.
• Closest-point queries. For a query point q in the free space, we can easily find the closest obstacle coordinate obs_q, by first finding the cell C_q in which q is located. This enables fast collision detection in a simulation. See Figure (a) below.
• Retractions. Each free point q has a unique mapping onto the medial axis (i.e. the ECM's edges). We define the retraction as the first point where the half-line from obs_q to q intersects the medial axis. This retraction lies inside the cell C_q. See Figure (a) below.
• Clearance information. Because the medial axis runs through the middle of the walkable space, it stays as far away from the obstacles as possible. Hence, the closest-obstacle information of an event point defines the clearance (or 'free width') of that point. For any point on the ECM's edges, we know how much free width is available. This is useful for path planning: a disk-shaped agent of radius r cannot walk along an edge if this edge has a minimum clearance below r. Consequently, the ECM supports path planning for agents of any radius, without the need to 'inflate' obstacles (which is done in most other navigation meshes).
• Visibility computations. Visibility lines and polygons can be computed efficiently in 2D and multi-layered 3D environments.
• Dynamic updates. We have introduced algorithms that can locally update the ECM after the insertion or deletion of an obstacle. Individuals (or the crowd) can react on these changes, e.g. when they see or know them, based on their strategy.
• Heterogeneous terrains. An environment can now be annotated with region or terrain information, such as roads and bicycle lanes, dangerous and pleasant areas.

Feature: Different re-planning strategies when an obstacle appears of disappears dynamically.

Feature: Example of a visibility polygon for point p in a multi-layered environment.

Features: Retraction Retr(p), nearest obstacle point np(p), corridor and indicative routes.

Our simulation includes the following:

• Crowd simulation. Our model consists of 5 different levels. High-level planning uses AI techniques to translate a semantic action (e.g. go home) to one or more geometric queries (find a path from position s to position g). Global planning computes an indicative route, i.e. a path from s to g that should be roughly followed. The three lower levels update the agent in every step of the simulation loop. Path following lets the agent choose a preferred velocity such that it follows the indicative route. Note that a velocity is a 2D vector that encodes both speed and direction. Local movement computes a velocity that deals with local hazards, e.g. to prevent collisions with other agents, while remaining close to the preferred velocity. The simulation then applies this velocity through time integration. Finally, animation handles the visual movement of the agent, down to its 3D skeleton representation. We implemented different strategies for each level.
• Coordination. Our model combines the advantages of agent-based and flow-based paradigms while only relying on local information. Our model can handle arbitrary and dynamically changing crowd densities, and it enables agents to gradually interpolate between individual and coordinated behavior. The model reduces the occurrence of deadlocks and yields visually convincing crowd behavior for high-density scenarios while maintaining individual agent behavior at lower densities.
• Corridors / Indicative routes. If an agent plans a path along the medial axis, the result is not only a path, but also a description of the free space around it. Such a corridor is defined as the sequence of the corresponding ECM cells, with extra disk segments around each vertex. Within a corridor, the character can plan a more sophisticated indicative route, e.g. one that stays on the left or right side of the corridor, or the shortest path through the corridor with a preferred amount of clearance. See Figure (b) above. An indicative route can also be computed while taking an agent profile and region/terrain preferences into account.
• Heterogeneous terrains. While planning an indicative route and while traversing the route, we take an agent's region preferences into account.
• Dynamic updates. After a dynamic update of an obstacle (e.g. when it is inserted, deleted, or moved), individuals (or the crowd) can react on these changes, e.g. when they see or know them, based on their strategy.
• Social group behaviors. Our Social Groups and Navigation (SGN) method simulates the walking behavior of small pedestrian groups in virtual environments. SGN is the first method to simulate group behavior on both global and local levels. We define quantitative metrics to measure the coherence and the sociality of a group based on existing empirical data of real crowds. SGN is designed to let groups stay in coherent and social formations without explicitly modeling such formations.
• Agent profiles. An agent profile is a collection of parameters that define the agent's properties and standard behavours. This facilitates easily spawning (i.e. creating) groups of agents with similar properties. Each spawn agent can then be created with a certain variation on these properties based on a specific distribution. An example of such a property is the walking speed that is normally distributed.

Features: Route planning and route following in weighted regions.

Screenshots of multi-layered navigation meshes

Below, we displayed several multi-layered 3D environments for which a single and exact navigation mesh was generated. For clarity, we only show the full navigation mesh in the first example.

A multi-layered train station. The navigation mesh was generated in 0.07s.

A multi-layered library, generated in 0.009s. Each layer has its own color.

A multi-layered tower, generated in 0.1s.

A city (500x500m) with 8 multi-layered buildings, generated in 0.9s.