Jag og dræb labyrintgenerator
Udgivet: 16. februar 2025 kl. 20.52.20 UTC
Labyrintgenerator ved hjælp af Hunt and Kill-algoritmen til at skabe en perfekt labyrint. Denne algoritme ligner den Rekursive Backtracker, men har en tendens til at generere labyrinter med noget mindre lange, snoede korridorer.Hunt and Kill Maze Generator
Hunt and Kill-algoritmen er virkelig en modificeret version af Recursive Backtracker. Modifikationen består af systematisk scanning (eller "jagt") efter en ny celle for at fortsætte fra når den ikke kan komme længere, i modsætning til en ægte rekursiv søgning, som altid vil gå tilbage til den forrige celle på stakken.
På grund af dette kan denne algoritme nemt tilpasses til at generere labyrinter med forskelligt udseende og fornemmelse, blot ved at vælge at gå ind i "jagt"-tilstand oftere eller i henhold til specifikke regler. Den version, der er implementeret her, går kun i "jagt"-tilstand, når den ikke kan gå længere fra den aktuelle celle.
En perfekt labyrint er en labyrint, hvor der er præcis én vej fra et hvilket som helst punkt i labyrinten til et hvilket som helst andet punkt. Det betyder, at du ikke kan ende med at gå rundt i cirkler, men du vil ofte støde på blindgyder, som tvinger dig til at vende om og gå tilbage.
De labyrintkort, der genereres her, indeholder en standardversion uden start- og slutpositioner, så du selv kan bestemme dem: der vil være en løsning fra ethvert punkt i labyrinten til ethvert andet punkt. Hvis du vil have inspiration, kan du aktivere en foreslået start- og slutposition - og endda se løsningen mellem de to.
Om Hunt and Kill-algoritmen
Hunt and Kill-algoritmen er en enkel, men effektiv metode til at generere labyrinter. Det minder lidt om en dybde-først-søgning (dvs. den rekursive tilbagesporingsalgoritme), bortset fra at når den ikke kan gå længere fra den aktuelle position, scanner den systematisk (eller "jager") over labyrinten for at finde en ny celle at gå videre fra. Algoritmen består af to hovedfaser: gåture og jagt.
Hvordan jagt og dræb-algoritmen fungerer for labyrintgenerering
Trin 1: Start ved en tilfældig celle
- Find en tilfældig celle i gitteret og marker den som besøgt.
Trin 2: Gåfase (Random Walk)
- Vælg en tilfældig ubesøgt nabo.
- Flyt til den nabo, marker den som besøgt, og læg en sti mellem den forrige og den nye celle.
- Gentag indtil der ikke er nogen ubesøgte naboer tilbage.
Trin 3: Jagtfase (tilbagesporing via scanning)
- Scan gitteret række for række (eller kolonne for kolonne).
- Find den første ubesøgte celle, der har mindst én besøgt nabo.
- Forbind den celle med en besøgt nabo for at genoptage gangfasen.
- Gentag indtil alle celler er blevet besøgt.