Generator labirinta Ellerjevega algoritma

Ellerjev algoritem je algoritem za ustvarjanje 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. Proizvaja labirinte, podobne Kruskalovemu algoritmu, vendar to počne tako, da ustvari samo eno vrstico naenkrat, ne da bi bilo treba shraniti celoten labirint 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 učinkovitem pristopu vrstice za vrstico za ustvarjanje labirintov, zaradi česar je idealen za neskončne labirinte ali labirinte, ustvarjene v realnem času. Običajno se navaja v literaturi o proceduralnem ustvarjanju vsebine in literaturi o ustvarjanju labirintov, vendar nisem mogel najti primarnih virov s podrobnostmi o njegovi prvotni objavi.

Kako deluje Ellerjev algoritem za ustvarjanje labirinta

Ellerjev algoritem obdeluje eno vrstico naenkrat, vzdržuje in spreminja nize povezanih celic. Zagotavlja povezljivost ob izogibanju zankam in učinkovito razširi labirint navzdol.

Teoretično ga je mogoče uporabiti za ustvarjanje neskončnih labirintov, vendar je za zagotovitev, da je ustvarjeni labirint dejansko rešljiv, treba na neki točki preklopiti na logiko "zadnje vrstice", da končate labirint.

1. korak: Inicializirajte prvo vrstico

• Vsaki celici v vrstici dodelite edinstven ID nabora.

2. korak: Vodoravno spojite nekaj sosednjih celic

• Naključno spojite sosednje celice tako, da jih nastavite na isti niz ID. To zagotavlja vodoravne prehode.

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

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

4. korak: Premaknite se v naslednjo vrstico

• Prenesite navpične povezave naprej tako, da dodelite isti ID niza ustreznim celicam spodaj.
• Dodelite nove ID-je nizov vsem nedodeljenim celicam.

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

• Nadaljujte z obdelavo vrstico za vrstico.

6. korak: obdelajte zadnjo vrstico

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