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

  • Authors

    • Aqsa Zafar
    • Krishna Kant Agrawal
    2018-03-11
    https://doi.org/10.14419/ijet.v7i2.6.10067
  • Path Finding, Optimal Path, A* algorithm, Shortest Path, A* Optimization, Hierarchical Path finding A* (HPA*)

  • 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.

  • References

    1. [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 www.researchgate.net/publication/303369993.

      [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 www.microsoft.com/games/empires, read on January 10, 2017.

      [10] Firaxis Games, “Sid Meier’s Civilization Vâ€, www.civilization5.com, 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. http://dx.doi.org/10.4336/jcc.2016.411002.

  • Downloads

  • How to Cite

    Zafar, A., & Kant Agrawal, K. (2018). Novel optimization using hierarchical Path finding A* (HPA*) algorithm for strategic gaming setup. International Journal of Engineering & Technology, 7(2.6), 54-57. https://doi.org/10.14419/ijet.v7i2.6.10067

    Received date: 2018-03-11

    Accepted date: 2018-03-11

    Published date: 2018-03-11