Jaga och döda labyrintgenerator

Jaga-och-döda-algoritmen är egentligen en modifierad version av den rekursiva backtracker-algoritmen. Modifieringen består av att systematiskt skanna (eller "jaga") efter en ny cell att fortsätta från när den inte kan gå vidare, i motsats till en verklig rekursiv sökning, som alltid går tillbaka till föregående cell i stacken.

På grund av detta kan denna algoritm enkelt anpassas för att generera labyrinter med olika utseende och känsla, bara genom att välja att gå in i "jaktläge" oftare eller enligt specifika regler. Versionen som implementeras här går bara in i "jaktläge" när den inte kan komma längre från den aktuella cellen.

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

Om algoritmen "Jakt och döda

Jaga-och-döda-algoritmen är en enkel men effektiv metod för att generera labyrinter. Den liknar i viss mån en djupgående sökning (dvs. den rekursiva backtracker-algoritmen), förutom att när den inte kan gå längre från den aktuella positionen, skannar den systematiskt (eller "jagar") över labyrinten för att hitta en ny cell att fortsätta från. Algoritmen består av två huvudfaser: vandring och jakt.

Hur jakt-och-död-algoritmen fungerar för labyrintgenerering

Steg 1: Börja i en slumpmässig cell

• Hitta en slumpmässig cell i rutnätet och markera den som besökt.

Steg 2: Gångfas (Slumpmässig promenad)

• Välj en slumpmässig obekymrad granne.
• Flytta till den grannen, markera den som besökt och skapa en väg mellan den föregående och den nya cellen.
• Upprepa tills det inte finns några obesökta grannar kvar.

Steg 3: Jaktfas (Tillbakagång via skanning)

• Skanna rutnätet rad för rad (eller kolumn för kolumn).
• Hitta den första obesökta cellen som har minst en besökt granne.
• Anslut den cellen till en besökt granne för att återuppta gångfasen.
• Upprepa tills alla celler har besökts.

Vidare läsning

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

• Kruskals algoritm labyrintgenerator
• Ellers algoritm labyrintgenerator
• Wilsons algoritm labyrintgenerator