Jakt og Drep Labyrint Generator
Publisert: 16. februar 2025 kl. 20:55:13 UTC
Labyrintgenerator som bruker Hunt and Kill-algoritmen for å lage en perfekt labyrint. Denne algoritmen ligner på Recursive Backtracker, men har en tendens til å generere labyrinter med noe mindre lange, svingete korridorer.Hunt and Kill Maze Generator
Hunt and Kill-algoritmen er egentlig en modifisert versjon av Recursive Backtracker. Modifikasjonen består av systematisk skanning (eller "jakt") etter en ny celle for å fortsette fra når den ikke kan gå lenger, i motsetning til et ekte rekursivt søk, som alltid vil gå tilbake til forrige celle på stabelen.
På grunn av dette kan denne algoritmen enkelt tilpasses for å generere labyrinter med forskjellig utseende og følelse, bare ved å velge å gå inn i "jakt"-modus oftere eller i henhold til spesifikke regler. Versjonen implementert her går bare inn i "jakt"-modus når den ikke kan gå lenger fra gjeldende celle.
En perfekt labyrint er en labyrint der det finnes nøyaktig én vei fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Det betyr at du ikke kan ende opp med å gå i sirkler, men at du ofte vil støte på blindveier som tvinger deg til å snu og gå tilbake.
Labyrintkartene som genereres her, inneholder en standardversjon uten start- og målposisjoner, slik at du selv kan bestemme disse: Det vil finnes en løsning fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Hvis du vil ha inspirasjon, kan du aktivere en foreslått start- og målposisjon - og til og med se løsningen mellom de to.
Om jakt- og drepealgoritmen
Hunt and Kill-algoritmen er en enkel, men effektiv metode for å generere labyrinter. Det ligner litt på et dybde-først-søk (dvs. Rekursive Backtracker-algoritmen), bortsett fra at når den ikke kan gå lenger fra den nåværende posisjonen, skanner den systematisk (eller "jager") over labyrinten for å finne en ny celle å fortsette fra. Algoritmen består av to hovedfaser: turgåing og jakt.
Hvordan jakt- og drepealgoritmen fungerer for labyrintgenerering
Trinn 1: Start ved en tilfeldig celle
- Finn en tilfeldig celle i rutenettet og merk den som besøkt.
Trinn 2: Gåfase (tilfeldig gange)
- Velg en tilfeldig ubesøkt nabo.
- Flytt til den naboen, merk den som besøkt, og skjær en sti mellom den forrige og den nye cellen.
- Gjenta til det ikke er noen ubesøkte naboer igjen.
Trinn 3: Jaktfase (tilbakesporing via skanning)
- Skann rutenettet rad for rad (eller kolonne for kolonne).
- Finn den første ubesøkte cellen som har minst én besøkt nabo.
- Koble den cellen til en besøkt nabo for å gjenoppta gåfasen.
- Gjenta til alle cellene er besøkt.