Miklix

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.

Halaman ini telah diterjemahkan mesin daripada bahasa Inggeris untuk menjadikannya boleh diakses oleh seramai mungkin orang. Malangnya, terjemahan mesin belum lagi merupakan teknologi yang sempurna, jadi ralat boleh berlaku. Jika anda mahu, anda boleh melihat versi bahasa Inggeris asal di sini:

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.


Hasilkan labirin baharu








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.
Kongsi di BlueskyKongsi di FacebookKongsi di LinkedInKongsi di TumblrKongsi di XKongsi di LinkedInSematkan pada Pinterest

Mikkel Christensen

Mengenai Pengarang

Mikkel Christensen
Mikkel ialah pencipta dan pemilik miklix.com. Beliau mempunyai lebih 20 tahun pengalaman sebagai pengaturcara komputer/pembangun perisian profesional dan kini bekerja sepenuh masa untuk sebuah syarikat IT Eropah yang besar. Apabila tidak menulis blog, dia menghabiskan masa lapangnya dengan pelbagai minat, hobi dan aktiviti, yang mungkin sedikit sebanyak dapat dilihat dalam pelbagai topik yang diliputi di laman web ini.