Novel optimization using hierarchical Path finding A* (HPA*) algorithm for strategic gaming setup

  • Abstract
  • Keywords
  • References
  • PDF
  • Abstract

    In game Industry, the most trending research area is shortest path finding. There are many video games are present who are facing the problem of path finding and there is various algorithms are present to solve this problem. In this paper brief introduction is given in the most using algorithm for path finding and A* algorithm has been proved the best algorithm for resolving the problem of shortest path finding in games. It provides the optimal solution for path finding as compare to other search algorithm. At the start of the paper, brief introduction about the path finding is given. Then the reviews of different search algorithm are presented on the basis of path finding. After that information of A* algorithm and optimization techniques are described. In the last, application and examples how the path finding techniques are used in the game is addressed and future work and conclusion are drawn.

  • Keywords

    Path Finding, Optimal Path, A* algorithm, Shortest Path, A* Optimization, Hierarchical Path finding A* (HPA*)

  • References

      [1] Xiao Cui &Hao Shi, “A*- based Path finding in Modern Computer Games,” IJCSNS, School of Engineering and Science, Victoria University, Melbourne, Australia, International Journal of Computer Science and Network Security, p125, VOL11 No1, Jan 2011.

      [2] Amit S. Wale, Taranpreet Singh Saini, Ahmed Mohammad Ali, Vandana S. Jagtap, “Survey Heuristic Search for Shortest Path finding in Games,” ISSN-Print 2393-8374, Online-ISSN 2394-0697, VOL2, I 12,2015

      [3] Xiang Xu and Kun Zou,” An Improved Path finding Algorithm in RTS Games”, Communications in Computer and Information Science- Springer 153, pp. 1-7, 2011.

      [4] Mehta Parth, Shah Hetasha, ShuklaSoumya, VermaSaurav,” A Review on Algorithm for Path finding in Computer Games”, available at

      [5] Rubén Tous,” Real Time Planning for Path finding in Computer Games”.

      [6] GeethuElizebeth Mathew,” Direction Based Heuristic for Path finding in Video Games”, Procedia of Computer Science 47,262-271, 2015.

      [7] Guni Sharon,” Thesis Summary Optimal Multi-Agent Path finding Algorithm”, Published at Twenty Ninth AAAI- Conference on Artificial Intelligence Proceedings.

      [8] Rubén Tous,” Real Time Planning for Path finding in Computer Games”, UniversitatPompeuFabra(UPF), Department de Tecnologia, Spain.

      [9] Age of Empire Game by Microsoft, read on January 10, 2017.

      [10] Firaxis Games, “Sid Meier’s Civilization V”,, read on January 10, 2017.

      [11] N. H. Barnouti, Al- Dabbagh, S S M &Naser, M A S “Path finding in Strategy Games & Maze Solving Using A* Search Algorithm”. @016 Journal of Computer & Communication, 4, 15-25.




Article ID: 10067
DOI: 10.14419/ijet.v7i2.6.10067

Copyright © 2012-2015 Science Publishing Corporation Inc. All rights reserved.