Path planning for walking characters in complicated virtual environments is a fundamental task in simulations and games. A navigation mesh is a data structure that allows efficient path planning. The Explicit Corridor Map (ECM) is a navigation mesh based on the medial axis. It enables path planning for disk-shaped characters of any radius.
In this paper, we formally extend the medial axis (and therefore the ECM) to 3D environments in which characters are constrained to walkable surfaces. Typical examples of such environments are multi-storey buildings, train stations, and sports stadiums. We give improved definitions of a walkable environment (WE: a description of walkable surfaces in 3D) and a multi-layered environment (MLE: a subdivision of a WE into connected layers). We define the medial axis of such environments based on projected distances on the ground plane. For an MLE with n boundary vertices and k connections, we show that the medial axis has size O(n), and we present an improved algorithm that constructs the medial axis in O(n log n log k) time.
The medial axis can be annotated with nearest-obstacle information to obtain the ECM navigation mesh. Our implementations show that the ECM can be computed efficiently for large 2D and multi-layered environments, and that it can be used to compute paths within milliseconds. This enables simulations of large virtual crowds of heterogeneous characters in real-time.
Wouter G. van Toll, Atlas F. Cook IV, Marc J. van Kreveld and Roland Geraerts. The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh. arXiv:1701.05141v2 (submitted to a journal), 26 July 2017.
Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Navigation Meshes for Realistic Multi-Layered Environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'11), pp. 3526-3532, 2011.
Wouter G. van Toll, Atlas F. Cook IV and Roland Geraerts. Multi-Layered Navigation Meshes. In ASCI - IPA - SIKS tracks, ICT.OPEN (ICT.OPEN 2011), pp. 317-323, 2011.
This paper has received the best paper award ASCI 2011.
The method is demonstrated in the following movie.
A multi-layered environment in R3 can be represented as a set of two-dimensional layers and a set of connections between these layers. For example, the connection C_01 connects layer 0 and layer 1, and the connection C_12 connects layer 1 and layer 2. Each connection is directed in the sense that it can only be used through its access side. The obstacle side of a connection is an impassable obstacle.
The medial axis of a simple multi-layered environment. The influence zone Z_ij is highlighted in blue. The intersection of M_i and M_j with C_ij is denoted by the points p_1, p_2 in C_ij.
More examples of multi-layered navigation meshes can be found on our page on crowd simulation software.
Such a mesh also allows dynamic updates when an obstacle is inserted, deleted or moved.