Membuat Labirin dengan Algo Prim dan Backtracker

Tau labirin kan ya? Dari waktu kecil dulu mungkin kita sering mainin biasanya di belakang sampul buku SI*DU hehe…

Dan labirin ini bisa kita program atau kita buat sendiri lewat bahasa pemrograman.

Cuma… saya nggak bakal kasih contoh bahasa pemrogramannya supaya kalian bisa terjemahin sendiri ke dalam bahasa pemrograman kalian.

Oh iya, Anandastoon juga punya permainan labirin yang bisa kalian mainkan online lho di sini. Setiap main permainan baru, labirinnya pasti bakal selalu beda. Seluruhnya dibuat pake AI bikinan Anandastoon sendiri whuahahah.

Saya mau coba bocorin resep rahasia yang nggak rahasia, kalau saya pake algoritma Prim dan Backtracker selama proses pembuatan atau pengodingan labirin itu. Oh iya, ada algo Kruskal juga cuma nggak bakal saya jelasin sekarang soalnya agak rumit hehe…

Silakan simak dan bereksperimen dengan bahasa pemrograman favorit kalian tentang pembuatan labirin otomatis ini.

Preparasi

Nah sebelum kalian masuk ke deskripsi masing-masing algo pembuatan labirin, yang terpenting kalian buat dulu layout labirinnya.

Ya bebas sih mau dimensi berapa aja, mau dimensi 10 x 10, 5 x 5, 20 x 20, atau berapa aja bebas dan gak harus persegi, atau kalau mau ekstrem bisa heksagon atau segi enam malah.

Kalau ingin pake HTML, bisa pake tag table atau display grid, bebas. Yang penting kebentuk dulu wadah labirinnya yang masih kotak semua.

Nah, di contoh nanti di bawah, saya buat labirinnya berdimensi 7 x 7, lebar tujuh kotak, tinggi tujuh kotak.

Terus langkah pertama, ambil salah satu kotak acak, terserah kotak yang mana, buat jadi awal mula pembuatan labirin.

Gak harus mulai dari pojok, dari tengah juga boleh.

Algo Prim

Bagi saya, ini adalah algoritma pembuatan labirin yang paling mudah. Seenggaknya hampir sama mudahnya dengan algo Backtracker.

Intinya dari kotak mulai cuma cek tetangga di atas, bawah, kanan, dan kiri. Kalau ada kotak nganggur, semuanya masukin ke daftar tetangga nganggur.

(Kasian cari kerja udah susah ya…)

Kalau gak ada tetangga nganggur, misalnya mentok di pojokan, ya skip proses pencarian tetangga nganggurnya.

Abis itu seluruh kotak yang ada di daftar nganggur, ambil salah satu, jadiin bagian dari jalan.

Setelah itu, buka deh jalannya.

Terus begitu sampe udah nggak ada lagi tetangga yang nganggur. Asik udah dapet kerja semuanya! Gajian bisa nikmatin traktiran ~

Berikut contoh interaktifnya.

Algo Backtracker

Ini juga sama, tentang pencarian tetangga nganggur. Cuma setelah dipilih jadi bagian dari labirin, seluruh tetangga nganggurnya di lepeh alias di reset lagi.

Dan tetangga yang terpilih masih belum jadi bagian resmi dari labirinnya.

Kalau udah nggak ada tetangga nganggur, alias udah mentok, dia wajib balik lagi dengan menggunakan tetangga-tetangga terakhirnya untuk track mundur (backtrack) dan resmi jadi bagian labirin.

Terus begitu sampai seluruh tetangga jadi bagian resmi dari labirin.

Bingung? Ini saya buatin contoh interaktifnya.

Kelebihan & Kekurangan

Sayangnya, algo Prim sama Backtracker ini ada kekurangannya.

Kelebihannya, ya gampang diterapin.

Tapi kekurangannya, kalau algo Prim itu dia cenderung bikin jalan lurus dan cabang yang pendek. Kesannya jadi kayak sisir dan bikin labirinnya jadi terlalu gampang buat dimainin.

Kalau kekurangan algo Backtracker, justru kebalikan dari Prim. Labirinnya jadi muter-muter dengan percabangan yang sedikit. Agak melelahkan untuk dimainin kalau dimensi labirinnya besar, juga cukup makan resource selama pembuatannya karena kerja dua kali.

Maksudnya kerja dua kali, tetangga yang terpilih belum bener-bener jadi labirin selama belum dipake buat jalan mundur selama proses pembuatan.

Tantangan

Setelah kalian berhasil membuat labirin sendiri lewat bahasa pemrograman favorit kalian, ada satu tantangan yang menarik kalau kalian punya banyak waktu.

Nggak, saya nggak bakal bilang suruh bikin pake algo Kruskal.

Karena kekurangan masing-masing labirin bikin labirin jadi terlalu mudah atau terlalu ribet, kita bisa gabungin algo keduanya.

Gimana caranya? Misalnya setiap 5 langkah pembuatan pakai algo Backtracker, terus gantian pakai Prim. Setiap 5 langkah sekali, atau bebas setiap berapa langkah sekali.

Ini bisa bikin tingkat kesulitan labirin jadi lebih seimbang. Berani coba?