Jaga och döda labyrintgenerator
Publicerad: 16 februari 2025 kl. 20:57:23 UTC
Labyrintgenerator som använder Hunt and Kill-algoritmen för att skapa en perfekt labyrint. Denna algoritm liknar den Rekursiva Backtracker, men tenderar att generera labyrinter med något mindre långa, slingrande korridorer.Hunt and Kill Maze Generator
Hunt and Kill-algoritmen är verkligen en modifierad version av Rekursiv Backtracker. Modifieringen består av att systematiskt skanna (eller "jaga") efter en ny cell för att fortsätta från när den inte kan gå längre, i motsats till en äkta rekursiv sökning, som alltid kommer att gå tillbaka till den tidigare cellen 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 "jakt"-läge oftare eller enligt specifika regler. Den version som implementeras här går bara in i "jakt"-läge när den inte kan gå 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 Hunt and Kill-algoritmen
Hunt and Kill-algoritmen är en enkel men effektiv metod för att skapa labyrinter. Det påminner lite om en djup-först-sökning (dvs. Rekursiv Backtracker-algoritmen), förutom att när den inte kan gå längre från den aktuella positionen, skannas den systematiskt (eller "jagar") över labyrinten för att hitta en ny cell att fortsätta från. Algoritmen består av två huvudfaser: promenader och jakt.
Hur Hunt and Kill-algoritmen fungerar för Maze Generation
Steg 1: Börja vid en slumpmässig cell
- Hitta en slumpmässig cell i rutnätet och markera den som besökt.
Steg 2: Promenadfas (Random Walk)
- Välj en slumpmässig obesökt granne.
- Flytta till den grannen, markera den som besökt och rita en väg mellan den tidigare och nya cellen.
- Upprepa tills det inte finns några obesökta grannar kvar.
Steg 3: Jaktfas (backtracking 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.