Implementasi Algoritma Simplified Memory Bounded A* Untuk Pencarian Kata PAda Permainan Word Search Puzzle

Permainan word search puzzle adalah permainan untuk mencari kata yang tersembunyi pada papan permainan yang disusun dalam bentuk matriks. Kata-kata tersebut dapat disusun secara horizontal, vertikal maupun tersusun dengan lebih dari satu ruas garis yang terhubung secara horizontal dan vertikal. Pencarian kata yang tersusun dengan lebih dari satu ruas garis memiliki karakteristik yang sama dengan permasalahan pathfinding, sehingga membutuhkan suatu algoritma pathfinding untuk melakukan pencarian. Algoritma Simplified Memory-Bounded A* (SMA*) adalah salah satu algoritma pathfinding yang dapat digunakan untuk melakukan pencarian kata pada pada permainan word search puzzle. Algoritma SMA* memiliki kelebihan pada penggunan memori yang lebih sedikit, hal ini dikarenakan penggunaan memori dibatasi hingga jumlah simpul tertentu. Berdasarkan hasil pengujian bahwa semakin panjang karakter pada kata yang dicari maka waktu pencarian akan semakin lama dan penggunaan memori juga akan semakin besar. Semakin banyak simpul yang tersedia untuk melakukan pancarian maka waktu pencarian akan semakin cepat, dimana persentase peningkatan kecepatan pencarian dengan penambahan simpul sebanyak 100% dapat meningkat hingga 21,99% dibandingkan dengan tidak ada penambahan simpul.

Word search puzzle game is a game to find the hidden words on the board game that it arranged in the form of a matrix. The words can be arranged horizontally, vertically or it can be arranged in more than one segment which are connected horizontally and vertically. Search word is compiled more than one line segment which has the same characteristics as pathfinding problems, so it requires a pathfinding algorithm to perform a search. Simplified Memory-Bounded A* (SMA*) Algorithm is one of the pathfinding algorithms that can be used to perform a word search on the word search puzzle game. SMA* algorithm has an advantage in uses of less memory, this thing because the memory usage is limited to a certain number of nodes. Based on test results that the longer of characters on the search terms so the search time will be longer and also memory usage will increase although. More nodes are available to search so it will be faster, wherein the percentage of search speed increase with adding nodes 100% it can be up to 21.99% than it does not add the nodes.