Generator de labirint al algoritmului de creștere a arborilor

Algoritmul Growing Tree este interesant, deoarece poate emula comportamentul mai multor alți algoritmi, în funcție de modul în care este aleasă următoarea celulă în timpul generării. Implementarea de pe această pagină folosește o abordare de tip coadă, bazată pe lățime (bound first).

Un labirint perfect este un labirint în care există exact o singură cale de la orice punct din labirint la orice alt punct. Aceasta înseamnă că nu puteți ajunge să vă învârtiți în cerc, dar veți întâlni adesea fundături, forțându-vă să vă întoarceți.

Hărțile labirintului generate aici includ o versiune implicită fără poziții de început și de sfârșit, astfel încât să le puteți decide singuri: va exista o soluție din orice punct al labirintului către orice alt punct. Dacă doriți să vă inspirați, puteți activa o poziție de început și de sfârșit sugerată - și chiar să vedeți soluția între cele două.

Despre algoritmul arborelui în creștere

Algoritmul Growing Tree este o metodă flexibilă și puternică pentru generarea de labirinturi perfecte. Algoritmul este interesant deoarece poate emula comportamentul altor algoritmi de generare a labirintului, cum ar fi algoritmul lui Prim, backtracking recursiv și divizarea recursivă, în funcție de modul în care selectați următoarea celulă de procesat.

Cum funcționează algoritmul arborelui în creștere

Pasul 1: Inițializare

• Începeți cu o grilă de celule nevizitate.
• Alegeți o celulă de început aleatorie și adăugați-o într-o listă.

Pasul 2: Bucla de generare a labirintului

• Cât timp lista de celule nu este goală: Selectați o celulă din listă pe baza unei strategii specifice (explicată mai jos). Creați un pasaj de la celula selectată la unul dintre vecinii săi nevizitați (aleși aleatoriu). Adăugați vecinul în listă, deoarece acum face parte din labirint. Dacă celula selectată nu are vecini nevizitați, eliminați-o din listă.

Pasul 3: Terminarea

• Algoritmul se termină când nu mai există celule în listă, ceea ce înseamnă că întregul labirint a fost sculptat.

Strategii de selecție a celulelor (flexibilitatea algoritmului)

Caracteristica definitorie a algoritmului Growing Tree este modul în care alegi ce celulă să procesezi în continuare. Această alegere afectează dramatic aspectul labirintului:

Cea mai nouă celulă (comportament de tip stivă) – Backtracker recursiv:

• Selectați întotdeauna celula adăugată cel mai recent.
• Produce coridoare lungi și întortocheate, cu multe fundături (ca un labirint de căutare în adâncime).
• Labirinturile tind să aibă pasaje lungi și sunt ușor de rezolvat.

Celulă aleatorie (algoritmul lui Prim randomizat):

• Alegeți o celulă aleatorie din listă de fiecare dată.
• Creează un labirint distribuit mai uniform, cu căi complexe și încâlcite.
• Mai puține coridoare lungi și mai multe ramificări.

Cea mai veche celulă (comportament similar coadei):

• Alegeți întotdeauna cea mai veche celulă din listă.
• Generează labirinturi cu o răspândire mai uniformă, precum un model de căutare bazat pe lățime.
• Pasaje scurte și stufoase, cu conexiuni dense.
• (Aceasta este versiunea implementată aici)

Abordări hibride:

Combinați strategii pentru diverse caracteristici ale labirintului. De exemplu:

• 90% cel mai nou, 10% aleatoriu: Arată în mare parte ca un labirint recursiv cu tracker invers, dar cu ramificații ocazionale care întrerup coridoare lungi.
• 50% cel mai nou, 50% cel mai vechi: Echilibrează coridoarele lungi cu o creștere densă.

Lectură suplimentară

Dacă ți-a plăcut această postare, s-ar putea să-ți placă și aceste sugestii:

• Generatorul de labirint al algoritmului lui Kruskal
• Generatorul de labirint de vânătoare și ucidere
• Generatorul de labirint al algoritmului lui Eller