A Navigation Mesh for Dynamic Environments

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

Reference
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
A Navigation Mesh for Dynamic Environments.
Computer Animation and Virtual Worlds (CAVW), 23(6):535-546, 2012.
Full text: [pdf] | Presentation [ppt]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Game-Changing: Fast Dynamic Updates in a Flexible Navigation Mesh.
ICT.OPEN 2013 (ICT.OPEN 2013).
Full text: [pdf] | Presentation [pptx] | Poster [pdf]

A multi-layered navigation mesh (navmesh), computed in 46ms.   A multi-layered navigation mesh (navmesh) in which a yellow/black obstacle was added dynamically.
A multi-layered navigation mesh in which a yellow/black obstacle was added dynamically.


Movie
The steps of our algorithm are visualized in the movie below.