Rekursiv Backtracker Maze Generator

Den rekursive backtracker-algoritme er i virkeligheden en generel dybdesøgning. Når den bruges til labyrintgenerering, modificeres den en smule for at vælge stien tilfældigt, hvorimod man typisk ville søge på hvert niveau i lineær rækkefølge, hvis den bruges til egentlige søgeformål. Den har en tendens til at producere labyrinter med lange, snoede korridorer og en meget lang, snoet løsning.

En perfekt labyrint er en labyrint, hvor der er præcis én vej fra et hvilket som helst punkt i labyrinten til et hvilket som helst andet punkt. Det betyder, at du ikke kan ende med at gå rundt i cirkler, men du vil ofte støde på blindgyder, som tvinger dig til at vende om og gå tilbage.

De labyrintkort, der genereres her, indeholder en standardversion uden start- og slutpositioner, så du selv kan bestemme dem: der vil være en løsning fra ethvert punkt i labyrinten til ethvert andet punkt. Hvis du vil have inspiration, kan du aktivere en foreslået start- og slutposition - og endda se løsningen mellem de to.

Den rekursive backtracker-algoritme er en dybdebaseret søgemetode til at generere perfekte labyrinter (labyrinter uden løkker og med en enkelt sti mellem to punkter). Den er enkel, effektiv og producerer visuelt tiltalende labyrinter med lange, snoede korridorer.

Trods navnet behøver den ikke nødvendigvis at blive implementeret ved hjælp af rekursion. Den implementeres ofte i en iterativ tilgang ved hjælp af en LIFO-kø (dvs. en stak). For meget store labyrinter er det mere sandsynligt, at brugen af rekursion resulterer i stackoverflow, afhængigt af programmeringssprog og tilgængelig hukommelse. En LIFO-kø kan lettere tilpasses til at håndtere store mængder data, endda ved at holde køen på disk eller i en database, hvis den tilgængelige hukommelse ikke er tilstrækkelig.

Sådan fungerer det

Algoritmen fungerer ved hjælp af en stakbaseret dybde-først søgemetode. Her er den trinvise opdeling:

1. Vælg en startcelle og marker den som besøgt.
2. Mens der er ubesøgte celler: Se på de nærliggende celler, der endnu ikke er blevet besøgt. Hvis der findes mindst én ubesøgt nabo: Vælg tilfældigt en af de ubesøgte naboer. Fjern væggen mellem den aktuelle celle og den valgte nabo. Flyt til den valgte nabo og marker den som besøgt. Skub den aktuelle celle ind på stakken. Hvis der ikke findes nogen ubesøgte naboer: Gå tilbage ved at poppe den sidste celle ud af stakken.
3. Fortsæt denne proces, indtil stakken er tom.

En interessant kendsgerning om denne algoritme er, at den fungerer både som en labyrintgenerator og som en labyrintløser. Hvis du kører den på en allerede genereret labyrint og bare stopper, når du når det bestemte slutpunkt, vil stakken indeholde løsningen til labyrinten.

Jeg har faktisk to versioner af denne algoritme i spil på denne side: en LIFO-købaseret version til at generere labyrinter på denne side og en rekursionsbaseret version til at løse labyrinter, også labyrinter genereret af andre algoritmer (det er sådan kortene med løsningerne er lavet). At have to forskellige versioner er kun for sportens skyld, fordi jeg er en nørd, der finder det interessant, begge kunne have virket for begge ;-)

Yderligere læsning

Hvis du kunne lide dette indlæg, kan du måske også lide disse forslag:

• Ellers algoritme labyrintgenerator
• Wilsons Algoritme Labyrintgenerator
• Jag og dræb labyrintgenerator