Jakt og Drep Labyrint 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 som er implementert her går bare inn i "jakt"-modus når den ikke kan gå lenger fra den nåværende cellen.

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 drap-algoritmen

Hunt and Kill-algoritmen er en enkel, men effektiv metode for å generere labyrinter. Det ligner litt på et dybde-først-søk (dvs. den rekursive Backtracker-algoritmen), bortsett fra at når den ikke kan gå lenger fra den nåværende posisjonen, skanner den systematisk (eller "jakter") over labyrinten for å finne en ny celle å gå ut fra. Algoritmen består av to hovedfaser: turgåing og jakt.

Hvordan jakt og drap-algoritmen fungerer for labyrintgenerering

Trinn 1: Start med en tilfeldig celle

• Finn en tilfeldig celle i rutenettet og merk den som besøkt.

Trinn 2: Gangfase (tilfeldig gange)

• Velg en tilfeldig ubesøkt nabo.
• Flytt til naboen, merk den som besøkt, og skjær en sti mellom forrige og nye celle.
• 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 gangfasen.
• Gjenta til alle cellene er besøkt.

Videre lesing

Hvis du likte dette innlegget, kan du også like disse forslagene:

• Growing Tree algoritme labyrintgenerator
• Kruskals algoritme-labyrint-generator
• Rekursiv Backtracker Maze Generator