Rekursif Backtracker Maze generator

Algoritma backtracker recursive saleresna mangrupikeun milarian jero-heula umum. Nalika dianggo pikeun ngahasilkeun maze, éta rada dirobih pikeun milih jalur sacara acak, sedengkeun upami dianggo pikeun tujuan pamilarian anu saleresna, biasana ngan ukur milarian unggal tingkat dina urutan linier. Ieu condong ngahasilkeun mazes kalawan panjang, koridor pungkal sarta pohara panjang, solusi twisting.

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 recursive mangrupikeun metode pamilarian anu paling jero pikeun ngahasilkeun mazes anu sampurna (mazes tanpa loop sareng jalur tunggal antara dua titik). Éta basajan, éfisién, sareng ngahasilkeun labirin anu pikaresepeun kalayan koridor anu panjang sareng berliku.

Sanajan ngaranna, teu merta kudu dilaksanakeun maké recursion. Hal ieu mindeng dilaksanakeun dina pendekatan iterative ngagunakeun antrian LIFO (ie tumpukan). Pikeun mazes anu kacida gedéna, ngagunakeun recursion leuwih gampang ngakibatkeun panggero tumpukan mudal, gumantung kana basa programming sarta memori sadia. Antrian LIFO bisa leuwih gampang diadaptasi pikeun nanganan jumlah badag data, malah tetep antrian dina disk atawa dina database lamun aya memori teu cukup.

Kumaha Gawéna

Algoritma ngoperasikeun ngagunakeun pendekatan pilarian jero-heula dumasar-tumpukan. Ieu léngkah-léngkah ngarecahna:

1. Pilih sél awal sareng cirian salaku dilongok.
2. Bari aya sél unvisited:
   • Neuteup sél tatangga nu can dilongok.
   • Upami sahenteuna aya tatangga anu teu didatangan:
     • Pilih sacara acak salah sahiji tatangga anu teu didatangan.
     • Cabut témbok antara sél ayeuna sareng tatangga anu dipilih.
     • Pindah ka tatangga anu dipilih sareng cirian salaku dilongok.
     • Nyorong sél ayeuna kana tumpukan.
   • Upami teu aya tatangga anu teu didatangan:
     • Backtrack ku popping sél panungtungan ti tumpukan.
3. Nuluykeun prosés ieu nepi ka tumpukan kosong.

Kanyataan anu pikaresepeun ngeunaan algoritma ieu nyaéta tiasa dianggo salaku generator Maze sareng salaku solver Maze. Lamun ngajalankeun eta dina Maze geus dihasilkeun sarta ngan eureun mun anjeun pencét titik tungtung mutuskeun, tumpukan bakal ngandung solusi pikeun Maze nu.

Sabenerna mah boga dua vérsi algoritma ieu dimaénkeun dina situs ieu: antrian LIFO dumasar hiji pikeun ngahasilkeun mazes dina kaca ieu sarta recursion dumasar hiji pikeun mazes ngarengsekeun, ogé mazes dihasilkeun ku algoritma séjén (éta kumaha peta jeung solusi dijieun). Ngabogaan dua vérsi anu béda ngan pikeun olahraga sabab kuring kutu buku anu mendakan éta pikaresepeun, boh tiasa dianggo pikeun duanana ;-)