Chandra, Owen Riady and Istiono, Wirawan (2022) A-star Optimization with Heap-sort Algorithm on NPC Character. Indian Journal of Science and Technology, 15 (35). pp. 1722-1731. ISSN 0974-5645
|
Text
5. A-star Optimization with Heap-sort Algorithm on NPC (1).pdf Download (2MB) | Preview |
Abstract
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.
| Item Type: | Article |
|---|---|
| Keywords: | AStar; Heap Sort; NonPlayable Character; Optimization Algorithm; Pathfinding |
| Subjects: | 000 Computer Science, Information and General Works > 000 Computer Science, Knowledge and Systems > 005 Computer Programming > 005.2 Programming for Specific Computers, Algorithm, HTML, PHP, java, C++ |
| Divisions: | Faculty of Engineering & Informatics > Informatics |
| Depositing User: | Administrator UMN Library |
| Date Deposited: | 10 Feb 2023 00:47 |
| Last Modified: | 10 Feb 2023 00:47 |
| URI: | https://kc.umn.ac.id/id/eprint/23055 |
Actions (login required)
 |
View Item |
