Generator Labirin Algoritma Wilson

Algoritma Wilson adalah metode penelusuran acak penghapusan 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, menjadikannya teknik pembuatan labirin yang tidak bias. Algoritma Wilson dapat dianggap sebagai versi yang lebih baik dari algoritma Aldous-Broder, karena menghasilkan labirin dengan karakteristik yang identik, tetapi berjalan jauh lebih cepat, jadi saya tidak perlu mengimplementasikan 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 dihilangkan loop-nya diciptakan oleh David Bruce Wilson.

Wilson pertama kali memperkenalkan algoritma ini pada tahun 1996 saat meneliti pohon rentang acak dan rantai Markov dalam teori probabilitas. Meskipun karyanya terutama di bidang matematika dan fisika statistik, algoritma ini sejak itu diadopsi secara luas untuk pembuatan labirin karena kemampuannya untuk menghasilkan labirin yang seragam sempurna.

Bagaimana Algoritma Wilson Bekerja untuk Pembuatan Labirin

Algoritma Wilson memastikan bahwa labirin akhir terhubung sepenuhnya tanpa adanya lingkaran dengan cara mengukir jalur secara iteratif dari sel-sel yang belum dikunjungi menggunakan penelusuran acak.

Langkah 1: Inisialisasi

• Mulailah dengan kisi-kisi yang diisi dengan dinding.
• Tentukan daftar semua sel lintasan yang mungkin.

Langkah 2: Pilih Sel Awal Secara Acak

• Pilih sel secara acak dan tandai sebagai telah dikunjungi. Ini berfungsi sebagai titik awal labirin selama proses pembuatan.

Langkah 3: Penelusuran Acak dengan Penghapusan Loop

• Pilih sel yang belum dikunjungi dan mulailah penelusuran acak (bergerak ke arah acak).
• Jika jalur tersebut mencapai sel yang sudah dikunjungi, hapus semua perulangan dalam jalur tersebut.
• Setelah jalur tersebut terhubung ke wilayah yang dikunjungi, tandai semua sel di jalur tersebut sebagai sel yang telah dikunjungi.

Langkah 4: Ulangi Hingga Semua Sel Dikunjungi:

• Lanjutkan memilih sel yang belum dikunjungi dan melakukan penelusuran acak hingga setiap sel menjadi bagian dari labirin.

Bacaan Lebih Lanjut

Jika Anda menikmati postingan ini, Anda mungkin juga menyukai saran berikut:

• Generator Labirin Algoritma Pohon Tumbuh
• Generator Labirin Algoritma Eller
• Generator Labirin Perburuan dan Bunuh