Name
Title | ||
|---|---|---|
The Explicit Corridor Map: A Medial Axis-Based Navigation Mesh for Multi-Layered Environments. |
Abstract | ||
|---|---|---|
Path planning for walking characters in complicated virtual environments is a fundamental task in simulations and games. In this paper, we present an improved definition of the Explicit Corridor Map (ECM), a navigation mesh that allows efficient path planning and crowd simulation for disk-shaped characters of any radius. The ECM is a medial axis (MA) annotated with nearest-obstacle information. For a planar environment with $n$ obstacle vertices, the ECM has size $O(n)$ and can be computed in $O(n log n)$ time. also introduce multi-layered environments (MLEs), in which multiple planar layers are connected by line segment connections. Typical real-world examples are multi-storey buildings, train stations, and sports stadiums. We define the MA and the ECM for multi-layered environments, based on projected distances on the ground plane. For an MLE with $n$ obstacle points and $k$ connections, the MA has size $O(n)$. We present an improved algorithm that constructs the MA and ECM in $O(n log n log k)$ time. 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. |
Year | Venue | Field |
|---|---|---|
2017 | arXiv: Computational Geometry | Motion planning,Discrete mathematics,Line segment,Topology,Binary logarithm,Vertex (geometry),Navigation mesh,Medial axis,Planar,Crowd simulation,Geometry,Mathematics |
DocType | Volume | Citations |
Journal | abs/1701.05141 | 0 |
PageRank | References | Authors |
0.34 | 32 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wouter van Toll | 1 | 5 | 4.18 |
| Atlas F. Cook | 2 | 49 | 4.56 |
| Marc J. van Kreveld | 3 | 1702 | 166.91 |
| Roland Geraerts | 4 | 381 | 25.70 |