BREADTH FIRST SEARC

 

Implementasi Algoritma Breadth First Search Pada Pacman Untuk

Mengatur Pergerakan Karakter

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

Algoritma Breadth First Search (BFS) merupakan algoritma penelusuran graf. Breadth First Search meupakan algoritma sederhana untuk melakukan penelusuran pada graf, algoritma ini merupakan algoritma yangmenjadi 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+1dari 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.

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

            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.

Maze atau labirin yang menjadi jalur lintasan yang akan dilalui oleh PacMan dan Ghost dibuat seperti game PacMan pada umumnya.

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

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 sesuaidengan 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

https://www.ejurnal.stmik-budidarma.ac.id/index.php/jurikom/article/view/1004/999