IMPLEMENTASI DAN ANALISIS ALGORITMA A* DAN JUMP POINT SEARCH UNTUK MENENTUKAN JALUR TERPENDEK PADA NON PLAYER CHARACTER
Daftar Isi:
- Pathfinding is the way to find the shortest route between two points. The A* and Jump Point Search algorithms use the number of nodes that must be taken to determine the shortest path that can be traversed by the NPC. To reach the goal, the NPC must go through a node that is not an obstacle so it can form a path that will be taken as the shortest path. A * algorithm combines Uniform Cost Search and Greedy-Best First Search, with the calculated costs derived from actual costs plus estimated costs, whereas the JPS algorithm uses pruning rules and jumping rules to do a simple pruning, with the aim of jumping over many places that only considered necessary. From the 5 levels of testing that has been conducted, the result shows that JPS algorithm can reduce the amount of nodes that will be used to find the path with the range of 533% until 1700% shorter compared to A* algorithm.