Penjana Maze Algoritma Wilson
Diterbitkan: 19 Mac 2025 pada 8:34:29 PTG UTC
Penjana maze menggunakan algoritma Wilson untuk mencipta maze yang sempurna. Algoritma ini menjana semua maze yang mungkin bagi saiz tertentu dengan kebarangkalian yang sama, jadi ia boleh secara teori menjana mazes bagi banyak susun atur bercampur, tetapi kerana terdapat lebih banyak maze yang mungkin dengan koridor yang lebih pendek daripada yang lebih panjang, anda akan lebih kerap melihatnya.Wilson's Algorithm Maze Generator
Algoritma Wilson ialah kaedah berjalan rawak padam gelung yang menjana pokok merentang seragam untuk penciptaan labirin. Ini bermakna semua labirin yang mungkin pada saiz tertentu berkemungkinan sama dijana, menjadikannya teknik penjanaan labirin yang tidak berat sebelah. Algoritma Wilson boleh dianggap sebagai versi algoritma Aldous-Broder yang dipertingkatkan, kerana ia menghasilkan labirin dengan ciri-ciri yang sama, tetapi ia berjalan lebih pantas, jadi saya tidak peduli untuk melaksanakan algoritma Aldous-Broder di sini.
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.
Mengenai Algoritma Wilson
Algoritma Wilson untuk menghasilkan pokok penutupan seragam menggunakan dinding rawak yang dipadamkan gelung telah dicipta oleh David Bruce Wilson.
Wilson pada asalnya memperkenalkan algoritma ini pada tahun 1996 semasa mengkaji pokok penutupan rawak dan rantai Markov dalam teori kebarangkalian. Walaupun kerjanya pada asalnya dalam bidang matematik dan fizik statistik, algoritma ini sejak itu telah diterima secara meluas untuk penjanaan labirin kerana keb kemampuannya untuk menghasilkan labirin yang seragam dengan sempurna.
Bagaimana Algoritma Wilson Berfungsi untuk Penjanaan Labirin
Algoritma Wilson memastikan bahawa labirin akhir adalah sepenuhnya bersambung tanpa sebarang gelung dengan memahat laluan dari sel yang belum dilawati menggunakan lintasan rawak secara berulang.
Langkah 1: Memulakan
- Mulakan dengan grid yang dipenuhi dengan dinding.
- Definisikan senarai semua sel laluan yang mungkin.
Langkah 2: Pilih Sel Permulaan Rawak
- Pilih mana-mana sel rawak dan tandakan ia sebagai dilawati. Ini berfungsi sebagai titik permulaan labirin semasa penjanaan.
Langkah 3: Lintasan Rawak dengan Pemadaman Gelung
- Pilih sel yang belum dilawati dan mulakan lintasan rawak (bergerak ke arah rawak).
- Jika lintasan mencapai sel yang sudah dilawati, padamkan sebarang gelung dalam laluan.
- Apabila lintasan bersambung dengan kawasan yang dilawati, tandakan semua sel dalam laluan tersebut sebagai dilawati.
Langkah 4: Ulangi Sehingga Semua Sel Dilawati:
- Teruskan memilih sel yang belum dilawati dan melakukan lintasan rawak sehingga setiap sel menjadi sebahagian daripada labirin.