GAME ALGORITHMS (Game Pacman = Algoritma Greedy)

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).