Elleri algoritmi labürindi generaator

Elleri algoritm on labürindi genereerimise algoritm, mis loob tõhusalt täiuslikke labürinte (ilma silmusteta labürindid ja mis tahes kahe punkti vahel on üks tee), kasutades ridade kaupa. See loob Kruskali algoritmiga sarnaseid labürindid, kuid teeb seda korraga vaid ühe rea genereerimisega, ilma et oleks vaja kogu labürinti mällu salvestada. See muudab selle kasulikuks väga suurte labürintide loomiseks 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 selle tõhusa rida-realt lähenemise poolest labürindi genereerimisele, mistõttu on see ideaalne lõpmatute labürindi või reaalajas genereeritud labürindi jaoks. Seda tsiteeritakse tavaliselt protseduurilise sisu loomise ja labürindi loomise kirjanduses, kuid ma ei ole suutnud leida algallikaid, mis kirjeldaksid selle algset avaldamist.

Kuidas Elleri algoritm labürindi genereerimise jaoks töötab

Elleri algoritm töötleb ühte rida korraga, säilitades ja muutes ühendatud rakkude komplekte. See tagab ühenduvuse, vältides samal ajal silmuseid, ja laiendab labürinti tõhusalt allapoole.

Teoreetiliselt saab seda kasutada lõpmatute labürindite genereerimiseks, kuid selleks, et tagada loodud labürindi tegelik lahendatavus, tuleb labürindi lõpetamiseks mingil hetkel lülituda "viimase rea" loogikale.

1. samm: lähtestage esimene rida

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

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

• Ühendage külgnevad lahtrid juhuslikult, määrates neile sama komplekti ID. See tagab horisontaalsete läbipääsude olemasolu.

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

• Iga real kuvatava komplekti jaoks peab vähemalt üks lahter allapoole ühendama (ühenduvuse tagamiseks).
• Järgmise reaga ühendamiseks valige igast komplektist juhuslikult üks või mitu lahtrit.

4. samm: liikuge järgmisele reale

• Edastage vertikaalsed ühendused, määrates allolevatele vastavatele lahtritele sama komplekti ID.
• Määrake määramata lahtritele uued komplekti ID-d.

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

• Jätkake töötlemist ridade kaupa.

6. samm: töötlege viimane rida

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