Rekursiivne Backtracker labürindi generaator

Rekursiivne tagasijälgija algoritm on tegelikult üldotstarbeline sügavusotsing. Labürindi genereerimiseks kasutatakse seda veidi modifitseeritult, et valida tee juhuslikult, samas kui tegeliku otsingu eesmärgil otsitakse tavaliselt igal tasandil lineaarses järjekorras. See kipub looma labürinte pikkade, looklevate koridoride ja väga pika, keerduva lahendusega.

Täiuslik labürint on labürint, kus on täpselt üks tee labürindi mis tahes punktist mis tahes teise punkti. See tähendab, et te ei saa sattuda ringiratastesse, kuid sageli satute ummikteedesse, mis sunnib teid ümber pöörama ja tagasi minema.

Siin genereeritud labürindi kaardid sisaldavad vaikimisi versiooni ilma algus- ja lõpp-punktideta, nii et saate need ise otsustada: labürindi mis tahes punktist mis tahes teise punkti on olemas lahendus. Kui soovite inspiratsiooni, saate lubada soovitatud algus- ja lõpupositsiooni - ja isegi näha lahendust nende kahe vahel.

Rekursiivne tagasijälgija algoritm on sügavuspõhine otsingumeetod täiuslike labürintide (labürindid ilma silmusteta ja kahe punkti vahel on ainult üks tee) genereerimiseks. See on lihtne, tõhus ja loob visuaalselt atraktiivseid labürinte pikkade ja looklevate koridoridega.

Vaatamata nimele ei pea seda tingimata rekursiooni abil rakendama. Sageli rakendatakse seda iteratiivsel lähenemisviisil, kasutades LIFO järjekorda (st pinu). Väga suurte labürintide puhul on rekursiooni kasutamine tõenäolisemalt tingitud väljakutsete pinu ületäitumisest, olenevalt programmeerimiskeelest ja saadaolevast mälust. LIFO järjekorda saab hõlpsamini kohandada suurte andmemahtude käsitlemiseks, hoides järjekorda isegi kettal või andmebaasis, kui saadaolevast mälust ei piisa.

Kuidas see toimib

Algoritm töötab pinupõhise sügavusotsingu meetodil. Siin on samm-sammult juhend:

1. Valige alguslahter ja märkige see külastatuks.
2. Kuni külastamata lahtreid on: vaadake naaberlahtreid, mida pole veel külastatud. Kui on olemas vähemalt üks külastamata naaber: valige juhuslikult üks külastamata naabritest. Eemaldage sein praeguse ja valitud lahtri vahelt. Liikuge valitud naabri juurde ja märkige see külastatuks. Lükake praegune lahter pinu peale. Kui külastamata naabreid pole: liikuge tagasi, eemaldades viimase lahtri pinust.
3. Jätkake seda protsessi, kuni virn on tühi.

Selle algoritmi huvitav fakt on see, et see töötab nii labürindi generaatorina kui ka labürindi lahendajana. Kui käivitada see juba loodud labürindil ja peatada lihtsalt kindlaksmääratud lõpp-punktini jõudes, sisaldab pinu labürindi lahendust.

Mul on sellel saidil tegelikult kaks selle algoritmi versiooni: LIFO-järjekorral põhinev labürintide genereerimiseks sellel lehel ja rekursioonil põhinev labürintide lahendamiseks, samuti teiste algoritmide loodud labürintide lahendamiseks (nii tehakse lahendustega kaardid). Kahe erineva versiooni omamine on ainult spordi jaoks, sest ma olen nohik, kellele see huvitav tundub, kumbki neist oleks võinud mõlema jaoks sobida ;-)

Lisalugemist

Kui see postitus teile meeldis, võivad teile meeldida ka need soovitused:

• Kasvava puu algoritmi labürindigeneraator
• Kruskali algoritmi labürindi generaator
• Jahti ja Tappa Labürindi Loodur