Växande trädalgoritm labyrintgenerator

Growing Tree-algoritmen är intressant eftersom den kan emulera 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 metod.

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 algoritmen för växande träd

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

Hur algoritmen för växande träd fungerar

Steg 1: Initialisering

• 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: Labyrintgenereringsloop

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

Steg 3: Avslut

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

Strategier för cellval (algoritmens flexibilitet)

Det avgörande kännetecknet för Growing Tree-algoritmen ä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:

• Markera alltid den senast tillagda cellen.
• Skapar långa, slingrande korridorer med många återvändsgränder (som en djupgående söklabyrint).
• Labyrinter tenderar att ha långa passager och är lätta att lösa.

Slumpmässig cell (slumpmässig Prims algoritm):

• 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örgreningar.

Äldsta cell (köliknande beteende):

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

Hybrida tillvägagångssätt:

Kombinera strategier för olika labyrintegenskaper. Till exempel:

• 90 % nyast, 10 % slumpmässigt: Ser mest ut som en rekursiv bakåtspårningslabyrint, men med enstaka grenar som bryter upp långa korridorer.
• 50 % nyast, 50 % äldst: Balanserar långa korridorer med buskig växtlighet.

Vidare läsning

Om du gillade det här inlägget kanske du också gillar dessa förslag:

• Wilsons algoritm labyrintgenerator
• Jaga och döda labyrintgenerator
• Kruskals algoritm labyrintgenerator