ALGORITMA FLOW FIELD A STAR UNTUK MELAKUKAN PATHFINDING PADA PERMAINAN REAL-TIME STARTEGY

ACHMAD JEIHAN P, Faizal Makhrus, Ph.D

2017 | Skripsi | S1 ILMU KOMPUTER

Pada permainan real-time strategy, proses pathfinding dilakukan untuk sekumpulan objek seperti prajurit yang bergerak dari source yang sama dan menuju ke target yang sama. Algoritma A* adalah algoritma pathfinding yang digunakan dalam permainan real-time startegy. Algoritma ini tidak dapat diskala secara efektif karena harus melakukan komputasi untuk setiap objek yang akan bergerak sehingga banyak komputasi dan memory digunakan. Pada penelitian ini, dikembangkan sebuah algoritma pathfinding Flow Field A* yang merupakan modifikasi dari algoritma A*. Algoritma ini mampu memproses pencarian path untuk sekumpulan objek yang memiliki source dan target sama. Selain itu, dengan mengubah output algoritma menjadi flow field, permasalahan collision antar objek juga dapat diatasi. Berdasarkan hasil pengujian, algoritma Flow Field A* memiliki running time 10 kali lebih cepat dari algoritma Flow Field Bruteforce dan 5 kali lebih cepat dari algoritma A*. Selain itu, penggunaan memory algoritma Flow Field A* 20 kali lebih sedikit dari algoritma A*.

In real-time strategy video games, pathfinding processes are done for a group of objects like soldiers that move from the same source to the same target. A* is a pathfinding algorithm used in this games. This algorithm tend to scale poorly because it must compute a path for each moving object, so that many computation and memory are being used. In this research, a new algorithm called Flow Field A* was developed by modifying A* algorithm. This algorithm was able to do pathfinding process for a group of objects that has the same source and target. In addition, by changing the output of pathfinding algorithm into a flow field, collision problem that occurs can be solved. Based on the experiments, the running time of Flow Field A* algorithm was 10 times faster than Flow Field Bruteforce and 5 times faster than A* algorithm. In addition, memory usage in Flow Field A* algorithm was 20 times fewer than A*.

Kata Kunci : pathfinding,flow field,real-time strategy games