Homepage > Crowd simulation > Software

We study how we can automatically create a data structure that represents the walkable surfaces in virtual environments, and how it can be updated dynamically and efficiently when it changes. We refer to this structure as a navigation mesh. This mesh enables efficient crowd simulation, which is our next topic of research. We study and develop a crowd simulation framework and its components, which ranges from global (AI) planning to local animation. We create models for realistic crowd behaviors, which includes studying how (groups of) people move and avoid collisions in such environments, based on agent profiles and semantics (such as terrain annotations).

Software

Crowd simulation

The UU Crowd Simulation 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. For questions or licensing information, please contact Roland Geraerts.

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.

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.

Ramps: a simple multi-layered environment with a continuous, exact  navigation mesh.

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 15.000 agents on a 1.5Keuro PC, and 65.000 on a 6Keuro 24-core 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:

Software

We have created a software package that consists of the (multi-layered) ECM navigation mesh generator and crowd simulator. The software is written in C++ and currently runs under Windows and Linux, in 32 as well as 64 bit. We created a library/API that can be accessed through C-calls. We created wrappers for C++ as well as C#. In addition, some demo projects are provided for both languages. This software has been integrated in e.g.

  • Unity3D. Our Unity3d plugin demonstrates the feasibility of integrating the software into games or serious applications. A demo of the plugin is given in the above movie. The movie and plugin were created by students following our Software project course, i.e. Dionysi Alexandridis, Ruben ten Cate, Roxanne van Dam, Lars Deelen, Simon Dirks, Philippe Kok, Dylan Kruyff, Frank Noorloos, Jordy van Opstal, Zhemin ter Kuile, Erik Wiersma and Tim Zoet. This version was based on its predecessor created by Angelos Kremyzas and Wouter van Toll.
  • Reach. It was used by Movares and us to perform simulations for the preparations of the Grand Départ of the Tour de France in Utrecht. It was also used for evacuation studies in three metro stations in the Noord/Zuid-lijn in Amsterdam (where people can transport/carry along bicycles).

Our UU crowd simulation software has been integrated into Unity3D.

Our ECM crowd simulation software has been integrated into Unity3D.

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 obsq, by first finding the cell Cq 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 obsq to q intersects the medial axis. This retraction lies inside the cell Cq. 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.

Our ECM crowd simulation software has been integrated into Unity3D.

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

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.

Feature: Retractions, nearest obstacle points, corridor and indicative route.

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.

Features: Route planning and route following in weighted regions.

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 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 library, generated in 0.009s (9ms).

A multi-layered tower, generated in 0.1s.

A multi-layered tower, generated in 0.1s (110ms).

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

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