Generator Labirin Pelacak Balik Rekursif

Algoritma backtracker rekursif sebenarnya adalah pencarian mendalam yang bersifat umum. Ketika digunakan untuk pembuatan labirin, ia dimodifikasi sedikit untuk memilih jalur secara acak, sedangkan jika digunakan untuk tujuan pencarian yang sebenarnya, seseorang biasanya hanya akan mencari setiap level dalam urutan linier. Ia cenderung menghasilkan labirin dengan koridor yang panjang dan berliku-liku serta solusi yang sangat panjang dan berliku-liku.

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 satu jalur antara dua titik). Metode ini sederhana, efisien, dan menghasilkan labirin yang menarik secara visual dengan koridor yang panjang dan berliku.

Meskipun namanya demikian, hal itu tidak harus diimplementasikan menggunakan rekursi. Hal itu sering diimplementasikan dalam pendekatan berulang menggunakan antrean LIFO (yaitu tumpukan). Untuk labirin yang sangat besar, penggunaan rekursi lebih mungkin mengakibatkan luapan tumpukan panggilan, tergantung pada bahasa pemrograman dan memori yang tersedia. Antrean LIFO dapat lebih mudah diadaptasi untuk menangani sejumlah besar data, bahkan menyimpan antrean di disk atau dalam basis data jika memori yang tersedia tidak mencukupi.

Cara Kerjanya

Algoritme ini beroperasi menggunakan pendekatan pencarian mendalam berbasis tumpukan. Berikut adalah rincian langkah demi langkahnya:

1. Pilih sel awal dan tandai sebagai telah dikunjungi.
2. Meskipun ada sel yang belum dikunjungi:
   • Lihatlah sel tetangga yang belum dikunjungi.
   • Jika setidaknya ada satu tetangga yang belum dikunjungi:
     • Pilih secara acak salah satu tetangga yang belum dikunjungi.
     • 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:
     • Mundur dengan mengeluarkan sel terakhir dari tumpukan.
3. Lanjutkan proses ini hingga tumpukannya kosong.

Fakta menarik tentang algoritma ini adalah ia bekerja baik sebagai pembuat labirin maupun sebagai pemecah labirin. Jika Anda menjalankannya pada labirin yang sudah dibuat dan berhenti begitu mencapai titik akhir yang ditentukan, tumpukan akan berisi solusi labirin.

Saya sebenarnya memiliki dua versi algoritma ini yang sedang dijalankan di situs ini: versi berbasis antrian LIFO untuk menghasilkan labirin di halaman ini dan versi berbasis rekursi untuk memecahkan labirin, juga labirin yang dihasilkan oleh algoritma lain (begitulah cara peta dengan solusi dibuat). Memiliki dua versi yang berbeda hanya untuk bersenang-senang karena saya seorang kutu buku yang menganggapnya menarik, keduanya bisa digunakan untuk keduanya ;-)