Pacman adalah sebuah permainan video arkade yang cukup terkenal. Cara bermainnya mudah yaitu pemain (pacman) diharuskan memakan makanan (berbentuk titik-titik kecil) dan sebuah bulatan besar (energizer) sampai habis di dalam sebuah labirin yang berliku-liku. Tidak hanya menghabiskan makanan tersebut, pemain juga harus menghindari 4 ‘hantu’ yang berkeliaran secara random untuk menangkap pemain. Jika pemain bertemu dengan hantu-hantu tersebut maka pemain dinyatakan gagal dan harus mengulangi dari awal lagi. Tetapi pemain bisa mengalahkan hantu tersebut dengan memakan energizer yang terdapat di pojokkan labirin. Jika pemain memakan titik besar tersebut, maka para hantu akan ketakutan dan berusaha menjauh dari pemain[1]. Dalam hal ini pemain bisa memakan hantu tersebut dan mendapatkan bonus yang besar, tetapi para hantu yang termakan tidak mati begitu saja, mereka kembali ke posisi semula dan kembali mengejar pemain. Pemain dinyatakan menang jika semua makanan habis tak tersisa dan pemain akan memasuki level berikutnya.
Pergerakan para hantu ini dipengaruhi oleh kecerdasan buatan atau Artificial intelligence (AI), dimana para hantu diberi kecerdasan untuk menentukan langkah dan mengambil keputusan akan bergerak kemana dengan menentukan rute yang paling pendek (minimum), tujuannya adalah menangkap pemain. Setiap hantu harus memiliki pemikiran berbeda dan memiliki kemampuan bekerja sama untuk mengejar pemain, sehingga permainan akan tampak lebih menarik. Persoalan mendekati karakter Pacman ini dapat diselesaikan dengan berbagai macam cara, salah satunya dengan menggunakan algoritma greedy[3].
Untuk melakukan hal ini, kita harus memberikan prioritas yang berbeda-beda pada masing-masing musuh, maka dengan sendirinya dia akan bergerak ke arah yang berbeda.
Kita ambil contoh dari keempat hantu itu, misalnya hantu yang berwarna merah. Hantu merah ini memulai gerakannya diluar rumah hantu. Dan digambarkan sebagai ancaman pertama yang muncul karena gerakannya hampir selalu di belakang pemain, begitu juga untuk ketiga hantu yang lainnya, mereka memiliki karakteristik masing-masing untuk mengejar target[2]. Berikut merupakan tampilan awal dari game Pacman :
Hantu yang berwarna merah akan terus mengikuti targetnya, jika target ke kanan maka hantu akan ke kanan, jika ke kiri maka dia juga ke kiri. Untuk hantu-hantu yang lainnya juga memiliki kemampuan dan karakteristik yang berbeda, misalkan hantu biru yang baru keluar dari rumah hantunya, dia ikut mengejar pemain, maka dengan menggunakan kemampuan yang diprogramkan, dapat dilihat apakah saat mengejar targetnya dia akan mendapat halangan (dinding labirin) atau tidak, maka disinilah para hantu di berikan kecerdasan untuk mengambil sebuah keputusan yang baik[2].
Cara Kerja
Kami akan menjelaskan cara kerja dari karakter musuh pacman tersebut dengan memberikan salah satu contoh keadaan dalam permainan pacman. Pada contoh kasus ini diasumsikan bahwa karakter Pacman tidak bergerak (diam saja di tempat), untuk menentukan apakah rute yang dipilih dari hasil algoritma greedy merupakan yang paling optimum atau tidak[3]. Berikut tampilannya :
Misal fungsi seleksi gerakkanMusuh diterapkan pada musuh Pacman yang berwarna oranye (gambar yang dilingkari). Posisi karakter musuh oranye berada di sebelah kiri karakter Pacman yang berwarna kuning, maka karakter musuh oranye seharusnya bergerak ke kanan, namun karena adanya dinding yang menghalangi, maka dilakukan pengecekan lagi terhadap perbandingan posisi Y dan didapati posisi karakter musuh oranye berada di sebelah atas karakter Pacman dan tidak ada dinding maupun karakter musuh lain yang menghalangi di atasnya, maka karakter musuh oranye dipindahkan ke atas[3]. Hasil pergerakan pertama adalah sebagai berikut :
Setelah itu, diterapkan lagi algoritma greedy untuk kedua kalinya, posisi karakter oranye sekarang ada di sebelah kiri karakter Pacman dan tidak ada yang menghalangi di sebelah kanannya, jadi karakter musuh bisa bergerak ke kanan[3], seperti tampilan berikut ini :
Setelah bergerak ke kanan, algoritma greedy diterapkan lagi dan karakter musuh berada di atas Pacman, maka karakter musuh digerakkan ke bawah sampai bertemu dengan karakter Pacman : jarak yang ditempuh untuk menemukan Pacman adalah jarak yang paling pendek[3].
Untuk kasus ini, algoritma greedy menghasilkan solusi yang optimal. Namun sesuai dengan dasar teori, algoritma greedy tidak selalu dapat menghasilkan solusi yang optimal karena algoritma greedy tidak memeriksa semua kemungkinan[3].
Contoh kasus berikut adalah kasus lain dari permainan pacman yang ternyata tidak dapat diselesaikan secara optimum oleh algoritma greedy seperti contoh kasus pertama di atas, namun solusi yang dihasilkan tidak terlalu buruk[3].
Pada contoh kasus yang kedua, tetap diasumsikan bahwa karakter Pacman tidak bergerak, selain itu, karakter musuh juga tidak ikut bergerak. Misal fungsi seleksi diterapkan pada karakter musuh warna oranye. Pada gambar 5, karena musuh oranye ada di sebelah kiri posisi Pacman, maka musuh digerakkan ke kanan[3]. Hasil pergerakan pertama sebagai berikut :
Setelah digerakkan ke kanan, posisi karakter musuh masih tetap di sebelah kiri Pacman, namun musuh tidak bisa bergerak ke kanan lagi karena terhalang dinding, setelah dicek, ternyata karakter musuh berada di sebelah atas Pacman, maka sesuai dengan algoritma greedy yang telah ditetapkan, karakter musuh digerakkan ke bawah[3]. Hasil pergerakan kedua sebagai berikut :
Setelah digerakkan ke bawah, posisi karakter musuh oranye ada di sebelah kiri dan di bawah Pacman. Algoritma greedy diterapkan sekali lagi dan karakter musuh seharusnya digerakkan ke kanan, namun karena ada karakter musuh lainnya di sana, maka karakter musuh oranye digerakkan ke bawah sekali lagi[3]. Hasil pergerakan ketiga seperti berikut :
Pada hasil pergerakan ketiga diatas, karakter oranye bergerak ke bawah sekali lagi, dan dari sini terlihat bahwa rute yang ditempuh oleh karakter musuh oranye sudah tidak mungkin menjadi optimal lagi jika dibandingkan dengan solusi optimal (rute terpendek) seperti contoh kasus pertama[3]. Berikut tampilannya :
Solusi yang telah dicapai oleh algoritma greedy hingga pada gambar 8 di atas menunjukkan bahwa algoritma greedy yang dipilih ternyata tidak selalu menghasilkan solusi yang paling optimal. Namun demikian, karena objektif dari karakter musuh Pacman ini tidak harus selalu bergerak pada rute yang merupakan solusi paling optimum, maka algoritma greedy cukup baik untuk mendapatkan hampiran-hampiran yang mendekati solusi paling optimum tersebut[3].
Sumber :
[1] Birch, Chad (2010), Understanding Pac-Man Ghost Behaviour, (diakses tangga l9 Oktober 2011 ) (http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior)
[2] Pittman, jamey (2010), Pac-Man Dossier, (diakses tanggal 9 Oktober 2011)
[3] Nugroho Chandra, Timotius (2010), Aplikasi Algoritma Greedy untuk Pergerakan Musuh pada Pac-Man, Institut Teknologi Bandung, Bandung (diakses tanggal 10 Oktober 2011)
Tidak ada komentar:
Posting Komentar