Penjana Maze Backtracker Rekursif

Algoritma penjejak belakang rekursif sebenarnya adalah carian mendalam-pertama tujuan umum. Apabila digunakan untuk penjanaan maze, ia sedikit diubah suai untuk memilih laluan secara rawak, manakala jika digunakan untuk tujuan carian sebenar, seseorang biasanya hanya akan mencari setiap peringkat dalam susunan linear. Ia cenderung untuk menghasilkan labirin dengan koridor yang panjang dan berliku dan penyelesaian yang sangat panjang dan berpusing.

Labirin yang sempurna ialah labirin di mana terdapat betul-betul satu laluan dari mana-mana titik dalam mez ke mana-mana titik lain. Ini bermakna anda tidak boleh mengelilingi dalam bulatan, tetapi anda sering menemui jalan buntu, memaksa anda untuk berpusing dan kembali.

Peta maze yang dijana di sini termasuk versi lalai tanpa sebarang kedudukan mula dan penamat, jadi anda boleh memutuskannya sendiri: akan ada penyelesaian dari mana-mana titik dalam maze ke mana-mana titik lain. Jika anda mahukan inspirasi, anda boleh mendayakan kedudukan permulaan dan penamat yang dicadangkan - malah melihat penyelesaian antara kedua-duanya.

Algoritma backtracker rekursif adalah kaedah carian mendalam untuk menghasilkan labirin sempurna (labirin tanpa gelung dan dengan satu laluan antara dua titik). Ia mudah, cekap, dan menghasilkan labirin yang menarik secara visual dengan lorong panjang yang berliku.

Walaupun namanya, ia tidak semestinya perlu dilaksanakan menggunakan rekursi. Ia sering dilaksanakan dengan pendekatan iteratif menggunakan antrian LIFO (iaitu tumpukan). Untuk labirin yang sangat besar, menggunakan rekursi lebih cenderung menyebabkan penimbunan tumpukan panggilan, bergantung pada bahasa pengaturcaraan dan memori yang tersedia. Antrian LIFO boleh lebih mudah disesuaikan untuk mengendalikan jumlah data yang besar, bahkan menyimpan antrian pada cakera atau dalam pangkalan data jika memori yang tersedia tidak mencukupi.

Bagaimana Ia Berfungsi

Algoritma berfungsi menggunakan pendekatan carian mendalam berasaskan tumpukan. Berikut adalah pecahan langkah demi langkah:

1. Pilih sel permulaan dan tandakan sebagai telah dilawati.
2. Semasa terdapat sel yang belum dilawati:
   • Lihat sel-sel jiran yang belum dilawati.
   • Jika sekurang-kurangnya satu jiran yang belum dilawati wujud:
     • Pilih secara rawak salah satu jiran yang belum dilawati.
     • Buang dinding antara sel semasa dan jiran yang dipilih.
     • Pindah ke jiran yang dipilih dan tandakan sebagai telah dilawati.
     • Masukkan sel semasa ke dalam tumpukan.
   • Jika tiada jiran yang belum dilawati wujud:
     • Kembali ke belakang dengan mengeluarkan sel terakhir dari tumpukan.
3. Teruskan proses ini sehingga tumpukan kosong.

Satu fakta menarik tentang algoritma ini adalah ia berfungsi kedua-duanya sebagai penjana labirin dan penyelesai labirin. Jika anda jalankan ia pada labirin yang sudah dijana dan hanya berhenti apabila anda sampai di titik penghujung yang diputuskan, tumpukan akan mengandungi penyelesaian kepada labirin tersebut.

Saya sebenarnya mempunyai dua versi algoritma ini di laman web ini: satu berasaskan antrian LIFO untuk menghasilkan labirin di halaman ini dan satu lagi berasaskan rekursi untuk menyelesaikan labirin, juga labirin yang dijana oleh algoritma lain (begitulah cara peta dengan penyelesaian dibuat). Memiliki dua versi yang berbeza adalah hanya untuk berseronok kerana saya seorang geek yang mendapati ia menarik, kedua-duanya boleh berfungsi untuk kedua-duanya ;-)