Comparison Analysis of Dijkstra and A-Star Algorithms in NPC (Non-Playable Character) Movement on a Single-Player Game

Case Study: Chaos Crossing Game

Abstract

Artificial intelligence in a game plays a vital role in enhancing the player's gaming experience, especially in single-player games. NPCs are the primary means of interaction in single-player games, assisting and guiding players like interactions with other players. Chaos Crossing requires pathfinding technology for optimal NPC movement, allowing them to navigate the environment grid-based while avoiding static obstacles. The Dijkstra algorithm and the A-Star algorithm need to be compared because, based on previous research, the Dijkstra algorithm has proven effective for calculating the shortest distance to the destination point in a static environment based on a two-dimensional grid with characters moving in it, as well as the A-Star algorithm can avoid a static environment based on grid and is used to determine the shortest distance to the destination point in the character's movement. This quantitative research aims to find a solution that optimizes NPC movement by testing and comparing Dijkstra's and A-Star's algorithms in a static environment grid based on the game Chaos Crossing. The test results and comparative analysis show that the A-Star algorithm performs a faster route search with an average value of 36.37 seconds than Dijkstra's algorithm with an average matter of 20.76 seconds and utilizes memory more efficiently with an average value of 20.19 MB than Dijkstra's algorithm with a value 22.17 MB on average. However, Dijkstra's algorithm produces a slightly shorter track distance, with an average value of 42.26 units, compared to the A-Star algorithm, with an average value of 42.39 units.