Hybridization of A* Pathfinding and Hierarchical Pathfinding A* Algorithm for Pathfinding in Grid Based Games

A* algorithm is one of the most used Pathfinding Algorithm to date as well as one of its variants, Hierarchical Pathfinding A*. The primary focus of this paper is A* issue with its scalability and its memory efficiency and HPA* inaccuracy when returning a path. By hybridizing the algorithms, it aims to solve the aforementioned issues of both algorithms and is also aimed to produce an alternative algorithm for game developers working with grid-based games like in open-world games where Pathfinding is a necessary process. A simulator was created wherein it returns specific values which are runtime in milliseconds, final path, length of the final path, the visited nodes, and the total number of nodes visited which is the comparison basis of this study. Using the simulator, it returned the mentioned data in the form of Test Seeds. By analyzing the results reflected in the Test Seeds conducted, it can be seen that by applying the hybrid algorithm, mentioned issues have been resolved, with A*+HPA* producing a faster run time than A* but slower than HPA*, A*+HPA* visiting fewer nodes than A*, and A*+HPA* returning a shorter path compared to HPA*. It can be concluded that the chosen enhancements significantly affected the performance of the algorithms in this study.