## Implementasi Algoritma Breadth First Search Pada Pacman Untuk Mengatur Pergerakan Karakter
Ulza Alkindi, Nur Akhmad, Yogo Kartiko, Triono Putro, Rumini
Fakultas Ilmu Komputer, Universitas AMIKOM, Yogyakarta, Indonesia Jl. Ring Road Utar, Condong Catur, Depok, Sleman, Yogyakarta 55281 Email :ulza.alkindi@students.amikom.ac.id 1) , nur.0075@students.amikom.ac.id 2) , yogo.katikoo@students.amikom.ac.id 3) , triono.se@students.amikom.ac.id 4) , rumini@amikom.ac.id 5)

## Abstrak
Kecerdasan buatan  menjadi faktor penting  dalam game antaa  manusia  melawan komputer (NPC = Non-Character Player). Salah satu metode kecerdasan buatan yang dapat digunakkan adalah algoritma Breadth First Search (BFS) dan logika fuzzy. Penelitian ini memilih game classic Pac-Man, pada permainan Pac-Man algoritma BFS diterapkan pada proses mencari dan mengejar Pac-Man. Untuk logika fuzzy  metode sugeno digunakkan pada saat pengambilan  keputusan  yaitu perilaku  ghost pada permainan tersebut. Metodologi yang digunakkan adalah metodologi prototype. Pada proses pengujian algoritma BFS digunakkan  teknik  pengujian  blackbox,  sedangkan  pada  logika  fuzzy  metode  Sugeno  digunakkan  pengujian  perbandingan perhitungan pada saat pengambilan keputusan. Dengan proses pengujian tersebut dapat ditarik bahwa Algoritma BFS sesuai untuk mencari jalur terpendek saat mengejar Pac-Man dan Logika Fuzzy metode Sugeno dapat digunakkan untuk pengambilan keputusan perilaku dari ghost dengan kecepatan pencarian 10 kali lebih cepat dari algoritma DFS.
Kata Kunci: Kecerdasan Buatan, BFS, Logika Fuzzy

## Abstract
Artificial intelligence is an important factor in games between humans against computers (NPC = Non-Character Player). One method of artificial intelligence that can be used is the Breadth First Search (BFS) algorithm and fuzzy logic. This study chose the classic Pac-Man game, in the game the Pac-Man BFS algorithm was applied to the process of finding and pursuing Pac- Man.  For  fuzzy  logic,  the  Sugeno  method  is  used  when  making  decisions,  namely  ghost  behavior  in  the  game.  The methodology used is the prototype methodology. In the testing process, the BFS algorithm is used in the black box testing technique, while the Sugeno fuzzy logic method is used to compare computation testing during decision making. With the testing  process,  it  can  be  drawn  that  the  appropriate  BFS  algorithm  to  find  the  shortest  path  while  pursuing  Pac-Man  and Sugeno Fuzzy Logic  method  can be  used for ghost behavior  decision  making  with search speed  10 times faster than DFS algorithm.
Keywords : Artificial Inteligence, BFS, Logika Fuzzy

## 1. PENDAHULUAN
Kecerdasan  buatan  merupakan salah satu cabang  ilmu komputer yang  memberikan  ilmu pengetahuan terhadap komputer  agar  mampu  menyelesaikan  tugas-tugas  atau  berpikir  seperti  manusia[1].  Dalam  perkembangannya kecerdasan  buatan  dalam  bidang  game  saat  ini  sangat  populer  untuk  permainan  manusia  melawan  komputer (NPC).  Permainan  antara  manusia  dan  komputer  dapat  meningkatkan  kualitas  game  agar  dapat  lebih menyenangkan dan menantang untuk dimainkan[1].
Algoritma Breadth First Search (BFS) merupakan algoritma penelusuran graf[3][4]. Breadth First Search meupakan algoritma sederhana untuk melakukan penelusuran pada graf, algoritma ini merupakan algoritma yang menjadi pola dasar dan fundamental bagi banyak algoritma graf. Algoritma BFS menelusuri batas ambang antara node  yang  sudah  dikunjungi  dan  node  yang  belum  dikunjungi.  Algoritma  ini  mengunjungi  node  sedemikian sehingga setiap node yang berjarak dari node awal akan dikunjungi sebelum mengunjungi node yang berjarak s+1 dari node awal(layer orde). Penelusuan graf pada algoritma Breadth First Search dilakukan dengan menelusuri setiap node dari awal. Struktur data antrian(queue) digunakkan untuk melakukan proses ekspansi Breadth First Search.
Struktur data antrian digunakkan untuk menampung setiap node atau kemungkinan node yang valid untuk dilalui. Sifat dari queue adalah First In First Out. Oleh karena itu setiap node yang dipilih dan di-expand pertama kali oleh algoritma ini akan pertama kali juga diproses dan ditelusuri. Sifat dari queue tersebut mempertahankan sifat dari algoritma Breadth First Search itu sendiri, dimana algoritma ini menelusuri secara layer order. Setiap node yang telah ditelusuri oleh algoritma breadth first search tidak akan dikunjungi lagi [3][4].
Dewasa ini Algoritma BFS merupakan algoritma untuk penentuan jalur terpendek antara titik awal dengan titik  akhir  tanpa  melewati  hambatan.  Algoritma  BFS  menggunakkan  pendekatan  heuristik  yang  menelusuri seluruh verteks yang direpresentasikan dengan node, dengan cara memperikirakan rute tebaik yang dapat dilalui dari node tersebut. Algoritma BFS banyak digunakkan dalam menyelesaikan masalah jalur terpendek dalam game karena kesederhanaan dan efektifitasnya[2].

## 2. METODE PENELITIAN

## 2.1 Logika Fuzzy
Logika  fuzzy  merupakan  kecerdasan  buatan  yang  dapat  membuat  komputer  menyelesaikan  masalah  perilaku sistem yang kompleks dan ketidakpastian yang disebabkan oleh kemampuan mengolah  informasi numerik dari variabel  yang  diukur.  Logika  fuzzy  dapat  diterapkan  untuk  pengambilan  keputusan  perilaku  komputer  dalam game[2]. Algoritma BFS dan Logika Fuzzy digunakkan karena Algoitma BFS lebih cepat dan lebih tepat dalam pencarian dan lebih tepat dalam penentuan keputusan.

## 3. ANALISA DAN PEMBAHASAN
Berdasarkan  penjelasan  diatas  akan  dilakukan  penelitian  dengan  memilih  game  classic  yaitu  Pac-Man  untuk menerapkan algoritma Breadth First Search (BFS) untuk mencari dan mengejar Pac-Man(player) dan menerapkan logika  fuzzy  metode  Sugeno  sebagai  pengambilan  keputusan  perilaku  ghost,  serta  jumlah  item  berdasarkan kondisi-kondisi yang diberikan, penelitian ini dilakukan dengan beberapa tahap yang saling berkesinambungan.

## 3.1 Merancang Prototype
a. Menentukan titik yang akan dilalui oleh NPC
Titik  atau  node  yang  akan  dilalui  oleh  NPC  direpresentasikan  dengan  huruf  didalam  elipse  disetiap persimpangan, sedangkan jalur yang akan dilalui NPC direpresentasikan dengan angka 1, seperti pada gambar 1.
Gambar 1. Jalur NPC
b. Merancang tampilan Game
Karakter NPC memiliki pergerakan  yang  berbeda  yakni random dan BFS, Karakter random  memiliki pergerakan  yang  dibuat  secara  acak  tanpa  menggunakkan  algoritma  BFS  sedangkan  karakter  BFS menggunakkan algoritma BFS serta Logika Fuzzy seperti pada tabel 1.
Tabel 1. Karakter NPC Daftar Ghost Perilaku Random BFS

## RANDOM

## RANDOM
Maze atau labirin yang menjadi jalur lintasan yang akan dilalui oleh PacMan dan Ghost dibuat seperti game PacMan pada  umumnya dengan  memodifikasi pada warna,  lintasan, serta tampilan seperti pada gambar 2.
Gambar 2. Maze Game Pacman

## 3.2 Menerapkan Algoritma Breadth First Search
Penerapan algoritma Breadth First Search pada penelitian ini memeiliki beberapa tahap yakni
a. memasukkan simpul node ke dalam antrian,
b. Ambil node pada awal antrian, kemudian dicek apakah merupakan solusi,
c. jika node merupakan solusi maka pencarian selesai dan hasil dikembalikan,
d. jika simpul bukan solusi, masukkan seluruh node yang bertetangga dengan node tersebut(node anak) ke dalam antrian,
e. jika antrian kosong dan setiap node sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan,
f. lalu mengulangi langkah b
Adapun pseudocode Algoritma BFS dapat dilihat pada berikut ini Procedure BFS (input v : integer) {v adalah simpul awal yang dikunjungi} Deklarasi W : integer q : queue;
procedure BuatAntrian(input/ouput q : queue) {Membuat antrian kosong}
procedure MasukAntrian(input/output q : queue, input v : integer) {Menambahkan v kedalam queue}
procedure HapusAntrian(input/output q : queue, output v : integer) {Menghapus data dari queue dan mengembalikan nilainya sebagai v}
Function AntrianKosong(q : queue) : boolean
{Menghasilkan true jika queue kosong dan false jika queue tidak kosong}
Algoritma : BuatAntrian(q) output(v) dikunjungi[v] ← true {Nyatakan simpul ke-v sudah dikunjungi} MasukAntrian(q,v) {travelsal ke tiap tetangga} while not AntrianKosong(q) do HapusAntrian(q,v) for tiap simpul w tetangga dari v do if not dikunjungi[w] then output(w) MasukAntrian(q,w) dikunjungi[w] ← true endif endfor endwhile
Pengujian algoritma Breadth First Search dilakukan dengan metode black-box cara membandingkan jalur yang dilalui NPC dengan skenario awal dari prototype yang  sudah dipetakan  apakah sudah sesuai atau belum,  jika belum maka akan dilakukan revisi terhadap kode program yang sudah dibuat.
Hasil pengujian algoritma Breadth First Search Dapat Dilihat pada tabel 2.
Tabel 2. Hasil Pengujian Algoritma BFS No Uji Coba Hasil Yang Diharapkan Hasil 1 Ghost dapat mendeteksi dan mengejar PacMan Ketika  Pac-Man  masuk  ke  area  ghost  maka ghost dapat mendeteksi dimana posisi pacman dan  akan  mengejar  melalui  jalur  terpendek tanpa melewati hambatan Berhasil 2 Ghost dapat mengejar Pac- Man  secara  terus menerus Ghost  akan  mengejar  Pac-Man  secara  terus menerus  melalui  jalur  terpendek  melewati hambatan Berhasil

## 3.3 Menerapkan Logika Fuzzy
Dalam penerapan Logika Fuzzy terdapat beberapa langkah yakni :
Menentukan derajat fungsi keanggotaan masing-masing himpunan fuzzy dari variabel input, variable yang menjadi  input adalah Distance pada gambar 3, Health pada gambar 4, Bonus pada gambar 5, Score pada gambar 6.
Gambar 3. Distance
Gambar 4. Health
Gambar 5. Bonus
Gambar 6. Score
Nilai inputan dari variabel Distance, Health, Bonus, dan Score dapat dilihat pada tabel 2.
Tabel 3. Nilai inputan Variabel Input Himpunan Fuzzy Rentang Nilai Distance Near 0 – 1000 Medium 600 -1600 Far 1200-2000 Health Few 1 – 45 Medium 25 – 75 Many 60 – 100 Bonus Few 0 – 5 Medium 4 - 8 Many 7 – 12 Score Low 0 – 2000 Medium 1000 – 4750 High 3000 - 6000
Pengujian dilakukan dengan membandingkan hasil perhitungan manual dengan perhitungan dengan sistem menggunakkan aplikasi  Matlab dengan  mengambil  sampel 10 nilai acak. Adapun  hasil pengujian dapat dilihat pada tabel 4.
Tabel 4. Hasil Pengujian Logika Fuzzy No Dista nce Healt h Bon us Score Hasil Hitung Manua l Hasil hitung Sistem 1 1900 100 10 5000 1 1 2 1900 100 9 4500 1
1 3 1800 80 8 4000 1 0.51908 4 1750 80 7 3900 0.519 0.519084 5 1525 75 7 3300 0 0.833 0.8333335 6 1400 75 7 3000 1 1 7 1400 66 6 2750 0.419 0.4186046 8 1350 55 6 2500 0.381 0.3809524 9 1000 50 6 2000 0 0
10 1000 40 6 1500 0.095 0.0949720 7

## 4. KESIMPULAN
Berdasarkan penelitian yang telah dilakukan, dapat diambil kesimpulan sebagai berikut : 1. Pengambilan keputusan perilaku ghos (NPC = Non-Player Character) dan jumlah item pada game sudah sesuai dengan  harapan  dengan  menggunakkan  logika  fuzzy  metode  Sugeno,  dimana  ghost  akan  bereaksi  dan menentukan jumlah item yang keluar berdasarkan kondisi-kondisi yang sudah diberikan.
2. Penerapan  Algoritma  BFS  dapat  berjalan  sesuai  dengan  harapan,  dimana  ghost  dapat  menentukan  jalur terpendek yang digunakkan dalam mencari dan mengejar pada game Pac-Man

## REFERENCES
[1] Wardana,  M.I,  Sumpeno,  S,  dan  Hariadi,  M.  2009.Kecerdasan  Buatan  dalam.  Game  untuk  Merespon  Emosi  dari  Teks  Berbahasa Indonesia. Menggunakan Klasifikasi Teks dan Logika Fuzzy. Teknik Elektro, Institut Teknologi Sepuluh Nopember Surabaya.
[2] J.F. Kelly, Lego Mindstroms NXT 2.0: The King’s Treasure, Springer, New York, 2009.
[3] T.H. Cormen, C.E. Leiserson, R.L. Rivest, & C. Stein, Introduction to Algorithm. 2nd ed, The MIT Press, Massachusetts, 2001.
[4] A.S.R.  Ansori,  M.  Hariadi,  W.  Endah,"Pemodelan  Retakan  Tiga  Dimensi  Akibat  Ledakan  Untuk  Serious  Games",  in  Proc. Semnasteknomedia 2013, pp.13-1, Januari 13,2013.
[5] A.S.R.  Ansori,  M.  Hariadi,  W.  Endah,"Pemodelan  Retakan  Tiga  Dimensi  Akibat  Ledakan  Untuk  Serious  Games",  in  Proc. Semnasteknomedia 2013, pp.13-1, Januari 13,2013.
[6] Github.com