Elleri algoritmi labürindi generaator

Elleri algoritm on labürindi genereerimise algoritm, mis loob rida-realt lähenedes tõhusalt täiuslikke labürinte (labürinte ilma silmusteta ja ühe teega mis tahes kahe punkti vahel). See loob labürinte, mis on sarnased Kruskali algoritmiga, kuid teeb seda genereerides korraga ainult ühe rea, ilma et oleks vaja kogu labürinti mällu salvestada. See teeb selle kasulikuks väga suurte labürintide genereerimiseks väga piiratud süsteemides ja protseduurilise sisu genereerimiseks.

Täiuslik labürint on labürint, kus on täpselt üks tee labürindi mis tahes punktist mis tahes teise punkti. See tähendab, et te ei saa sattuda ringiratastesse, kuid sageli satute ummikteedesse, mis sunnib teid ümber pöörama ja tagasi minema.

Siin genereeritud labürindi kaardid sisaldavad vaikimisi versiooni ilma algus- ja lõpp-punktideta, nii et saate need ise otsustada: labürindi mis tahes punktist mis tahes teise punkti on olemas lahendus. Kui soovite inspiratsiooni, saate lubada soovitatud algus- ja lõpupositsiooni - ja isegi näha lahendust nende kahe vahel.

Elleri algoritmi kohta

Elleri algoritmi tutvustas David Eller.

Algoritm on tähelepanuväärne oma tõhusa rida-realt lähenemise poolest labürindi genereerimisel, mis teeb sellest ideaalse lahenduse lõpmatute või reaalajas genereeritud labürintide jaoks. Seda tsiteeritakse sageli protseduurilise sisu genereerimise ja labürindi genereerimise kirjanduses, kuid ma ei ole suutnud leida algseid avaldamist kirjeldavaid allikaid.

Kuidas Elleri algoritm labürindi genereerimiseks töötab

Elleri algoritm töötleb korraga ühte rida, säilitades ja muutes ühendatud lahtrite komplekte. See tagab ühenduvuse, vältides samal ajal tsükleid, ning pikendab labürinti tõhusalt allapoole.

Teoreetiliselt saab seda kasutada lõpmatute labürintide genereerimiseks, kuid selleks, et loodud labürint oleks tegelikult lahendatav, on vaja mingil hetkel lülituda "viimase rea" loogikale, et labürint lõpetada.

1. samm: esimese rea initsialiseerimine

• Määrake igale rea lahtrile unikaalne komplekti ID.

2. samm: ühendage mõned külgnevad lahtrid horisontaalselt

• Ühenda külgnevad lahtrid juhuslikult, määrates neile sama komplekti ID. See tagab horisontaalsete lõikude olemasolu.

3. samm: looge vertikaalsed ühendused järgmise reaga

• Iga reas kuvatava komplekti kohta peab vähemalt üks lahter olema allapoole ühendatud (ühenduvuse tagamiseks).
• Vali igast komplektist juhuslikult üks või mitu lahtrit, et need järgmise reaga ühendada.

4. samm: liikuge järgmisele reale

• Kandke vertikaalsed ühendused edasi, määrates vastavatele allpool olevatele lahtritele sama komplekti ID.
• Määrake määramata lahtritele uued komplekti ID-d.

5. samm: korrake samme 2–4, kuni jõutakse viimase reani

• Jätka töötlemist rida-realt.

6. samm: töötle viimane rida

• Veenduge, et kõik viimase rea lahtrid kuuluvad samasse komplekti, ühendades kõik ülejäänud eraldi komplektid.

Lisalugemist

Kui see postitus teile meeldis, võivad teile meeldida ka need soovitused:

• Rekursiivne Backtracker labürindi generaator
• Wilsoni algoritmi labürindi generaator
• Jahti ja Tappa Labürindi Loodur