Rekursiv Backtracker Maze Generator

Den rekursive backtracker-algoritme er virkelig en generel dybde-først-søgning. Når den blev brugt til labyrintgenerering, blev den en smule ændret til at vælge stien tilfældigt, mens hvis den blev brugt til faktiske søgeformål, ville man typisk blot søge hvert niveau i lineær rækkefølge. Det 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 dybde-først søgemetode til at generere perfekte labyrinter (labyrinter uden sløjfer og en enkelt vej mellem to vilkårlige punkter). Den er enkel, effektiv og producerer visuelt tiltalende labyrinter med lange, snoede korridorer.

På trods af navnet behøver det ikke nødvendigvis at blive implementeret ved hjælp af rekursion. Det 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 brug af rekursion resulterer i overløb af opkaldsstak, afhængigt af programmeringssprog og tilgængelig hukommelse. En LIFO-kø kan nemmere tilpasses til at håndtere store mængder data, selv at holde køen på disk eller i en database, hvis den tilgængelige hukommelse er utilstrækkelig.

Hvordan det virker

Algoritmen fungerer ved hjælp af en stak-baseret dybde-først-søgningstilgang. Her er en trin-for-trin opdeling:

1. Vælg en startcelle, og marker den som besøgt.
2. Mens der er ubesøgte celler:
   • Se på nabocellerne, der endnu ikke er 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 nuværende 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 ubesøgte naboer:
     • Gå tilbage ved at springe den sidste celle fra stakken.
3. Fortsæt denne proces, indtil stakken er tom.

Et interessant faktum 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 rammer 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 til generering af labyrinter på denne side og en rekursionsbaseret til løsning af labyrinter, også labyrinter genereret af andre algoritmer (det er sådan, kortene med løsningerne er lavet). At have to forskellige versioner er kun til sport, fordi jeg er en nørd, der finder det interessant, enten kunne have fungeret for begge ;-)