Rekursif Backtracker Maze generator

Algoritma backtracker rekursif sabenerna mangrupikeun pamilarian anu mimitina jero pikeun tujuan umum. Nalika dianggo pikeun ngahasilkeun labirin, éta rada dirobih pikeun milih jalur sacara acak, sedengkeun upami dianggo pikeun tujuan pamilarian anu saleresna, urang biasana ngan ukur milarian unggal tingkat dina urutan linier. Éta condong ngahasilkeun labirin kalayan koridor anu panjang sareng ngagulung sareng solusi anu panjang pisan sareng ngagulung.

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.

Algoritma backtracker rekursif nyaéta metode panéangan jero-heula pikeun ngahasilkeun labirin anu sampurna (labirin tanpa puteran sareng hiji jalur antara dua titik). Éta saderhana, efisien, sareng ngahasilkeun labirin anu pikaresepeun sacara visual kalayan koridor anu panjang sareng ngagulung.

Sanajan ngaranna kitu, éta teu kudu diimplementasikeun maké rékursi. Ieu sering diimplementasikeun dina pendekatan iteratif maké antrian LIFO (contona tumpukan). Pikeun labirin anu ageung pisan, maké rékursi leuwih gampang nyababkeun limpahan tumpukan panggero, gumantung kana basa pamrograman sareng mémori anu sayogi. Antrian LIFO bisa leuwih gampang diadaptasi pikeun nanganan data anu ageung, sanajan tetep nyimpen antrian dina disk atawa dina database lamun mémori anu sayogi teu cukup.

Kumaha Cara Gawéna

Algoritma ieu beroperasi nganggo pendekatan panéangan jero-heula dumasar kana tumpukan. Ieu rincian léngkah-léngkahna:

1. Pilih sél awal teras tandai salaku anu parantos didatangan.
2. Salami aya sél anu teu acan didatangan: Tingali sél tatangga anu tacan didatangan. Upami sahenteuna aya hiji tatangga anu teu acan didatangan: Pilih sacara acak salah sahiji tatangga anu teu acan didatangan. Cabut témbok antara sél ayeuna sareng tatangga anu dipilih. Pindah ka tatangga anu dipilih teras tandai salaku anu parantos didatangan. Dorong sél ayeuna kana tumpukan. Upami teu aya tatangga anu teu acan didatangan: Mundur ku cara ngaluarkeun sél terakhir tina tumpukan.
3. Teraskeun prosés ieu dugi ka tumpukan kosong.

Hiji kanyataan anu pikaresepeun ngeunaan algoritma ieu nyaéta éta tiasa dianggo salaku generator labirin sareng salaku pemecah labirin. Upami anjeun ngajalankeunana dina labirin anu parantos dihasilkeun sareng eureun nalika anjeun ngahontal titik ahir anu ditangtukeun, tumpukan éta bakal ngandung solusi pikeun labirin éta.

Kuring sabenerna gaduh dua vérsi algoritma ieu anu dianggo di situs ieu: anu dumasar kana antrian LIFO pikeun ngahasilkeun labirin dina halaman ieu sareng anu dumasar kana rekursi pikeun ngarengsekeun labirin, ogé labirin anu dihasilkeun ku algoritma sanés (kitu kumaha peta sareng solusina dijieun). Ngagaduhan dua vérsi anu béda ngan ukur pikeun olahraga sabab kuring kutu buku anu mendakan éta pikaresepeun, boh tiasa dianggo pikeun duanana ;-)

Bacaan salajengna

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

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