Jag og dræb labyrintgenerator

Hunt and Kill-algoritmen er i virkeligheden en modificeret version af den rekursive backtracker. Modifikationen består i systematisk at scanne (eller "jage") efter en ny celle at fortsætte fra, når den ikke kan gå videre, i modsætning til en ægte rekursiv søgning, som altid går tilbage til den forrige celle i stakken.

På grund af dette kan denne algoritme nemt tilpasses til at generere labyrinter med forskelligt udseende og funktionalitet, blot ved at vælge at gå 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 komme længere væk 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 Jagt og Dræb-algoritmen

Jagt-og-dræb-algoritmen er en simpel, men effektiv metode til at generere labyrinter. Den minder noget om en dybdesøgning (dvs. den rekursive backtracker-algoritme), bortset fra at når den ikke kan komme længere fra den aktuelle position, scanner den systematisk (eller "jager") over labyrinten for at finde en ny celle at fortsætte fra. Algoritmen består af to hovedfaser: at gå og jage.

Hvordan "Hunt and Kill"-algoritmen fungerer til labyrintgenerering

Trin 1: Start i en tilfældig celle

• Find en tilfældig celle i gitteret og marker den som besøgt.

Trin 2: Gåfase (Tilfældig gang)

• Vælg en tilfældig, ubesøgt nabo.
• Flyt til den nabo, marker den som besøgt, og lav en sti mellem den forrige og den nye celle.
• Gentag indtil der ikke er flere 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 til en besøgt nabo for at genoptage gangfasen.
• Gentag indtil alle celler er blevet besøgt.

Yderligere læsning

Hvis du kunne lide dette indlæg, kan du måske også lide disse forslag:

• Rekursiv Backtracker Maze Generator
• Wilsons Algoritme Labyrintgenerator
• Ellers algoritme labyrintgenerator