Growing Tree algoritme labyrintgenerator

Growing Tree-algoritmen er interessant, fordi den kan efterligne opførslen af adskillige 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 algoritmen for voksende træer

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

Sådan fungerer algoritmen for voksende træer

Trin 1: Initialisering

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

Trin 2: Labyrintgenereringsløkke

• Mens cellelisten ikke er tom: Vælg en celle fra listen baseret på en specifik strategi (forklaret nedenfor). Udskær en passage fra den valgte celle til en af dens ubesøgte naboer (tilfældigt valgt). 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 blevet udskåret.

Strategier til celleudvælgelse (algoritmens fleksibilitet)

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

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

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

Tilfældig celle (tilfældig 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 mere forgrening.

Æ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 passager med tætte forbindelser.
• (Dette er den version, der er implementeret her)

Hybride tilgange:

Kombinér strategier for forskellige labyrintkarakteristika. For eksempel:

• 90 % nyeste, 10 % tilfældig: Ligner mest en rekursiv backtracker-labyrint, men med lejlighedsvise grene, der opbryder lange korridorer.
• 50 % nyeste, 50 % ældste: Balancerer lange korridorer med buskagtig vækst.

Yderligere læsning

Hvis du kunne lide dette indlæg, kan du måske også lide disse forslag:

• Jag og dræb labyrintgenerator
• Wilsons Algoritme Labyrintgenerator
• Kruskal's Algoritme Maze Generator