Miklix

Rekursiv Backtracker Maze Generator

Publisert: 16. februar 2025 kl. 18:16:18 UTC

Labyrintgenerator som bruker den rekursive backtracker-algoritmen for å lage en perfekt labyrint. Denne algoritmen har en tendens til å skape labyrinter med lange, svingete korridorer og en veldig lang, kronglete løsning.

Denne siden er maskinoversatt fra engelsk for å gjøre den tilgjengelig for så mange som mulig. Dessverre er maskinoversettelse ennå ikke en fullkommen teknologi, så det kan forekomme feil. Hvis du foretrekker det, kan du se den engelske originalversjonen her:

Recursive 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.


Generer ny labyrint








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 ;-)

Del på BlueskyDel på FacebookDel på LinkedInDel på TumblrDel på XDel på LinkedInFest på Pinterest

Mikkel Bang Christensen

Om forfatteren

Mikkel Bang Christensen
Mikkel er skaperen og eieren av miklix.com. Han har over 20 års erfaring som profesjonell dataprogrammerer/programvareutvikler og er for tiden ansatt på fulltid i et stort europeisk IT-selskap. Når han ikke blogger, bruker han fritiden sin på en lang rekke interesser, hobbyer og aktiviteter, noe som til en viss grad kan gjenspeiles i de mange ulike temaene som dekkes på dette nettstedet.