Reducing the Search Space for Pathfinding in Navigation Meshes by Using Visibility Tests
Hyung-Il Kim, Kyeonah Yu, Juntae Kim · Journal of Electrical Engineering and Technology · 2011
A navigation mesh (NavMesh) is a suitable tool for the representation of a three-dimensional game world. A NavMesh consists of convex polygons covering free space, so the path can be found reliably without detecting collision with obstacles. The main disadvantage of a NavMesh is the huge state space. When the $A^*$ algorithm is applied to polygonal meshes for detailed terrain representation, the pathfinding can be inefficient due to the many states to be searched. In this paper, we propose a method to reduce the number of states searched by using visibility tests to achieve fast searching even on a detailed terrain with a large number of polygons. Our algorithm finds the visible vertices of the obstacles from the critical states and uses the heuristic function of $A^*$ , defined as the distance to the goal through such visible vertices. The results show that the number of searched states can be substantially reduced compared to the $A^*$ search with a straight-line distance heuristic.