To search, Click below search items. |
| All Published Papers Search Service |
|
|
|
Title |
An Overview of Pathfinding in Navigation Mesh |
|
Author |
Xiao Cui, Hao Shi |
| Citation |
Vol. 12 No. 12 pp. 48-51 |
|
Abstract |
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. |
|
Keywords |
Pathfinding, A*, navigation mesh, triangulation, funnel algorithm |
|
URL |
