COMPARATIVE ANALYSIS OF PATHFINDING ARTIFICIAL INTELLIGENCE USING DIJKSTRA AND A* ALGORITHMS BASED ON RPG MAKER MV

  • Riska Nurtantyo Sarbini (1*) Universitas Pertahanan
  • Irdam Ahmad (2) Universitas Pertahanan
  • Romie Oktovianus Bura (3) Universitas Pertahanan
  • Luhut Simbolon (4) Universitas Pertahanan

  • (*) Corresponding Author
Keywords: Artificial Intelligence, Pathfinding, Dijkstra Algorithm, A* algorithm

Abstract

In most games, an artificial pathfinding intelligence is required for traversing the fastest discovery. It is essential for many video games, particularly Role Playing Games (RPGs). The algorithm pathfindings implemented in this game are A* and Dijkstra Algorithms. This study aims to test an artificial intelligence system for discovering routes using the A* and Dijkstra algorithms based on RPG Maker MV. The result showed that from the time obtained, in the experiment on eight nodes using the Pathfinding mechanism of A* algorithm has faster result in discovering the nearest route with the time 08:15:23 with format (mm:ss: ms) whereas Dijkstra Algorithm has a 34:47:43 time result. The time record needed represents the distance between the search nodes. It indicates that the multiple weighting in the impassable nodes caused the cost calculation process becomes faster and more efficient.

Downloads

Download data is not yet available.

References

Arikunto, S. (2006). Prosedur penelitian suatu pendekatan praktik (IV). Jakarta: Penerbit PT Rineka Cipta.

Chen, J. H., Shih, T. K., & Chen, J. Y. (2012). To develop the ubiquitous adventure RPG (role play game) game-based learning system. Conference Proceedings - IEEE International Conference on Systems, Man and Cybernetics, 2973–2978. https://doi.org/10.1109/ICSMC.2012.6378247

Hammedi, S., Essalmi, F., Jemni, M., & Qaffas, A. A. (2020). An investigation of AI in games: Educational intelligent games vs non-educational games. Proceedings of 2020 International Multi-Conference on: Organization of Knowledge and Advanced Technologies, OCTA 2020. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/OCTA49274.2020.9151738

Harahap, M. K., & Khairina, N. (2017). Pencarian Jalur Terpendek dengan Algoritma Dijkstra. SinkrOn, 2(2), 18. https://doi.org/10.33395/sinkron.v2i2.61

Hu, J., Gen Wan, W., & Yu, X. (2012). A pathfinding algorithm in real-time strategy game based on Unity3D. ICALIP 2012 - 2012 International Conference on Audio, Language and Image Processing, Proceedings, 1159–1162. https://doi.org/10.1109/ICALIP.2012.6376792

Iqbal, M., & Rizwan, M. (2009). Application of 80/20 rule in software engineering Waterfall Model. 2009 International Conference on Information and Communication Technologies, ICICT 2009, 223–228. https://doi.org/10.1109/ICICT.2009.5267186

Iskandar, U. A. S., Diah, N. M., & Ismail, M. (2020). Identifying Artificial Intelligence Pathfinding Algorithms for Platformer Games. 2020 IEEE International Conference on Automatic Control and Intelligent Systems, I2CACIS 2020 - Proceedings, 74–80. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/I2CACIS49202.2020.9140177

Maria, B., Hanna, P., & Yosefina, R. (2022). Penerapan algoritma dijkstra untuk menentukan rute terpendek dari pusat kota surabaya ke tempat bersejarah. Jurnal Teknologi Dan Sistem Informasi Bisnis, 4(1), 213–223. https://doi.org/10.47233/jteksis.v4i1.407

Rachmawati, D., & Gustin, L. (2020). Analysis of Dijkstra's Algorithm and A∗ Algorithm in Shortest Path Problem. Journal of Physics: Conference Series, 1566(1), 012061. Institute of Physics Publishing. https://doi.org/10.1088/1742-6596/1566/1/012061

Saravanan, T., Jha, S., Sabharwal, G., & Narayan, S. (2020). Comparative Analysis of Software Life Cycle Models. Proceedings - IEEE 2020 2nd International Conference on Advances in Computing, Communication Control and Networking, ICACCCN 2020, 906–909. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ICACCCN51052.2020.9362931

Sazaki, Y., Primanita, A., & Syahroyni, M. (2018). Pathfinding car racing game using dynamic pathfinding algorithm and algorithm A∗. Proceedings - ICWT 2017: 3rd International Conference on Wireless and Telematics 2017, 2017-July, 164–169. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/ICWT.2017.8284160

Sinha, A., & Das, P. (2021). Agile Methodology Vs. Traditional Waterfall SDLC: A case study on Quality Assurance process in Software Industry. 2021 5th International Conference on Electronics, Materials Engineering & Nano-Technology (IEMENTech). Kolkata, India: IEEE. https://doi.org/10.1109/IEMENTech53263.2021.9614779

Tang, C., Wang, Z., Sima, X., & Zhang, L. (2020). Research on artificial intelligence algorithm and its application in games. Proceedings - 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture, AIAM 2020, 386–389. Institute of Electrical and Electronics Engineers Inc. https://doi.org/10.1109/AIAM50918.2020.00085

Trivedi, P., & Sharma, A. (2013). A comparative study between iterative waterfall and incremental software development life cycle model for optimizing the resources using computer simulation. Proceedings of the 2013 2nd International Conference on Information Management in the Knowledge Economy : 19-20 December 2013. Punjab, India: Chitkara University. Retrieved from https://ieeexplore.ieee.org/abstract/document/6915096/authors#authors

Wahyuningsih, D., & Syahreza, E. (2018). Shortest Path Search Futsal Field Location With Dijkstra Algorithm. IJCCS (Indonesian Journal of Computing and Cybernetics Systems), 12(2), 161–170. https://doi.org/10.22146/IJCCS.34513

Waleed, S., Faizan, M., Iqbal, M., & Anis, M. I. (2017). Demonstration of single link failure recovery using Bellman Ford and Dijikstra algorithm in SDN. ICIEECT 2017 - International Conference on Innovations in Electrical Engineering and Computational Technologies 2017, Proceedings. https://doi.org/10.1109/ICIEECT.2017.7916533

Zhao, M. (2020). Analysis on the connection between nonplayer character and artificial intelligence. Proceedings - 2020 International Conference on Intelligent Computing and Human-Computer Interaction, ICHCI 2020, 105–108. https://doi.org/10.1109/ICHCI51889.2020.00030

Published
2022-06-20
How to Cite
Sarbini, R., Ahmad, I., Bura, R., & Simbolon, L. (2022). COMPARATIVE ANALYSIS OF PATHFINDING ARTIFICIAL INTELLIGENCE USING DIJKSTRA AND A* ALGORITHMS BASED ON RPG MAKER MV. Jurnal Riset Informatika, 4(3), 283-290. https://doi.org/10.34288/jri.v4i3.384
Article Metrics

Abstract viewed = 26 times
PDF downloaded = 14 times