Algoritma Maze generator Wilson urang

Algoritma Wilson nyaéta metode random walk anu dihapus ku loop anu ngahasilkeun tangkal rentang anu seragam pikeun nyiptakeun labirin. Ieu ngandung harti yén sadaya labirin anu mungkin tina ukuran anu ditangtukeun sami kamungkinanana dihasilkeun, jantenkeun éta téknik generasi labirin anu teu bias. Algoritma Wilson tiasa dianggap vérsi anu ditingkatkeun tina algoritma Aldous-Broder, sabab ngahasilkeun labirin kalayan karakteristik anu sami, tapi jalanna langkung gancang, janten kuring henteu repot-repot nerapkeun algoritma Aldous-Broder di 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 anu membentang seragam nganggo témbok acak anu dihapus ku loop diciptakeun ku David Bruce Wilson.

Wilson mimitina ngenalkeun algoritma ieu dina taun 1996 nalika nalungtik tangkal rentang acak sareng ranté Markov dina téori probabilitas. Sanaos karyana utamina dina matematika sareng fisika statistik, algoritma ieu parantos seueur diadopsi pikeun generasi labirin kusabab kamampuanna pikeun ngahasilkeun labirin anu seragam sampurna.

Kumaha Algoritma Wilson Gawéna pikeun Generasi Labirin

Algoritma Wilson mastikeun yén labirin ahir nyambung sapinuhna tanpa aya puteran ku cara ngukir jalur sacara iteratif tina sél anu teu acan didatangan nganggo jalan acak.

Léngkah 1: Inisialisasi

• Mimitian ku grid anu dieusi ku témbok.
• Tangtukeun daptar sadaya sél petikan anu mungkin.

Léngkah 2: Pilih Sél Mimitian Acak

• Pilih sél acak mana waé teras tandai salaku anu parantos dilongok. Ieu janten titik awal labirin salami generasi.

Léngkah 3: Leumpang Acak nganggo Panghapusan Putaran

• Pilih sél anu teu acan didatangan teras mimitian leumpang sacara acak (ngaléngkah ka arah anu acak).
• Upami leumpangna dugi ka sél anu parantos didatangan, hapus sadaya puteran dina jalur éta.
• Sakali jalan-jalan nyambung ka daérah anu parantos dikunjungi, tandai sadaya sél dina jalur éta salaku anu parantos dikunjungi.

Léngkah 4: Balikan deui dugi ka sadaya sél parantos didatangan:

• Teraskeun milih sél anu teu acan didatangan sareng ngalakukeun leumpang acak dugi ka unggal sél janten bagian tina labirin.

Bacaan salajengna

Upami anjeun resep kana tulisan ieu, anjeun ogé tiasa resep saran ieu:

• Kruskal urang Algoritma Maze generator
• Hunt jeung maéhan Maze generator
• Tumuwuh Tangkal Algoritma Maze Generator