A-star Optimization with Heap-sort Algorithm on NPC Character

Owen Riady Chandra; Wirawan Istiono

doi:10.17485/IJST/v15i35.857

Article

A-star Optimization with Heap-sort Algorithm on NPC Character

VIEWS 1147
PDF 203

Indian Journal of Science and Technology

DOI: 10.17485/IJST/v15i35.857

Year: 2022, Volume: 15, Issue: 35, Pages: 1722-1731

Original Article

A-star Optimization with Heap-sort Algorithm on NPC Character

Owen Riady Chandra¹, Wirawan Istiono^1*

¹Universitas Mutltimedia Nusantara, Scientia Boulevard Curug Sangereng, Tangerang, Banten, 15810, Indonesia

*Corresponding Author
Email: [email protected]

Received Date:25 April 2022, Accepted Date:09 August 2022, Published Date:07 September 2022

This work is licensed under a Creative Commons Attribution 4.0 International License.

Abstract

Objectives: To find out whether the A-star algorithm that is optimized with the heap-sort algorithm can reach the target destination faster than the native Astar when applied on NPC to find the path. Methods: Comparisons are made by implementing an optimized A-star algorithm with heap-sort and native Astar on an NPC in a dungeon-crawling game genre by applying five different scenarios, where each scenario has a different start position of the NPC, and the target goal is set. The comparison is made by measuring the time required by both algorithms to reach the target goal in milliseconds with Unity engine software and C# language. Findings: From the results of experiments and calculation, it was found that the A-star algorithm optimized with the heap-sort algorithm was 50%-80% faster than using only the A-star algorithm in cases that was applied alone on NPC in dungeon-crawling game. Novelty: The novelty in this research is the optimization of the A-star algorithm with heap-sort, and then that algorithm is compared with the native A-star algorithm that is applied to NPCs in the dungeon-crawling game genre.

Keywords: AStar; Heap Sort; NonPlayable Character; Optimization Algorithm; Pathfinding

References

Pardede SL, Athallah FR, Huda YN, Zain FD. A Review of Pathfinding in Game Development. CEPAT Journal of Computer Engineering: Progress, Application and Technology. 2022;1(01):47. Available from: https://doi.org/10.25124/cepat.v1i01.4863
Wang H, Lou S, Jing J, Wang Y, Liu W, Liu T. The EBS-A* algorithm: An improved A* algorithm for path planning. PLOS ONE. 2022;17(2):e0263841. Available from: https://doi.org/10.1371/journal.pone.0263841
Istiono W. Effectiveness of Mobile Game-based Education on Algorithm Thinking: Informatic Engineering Case. International Journal of Emerging Trends in Engineering Research. 2021;9(3):163–168. Available from: https://doi.org/10.30534/ijeter/2021/02932021
Shi J, Su Y, Bu C, Fan X. A mobile robot path planning algorithm based on improved A*. Journal of Physics: Conference Series. 2020;1486(3):032018. Available from: https://doi.org/10.1088/1742-6596/1486/3/032018
Foead D, Ghifari A, Kusuma MB, Hanafiah N, Gunawan E. A Systematic Literature Review of A* Pathfinding. Procedia Computer Science. 2021;179(2020):507–514. Available from: https://doi.org/10.1016/j.procs.2021.01.034
Erke S, Bin D, Yiming N, Qi Z, Liang X, Dawei Z. An improved A-Star based path planning algorithm for autonomous land vehicles. International Journal of Advanced Robotic Systems. 2020;17(5):172988142096226. Available from: https://doi.org/10.1177/1729881420962263
He Z, Liu C, Chu X, Negenborn RR, Wu Q. Dynamic anti-collision A-star algorithm for multi-ship encounter situations. Applied Ocean Research. 2022;118:102995. Available from: https://doi.org/10.1016/j.apor.2021.102995
Zhang J, Wu J, Shen X, Li Y. Autonomous land vehicle path planning algorithm based on improved heuristic function of A-Star. International Journal of Advanced Robotic Systems. 2021;18(5):172988142110427. Available from: https://doi.org/10.1177/17298814211042730
Istiono W, Suryadibrata A, Waworuntu A, Nusantara UM. List Point Marker Path Finding for Artificial Intelligence Movement in 3D Games. International Journal of Emerging Trends in Engineering Research. 2021;9(10):1336–1340. Available from: https://doi.org/10.30534/ijeter/2021/079102021
Liu C, Mao Q, Chu X, Xie S. An Improved A-Star Algorithm Considering Water Current, Traffic Separation and Berthing for Vessel Path Planning. Applied Sciences. 2019;9(6):1057. Available from: https://doi.org/10.3390/app9061057
Bayeck RY. Examining Board Gameplay and Learning: A Multidisciplinary Review of Recent Research. Simulation & Gaming. 2020;51(4):411–431. Available from: https://doi.org/10.1177/1046878119901286
Chen F, Chen N, Mao H, Hu H. An efficient sorting algorithm - Ultimate Heapsort(UHS) 2019. Available from: https://doi.org/10.48550/arXiv.1902.00257
Abhay G, Abhishek S, Namita G. A variant of Bucket Sort. 10th International Conference on Computing, Communication and Networking Technologies (ICCCNT). 2019;p. 1–5.
Tofterdahl M. Localization Tools in General Purpose Game Engines: A Systematic Mapping Study. International Journal of Computer Games Technology. 2021;2021:1–15. Available from: https://doi.org/10.1155/2021/9979657
Hong Z, Sun P, Tong X, Pan H, Zhou R, Zhang Y, et al. Improved A-Star Algorithm for Long-Distance Off-Road Path Planning Using Terrain Data Map. ISPRS International Journal of Geo-Information. 10(11):785. Available from: https://doi.org/10.3390/ijgi10110785

Copyright

© 2022 Chandra & Istiono.This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.

Published By Indian Society for Education and Environment (iSee)