Penjana Memburu dan Membunuh Maze

Algoritma Hunt dan Kill sebenarnya merupakan versi pengubahsuaian Recursive Backtracker. Pengubahsuaian terdiri daripada mengimbas secara sistematik (atau "memburu") untuk meneruskan sel baharu daripada apabila ia tidak dapat pergi lebih jauh, berbanding carian rekursif sebenar, yang akan sentiasa kembali ke sel sebelumnya pada timbunan.

Oleh sebab itu, algoritma ini boleh disesuaikan dengan mudah untuk menghasilkan labirin dengan rupa dan rasa yang berbeza, hanya dengan memilih untuk memasuki mod "memburu" dengan lebih kerap atau mengikut peraturan tertentu. Versi yang dilaksanakan di sini hanya memasuki mod "memburu" apabila ia tidak dapat pergi lebih jauh dari sel semasa.

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.

Tentang Algoritma Hunt and Kill

Algoritma Hunt and Kill adalah kaedah yang mudah tetapi berkesan untuk menghasilkan labirin. Ia agak serupa dengan pencarian pertama kedalaman (iaitu algoritma Recursive Backtracker), kecuali apabila ia tidak dapat bergerak lebih jauh dari kedudukan semasa, ia secara sistematik mengimbas (atau "memburu") melalui labirin untuk mencari sel baru untuk diteruskan. Algoritma ini terdiri daripada dua fasa utama: berjalan dan memburu.

Bagaimana Algoritma Hunt and Kill Berfungsi untuk Penjanaan Labirin

Langkah 1: Mula di sel rawak

• Cari sel rawak dalam grid dan tandakan ia sebagai telah dilawati.

Langkah 2: Fasa Berjalan (Perjalanan Rawak)

• Pilih jiran yang tidak dilawati secara rawak.
• Bergerak ke jiran tersebut, tandakan ia sebagai telah dilawati, dan ukir jalan antara sel sebelumnya dan sel baru.
• Ulangi sehingga tiada jiran yang belum dilawati yang tinggal.

Langkah 3: Fasa Memburu (Mundur melalui Pengimbasan)

• Imbas grid baris demi baris (atau lajur demi lajur).
• Cari sel yang belum dilawati yang mempunyai sekurang-kurangnya satu jiran yang telah dilawati.
• Sambungkan sel tersebut ke jiran yang telah dilawati untuk menyambung semula fasa berjalan.
• Ulangi sehingga semua sel telah dilawati.