A Navigation Mesh for Dynamic Environments
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
Computer Animation and Virtual Worlds (CAVW), vol. 23 (6), pp. 535-546, 2012.
Resources:
Full text (pdf) - Presentation (ppt)
Also presented at a national conference:
Game-Changing: Fast Dynamic Updates in a Flexible Navigation Mesh
Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts
In ASCI.OPEN / ICT.OPEN 2013.
Resources:
Full text (pdf) - Presentation (pptx) - Poster (pdf)
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.
@article{vanToll2012-Dynamic,
author = {{\noop{toll}}van Toll, W.G. and {Cook IV}, A.F. and Geraerts, R.},
journal = {Computer Animation and Virtual Worlds},
title = {A navigation mesh for dynamic environments},
volume = {23},
number = {6},
year = {2012},
pages = {535--546}
}
Additional information can be found on the research page of Roland Geraerts.