Implementasi Algoritma Iterative Deepening A* (IDA*) Dengan Stochastic Node Caching (SNC) Untuk Pathfinding Musuh Pada Game Labirin

Game labirin adalah sebuah permainan jaringan jalan yang bertujuan untuk menentukan jalur yang tepat dalam mencapai tujuan yang telah di tetapkan. Untuk meningkatkan kesulitan dalam bermain maka ditambahkan karakter musuh untuk mengejar karakter pemain. Di dalam game labirin terdapat banyak pilihan jalan dan dibatasi oleh tembok, sehingga diperlukan suatu algoritma pencarian jalur yang optimal.Iterative Deepening A* (IDA*) adalah salah satu algoritma pathfinding dimana dalam penerapannya pada game labirin digunakan untuk mendapatkan jalur terpendek dari posisi musuh ke posisi pemain. Pencarian pada algoritma IDA* dilakukan secara iteratif. Hal ini menyebabkan banyaknya proses ekspansi simpul dan waktu eksekusi menjadi lama.Untuk mengatasi masalah tersebut ditambahkan sebuah fitur yaitu Stochastic Node Caching (SNC). SNC menambahkan paramater yaitu inputan cache (M) dan probabilitas (p) yang digunakan untuk mengurangi waktu eksekusi IDA*. Dalam penelitian ini algoritma IDA* dan IDA* SNC akan diimplementasikan ke dalam musuh pada game labirin berbasis desktop. Game labirin ini terdapat 3 kerumitan labirin, dimana terdapat jumlah tembok penghalang berbeda. Dari hasil pengujian di yang dilakukan di tiap kerumitan labirin dapat disimpulkan bahwa musuh yang menggunakan algoritma IDA* SNC menghasilkan solusi optimal dengan jumlah ekspansi simpul yang lebih sedikit dan waktu pencarian yang lebih cepat dari musuh yang menggunakan algoritma IDA*. Posisi pemain dan musuh juga akan mempengaruhi jumlah ekspansi simpul.Semakin jauh jarak antara pemain dan musuh, maka akan semakin banyak simpul yang diekspansi.

Maze game is a path network game which has a purpose to determine the right path for finding the goal that has been set. To increase the game difficulty then we added an enemy character to chase Player character. In a maze game there are many different path that bounded by walls, therefore it need an optimal pathfinding algorithm. Iterative Deepening A* (IDA*) is one of the pathfinding algorithm which its application on maze game is to find the shortest path from enemy position to player position. Searching on IDA* algorithm is performed iteratively. This will cause a lot of node expansion process and execution time becomes longer. To fix these problem we added a new feature called Stochastic Node Caching (SNC). SNC added input parameter cache (M) and probability (p) that use to reduce execution time of IDA*. In this research IDA* algorithm and IDA* SNC will be implemented into 5 NPC on desktop-based maze game. This maze game has 3 levels, which every level has different number of wall. From the testing result on each level, it can be concluded that the enemy that use IDA*SNC have an optimal solution with fewer node expansion and faster searching time than enemy that use ida* algorithm. Position of player and enemy will influence the total of node expansion. The father the distace between player and enemy location, the more node will be expand.