Miklix

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.

Denna sida har maskinöversatts från engelska för att göra den tillgänglig för så många som möjligt. Tyvärr är maskinöversättning ännu inte en fulländad teknik, så fel kan uppstå. Om du föredrar det kan du se den engelska originalversionen här:

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å.


Generera ny labyrint








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.

Dela på BlueskyDela på FacebookDela på LinkedInDela på TumblrDela på XDela på LinkedInFäst på Pinterest

Mikkel Bang Christensen

Om författaren

Mikkel Bang Christensen
Mikkel är skaparen och ägaren av miklix.com. Han har över 20 års erfarenhet som professionell datorprogrammerare/mjukvaruutvecklare och är för närvarande heltidsanställd på ett stort europeiskt IT-bolag. När han inte bloggar ägnar han sin fritid åt en mängd olika intressen, hobbies och aktiviteter, vilket i viss mån kan återspeglas i de olika ämnen som behandlas på den här webbplatsen.