Generator Labirin Algoritma Wilson
Diterbitkan: 16 Februari 2025 pukul 19.31.57 UTC
Pembuat labirin menggunakan algoritma Wilson untuk membuat labirin yang sempurna. Algoritma ini menghasilkan semua labirin yang mungkin dengan ukuran tertentu dengan probabilitas yang sama, sehingga secara teori dapat menghasilkan labirin dengan banyak tata letak campuran, tetapi karena ada lebih banyak labirin yang mungkin dengan koridor yang lebih pendek daripada yang lebih panjang, Anda akan lebih sering melihatnya.Wilson's Algorithm Maze Generator
Algoritma Wilson adalah metode jalan acak yang dihapus loop yang menghasilkan pohon rentang seragam untuk pembuatan labirin. Ini berarti bahwa semua labirin yang mungkin dengan ukuran tertentu memiliki kemungkinan yang sama untuk dihasilkan, sehingga menjadikannya teknik pembuatan labirin yang tidak bias. Algoritma Wilson dapat dianggap sebagai versi perbaikan dari algoritma Aldous-Broder, karena menghasilkan labirin dengan karakteristik yang identik, tetapi berjalan jauh lebih cepat, jadi saya tidak repot-repot menerapkan algoritma Aldous-Broder di sini.
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.
Tentang Algoritma Wilson
Algoritma Wilson untuk menghasilkan pohon rentang seragam menggunakan dinding acak yang dihapus loop diciptakan oleh David Bruce Wilson.
Wilson awalnya memperkenalkan algoritma ini pada tahun 1996 saat meneliti pohon rentang acak dan rantai Markov dalam teori probabilitas. Meskipun karyanya terutama dalam matematika dan fisika statistik, algoritma ini telah diadopsi secara luas untuk pembuatan labirin karena kemampuannya menghasilkan labirin yang sangat seragam.
Cara Kerja Algoritma Wilson untuk Pembuatan Labirin
Algoritma Wilson memastikan bahwa labirin akhir terhubung sepenuhnya tanpa putaran apa pun dengan mengukir jalur secara berulang dari sel yang belum dikunjungi menggunakan jalan acak.
Langkah 1: Inisialisasi
- Mulailah dengan kotak yang penuh dengan dinding.
- Tentukan daftar semua sel lintasan yang memungkinkan.
Langkah 2: Pilih Sel Awal Acak
- Pilih sel acak dan tandai sebagai sel yang telah dikunjungi. Ini berfungsi sebagai titik awal labirin selama pembuatan.
Langkah 3: Jalan Acak dengan Penghapusan Loop
- Pilih sel yang belum dikunjungi dan mulailah berjalan secara acak (bergerak ke arah acak).
- Jika perjalanan mencapai sel yang sudah dikunjungi, hapus semua putaran pada jalur tersebut.
- Setelah perjalanan terhubung ke wilayah yang dikunjungi, tandai semua sel di jalur tersebut sebagai telah dikunjungi.
Langkah 4: Ulangi Sampai Semua Sel Dikunjungi :
- Lanjutkan memilih sel yang belum dikunjungi dan lakukan penelusuran acak hingga setiap sel menjadi bagian labirin.