Implementation of a* algorithm within navigation mesh in an artificial intelligence based video games

  • Authors

    • Temmy Subrando
    • Fauzan Akbar Prasetyatama
    • Devi Fitrianah
    https://doi.org/10.14419/ijet.v7i4.21573

  • Abstract

    Pathfinding is one of the key components for Artificial Intelligence in video games, It addresses the problem to find the shortest path be-tween starting point and destination point, before A* became a staple algorithm for pathfindings, many search algorithms were used in-cluding Djikstra, Depth, and Breadth-First searches, Pathfindings are known to be resource-intensive processes especially in a large world but it mostly depends on what algorithm the game is using and what method it is implemented, using A* combined with Navigation Mesh, a popular abstract data structure in video games, this paper reviews the overall system resources used during the pathfinding pro-cess with a destination point that is always moving in a real-time so that it will gives realistic results since, in video games, a Player is constantly moves around the world, the result that we have gathered, we have concluded that A* flawlessly works with Navigation Mesh, and the performance impacts of both A* and Navigation Mesh combined is non-existent.

  • References

    1. [1] M. Zikky, Review of A * (A Star) Navigation Mesh Pathfinding as the Alternative of Artificial Intelligent for Ghosts Agent on the Pacman Game, Emit. Int. J. Eng. Technol., vol. 4, no. 1, pp. 141–149, 2016.

      [2] X. Cui and H. Shi, An Overview of Pathfinding in Navigation Mesh, IJCSNS International Journal of Computer Science and Network Security, IJCSNS Int. J. Comput. Sci. Netw. Secure. vol. 12, no. 48, 2012.

      [3] X. Cui and H. Shi, A*-based Pathfinding in Modern Computer Games, Int. J. Comput. Sci. Netw. Secur. vol. 11, no. 1, pp. 125–130, 2011.

      [4] S. Rabin et al., Game AI Pro: Collected Wisdom of Game AI Professionals. 2013.

      [5] R. Coleman, Fractal analysis of stealthy pathfinding aesthetics, Int. J. Comput. Games Technol., no. 1, 2009.

      [6] N. H. Barnouti and S. S. M. Al-Dabbagh, Pathfinding in Strategy Games and Maze Solving Using A Search Algorithm, J. Comput., pp. 15–25, 2016.

      [7] P. L. Newton and J. Feng, Unreal Engine 4 AI Programming Essentials. 2016.

      [8] F. Safadi, Artificial Intelligence in Video Games: Towards a Unified Framework, 2015.

      [9] Valve, Dota 2. Taken September 27, 2017.

      [10] Bethesda Softworks, The Elder Scrolls V: Skyrim, http://elderscrolls.wikia.com/wiki/Season_Unending. Retrieved May 2, 2018.

      [11] Mixamo, Mixamo Animation Pack by Mixamo in Characters - UE4 Marketplace. https://www.unrealengine.com/marketplace/mixamo-animation-pack. [Accessed: 23-Jul-2018].

      [12] Yaroslav, 3D Buick gsx 455 | CGTrader. https://www.cgtrader.com/free-3d-models/car/sport/buick-gsx-455. [Accessed: 23-Jul-2018].

      [13] E. Games, Soul: Cave by Epic Games in Epic Showcase,Environments - UE4 Marketplace. https://www.unrealengine.com/marketplace/soul-cave. [Accessed: 23-Jul-2018].

      [14] Anafeyka, [FREE] Knife and Blade for community - Unreal Engine Forums. https://forums.unrealengine.com/community/community-content-tools-and-tutorials/39180-free-knife-and-blade-for-community. [Accessed: 23-Jul-2018].

      [15] E. Games, Open World Demo Collection by Epic Games in Epic Showcase, Environments - UE4 Marketplace. https://www.unrealengine.com/marketplace/open-world-demo-collection. [Accessed: 23-Jul-2018].

      [16] Gameworld3d, Container Pack with Fence 3D asset | CGTrader. https://www.cgtrader.com/free-3d-models/exterior/industrial/container-pack-with-fence. [Accessed: 23-Jul-2018].

      [17] E. Games, Animation Starter Pack by Epic Games in Epic Showcase,Animations - UE4 Marketplace. https://www.unrealengine.com/marketplace/animation-starter-pack. [Accessed: 23-Jul-2018].

      [18] A. T. Wibowo and D. Fitrianah, A K-Nearest Algorithm Based Application To Predict Snmptn Acceptance for High School, Int. Res. J. Comput. Sci., vol. 5, no. 01, pp. 9–20, 2018.

      [19] E. Yunianto, S. Rudiarto, and D. Fitrianah, Implementation Of Hamming Network Algorithm To Decipher The Characters Of Pigpen Code In Scouting, Int. Res. J. Comput. Sci., vol. 5, no. 01, 2018.

      [20] D. Ramayanti, The 3D Game Simulation of ‘Anjungan DKI Jakarta’ at Taman Mini Indonesia Indah and Betawi Culture based on FPS (First Person Shooter, Int. Res. J. Comput. Sci., vol. 2, no. 12, 2015.

  • Downloads

  • How to Cite

    Subrando, T., Prasetyatama, F. A., & Fitrianah, D. (2018). Implementation of a* algorithm within navigation mesh in an artificial intelligence based video games. International Journal of Engineering & Technology, 7(4), 3249-3254. https://doi.org/10.14419/ijet.v7i4.21573

    Received date: 2018-11-25

    Accepted date: 2018-11-25