Homepage > Crowd simulation > Research overview

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).

Research overview

A multi-layered navigation mesh.

References

Motivation, or: why would we need to simulate a crowd?

The results can be used

  • to decide whether crowd pressures do not build up too much during a festival such as the Love Parade;
  • to find out how to improve crowd flow in a train station;
  • to plan escape routes for use during a fire evacuation;
  • to train emergency personnel to deal with evacuation scenarios;
  • to study a range of scenarios during an event; or
  • to populate a game environment with realistic agents; or;
  • to train soldiers operating in huge digital twin city.

From a virtual environment to a navigation mesh

We cannot directly start a simulation by using the raw 3D geometry that describes the 3D environment. It first needs to be processed so that the simulation knows where agents can move or not. How does that work?

Polygonal environment

Polygonal environment

Walkable environment

Walkable environment

Multi-layered environment

Multi-layered environment

Multi-layered navigation mesh

Multi-layered navigation mesh

We are given a 3D polygonal environment which consists of collection of polygons. We assume that there is a static gravitation vector (which implies for instance that we do not support sphere-like virtual worlds). We convert this environment into a walkable environment by removing polygons that are too steep, too close to a ceiling (e.g. an agent would otherwise bump his head) or polygons that are part of an area that is too small to move on. In the next step, we decompose this environment into a set of 2D layers (and connections between the layers) such that there is no internal overlap within each layer when its polygons would be projected onto the ground floor. Heuristics are applied to separate the layers. The resulting multi-layered environment is then in the right format for many algorithms that normally only work in 2D (such as algorithms that compute a shortest path which optionally has some minimum amount of clearance to obstacles, a visibility region, or a navigation mesh). For each layer, we compute a 2D navigation mesh, based on the generalized Voronoi diagram or medial axis. More specifically, the navigation mesh is a Corridor Map that decomposes the walkable environment into a set of non-overlapping simple cells that fully cover the walkable space. The meshes are stitched together at the connections such that a continuous multi-layered navigation mesh appears. We compared this navigation mesh with others in a comparative study.

When an polygonal obstacle is added, deleted, or moved, the navigation mesh can be locally updated to reflect the changes. This mesh can then be used in our simulation framework.

UU Crowd simulation framework

Our simulation framework consists of five levels of planning, which allows for efficient and flexible crowd simulations.

A five-level hierarchy for path planning and crowd simulation systems. The geometric levels, which can be solved using our algorithms and software, require an efficient navigation mesh of the environment.

A five-level hierarchy for path planning and crowd simulation systems.

At the top of the hierarchy, event management and action planning (5) generate a set of geometric path planning queries, consisting of start/goal pairs. In this phase, we support for instance social groups, large groups, re-planning of agents when the navigation mesh changes or when crowd densities change.

Next, the global route planning level (4) uses a query to produce a static indicative route for an agent or group, which indicates how they should globally walk. There are many choices in how to create indicative routes. For instance, they can be the shortest path, or the shortest path with some amount of minimum distance to the obstacles, or they can be optimized for camera movement or stealth movement.

The three lower levels move the crowd in every step of the simulation. On the route following level (3), the global routes are being traversed using our Indicative Route Method, yielding preferred velocities (i.e. speed/direction pairs). These paths can also be generated in annotated environments by using its successor, MIRAN, which supports environments whose walkable polygons have received a weight.

The preferred velocities are adapted in the local movement level (2) where a pedestrian might temporarily deviate from its global route to coordinate its movements and to handle potential collisions with the crowd, yielding a velocity that is used by the animation system in level (1) to move an agent.

Extensions

In our crowd prediction project, we extend our UU crowd simulation software to calibrate a crowd simulation in real-time (using video camera's) while an event is going on. In addition, we program a prediction model that can predict what the (near) future state of a crowd will be.

This project is the result of a software project carried out by our bachelor computer science students: Patrick van Eijk, Rens de Heer, Raphael Claasen, Sophie Huiberts, Martin Korevaar, Jurriaan Pijpers, Adolfo Ochahavia, Tim de Bie, Patrick Habekotte and Guido Oskam. Special thanks goes to Atlas Cook (voice), and my PhD students Arne Hillebrand and Wouter van Toll for their endless support.

Publication overview

Crowd simulation basis

Digital twins and Synthetic single environments

Machine learning

Pedestrian dynamics

Navigation meshes

Augmented reality and virtual reality

Path planning

Animation