To search, Click below search items.


All Published Papers Search Service


An Overview of Pathfinding in Navigation Mesh


Xiao Cui, Hao Shi


Vol. 12  No. 12  pp. 48-51


Pathfinding is a fundamental problem that most commercial games must deal with. Due to the increase in game complexity, early solutions to the problem of pathfinding were soon overwhelmed. A* alone, a classic search algorithm, is no longer sufficient to provide the best solution. The popularization of using navigation mesh in pathfinding makes A* search a very small proportion of pathfinding implementation. In this paper, it systematically reviews the entire process of using a navigation mesh to find an optimal path. First a general pathfinding solution is described. Then examples of using A* in a navigation mesh are given. Additionally, implementation details of using funnel algorithm in both triangulation and polygonization are given, which is a major contribution of this paper.


Pathfinding, A*, navigation mesh, triangulation, funnel algorithm