Rekursiv Backtracker Maze Generator

Den rekursive backtracker-algoritmen er egentlig et generell dybdesøk. Når den brukes til labyrintgenerering, er den litt modifisert for å velge banen tilfeldig, mens hvis den brukes til faktiske søkeformål, vil man vanligvis bare søke på hvert nivå i lineær rekkefølge. Den har en tendens til å produsere labyrinter med lange, svingete korridorer og en veldig lang, kronglete løsning.

En perfekt labyrint er en labyrint der det finnes nøyaktig én vei fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Det betyr at du ikke kan ende opp med å gå i sirkler, men at du ofte vil støte på blindveier som tvinger deg til å snu og gå tilbake.

Labyrintkartene som genereres her, inneholder en standardversjon uten start- og målposisjoner, slik at du selv kan bestemme disse: Det vil finnes en løsning fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Hvis du vil ha inspirasjon, kan du aktivere en foreslått start- og målposisjon - og til og med se løsningen mellom de to.

Den rekursive backtracker-algoritmen er en dybde-først søkemetode for å generere perfekte labyrinter (labyrinter uten løkker og en enkelt bane mellom to punkter). Den er enkel, effektiv og produserer visuelt tiltalende labyrinter med lange, svingete korridorer.

Til tross for navnet, trenger det ikke nødvendigvis å være implementert ved bruk av rekursjon. Det implementeres ofte i en iterativ tilnærming ved å bruke en LIFO-kø (dvs. en stack). For svært store labyrinter er det mer sannsynlig at bruk av rekursjon vil føre til overløp av anropsstabel, avhengig av programmeringsspråk og tilgjengelig minne. En LIFO-kø kan lettere tilpasses til å håndtere store datamengder, til og med å holde køen på disk eller i en database hvis tilgjengelig minne er utilstrekkelig.

Hvordan det fungerer

Algoritmen opererer ved å bruke en stabelbasert dybde-først-søk-tilnærming. Her er en trinnvis oversikt:

1. Velg en startcelle og merk den som besøkt.
2. Mens det er ubesøkte celler:
   • Se på nabocellene som ennå ikke er besøkt.
   • Hvis det finnes minst én ubesøkt nabo:
     • Velg tilfeldig en av de ubesøkte naboene.
     • Fjern veggen mellom den nåværende cellen og den valgte naboen.
     • Flytt til den valgte naboen og merk den som besøkt.
     • Skyv gjeldende celle på stabelen.
   • Hvis det ikke finnes ubesøkte naboer:
     • Gå tilbake ved å sprette den siste cellen fra stabelen.
3. Fortsett denne prosessen til stabelen er tom.

Et interessant faktum om denne algoritmen er at den fungerer både som en labyrintgenerator og som en labyrintløser. Hvis du kjører den på en allerede generert labyrint og bare stopper når du treffer det bestemte endepunktet, vil stabelen inneholde løsningen på labyrinten.

Jeg har faktisk to versjoner av denne algoritmen i spill på denne siden: en LIFO-købasert en for å generere labyrinter på denne siden og en rekursjonsbasert for å løse labyrinter, også labyrinter generert av andre algoritmer (det er slik kartene med løsningene er laget). Å ha to forskjellige versjoner er bare for sport fordi jeg er en nerd som synes det er interessant, enten kunne ha fungert for begge ;-)