A study on Bee algorithm and A∗ algorithm for pathfinding in games

摘要

Pathfinding is essential and necessary for agent movement used in computer games and many other applications. A primary concern of pathfinding is to find the shortest feasible path. The past decade has seen the rapid development of pathfinding in many games industry. Several attempts and solutions have been made to solve the problem. Heuristic A* algorithm has proven given an optimal for single agent and small size of search in current game industry. However, pathfinding solution is often requiring huge amount of resources especially in complex game environment. Hence, generation a feasible and optimal path more computationally burdensome or intractable. More recently, literature has come out that offers findings about metaheuristic in pathfinding. Metaheuristic is usually used in pathfinding problem. Bee algorithm is a metaheuristic algorithm which is naturally behaves as multi-agent approach and proven efficient in solving the path planning problem. The current research on Bee algorithm mostly focused on improving optimization for agent. The aim of this paper is to describe and compare traditional algorithm, A* algorithm and optimization search, Bee algorithm in pathfinding.