## Implementasi Algoritma Greedy Pada Game Pacman
Pamela Hapsari Putri, Muhammad Ridlo Arifandi, Edy Hardianto Rifeni, Fakhrur Wiradhika, Rumini, Anggit Dwi Hartanto
Jurusan Informatika, Fakulitas Ilmu Komputer, Universitas AMIKOM Yogyakarta, Indonesia Jl. Ring Road Utara, Condong Catur, Sleman, Yogyakarta, Indonesia E-mail: 1 Pamela.putri@students.amikom.ac.id, 2 Muhammad.arifandi@students.amikom.ac.id,
3 Edy.rifeni@students.amikom.ac.id, 4 Fakhrur.wiradhika@students.amikom.ac.id, 5 Rumini@amikom.ac.id,
6 Anggit@amikom.ac.id
Abstrak
Pacman adalah sebuah game arkade yang di kembangkan oleh Namco dan dirilis di Jepang pada 22 Mei 1980. Pac-Man yang masih populer  hingga kini telah dirilis pula dalam platform lainnya seperti Game Boy dan SNES . Perancang permainan ini adalah Toru Iwatani , yang merupakan karyawan Namco. Konsep permainan pada game pacman pun sangat sederhana : Pemain harus mengontrol karakter pacman untuk memakan semua titik-titik kecil dan benda-benda khusus lainnya yang berada dalam labirin  tanpa  tertangkap  oleh  4  hantu.  Algortima  greedy  digunakan  untuk mencari  lintasan  terpendek  saat  ini  dari  posisi karakter musuh (ghost) ke posisi karakter Pacman.
Kata Kunci : Greedy, Pacman, Lintasan Terpendek

## Abstract
Pacman is an arcade game developed by Namco and released in Japan on May 22, 1980. Pac-Man, which is still popular today, has also been released on other platforms such as Game Boy and SNES. The designer of this game is Toru Iwatani, who is a Namco employee. The concept of the game in the Pacman game is very simple: Players must control the Pacman character to eat all the small dots and other special objects that are in the maze without being caught by 4 ghosts. The greedy algorithm is used to find the current shortest path from the position of the ghost character to the position of the Pacman character.
Keywords : Greedy, Pacman, Shortest Path

## 1. PENDAHULUAN
Pacman  adalah  game  yang  beraliran  labirin  (maze)  dengan  konsep  yang  sederhana  :  terdapat  1  labirin  dengan beberapa dinding sebagai pengahalang  atau rintangan di dalammnya, suatu titik  menjadi titik awal  munculnya karakter Pacman, titik-titik sebagai makanan yang harus dimakan oleh karakter Pacman, dan hantu sebagai musuh yang harus di hindari. Ketika permainan Pacman di mulai, selama beberapa detik  musuh akan terkurung dalam sebuah kotak yang berada di dalam labirin, setelah beberapa detik, karakter musuh tersebut akan bebas dan mulai berjalan  secara  acak  Untuk  meningkatkan  tantangan  dan  kesulitan  pada  game  Pacman,  musuh  di  berikan kecerdasan  khusus  untuk  mementukan  rute  paling  pendek  (minimum)  agar  dapat  mendekati  karakter  Pacman. Kecerdasan yang di gunakan pada musuh karakter pacman pun beragam. Salah satunya menggunakan Algoritma.

## 2. TEORITIS

## 2.1 Algoritma Greedy
Persoalan karakter musuh (ghost) dalam menentukan arah mana yang harus di lewatinya untuk mendekatkan diri pada karakter pacman dapat di kategorikan sebagai persoalan optimasi, dan persoalan ini cukup efektif dipecahkan menggunakan algoritma Greedy [2] . Persoalan optimasi  pada ghost termasuk persoalan  minimasi,  yaitu  mencari lintasan terpendek untuk menuju ke karakter pacman.
Prinsip  algoritma  greedy  adalah  memilih  keputusan  yang  terbaik  dalam  setiap  langkahnya  (Optimum local).  Keputusan  local  yang  di  ambil  akhirnya  akan  menjadi  solusi  optimum  yang  mutlak  (Optimum  global). Berikut adalah elemen dari algoritma Greedy :
a. Himpunan Kandidat
b. Himpunan Solusi : himpunan bagian dari himpunan kandidat yang merupakan solusi dari permasalahan.
c. Fungsi Seleksi : fungsi yang memiliki unsur greedy, digunakan untuk menyeleksi himpunan kandidat.
d. Fungsi Layak : digunakan untuk memeriksa apakah solusi yang dipilih merupakan solusi yang layak atau tidak.
e. Fungsi Objektif : solusi yang dihasilkan optimum
Namun,  kekurangan  dari  algortima  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 relative terhadap fungsi seleksi yang didefinisikan. Meskipun demikian,  algortima  greedy  cocok  di  terapkan  untuk  mendapatkan  solusi  yang  mendekati  optimum.  Untuk mendapatkan  solusi  yang  semakin  mendekati  optimum,  hal  yang  paling  menentukan  adalah  pemilihan  fungsi seleksi, karena fungsi tersebut menentukan langkah mana yang di ambil tiap tahap.
Strategi  algotima  greedy  pada  suatu  persoalan  tidak  hanya  satu,  namun  bisa  menjadi  sangat  banyak  ,  dan tiap strategi bisa menghasilkan solusi yang berbeda-beda. Karena algoritma greedy tidak menjamin optimalitas solusi, maka pemilihan fungsi seleksi menjadi sangat penting. Strategi yang digunakan algoritma greedy cukup ampuh untuk  diterapkan  pada  persoalan-persoalan  optimasi.  Hasil  solusi  yang  didapatkan  oleh  algoritma greedy cenderung  mendekati /  menghampiri  hasil  solusi  optimal,  selain  itu,  yang  menjadi kelebihan algoritma greedy sendir adalah implementasinya yang sangat sederhana dan langsung[3]. Namun demikian, jika yang dibutuhkan adalah solusi yang mengharuskan didapatkannya solusi yang paling optimum suatu algoritma greedy harus dapat dibuktikan  secara  matematis  terlebih  dulu  bahwa  algoritma  tersebut  dapat  menghasilkan  solusi  yang  paling optimum, jika tidak, maka tidak bisa dijamin bahwa algoritma greedy yang dibuat akan optimum untuk semua kasus.

## 3. ANALISA DAN PEMBAHASAN
Berikut adalah elemen algoritma greedy pada permasalahan karakter ghost :
a. Himpunan  kandidat  :  kumpulan  titik-titik  (node)  yang  merupakan  lintasan  yang  dapat  di  lalui  oleh karakter ghost
b. Himpunan  solusi :  kumpulan titik-titik (node)  yang di pilih adalah  lintasan  yang  berakhir pada posisi karakter pacman
c. Fungsi seleksi : node yang dipilih semakin mendekati karakter pacman
d. Fungsi layak : node yang dipilih dapat dilalui. Bukan tembok atau karakter musuh lain
e. Fungsi objektif : lintasan yang dipilih adalah lintasan yang paling optimum (paling pendek) Fungsi seleksi pada kasus ini dapat dijabarkan sebagai berikut :
a. Jika karakter pacman ada di sebelah kanan ghost, maka ghost pindah ke kanan, jika tidak pindah kekiri
b. Jika karakter pacman ada di atas ghost, maka ghost pindah ke atas, jika tidak pindah kebawah
Sebelum  ghost  berpindah,  maka  terlebih  dahulu  dicek  apakah  langkah  tersebut  layak,  dalam  hal  ini  tidak  ada tembok atau karakter ghost lain yang menghalangi.
Pada  kode  semu  di  bawah  digunakan  dua  tipe  variable  yaitu  “ghost”  dan  “pacman”  yang  merepresentasikan karakter  hantu  (musuh)  dan  karakter  pacman.  Masing-masing  tipe  tersebut  memiliki  atribut  X  dan  Y  yang menunjukan posisi dan ordinat tipe tersebut pada maze atau labirin permainan. Kode semu algoritma greedy untuk menentukan arah pergerakan karakter ghost adalah sebegai berikut :
Fungsi seleksi :
Fungsi layak : untuk menentukan apakah pada posisi x dan y terdapat dinding atau karakter ghost (musuh) lain yang menghalangi
Dengan algotima di atas karakter ghost digerakkan hingga  mencapai suatu titik dalam  labirin  yang  merupakan percabangan atau persimpangan. Jadi fungsi gerakGhost di atas akan di panggil secara berulang setiap karakter ghost sampai di suatu percabangan.
function isOK(x, y:integer)-> boolean { if(noDinding(x,y) && noGhost(x,y))
➔ true
else
➔ false
}
procedure gerakGhost(g:host,p:pacman) { if(p.X() >= g.X and isOK(g.X+1, g.Y)) then pindahKanan(g) else if(p.Y()>= g.Y and (isOK(g.X, g.Y+1)) then pindahAtas(g) else if  (isOK(g.X, g.Y - 1) Then pindahBawah(g) else if(isOK(g.X-1, Y)) then pindahKiri(g) }
Berikut  adalah  contoh  keadaan  dalam  permainan  pacman.  Pada  kasus  ini  di  asumsikan  karakter  pacman  tidak bergerak, untuk  menentukan apakah  lintasan  yang di pilih oleh hasil algortima greedy  merupakan  yang paling optimum atau tidak.

## Gambar 1. Contoh keadaan permainan pacman
Misalkan  fungsi  seleksi  gerakGhost  diterapkan  pada  salah  satu  karakter  ghost.  Posisi  karakter  ghost  berada  di sebelah kiri pacman (g.X < p.X), maka  karakter ghost seharusnya bergerak ke kanan, namun ada dinding yang menghalangi, maka di lakukan pengecekan terhadap perbandingan posisi Y dan didapati karakter ghost berada di atas  pacman  (g.Y  >  p.Y)  dan  tidak  ada  dinding  atau  karakter  ghost  lain  yang  menghalangi,  maka  ghost  di pindahkan ke atas.
Gambar 2 . Hasil pergerakan pertama
Setelah itu di terapkan lagi algoritma greedy untuk kedua kalinya. Posisi karakter ghost sekarang berada di sebelah kiri pacman (g.X < p.X) dan tidak ada yang menghalangi pada sebelah kanannya, maka karakter ghost bergerak ke kanan.
Gambar 3 . Hasil pergerakan kedua
Setelah bergerak ke kanan, di terapkan  lagi algoritma greedy dan karakter ghost  berada di atas pacman (g.Y > p.Y), maka ghost di gerakkan ke bawah sampai bertemu dengan pacman : jarak yang di tempuh untuk menemukan pacman adalah  jarak  yang paling pendek. Untuk kasus  ini, algoritma greedy  menghasilkan hasil  yang optimal. Namun  algoritma  greedy  tidak  selalu  dapat  menghasilkan  solusi  yang  optimal  karena  algortima  greedy  tidak memeriksa semua kemungkinan. Berikut adalah contoh lain dari permainan pacman yang ternyata tidak dapat di selesaikan secara optimum, namun solusi yang di hasilkan tidak terlalu buruk.
Gambar 4. Contoh kedua
Pada contoh di atas karakter ghost berada di sebelah kiri posisi pacman (g.X < p.X), maka ghost di gerakkan ke kanan.
Gambar 5. Hasil pergerakan pertama
Setelah bergerak ke kanan, posisi ghost tetap berada di sebelah kiri pacman, namun musuh tidak bisa bergerak ke kanan  lagi karena terhalang dinding, setelah di cek ternyata karakter ghost berada di atas pacman (g.Y > p.Y) maka sesuai dengan algoritma greedy yang telah di tetapkan, ghost di gerakkan ke bawah.
Gambar 6. Hasil pergerakan kedua
Setelah bergerak ke bawah, posisi karakter ghost ada di sebelah kiri dan di bawah karakter pacman. Di terapkan lagi algoritma greedy. Ghost seharusnya di gerakkan ke kanan, namun ternyata ada karakter musuh yang lainnya maka ghost de gerakkan ke bawah lagi.
Gambar 7 . Hasil pergerakan ketiga
Pada hasil pergerakan ketiga, karakter ghost  bergerak ke bawah  lagi, dan dapat diketahui  bahwa  lintasan  yang ditempuh karakter ghost sudah tidak mungkin menjadi optimal lagi di bandingkan dengan solusi optimal (lintasan terpendek) yang mungkin dari posisi awal karakter ghost ke pacman seperti berikut :
Gambar 8. Solusi optimal pergerakan karakter ghost
Solusi yang telah di capai algoritma greedy hingga pada gambar 8 di atas menunjukkan bahwa algoritma greedy tidak selalu menghasilkan solusi yang paling optimal. Namun karena objektif dari karakter ghost tidak harus selalu bergerak  pada  lintasan  yang  meupakan  solusi  paling  optimum,  maka  algoritma  greedy  cukup  baik  untuk mendapatkan solusi yang mendekati solusi paling optimum tersebut.

## 4. KESIMPULAN
Strategi  yang  digunakan  algortima  greedy  cukup  ampuh  untuk  di  terapkan  pada  permasalahan  optimasi.  Hasil solusi  yang  di  dapatkan  cenderung  mendekati  hasil  solusi  optimal.  Selain  itu,  kelebihan  dari  algortima  greedy adalah  implementasinya  yang  sederhana.  Namun,  jika  di  yang  di  perlukan  adalah  solusi  yang  mengharuskan didapatkannya  solusi  yang  paling  optimum  maka  harus  dibuktikan  secara  sistematis  terlebih  dahulu  bahwa algoritma  tersebut  dapat  menghasilkan  solusi  yang  paling  optimum.  Untuk  permasalahan  optimasi  yang  tidak mengharusan di dapatkannya solusi yang paling optimum, algoritma greedy sangat cocok di terapkan.

## UCAPAN TERIMA KASIH
Kami  para  peneliti  mengucapkan  banyak  terima  kasih  kepada  Allah  SWT  yang  telah  memberikan  kemudahan serta kelancaran kepada kami, dan juga kepada dosen pembimbing kami, orang tua kami dan jurnal atau paper- paper yang ada dalam referensi kami.

## REFERENCES
[1] Pac-Man . http://en.wikipedia.org/wiki/Pacman . Waktu akses : 27 Oktober 2018 pukul 23:00
[2]   Munir.  Rinaldi.  “Diktat  Kuliah  IF2251  Strategi  Algoritmik”.  2005.  Bandung:  Program  Studi  Teknik  Informatika  –  Institut  Teknologi Bandung
[3]   Nugroho Chandra. Timotus. “ Aplikasi Algoritma Greedy untuk Pergerakan Musuh pada Permainan Pac-Man ”. 2010. Bandung: Program Studi Teknik Informatika – Institut Teknologi Bandung
[4]   Sumber source code program pacman : https://github.com/vilbeyli/Pacman . Waktu akses : 20 Oktober 2018