Miklix

Växande trädalgoritm labyrintgenerator

Publicerad: 16 februari 2025 kl. 21:37:21 UTC
Senast uppdaterad: 6 mars 2025 kl. 09:57:03 UTC

Labyrintgenerator som använder Growing Tree-algoritmen för att skapa en perfekt labyrint. Denna algoritm tenderar att generera labyrinter som liknar Hunt and Kill-algoritmen, men med en något annorlunda typisk lösning.

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:

Growing Tree Algorithm Maze Generator

Growing Tree-algoritmen är intressant, eftersom den kan efterlikna beteendet hos flera andra algoritmer, beroende på hur nästa cell väljs under genereringen. Implementeringen på den här sidan använder en bredd-först, köliknande tillvägagångssätt.

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 den växande trädalgoritmen

Growing Tree-algoritmen är en flexibel och kraftfull metod för att skapa perfekta labyrinter. Algoritmen är intressant eftersom den kan emulera beteendet hos flera andra labyrintgenereringsalgoritmer, såsom Prims algoritm, rekursiv backtracking och rekursiv division, beroende på hur du väljer nästa cell att bearbeta.

Hur den växande trädalgoritmen fungerar

Steg 1: Initiering

  • Börja med ett rutnät av obesökta celler.
  • Välj en slumpmässig startcell och lägg till den i en lista.

Steg 2: Maze Generation Loop

  • Medan celllistan inte är tom:
    • Välj en cell från listan baserat på en specifik strategi (förklaras nedan).
    • Skär en passage från den valda cellen till en av dess obesökta grannar (vald slumpmässigt).
    • Lägg till grannen till listan eftersom den nu är en del av labyrinten.
    • Om den markerade cellen inte har några obesökta grannar tar du bort den från listan.

Steg 3: Uppsägning

  • Algoritmen avslutas när det inte finns fler celler i listan, vilket betyder att hela labyrinten har ristats.

Cellurvalsstrategier (algoritmens flexibilitet)

Den definierande egenskapen hos algoritmen för växande träd är hur du väljer vilken cell som ska bearbetas härnäst. Detta val påverkar dramatiskt labyrintens utseende:

Nyaste cell (stackliknande beteende) – Rekursiv backtracker:

  • Välj alltid den senast tillagda cellen.
  • Producerar långa, slingrande korridorer med många återvändsgränder (som en djup-först söklabyrint).
  • Labyrinter tenderar att ha långa passager och är lätta att lösa.

Random Cell (Randomized Prim's Algorithm):

  • Välj en slumpmässig cell från listan varje gång.
  • Skapar en mer jämnt fördelad labyrint med komplexa, trassliga banor.
  • Färre långa korridorer och mer förgrening.

Äldsta cellen (köliknande beteende):

  • Välj alltid den äldsta cellen i listan.
  • Genererar labyrinter med en mer enhetlig spridning, som ett sökmönster med bredd först.
  • Korta, buskiga passager med täta förbindelser.
  • (Detta är versionen som implementeras här)

Hybridmetoder:

Kombinera strategier för olika labyrintegenskaper. Till exempel:

  • 90 % senaste, 10 % slumpmässigt: Ser mest ut som en rekursiv backtracker-labyrint, men med enstaka grenar som bryter upp långa korridorer.
  • 50% nyaste, 50% äldsta: Balanserar långa korridorer med buskig tillväxt.

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.