COMPUTER ANIMATION AND VIRTUAL WORLDS
Comp. Anim. Virtual Worlds
2012; 23:535–546
Published online 12 June 2012 in Wiley Online Library (wileyonlinelibrary.com). DOI: 10.1002/cav.1468
SPECIAL ISSUE PAPER
A navigation mesh for dynamic environments
†
Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts*
Department of Information and Computing Sciences, Utrech t University, 3584 CC Utrecht, The Netherlands
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. The main novelty of this paper is that we s how 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. Copyright © 2012 John Wiley & Sons, Ltd.
KEYWORDS
navigation mesh; dynamic environments; medial axis; Voronoi diagram
*Correspondence
Roland Geraerts, Department of Information and Computing Sciences, Utrecht University, 3584 CC Utrech t, The Netherlands.
E-mail: R.J.Geraerts@uu.nl
1. INTRODUCTION
A navigation mesh is a data structure that uses a set of
two-dimensional (2D) regions to represent the walkable
space in an environment [1]. These regions are commonly
used to plan visually convincing paths through complicated
environments [2–6].
Current environments are largely static because it is a
relatively expensive operation to recompute the entire nav-
igation mesh each time the environment changes. The goal
of this paper i s to show that a navigation mesh that is based
on a medial axis can be updated very quickly. We locally
repair only the affected regions of the navigation mesh
each time the environment changes. Our experiments show
that local operations can be performed quickly enough to
support dynamic environments where many obstacles are
frequently moved, added, and removed.
The navigation mesh that we choose to locally repair
is the Explicit Corridor Map (ECM) [2,6]. The ECM was
chosen because it can quickly produce smooth and short
paths with any feasible amount of clearance to the obsta-
cles. This navigation mesh can be used to plan paths for
characters that may have a variety of widths and clearance
preferences. The ECM has a small memory footprint and
has previously been used to plan visually convincing paths
for thousands of virtual characters in real time [7].
†
Supporting information may be found in the online version of this
paper.
To the best of our knowledge, this paper is the first to
describe how to perform dynamic updates in an exact 2.5D
navigation mesh. As illustrated in Figure 1, such a mesh
describes the walkable areas for a connected set of 2D
floors. Such a multilayered structure can be used to model
buildings with multiple floors.
1.1. Static Environments
Most path planners assume that the obstacles in an environ-
ment are fixed. This means that the environment is static.
Graph-based techniques such as probabilistic roadmaps
[8], rapidly exploring random trees [9], waypoint graphs
[10], and reactive deformation roadmaps [11] represent
the walkable environment (or a high-dimensional config-
uration space) using a set of one-dimensional edges. By
contrast, a navigation mesh partitions the walkable envi-
ronment into a set of 2D walkable areas. These walkable
areas permit virtual characters to control their movements
inside each 2D region so that they can more easily avoid
other moving characters [12,13].
There are many techniques to construct navigation
meshes. Pettré et al. [5] use a set of overlapping disks to
describe the walkable space. Mononen’s [3] open-source
Recast Navigation project discretizes the environment into
cubic voxels, extracts the walkable surfaces, and connects
all adjacent cells. Hale et al. [14] seed the environment with
a series of quads, and each quad grows until it is as large
Copyright © 2012 John Wiley & Sons, Ltd. 535
剩余11页未读，继续阅读
资源评论
