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).
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.
Many people have contributed to this software, including my PhD students,
Wouter van Toll,
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.
The framework is described on our research page and is based on the following paper:
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
Letting the agents avoid collisions with other agents while following their
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.
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.
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)
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.
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.