Multi-Layered Navigation Meshes

Virtual characters often need to plan visually convincing paths through a complicated environment. For example, a traveler may need to walk from an airport entrance to a staircase, descend the staircase, walk to a shuttle, ride the shuttle to a destination, ride an elevator back to the ground floor, and finally move on the ground floor again to reach the desired airplane. Most previous research only supports path planning in a single plane because the underlying data structures are twodimensional. The goal of this paper is to permit visually convincing paths to be efficiently computed in a multilayered environment such as an airport or a multi-storey building. We describe an algorithm to create a navigation mesh, and our implementation demonstrates the feasibility of the approach. A multi-layered environment is represented by a set of two-dimensional layers and a set of connections. Each layer is a collection of two-dimensional polygons that all lie in a single plane, and each connection provides a means of moving between layers. We first compute the traditional medial axis of each two-dimensional layer in the environment. The connections are then used to iteratively merge this collection of medial axes into a single data structure. By adding a linear number of line segments to this structure, we obtain a navigation mesh that mathematically describes the walkable areas in a multi-layered environment. This mesh can easily be input into existing planners to generate visually convincing paths for thousands of virtual characters in real-time.