Growing Tree algoritme labyrintgenerator

Growing Tree-algoritmen er interessant, fordi den kan efterligne adfærden fra flere andre algoritmer, afhængigt af hvordan den næste celle vælges under genereringen. Implementeringen på denne side bruger en bredde-først, kølignende tilgang.

En perfekt labyrint er en labyrint, hvor der er præcis én vej fra et hvilket som helst punkt i labyrinten til et hvilket som helst andet punkt. Det betyder, at du ikke kan ende med at gå rundt i cirkler, men du vil ofte støde på blindgyder, som tvinger dig til at vende om og gå tilbage.

De labyrintkort, der genereres her, indeholder en standardversion uden start- og slutpositioner, så du selv kan bestemme dem: der vil være en løsning fra ethvert punkt i labyrinten til ethvert andet punkt. Hvis du vil have inspiration, kan du aktivere en foreslået start- og slutposition - og endda se løsningen mellem de to.

Om den voksende træalgoritme

Growing Tree-algoritmen er en fleksibel og kraftfuld metode til at generere perfekte labyrinter. Algoritmen er interessant, fordi den kan efterligne adfærden af ​​flere andre labyrintgenereringsalgoritmer, såsom Prims algoritme, rekursiv backtracking og rekursiv division, afhængigt af hvordan du vælger den næste celle, der skal behandles.

Hvordan den voksende træalgoritme fungerer

Trin 1: Initialisering

• Start med et gitter af ubesøgte celler.
• Vælg en tilfældig startcelle, og føj den til en liste.

Trin 2: Maze Generation Loop

• Mens cellelisten ikke er tom:
  • Vælg en celle fra listen baseret på en specifik strategi (forklaret nedenfor).
  • Skær en passage fra den valgte celle til en af ​​dens ubesøgte naboer (valgt tilfældigt).
  • Tilføj naboen til listen, da den nu er en del af labyrinten.
  • Hvis den valgte celle ikke har nogen ubesøgte naboer, skal du fjerne den fra listen.

Trin 3: Opsigelse

• Algoritmen afsluttes, når der ikke er flere celler på listen, hvilket betyder, at hele labyrinten er skåret ud.

Cellevalgsstrategier (algoritmens fleksibilitet)

Den definerende egenskab ved Growing Tree-algoritmen er, hvordan du vælger, hvilken celle der skal behandles næste gang. Dette valg påvirker dramatisk labyrintens udseende:

Nyeste celle (staklignende adfærd) – Rekursiv backtracker:

• Vælg altid den senest tilføjede celle.
• Producerer lange, snoede korridorer med mange blindgyder (som en dybde-først søgelabyrint).
• Labyrinter har tendens til at have lange passager og er nemme at løse.

Tilfældig celle (randomiseret Prims algoritme):

• Vælg en tilfældig celle fra listen hver gang.
• Skaber en mere jævnt fordelt labyrint med komplekse, sammenfiltrede stier.
• Færre lange korridorer og flere forgreninger.

Ældste celle (kølignende adfærd):

• Vælg altid den ældste celle på listen.
• Genererer labyrinter med en mere ensartet spredning, som et bredde-først søgemønster.
• Korte, buskede gange med tætte forbindelser.
• (Dette er versionen implementeret her)

Hybride tilgange:

Kombiner strategier for forskellige labyrintegenskaber. For eksempel:

• 90 % nyeste, 10 % tilfældigt: Ser mest ud som en rekursiv backtracker-labyrint, men med lejlighedsvise grene, der bryder lange korridorer op.
• 50 % nyeste, 50 % ældste: Balancerer lange korridorer med busket vækst.