Rekursiivne Backtracker labürindi generaator

Rekursiivne backtracker algoritm on tõesti üldotstarbeline sügavus-esimene otsing. Kui seda kasutatakse labürindi genereerimiseks, muudeti seda veidi, et valida tee juhuslikult, samas kui tegelikuks otsinguks kasutati, otsitakse tavaliselt igal tasandil lineaarses järjekorras. See kipub tekitama pikkade käänuliste koridoride ja väga pikkade keerdlahendustega labürinti.

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älituse algoritm on sügavus-esimene otsingumeetod täiuslike labürindite (ilma silmusteta labürindid ja ühe tee kahe punkti vahel) loomiseks. See on lihtne, tõhus ja loob visuaalselt atraktiivsed pikkade käänuliste koridoridega labürindid.

Vaatamata oma nimele ei pea seda tingimata rakendama rekursiooni abil. Seda rakendatakse sageli iteratiivse lähenemisega, kasutades LIFO järjekorda (st pinu). Väga suurte labürindi puhul põhjustab rekursiooni kasutamine suurema tõenäosusega kõnepinu ületäitumist, olenevalt programmeerimiskeelest ja vabast mälust. LIFO järjekorda saab hõlpsamini kohandada suurte andmemahtude käitlemiseks, isegi järjekorra hoidmiseks kettal või andmebaasis, kui saadaolevast mälust ei piisa.

Kuidas see töötab

Algoritm töötab virnapõhise sügavus-eesotsingu lähenemisviisi abil. Siin on samm-sammuline jaotus:

1. Valige alguslahter ja märkige see külastatuks.
2. Kuigi on külastamata lahtreid:
   • Vaadake naaberrakke, mida pole veel külastatud.
   • Kui on olemas vähemalt üks külastamata naaber:
     • Valige juhuslikult üks külastamata naabritest.
     • Eemaldage sein praeguse lahtri ja valitud naabri vahel.
     • Liikuge valitud naabri juurde ja märkige see külastatuks.
     • Lükake praegune lahter virnale.
   • Kui külastamata naabreid pole:
     • Tagasi liikumiseks hüppab virna viimane lahter.
3. Jätkake seda protsessi, kuni virn on tühi.

Huvitav fakt selle algoritmi kohta on see, et see töötab nii labürindi generaatorina kui ka labürindi lahendajana. Kui käivitate selle juba loodud labürindis ja peatute otsustatud lõpp-punkti jõudmisel, sisaldab virn labürindi lahendust.

Mul on sellel saidil tegelikult mängus kaks versiooni sellest algoritmist: LIFO järjekord, mis põhineb sellel lehel labürindite genereerimiseks ja rekursioonipõhine labürindite lahendamiseks, samuti muude algoritmide poolt genereeritud labürindid (nii tehakse lahendustega kaardid). Kaks erinevat versiooni on mõeldud ainult sportimiseks, sest ma olen nohik, kellele see tundub huvitav, kumbki oleks võinud mõlema jaoks sobida ;-)