• P-ISSN 0974-6846 E-ISSN 0974-5645

Indian Journal of Science and Technology


Indian Journal of Science and Technology

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

Original Article

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

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


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


  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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.
  11. 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
  12. 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


© 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


Subscribe now for latest articles and news.