Gjeneratori Maze i Algoritmit të Ellerit

Algoritmi i Ellerit është një algoritëm i gjeneratës së labirinteve që prodhon në mënyrë efikase labirintet e përsosura (labirintet pa loope dhe një rrugë të vetme midis çdo dy pikash) duke përdorur një qasje rresht pas rreshti. Prodhon labirinte të ngjashme me algoritmin e Kruskalit, por e bën këtë duke gjeneruar vetëm një rresht në një kohë, pa pasur nevojë për ruajtjen e të gjithë labirintit në kujtesë. Kjo e bën të dobishme për gjenerimin e labirinteve shumë të mëdha në sisteme shumë të kufizuara dhe për gjenerimin e përmbajtjes procedurale.

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ë Ellerit

Algoritmi i Eller u prezantua nga David Eller.

Algoritmi është i shquar për qasjen e tij efikase rresht pas rreshti në brezin e labirinteve, duke e bërë atë ideal për labirintet apo labirintet e pafundme të gjeneruara në kohë reale. Zakonisht citohet në literaturën procedurale të gjenerimit të përmbajtjes dhe të brezit të labirinteve, por nuk kam qenë në gjendje të gjej burime kryesore që detajojnë botimin e saj origjinal.

Si funksionon algoritmi i Ellerit për brezin Maze

Algoritmi i Eller përpunon një rresht në një kohë, duke ruajtur dhe modifikuar grupe qelizash të lidhura. Siguron lidhshmërinë duke shmangur kthesat dhe e shtrin me efektshmëri labirintin poshtë.

Teorikisht mund të përdoret për të gjeneruar labirinte të pafundme, megjithatë në mënyrë që të sigurohet që labirinti i gjeneruar është në të vërtetë i solvueshëm, është e nevojshme të kalohet në logjikën e "rreshtit përfundimtar" në një moment për të përfunduar labirintin.

Hapi 1: Nis rreshti i parë

• Caktoni çdo qelizë në rresht një ID unike të vendosur.

Hapi 2: Bashkohu me disa qeliza ngjitur horizontalisht

• Shkrini rastësisht qelizat ngjitur duke i vendosur ato në të njëjtin letërnjoftim të vendosur. Kjo siguron që ka kalime horizontale.

Hapi 3: Krijo lidhje vertikale me rreshtin tjetër

• Për çdo set që shfaqet në rresht, të paktën një qelizë duhet të lidhet poshtë (për të siguruar lidhshmërinë).
• Zgjidhni rastësisht një ose më shumë qeliza nga çdo set për t'u lidhur me rreshtin tjetër.

Hapi 4: Kaloni në rreshtin tjetër

• Transportoni përpara lidhjet vertikale duke caktuar të njëjtin ID të vendosur në qelizat përkatëse më poshtë.
• Caktoni ID të reja të vendosura në çdo qelizë të pacaktuar.

Hapi 5: Përsëriteni hapat 2-4 deri në arritjen e rreshtit të fundit

• Vazhdoni përpunimin rresht pas rreshti.

Hapi 6: Përpunoni rreshtin përfundimtar

• Sigurohuni që të gjitha qelizat në rreshtin e fundit t'i përkasin të njëjtit set duke shkrirë çdo set të mbetur të veçantë.