Generator de labirint al algoritmului de creștere a arborilor

Algoritmul Growing Tree este interesant, deoarece poate emula comportamentul altor câțiva 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 breadth first, asemănătoare coadă.

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 câțiva algoritmi de generare a labirintului, cum ar fi algoritmul lui Prim, backtracking recursiv și divizare recursivă, în funcție de modul în care selectați următoarea celulă de procesat.

Cum funcționează algoritmul de creștere a arborilor

Pasul 1: Inițializare

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

Pasul 2: Bucla de generare a labirintului

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

Pasul 3: Rezilierea

• 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 alegeți ce celulă să procesați în continuare. Această alegere afectează dramatic aspectul labirintului:

Cea mai nouă celulă (comportament asemănător stivei) – Backtracker recursiv:

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

Celulă aleatorie (algoritmul Prim randomizat):

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

Cel mai veche celulă (comportament de coadă):

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

Abordări hibride:

Combină strategii pentru caracteristici variate de labirint. De exemplu:

• 90% cel mai nou, 10% aleatoriu: arată în mare parte ca un labirint recursiv de backtracker, dar cu ramuri ocazionale care despart coridoare lungi.
• 50% cel mai nou, 50% cel mai vechi: echilibrează coridoarele lungi cu creșterea stufoasă.