Algoritma Maze generator Wilson urang
Diterbitkeun: 16 Pébruari 2025 jam 19.38.09 UTC
Maze generator ngagunakeun algoritma Wilson pikeun nyieun Maze sampurna. Algoritma ieu dibangkitkeun sagala mazes mungkin tina ukuran tinangtu jeung probabiliti sarua, ku kituna dina téori bisa ngahasilkeun mazes loba layouts dicampur, Tapi sakumaha aya leuwih mungkin mazes kalawan koridor pondok ti panjang, anjeun bakal leuwih mindeng ningali eta.Wilson's Algorithm Maze Generator
Algoritma Wilson mangrupikeun metodeu leumpang acak anu dipupus ku loop anu ngahasilkeun tangkal anu manjang seragam pikeun nyiptakeun maze. Ieu ngandung harti yén sakabéh mazes mungkin tina ukuran tinangtu sarua kamungkinan dihasilkeun, sahingga téhnik generasi maze unbiased. Algoritma Wilson bisa dianggap versi ningkat tina algoritma Aldous-Broder, sabab dibangkitkeun mazes kalawan ciri idéntik, tapi ngajalankeun leuwih gancang, jadi kuring geus teu ganggu nerapkeun algoritma Aldous-Broder dieu.
Maze sampurna nyaéta Maze dimana aya persis hiji jalur ti titik mana waé dina Maze ka titik séjén. Éta hartina anjeun moal bisa mungkas nepi ka sabudeureun dina bunderan, tapi anjeun bakal mindeng sapatemon dead ends, forcing anjeun ngahurungkeun sabudeureun tur balik.
Peta Maze anu dihasilkeun di dieu kalebet versi standar tanpa posisi awal sareng akhir, ku kituna anjeun tiasa mutuskeun pikeun diri anjeun: bakal aya solusi ti mana waé dina maze ka titik anu sanés. Upami anjeun hoyong inspirasi, anjeun tiasa ngaktipkeun posisi mimiti sareng bérés anu disarankeun - komo ningali solusi antara dua.
Ngeunaan Algoritma Wilson
Algoritma Wilson pikeun ngahasilkeun tangkal manjang seragam ngagunakeun témbok acak loop-erased dijieun ku David Bruce Wilson.
Wilson mimitina ngenalkeun algoritma ieu dina taun 1996 nalika nalungtik tatangkalan acak sareng ranté Markov dina téori probabiliti. Sanajan karyana utamana dina matématika jeung fisika statistik, algoritme ieu geus loba diadopsi pikeun generasi maze alatan kamampuhna pikeun ngahasilkeun mazes seragam sampurna.
Kumaha Algoritma Wilson Gawé pikeun Generasi Maze
Algoritma Wilson ngajamin yén maze ahir disambungkeun sapinuhna tanpa puteran ku cara ngukir jalur tina sél anu teu didatangan ku jalan acak.
Lengkah 1: Initialize
- Mimitian ku grid ngeusi tembok.
- Nangtukeun daptar sadaya sél petikan mungkin.
Lengkah 2: Pilih Sél Mimiti Acak
- Pilih sél acak naon waé sareng tandai salaku dilongok. Ieu boga fungsi minangka titik awal Maze salila generasi.
Lengkah 3: Acak Walk sareng Loop-Erasing
- Pilih sél anu teu didatangan sareng mimitian jalan-jalan acak (pindah dina arah anu acak).
- Lamun leumpang nepi ka sél geus dilongok, hapus sagala loop dina jalur.
- Sakali walk nyambung ka wewengkon dilongok, cirian sakabéh sél dina jalur sakumaha dilongok.
Lengkah 4: Ulang dugi Sadaya Sél Didatangan :
- Nuluykeun milih sél unvisited tur ngajalankeun acak walks dugi unggal sél mangrupa bagian tina Maze nu.