Rekursiv Backtracker Maze Generator

Den rekursiva backtracker-algoritmen är verkligen en allmän sökning med djupet först. När den används för generering av labyrint, modifierades den något för att välja vägen slumpmässigt, medan om den används för faktiska sökändamål, skulle man vanligtvis bara söka varje nivå i linjär ordning. Det tenderar att producera labyrinter med långa, slingrande korridorer och en mycket lång, vridbar lösning.

En perfekt labyrint är en labyrint där det finns exakt en väg från varje punkt i labyrinten till varje annan punkt. Det betyder att du inte kan gå runt i cirklar, men du kommer ofta att stöta på återvändsgränder, vilket tvingar dig att vända om och gå tillbaka.

De labyrintkartor som genereras här innehåller en standardversion utan några start- och målpositioner, så att du själv kan bestämma dem: det kommer att finnas en lösning från vilken punkt som helst i labyrinten till vilken annan punkt som helst. Om du vill ha inspiration kan du aktivera en föreslagen start- och målposition - och till och med se lösningen mellan de två.

Den rekursiva backtracker-algoritmen är en djup-först sökmetod för att generera perfekta labyrinter (labyrinter utan loopar och en enda väg mellan två valfria punkter). Det är enkelt, effektivt och producerar visuellt tilltalande labyrinter med långa, slingrande korridorer.

Trots namnet behöver det inte nödvändigtvis implementeras med hjälp av rekursion. Det implementeras ofta i en iterativ metod med hjälp av en LIFO-kö (dvs. en stack). För mycket stora labyrinter är det mer sannolikt att användning av rekursion leder till översvämning av samtalsstack, beroende på programmeringsspråk och tillgängligt minne. En LIFO-kö kan lättare anpassas för att hantera stora datamängder, även att hålla kön på disk eller i en databas om tillgängligt minne är otillräckligt.

Hur det fungerar

Algoritmen använder en stack-baserad djup-först-sökningsmetod. Här är en steg-för-steg-uppdelning:

1. Välj en startcell och markera den som besökt.
2. Medan det finns obesökta celler:
   • Titta på granncellerna som ännu inte har besökts.
   • Om det finns minst en obesökt granne:
     • Välj slumpmässigt en av de obesökta grannarna.
     • Ta bort väggen mellan den nuvarande cellen och den valda grannen.
     • Flytta till den valda grannen och markera den som besökt.
     • Skjut den aktuella cellen på stapeln.
   • Om det inte finns några obesökta grannar:
     • Gå tillbaka genom att ta bort den sista cellen från stacken.
3. Fortsätt denna process tills stacken är tom.

Ett intressant faktum om denna algoritm är att den fungerar både som en labyrintgenerator och som en labyrintlösare. Om du kör den på en redan genererad labyrint och bara stannar när du träffar den bestämda slutpunkten, kommer stacken att innehålla lösningen till labyrinten.

Jag har faktiskt två versioner av den här algoritmen i spel på den här sidan: en LIFO-köbaserad en för att generera labyrinter på den här sidan och en rekursionsbaserad för att lösa labyrinter, även labyrinter genererade av andra algoritmer (det är så kartorna med lösningarna är gjorda). Att ha två olika versioner är bara för sport eftersom jag är en nörd som tycker att det är intressant, antingen kunde ha fungerat för båda ;-)