Rekursiv Backtracker Maze Generator

Den rekursiva backtracker-algoritmen är egentligen en generell djupsökning. När den används för labyrintgenerering modifieras den något för att välja sökvägen slumpmässigt, medan man vid faktiska sökändamål vanligtvis bara skulle söka på varje nivå i linjär ordning. Den tenderar att producera labyrinter med långa, slingrande korridorer och en mycket lång, slingrande 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 djupbaserad sökmetod för att generera perfekta labyrinter (labyrinter utan loopar och med en enda väg mellan två punkter). Den är enkel, effektiv och producerar visuellt tilltalande labyrinter med långa, slingrande korridorer.

Trots namnet behöver den inte nödvändigtvis implementeras med rekursion. Den 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 rekursion leder till stacköverflöde, beroende på programmeringsspråk och tillgängligt minne. En LIFO-kö kan lättare anpassas för att hantera stora mängder data, till och med 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 stackbaserad djup-först-sökningsmetod. Här är en steg-för-steg-beskrivning:

1. Välj en startcell och markera den som besökt.
2. Medan det finns obesökta celler: Titta på de angränsande cellerna 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 aktuella cellen och den valda grannen. Flytta till den valda grannen och markera den som besökt. Skjut den aktuella cellen till stapeln. Om det inte finns några obesökta grannar: Gå tillbaka genom att dra ut den sista cellen från stapeln.
3. Fortsätt denna process tills stapeln är tom.

Ett intressant faktum med den här algoritmen ä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 når 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 webbplatsen: en LIFO-köbaserad 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 skapas). Att ha två olika versioner är bara för sport eftersom jag är en nörd som tycker det är intressant, endera hade kunnat fungera för båda ;-)

Vidare läsning

Om du gillade det här inlägget kanske du också gillar dessa förslag:

• Ellers algoritm labyrintgenerator
• Kruskals algoritm labyrintgenerator
• Jaga och döda labyrintgenerator