Homepage > Crowd simulation > List of publications > Paper

We study how we can automatically create a data structure that represents the walkable surfaces in such an environment, 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).

A Navigation Mesh for Dynamic Environments

A multi-layered navigation mesh in which a yellow/black obstacle was added dynamically.


Games and simulations frequently model scenarios where obstacles move, appear, and disappear in an environment. A city environment changes as new buildings and roads are constructed, and routes can become partially blocked by small obstacles many times in a typical day. This paper studies the effect of using local updates to repair only the affected regions of a navigation mesh in response to a change in the environment. The techniques are inspired by incremental methods for Voronoi diagrams. Experiments show that local updates are fast enough to permit real-time updates of the navigation mesh. The main novelty of this paper is that we show how to maintain a 2D or 2.5D navigation mesh in an environment that contains dynamic polygonal obstacles.


  • Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. A Navigation Mesh for Dynamic Environments. Computer Animation and Virtual Worlds (CAVW), 23(6):535-546, 2012.

    Full text Full text YouTube
  • Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Game-Changing: Fast Dynamic Updates in a Flexible Navigation Mesh. ICT.OPEN 2013 (ICT.OPEN 2013).

    pdf poster pptx


The method is demonstrated in the following movie.

Adding, deleting, or moving an obstacles dynamically in the navigation mesh.