Implementasi algoritma SMA* pada game TPS Moster Nest berbasis mobile

Algoritma pathfinding yang paling sering digunakan adalah A*, yang terbukti optimal untuk pencarian, walaupun A* adalah algoritma pencarian yang baik, algoritma A* menghabiskan banyak resources. Pada peta besar, ratusan atau bahkan ribuan node mungkin akan berada dalam open list dan closed list, yang dapat memakan memori lebih banyak dari yang tersedia pada sistem dengan memori yang terbatas. Untuk mengatasi ini dipilih algoritma SMA* (Simplified Memory-Bounded A* ).Algoritma SMA* yang mengatasi masalah storage problem dengan meletakkan limit tetap pada ukuran open list, di dalam tugas akhir ini akan diimplementasikan di dalam game pada NPC (Non-Playable Computer) untuk memberikan kemampuan pencarian jalan agar NPC dapat menemukan posisi pemain, dan akan dilakukan pengujian terhadap penggunaan memori SMA* dengan melihat jumlah node yang ada di dalam open list dan closed list.Dari hasil pengujian yang dilakukan dapat disimpulkan bahwa algoritma SMA* dapat diimplementasikan di dalam game monster nest dan menggunakan memori lebih sedikit dibandingkan dengan algoritma A*, dengan melihat jumlah dari open list dan closed list yang dihasilkan selama pencarian. Limit pada open list di algoritma SMA* mempengaruhi hasil dari pencarian, apabila tidak mencukupi maka hasil dari pencarian tidak bisa optimal seperti algoritma A*.

Pathfinding algorithm most commonly used is A *, which proved optimal for search. Although A* is about good a search algorithm, it can be wasteful of resources. On a large map, hundreds or even thousands of nodes might be in the open lists and closed lists, which can take up more memory than is available on systems with constrained memory. To overcome these selected SMA * algorithm (Simplified Memory-Bounded A *). Simplified memory-bounded A* which solves the storage problem by putting a fixed limit on the size of the open list, in this final project will be implemented in the game at the NPC (Non-Playable Computer) to provide search capabilities so NPC can find a path to player position, and will be done testing of SMA * memory usage by looking at the number of nodes in the open list and a closed list.From the test results it can be concluded that SMA * algorithm can be implemented in the game monster nest and uses less memory than the algorithm A*, figures from the open list and a closed list generated during the search. Limit on the open list in SMA * algorithm affect the results of the search, if not sufficient then the results of the search can not be optimal as the A * algorithm.