Växande trädalgoritm labyrintgenerator

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

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.