Indian Journal of Science and Technology
Year: 2022, Volume: 15, Issue: 35, Pages: 1722-1731
Owen Riady Chandra1, Wirawan Istiono1*
1Universitas Mutltimedia Nusantara, Scientia Boulevard Curug Sangereng, Tangerang, Banten, 15810, Indonesia
Email: [email protected]
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
© 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.