Growing Tree algoritme labyrintgenerator

Growing Tree-algoritmen er interessant, fordi den kan emulere oppførselen til flere andre algoritmer, avhengig av hvordan neste celle velges under generering. Implementeringen på denne siden bruker en bredde-først, kølignende tilnærming.

En perfekt labyrint er en labyrint der det finnes nøyaktig én vei fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Det betyr at du ikke kan ende opp med å gå i sirkler, men at du ofte vil støte på blindveier som tvinger deg til å snu og gå tilbake.

Labyrintkartene som genereres her, inneholder en standardversjon uten start- og målposisjoner, slik at du selv kan bestemme disse: Det vil finnes en løsning fra et hvilket som helst punkt i labyrinten til et hvilket som helst annet punkt. Hvis du vil ha inspirasjon, kan du aktivere en foreslått start- og målposisjon - og til og med se løsningen mellom de to.

Om algoritmen for voksende tre

Growing Tree-algoritmen er en fleksibel og kraftig metode for å generere perfekte labyrinter. Algoritmen er interessant fordi den kan emulere oppførselen til flere andre labyrintgenereringsalgoritmer, for eksempel Prims algoritme, rekursiv tilbakesporing og rekursiv divisjon, avhengig av hvordan du velger neste celle som skal behandles.

Hvordan algoritmen for voksende tre fungerer

Trinn 1: Initialisering

• Start med et rutenett av ubesøkte celler.
• Velg en tilfeldig startcelle og legg den til i en liste.

Trinn 2: Maze Generation Loop

• Mens cellelisten ikke er tom:
  • Velg en celle fra listen basert på en bestemt strategi (forklart nedenfor).
  • Skjær en passasje fra den valgte cellen til en av dens ubesøkte naboer (valgt tilfeldig).
  • Legg til naboen på listen siden den nå er en del av labyrinten.
  • Hvis den valgte cellen ikke har noen ubesøkte naboer, fjern den fra listen.

Trinn 3: Oppsigelse

• Algoritmen avsluttes når det ikke er flere celler i listen, noe som betyr at hele labyrinten er skåret ut.

Cellevalgstrategier (algoritmens fleksibilitet)

Den definerende funksjonen til Growing Tree-algoritmen er hvordan du velger hvilken celle som skal behandles neste. Dette valget påvirker dramatisk labyrintens utseende:

Nyeste celle (stabellignende oppførsel) – Rekursiv tilbakesporing:

• Velg alltid den sist lagt til cellen.
• Produserer lange, kronglete korridorer med mange blindveier (som en dybde-først søkelabyrint).
• Labyrinter har en tendens til å ha lange passasjer og er enkle å løse.

Tilfeldig celle (randomisert Prims algoritme):

• Velg en tilfeldig celle fra listen hver gang.
• Skaper en mer jevnt fordelt labyrint med komplekse, sammenfiltrede stier.
• Færre lange korridorer og mer forgrening.

Eldste celle (kølignende oppførsel):

• Velg alltid den eldste cellen i listen.
• Genererer labyrinter med en mer jevn spredning, som et bredde-først søkemønster.
• Korte, buskete passasjer med tette forbindelser.
• (Dette er versjonen implementert her)

Hybride tilnærminger:

Kombiner strategier for varierte labyrintegenskaper. For eksempel:

• 90 % nyeste, 10 % tilfeldig: Ser mest ut som en rekursiv backtracker-labyrint, men med sporadiske grener som bryter opp lange korridorer.
• 50 % nyeste, 50 % eldst: Balanserer lange korridorer med buskete vekst.