Rekursiv Backtracker Maze Generator

Den rekursive backtracker-algoritmen er egentlig et generelt dybde-først-søk. Når den ble brukt til labyrintgenerering, ble den litt modifisert for å velge banen tilfeldig, mens hvis den ble brukt til faktiske søkeformål, ville 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, vridd 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 vilkårlige punkter). Det er enkelt, effektivt og produserer visuelt tiltalende labyrinter med lange, svingete korridorer.

Til tross for navnet, trenger det ikke nødvendigvis å bli implementert ved hjelp av rekursjon. Det implementeres ofte i en iterativ tilnærming ved hjelp av en LIFO-kø (dvs. en stabel). For svært store labyrinter er det mer sannsynlig at bruk av rekursjon resulterer i overflyt 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 ikke er tilstrekkelig.

Slik fungerer det

Algoritmen opererer ved hjelp av en stabelbasert dybde-først-søketilnærming. Her er trinn-for-trinn-oversikten:

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 gjeldende celle og den valgte naboen.
     • Gå til den valgte naboen og merk den som besøkt.
     • Skyv gjeldende celle på stabelen.
   • Hvis det ikke finnes noen ubesøkte naboer:
     • Gå tilbake ved å poppe 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 sluttpunktet, vil stabelen inneholde løsningen på labyrinten.

Jeg har faktisk to versjoner av denne algoritmen i spill på dette nettstedet: en LIFO-købasert 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, begge kunne ha fungert for begge ;-)

Videre lesing

Hvis du likte dette innlegget, kan du også like disse forslagene:

• Wilsons algoritme labyrintgenerator
• Jakt og Drep Labyrint Generator
• Growing Tree algoritme labyrintgenerator