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, varësisht nga mënyra se si zgjidhet qeliza tjetër gjatë gjenerimit. Implementimi në këtë faqe përdor një qasje të ngjashme me radhën e radhës, që vë në dukje gjerësinë e parë.

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ë Rritjes së Pemës

Algoritmi "Growing Tree" është një metodë fleksibile dhe e fuqishme për gjenerimin e labirinteve perfekte. Algoritmi është interesant sepse mund të imitojë sjelljen e disa algoritmeve të tjera të gjenerimit të labirinteve, siç është algoritmi i Primit, kthimi prapa rekursiv dhe ndarja rekursive, varësisht nga mënyra se si zgjidhni qelizën tjetër për t'u përpunuar.

Si funksionon algoritmi i rritjes së pemës

Hapi 1: Inicializimi

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

Hapi 2: Cikli i Gjenerimit të Labirintit

• Ndërsa lista e qelizave nuk është bosh: Zgjidhni një qelizë nga lista bazuar në një strategji specifike (e shpjeguar më poshtë). Gdhendni një pasazh nga qeliza e zgjedhur te një nga fqinjët e saj të pavizituar (të zgjedhur rastësisht). Shtoni fqinjin në listë meqenëse 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 "Pema në rritje" është mënyra se si zgjidhni se cilën qelizë do të përpunoni më pas. Kjo zgjedhje ndikon në mënyrë dramatike në pamjen e labirintit:

Qeliza më e re (Sjellje e ngjashme me grumbullin) – Gjurmues prapa rekursiv:

• Zgjidh gjithmonë qelizën e shtuar më së fundmi.
• Prodhon korridore të gjata e dredha-dredha me shumë skaje pa krye (si një labirint kërkimi që vendos thellësinë në radhë të parë).
• Labirintet kanë tendencë të kenë kalime të gjata dhe janë të lehta për t'u zgjidhur.

Qelizë e Rastësishme (Algoritmi i Primit i Rastësishëm):

• Zgjidhni 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):

• Gjithmonë zgjidhni qelizën më të vjetër në listë.
• Gjeneron labirinte me një përhapje më uniforme, si një model kërkimi që vendos gjerësinë së pari.
• Kalime të shkurtra, me shkurre me lidhje të dendura.
• (Ky është versioni i implementuar këtu)

Qasje Hibride:

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

• 90% më i riu, 10% i rastësishëm: Duket kryesisht si një labirint rekursiv prapavajtës, por me degë të rastësishme që ndajnë korridore të gjata.
• 50% më të rejat, 50% më të vjetrat: Balancon korridoret e gjata me rritjen e shkurreve.

Lexime të mëtejshme

Nëse ju pëlqeu ky postim, mund t'ju pëlqejnë edhe këto sugjerime:

• Gjeneratori Maze i Algoritmit të Ellerit
• Gjeneratori i Mazes së Algoritmit të Kruskalit
• Gjeneratori i Algoritmit Maze të Uillsonit