Pada pembahasan “Game Algorithms” ini saya akan
melanjutkan dari penulisian yang sebelumnya, yaitu “Analisa Game Pacman”.
Persoalan karakter musuh Pacman dalam menentukan arah mana yang
harus dijalaninya untuk semakin mendekatkan dirinya kepada karakter Pacman dapat
dikategorikan sebagai persoalan optimasi, dan persoalan optimasi cukup efektif
dipecahkan dengan menggunakan algoritma Greedy. Persoalan optimasi pada
musuh Pacman ini termasuk persoalan minimasi, yaitu mencari rute
terpendek saat ini dari posisi karakterk musuh ke posisi karakter Pacman.
Dalam bahasa
Indonesia, Greedy adalah rakus. Prinsip dari algoritma Greedy adalah memilih keputusan yang
terbaik pada setiap langkahnya (optimum lokal). Keputusa n – keputusan lokal
yang diambil pada akhirnya menjadi solusi optimum yang mutlak (optimum global).
Elemen-elemen
dari algoritma greedy adalah sebagai berikut :
·
Himpunan Kandidat
·
Himpunan Solusi, yaitu himpunan bagian
dari himpunan kandidat yang merupakan solusi atas permasalahan.
·
Fungsi Seleksi, yaitu fungsi yang di dalamnya memiliki unsur
greedy, yang digunakan untuk menyeleksi himpunan kandidat.
·
Fungsi Layak, yaitu untuk memeriksa
apakah solusi yang dipilih merupakan solusi yang layak atau tidak.
·
Fungsi Objektif,yaitu solusi yang
dihasilkan optimum.
Kekurangan dari algoritma greedy
adalah solusi akhir yang dibentuk oleh fungsi seleksi tidak selalu
menghasilkan solusi global yang paling optimum. Hal ini dikarenakan algoritma greedy
tidak memeriksa semua kemungkinan dan hanya mengambil yang terbaik relatif
terhadap fungsi seleksi yang didefinisikan. Meskipun demikian, algoritma greedy
sangat cocok diterapkan untuk mendapatkan solusi yang mendekati optimum.
Untuk dapat menghasilkan solusi yang semakin mendekati optimum, hal yang sangat
menentukan adalah pemilihan fungsi seleksi, karena fungsi tersebut yang
menentukan langkah mana yang diambil di tiap tahap. Strategi atau pendekatan
algoritma greedy pada suatu persoalan bukan hanya satu, namun bisa
menjadi sangat banyak, dan masing – masing strategi bisa menghasilkan solusi
yang berbeda-beda. Karena algoritma greedy tidak menjamin optimalitas solusi, maka
pemilihan fungsi seleksi pada algoritma ini menjadi sangat penting.
Elemen-elemen
algoritma greedy pada permasalahan musuh Pacman sebagai berikut :
·
Himpunan Kandidat : himpunan
titik-titik (node) yang merupakan posisi yang dapat dilalui oleh musuh Pacman.
·
Himpunan Solusi : himpunan
titik-titik yang dipilih adalah rute yang berakhir pada posisi karakter Pacman.
·
Fungsi Seleksi : titik (node)
yang dipilih semakin mendekati posisi karakter Pacman.
·
Fungsi Layak : titik yang dipilih
dapat dilalui (bukan tembok atau karakter musuh lain).
·
Fungsi Objektif : rute yang
dipilih adalah rute yang paling optimum (dalam hal ini, paling pendek).
Fungsi
seleksi pada persoalan ini dapat dijabarkan sebagai berikut :
·
Jika karakter Pacman ada di
sebelah kanan karakter musuh saat ini, maka musuh pindah ke kanan, jika tidak
pindah ke kiri.
·
Jika karakter Pacman ada di
sebelah atas karakter musuh saat ini, maka musuh pindah ke atas, jika tidak
pindah ke bawah.
Sebelum karakter musuh dipindahkan, sebaiknya dicek terlebih dahulu apakah langkah
pemindahan tersebut sah / layak (tidak ada dinding / tembok atau karakter musuh lain yang menghalangi).
Dibawah ini merupakan program yang digunakan
untuk menentukan arah pergerakan karakter musuh pada pacman,yaitu dengan
menggunakan dua
variabel bernama “musuh” dan “pacman” yang masing-masing merepresentasikan
karakter musuh dan karakter pacman. Masing-masing tipe tersebut memiliki
atribut X dan Y yang menunjukkan posisi absis dan ordinat tipe tersebut pada
labirin permainan pacman. Algoritmanya sebagai berikut :
·
Fungsi seleksi :
procedure
gerakMusuh(m:musuh,p:pacman)
{
if(p.X()
>= m.X and isOK(m.X+1, m.Y)) then
pindahKanan(m)
else
if(p.Y()>=
m.Y and (isOK(m.X, m.Y+1)) then
pindahAtas(m)
else
if(isOK(m.X,
m.Y - 1) then
pindahBawah(m)
else
if(isOK(m.X-1,
Y)) then
pindahKiri(m)
}
·
Fungsi layak : untuk menentukan
apakah di posisi x dan y terdapat dinding atau karakter musuh lain yang
menghalangi.
function isOK(x, y:integer)->
boolean
{
if(noDinding(x,y)
&& noMusuh(x,y))
è true
else
è false
}
Algoritma di atas menentukan bahwa karakter
musuh pada pacman akan berjalan sampai disuatu percabangan,
saat itu juga fungsi gerakkan musuh di atas akan dipanggil secara
berulang-ulang.
Referensi :
Nugroho Chandra, Timotius (2010), Aplikasi Algoritma Greedy untuk Pergerakan Musuh pada Pac-Man, Institut
Teknologi Bandung, Bandung (diakses tanggal 10 Oktober 2011).
