Path-finding can become an important bottleneck as both the size of the virtual environments and the number of agents navigating them increase. It is important to develop techniques that can be efficiently applied to any environment independently of its abstract representation. In this paper we present a hierarchical NavMesh representation to speed up path-finding. Hierarchical path-finding (HPA*) has been successfully applied to regular grids, but there is a need to extend the benefits of this method to polygonal navigation meshes. As opposed to regular grids, navigation meshes offer representations with higher accuracy regarding the underlying geometry, while containing a smaller number of cells. Therefore, we present a bottom-up method to create a hierarchical representation based on a multilevel k-way partitioning algorithm (MLkP), annotated with sub-paths that can be accessed online by our Hierarchical NavMesh Path-finding algorithm (HNA*). The algorithm benefits from searching in graphs with a much smaller number of cells, thus performing up to 7.7 times faster than traditional A¿ over the initial NavMesh. We present results of HNA* over a variety of scenarios and discuss the benefits of the algorithm together with areas for improvement. ; Peer Reviewed ; Postprint (author's final draft)
Hierarchical path-finding for Navigation Meshes (HNA*)
2016-10-01
Article (Journal)
Electronic Resource
English
DDC: | 629 |
Finding a path in the hierarchical road networks
IEEE | 2001
|Finding a Path in the Hierarchical Road Networks
British Library Conference Proceedings | 2001
|Evaluation of Hierarchical Path Finding Techniques for ITS Route Guidance
British Library Conference Proceedings | 1996
|Vision-based Navigation and Reinforcement Learning Path Finding for Social Robots
BASE | 2010
|