Implementasi Algoritma Dijkstra pada Game Pacman

Game Pacman sangatlah dikenal dikalangan banyak orang, namun pernah kah anda memikirkan bagaimana caranya ghost pada game pacman dapat mencari rute terdekat untuk bisa menangkap karakter pacman? Ternyata dalam game Pacman terdapat sebuah algoritma yang dapat mencari jarak terpendek untuk ghost bisa menangkap karakter pacman, algoritma tersebut dikenal sebagai Algoritma Dijkstra

Algoritma Dijkstra merupakan algoritma greedy yang digunakan untuk menyelesaikan masalah jarak terpendek untuk graf berarah dengan bobot sisi non-negatif. Ide dasar dari algoritma Dijkstra sendiri adalah untuk mencari nilai biaya yang paling dekat dengan tujuan yang berfungsi pada graf berbobot, sehingga dapat membantu memberikan pilihan jalur. Dalam Algoritma Dijkstra, node digunakan karena Algoritma Dijkstra menggunakan graf berarah untuk menentukan jalur terpendek. Algoritma ini bertujuan untuk mencari jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya. Misalkan titik mewakili bangunan dan garis menggambarkan jalan, maka Algoritma Dijkstra melakukan perhitungan pada semua kemungkinan bobot terkecil dari setiap titik.

Berikut ini adalah alur implementasi algoritma dengan membuat peta, mengubah peta menjadi biner, penempatan ghost dan pacman, pengujian menggunakan tabel. Berikut ini adalah alur penerapan algoritma dengan membuat peta, mengubah peta menjadi biner, penempatan ghost dan pacman, pengujian menggunakan tabel

1. Pembuatan Peta

Tahap pertama membuat peta pacman, peta adalah peta atau labirin yang digunakan sebagai tempat hantu dan pacman berada.

2. Konversi Peta ke Biner

Tahap kedua adalah konversi peta ke biner, konversi dilakukan setelah membuat peta dan menentukan putaran sudut seperti A, B, C dan seterusnya dari peta yang kami desain lagi, kami mengubahnya menjadi biner dengan angka 0 dan 1.

3. Penempatan Ghost dan Pacman

Tahap ketiga adalah penempatan hantu dan pacman di tempat awal atau di titik 0 penempatannya bisa ditempatkan selama masih ada di peta. Dari gambar di bawah, pacman berada di titik A dan Ghost berada di titik K.

4. Pengujian Menggunakan Tabel

Tahap keempat adalah pengujian menggunakan tabel yang digunakan oleh ghost sebagai pencarian rute terpendek untuk menangkap pacman. Berikut ini adalah beberapa aturan dari algoritma dijkstra yang digunakan untuk menyelesaikan masalah rute terpendek:

1. Titik awal layak 0/nol
2. Titik lain = tidak diketahui/tak terhingga (∞). Titik lainnya berarti titik-titik yang tidak terhubung langsung dengan mengunjungi contoh node K dengan N, node K sampai N diberi tanda (∞) karena tidak terhubung langsung dengan node K tetapi terhubung dengan node M.
3. Pilih titik dengan jarak paling optimal dari titik awal. Jarak optimum adalah jarak terbaik yang didapat dari kunjungan, pilih jarak dengan nilai terkecil.
4. Titik terdekat yang belum dikunjungi pada titik terakhir kita melakukan perhitungan untuk menentukan jaraknya dari titik awal.
5. Jika jarak yang dihitung lebih kecil dari jarak yang diketahui maka kita tentukan bahwa jarak terdekat adalah dari titik yang baru saja kita hitung.
6. Kemudian kita perbarui poin sebelumnya dengan poin baru
7. Setelah selesai, pada titik akhir yang sudah optimal, kami memasukkannya ke dalam daftar yang dikunjungi sehingga tidak ada lagi perhitungan yang dilakukan.

Dan bila anda sadar, algoritma seperti ini juga digunakan oleh google maps untuk menentukan rute tercepat pada maps apabila kita ingin bepergian dari satu tempat ke tempat lain. Dengan algoritma ini, google juga menambahkan beberapa fungsi untuk mencari rute tercepat atau memutar apabila terdapat kemacetan pada jalan yang akan dilalui.

Sehingga Algoritma Dijkstra ini sangatlah berguna, tidak hanya digunakan pada game arkade lama saja, namun juga digunakan di salah satu software terdekat kita yaitu google.

LINK YOUTUBE : https://youtu.be/xC_5pP65zt0