Generator labirinta Ellerjevega algoritma

Ellerjev algoritem je algoritem za generiranje labirintov, ki učinkovito ustvarja popolne labirinte (labirinte brez zank in z eno samo potjo med katerima koli dvema točkama) z uporabo pristopa vrstica za vrstico. Labirinte ustvarja podobno kot Kruskalov algoritem, vendar to stori tako, da generira le eno vrstico naenkrat, brez potrebe po shranjevanju celotnega labirinta v pomnilnik. Zaradi tega je uporaben za generiranje zelo velikih labirintov na zelo omejenih sistemih in za generiranje proceduralne vsebine.

Popoln labirint je labirint, v katerem obstaja natanko ena pot od katere koli točke v labirintu do katere koli druge točke. To pomeni, da se ne morete vrteti v krogu, vendar boste pogosto naleteli na slepe ulice, zaradi česar se boste morali obrniti in vrniti nazaj.

Tukaj ustvarjeni zemljevidi labirintov vključujejo privzeto različico brez začetnih in končnih položajev, tako da jih lahko določite sami: iz katere koli točke v labirintu do katere koli druge točke obstaja rešitev. Če želite navdih, lahko omogočite predlagana začetni in končni položaj - in si celo ogledate rešitev med njima.

O Ellerjevem algoritmu

Ellerjev algoritem je predstavil David Eller.

Algoritem je znan po svojem učinkovitem pristopu k generiranju labirintov vrstico za vrstico, zaradi česar je idealen za neskončne labirinte ali labirinte, generirane v realnem času. Pogosto se navaja v literaturi o generiranju proceduralne vsebine in generiranju labirintov, vendar nisem mogel najti primarnih virov, ki bi podrobno opisovali njegovo prvotno objavo.

Kako deluje Ellerjev algoritem za generiranje labirinta

Ellerjev algoritem obdeluje eno vrstico naenkrat, pri čemer vzdržuje in spreminja nize povezanih celic. Zagotavlja povezljivost, hkrati pa se izogiba zankam in učinkovito razširja labirint navzdol.

Teoretično se lahko uporablja za generiranje neskončnih labirintov, vendar je za zagotovitev, da je generirani labirint dejansko rešljiv, potrebno na neki točki preklopiti na logiko "zadnje vrstice", da se labirint zaključi.

1. korak: Inicializacija prve vrstice

• Vsaki celici v vrstici dodelite edinstven ID nabora.

2. korak: Vodoravno združite nekaj sosednjih celic

• Naključno združite sosednje celice tako, da jim nastavite isti ID nabora. To zagotavlja, da obstajajo vodoravni prehodi.

3. korak: Ustvarite navpične povezave z naslednjo vrstico

• Za vsak niz, ki se pojavi v vrstici, se mora vsaj ena celica povezati navzdol (da se zagotovi povezljivost).
• Naključno izberite eno ali več celic iz vsakega niza, da jih povežete z naslednjo vrstico.

4. korak: Premaknite se v naslednjo vrstico

• Navpične povezave nadaljujte tako, da ustreznim spodnjim celicam dodelite isti ID nabora.
• Nedodeljenim celicam dodelite nove ID-je nizov.

5. korak: Ponavljajte korake 2–4, dokler ne dosežete zadnje vrstice

• Nadaljujte z obdelavo vrstico za vrstico.

6. korak: Obdelava zadnje vrstice

• Zagotovite, da vse celice v zadnji vrstici pripadajo istemu naboru, tako da združite vse preostale ločene nabore.

Nadaljnje branje

Če vam je bila ta objava všeč, vam bodo morda všeč tudi ti predlogi:

• Rekurzivni Backtracker Maze Generator
• Generator labirinta Kruskalovega algoritma
• Generator labirinta Wilsonovega algoritma