Gjenerator i labirintit të algoritmit të pemëve në rritje

Algoritmi Growing Tree është interesant, sepse mund të imitojë sjelljen e disa algoritmeve të tjera, në varësi të mënyrës se si zgjidhet qeliza tjetër gjatë gjenerimit. Zbatimi në këtë faqe përdor një qasje të gjerë, të ngjashme me radhë.

Një labirint i përsosur është një labirint në të cilin ka saktësisht një rrugë nga çdo pikë në labirint në çdo pikë tjetër. Kjo do të thotë që nuk mund të përfundoni duke ecur në rreth, por shpesh do të hasni në rrugë pa krye, duke ju detyruar të ktheheni dhe të ktheheni.

Hartat e labirintit të krijuara këtu përfshijnë një version të paracaktuar pa asnjë pozicion fillimi dhe mbarimi, kështu që ju mund t'i vendosni ato vetë: do të ketë një zgjidhje nga çdo pikë në labirint në çdo pikë tjetër. Nëse dëshironi frymëzim, mund të aktivizoni një pozicion të sugjeruar fillimi dhe përfundimi - dhe madje të shihni zgjidhjen midis të dyjave.

Rreth algoritmit të pemëve në rritje

Algoritmi Growing Tree është një metodë fleksibël dhe e fuqishme për gjenerimin e labirinteve të përsosur. Algoritmi është interesant sepse mund të imitojë sjelljen e disa algoritmeve të tjera të gjenerimit të labirintit, të tilla si algoritmi i Prim-it, ndjekja rekursive dhe ndarja rekursive, në varësi të mënyrës se si zgjidhni qelizën tjetër për t'u përpunuar.

Si funksionon algoritmi i pemës në rritje

Hapi 1: Inicializimi

• Filloni me një rrjet qelizash të pavizituara.
• Zgjidhni një qelizë fillestare të rastësishme dhe shtojeni atë në një listë.

Hapi 2: Labirinti i Gjenerimit të Labirintit

• Ndërsa lista e qelizave nuk është bosh:
  • Zgjidhni një qelizë nga lista bazuar në një strategji specifike (shpjeguar më poshtë).
  • Gdhendni një pasazh nga qeliza e zgjedhur në një nga fqinjët e saj të pavizituar (i zgjedhur rastësisht).
  • Shtoni fqinjin në listë pasi tani është pjesë e labirintit.
  • Nëse qeliza e zgjedhur nuk ka fqinjë të pavizituar, hiqeni atë nga lista.

Hapi 3: Përfundimi

• Algoritmi përfundon kur nuk ka më qeliza në listë, që do të thotë se i gjithë labirinti është gdhendur.

Strategjitë e përzgjedhjes së qelizave (Fleksibiliteti i algoritmit)

Karakteristika përcaktuese e algoritmit të Pemës në rritje është se si ju zgjidhni cilën qelizë të përpunoni më pas. Kjo zgjedhje ndikon në mënyrë dramatike pamjen e labirintit:

Qeliza më e re (Sjellje e ngjashme me stivën) – Backtracker rekurziv:

• Zgjidhni gjithmonë qelizën e shtuar së fundmi.
• Prodhon korridore të gjata e të përdredhura me shumë qoshe (si një labirint kërkimi në thellësi).
• Labirintet priren të kenë kalime të gjata dhe janë të lehta për t'u zgjidhur.

Qeliza e rastësishme (Algoritmi i rastësishëm i Prim):

• Zgjidh një qelizë të rastësishme nga lista çdo herë.
• Krijon një labirint më të shpërndarë në mënyrë të barabartë me shtigje komplekse dhe të ngatërruara.
• Më pak korridore të gjata dhe më shumë degëzime.

Qeliza më e vjetër (sjellje e ngjashme me radhën):

• Zgjidhni gjithmonë qelizën më të vjetër në listë.
• Gjeneron labirint me një shtrirje më uniforme, si një model kërkimi në gjerësi.
• Vendkalime të shkurtra, me shkurre me lidhje të dendura.
• (Ky është versioni i implementuar këtu)

Qasjet hibride:

Kombinoni strategji për karakteristika të ndryshme të labirintit. Për shembull:

• 90% më e reja, 10% e rastësishme: Duket kryesisht si një labirint prapaveprues rekurziv, por me degë të rastësishme që thyejnë korridore të gjata.
• 50% më e reja, 50% më e vjetra: Balancon korridoret e gjata me rritje me shkurre.