Growing Tree algoritme labyrintgenerator

Growing Tree-algoritmen er interessant, fordi den kan etterligne 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 etterligne 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 med 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 spesifikk strategi (forklart nedenfor).
  • Skjær en passasje fra den valgte cellen til en av dens ubesøkte naboer (valgt tilfeldig).
  • Legg naboen til listen siden den nå er en del av labyrinten.
  • Hvis den merkede cellen ikke har noen ubesøkte naboer, fjerner du 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.

Cellevalgsstrategier (fleksibilitet i algoritmen)

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

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

• Velg alltid den sist tilføyde 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 jevnere fordelt labyrint med komplekse, sammenfiltrede stier.
• Færre lange korridorer og mer forgrening.

Eldste celle (kølignende virkemåte):

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

Hybride tilnærminger:

Kombiner strategier for varierte labyrintegenskaper. For eksempel:

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

Videre lesing

Hvis du likte dette innlegget, kan du også like disse forslagene:

• Kruskals algoritme-labyrint-generator
• Wilsons algoritme labyrintgenerator
• Ellers algoritme-labyrintgenerator