A navigation mesh for dynamic environments

作者：van Toll Wouter G; Cook Atlas F; Geraerts Roland^*

来源：Computer Animation and Virtual Worlds, 2012, 23(6): 535-546.

DOI：10.1002/cav.1468

• navigation mesh
• dynamic environments
• medial axis
• Voronoi diagram

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. 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. Experiments show that local updates are fast enough to permit real-time updates of the navigation mesh.

• 出版日期2012-12