Generator Labirin Pelacak Balik Rekursif

Algoritma backtracker rekursif sebenarnya adalah pencarian mendalam (depth-first search) serbaguna. Ketika digunakan untuk pembuatan labirin, algoritma ini sedikit dimodifikasi untuk memilih jalur secara acak, sedangkan jika digunakan untuk tujuan pencarian sebenarnya, biasanya setiap level akan dicari secara linear. Algoritma ini cenderung menghasilkan labirin dengan koridor panjang dan berliku-liku serta solusi yang sangat panjang dan berbelit-belit.

Labirin yang sempurna adalah labirin yang hanya memiliki satu jalan dari titik mana pun di dalam labirin ke titik lainnya. Itu berarti Anda tidak bisa berputar-putar, tetapi Anda akan sering menemui jalan buntu, memaksa Anda untuk berbalik dan kembali.

Peta labirin yang dibuat di sini termasuk versi default tanpa posisi awal dan akhir, sehingga Anda dapat menentukannya sendiri: akan ada solusi dari titik mana pun di dalam labirin ke titik lainnya. Jika Anda menginginkan inspirasi, Anda dapat mengaktifkan posisi awal dan akhir yang disarankan - dan bahkan melihat solusi di antara keduanya.

Algoritma backtracker rekursif adalah metode pencarian mendalam untuk menghasilkan labirin sempurna (labirin tanpa lingkaran dan hanya memiliki satu jalur antara dua titik). Algoritma ini sederhana, efisien, dan menghasilkan labirin yang menarik secara visual dengan koridor panjang dan berkelok-kelok.

Meskipun namanya demikian, metode ini tidak harus selalu diimplementasikan menggunakan rekursi. Metode ini sering diimplementasikan dengan pendekatan iteratif menggunakan antrian LIFO (yaitu tumpukan). Untuk labirin yang sangat besar, penggunaan rekursi lebih cenderung menyebabkan luapan tumpukan panggilan (call stack overflow), tergantung pada bahasa pemrograman dan memori yang tersedia. Antrian LIFO lebih mudah diadaptasi untuk menangani sejumlah besar data, bahkan menyimpan antrian di disk atau di basis data jika memori yang tersedia tidak mencukupi.

Cara Kerjanya

Algoritma ini beroperasi menggunakan pendekatan pencarian mendalam berbasis tumpukan (stack-based depth-first search). Berikut adalah uraian langkah demi langkahnya:

1. Pilih sel awal dan tandai sebagai sel yang telah dikunjungi.
2. Selama masih ada sel yang belum dikunjungi: Lihat sel-sel tetangga yang belum dikunjungi. Jika setidaknya ada satu tetangga yang belum dikunjungi: Pilih salah satu tetangga yang belum dikunjungi secara acak. Hapus dinding antara sel saat ini dan tetangga yang dipilih. Pindah ke tetangga yang dipilih dan tandai sebagai telah dikunjungi. Dorong sel saat ini ke tumpukan. Jika tidak ada tetangga yang belum dikunjungi: Lakukan penelusuran balik dengan mengeluarkan sel terakhir dari tumpukan.
3. Lanjutkan proses ini hingga tumpukan kosong.

Fakta menarik tentang algoritma ini adalah bahwa ia berfungsi baik sebagai generator labirin maupun sebagai pemecah labirin. Jika Anda menjalankannya pada labirin yang sudah dibuat dan berhenti ketika mencapai titik akhir yang ditentukan, tumpukan akan berisi solusi untuk labirin tersebut.

Sebenarnya saya memiliki dua versi algoritma ini yang digunakan di situs ini: versi berbasis antrian LIFO untuk menghasilkan labirin di halaman ini dan versi berbasis rekursi untuk memecahkan labirin, termasuk labirin yang dihasilkan oleh algoritma lain (itulah cara peta dengan solusi dibuat). Memiliki dua versi berbeda hanya untuk bersenang-senang karena saya seorang kutu buku yang menganggapnya menarik, salah satunya bisa saja berfungsi untuk keduanya ;-)

Bacaan Lebih Lanjut

Jika Anda menikmati postingan ini, Anda mungkin juga menyukai saran berikut:

• Generator Labirin Algoritma Kruskal
• Generator Labirin Perburuan dan Bunuh
• Generator Labirin Algoritma Wilson