Ellerin algoritmin sokkelogeneraattori

Ellerin algoritmi on sokkeloiden generointialgoritmi, joka tuottaa tehokkaasti täydellisiä sokkeloita (sokkeloita ilman silmukoita ja vain yhden polun minkä tahansa kahden pisteen välillä) rivi riviltä -lähestymistavalla. Se tuottaa sokkeloita, jotka ovat samanlaisia kuin Kruskalin algoritmi, mutta se tekee sen luomalla vain yhden rivin kerrallaan ilman, että koko sokkeloa tarvitsee tallentaa muistiin. Tämä tekee siitä hyödyllisen erittäin suurten sokkeloiden luomiseen erittäin rajoitetuissa järjestelmissä ja proseduraaliseen sisällön luomiseen.

Täydellinen sokkelo on sokkelo, jossa on täsmälleen yksi reitti mistä tahansa sokkelon pisteestä mihin tahansa toiseen pisteeseen. Tämä tarkoittaa, että et voi päätyä kiertämään ympyrää, mutta joudut usein umpikujaan, jolloin sinun on pakko kääntyä ympäri ja palata takaisin.

Tässä luotuihin sokkelokarttoihin sisältyy oletusversio, jossa ei ole alku- ja loppupisteitä, joten voit päättää ne itse: mistä tahansa sokkelon pisteestä mihin tahansa muuhun pisteeseen on olemassa ratkaisu. Jos haluat inspiraatiota, voit ottaa käyttöön ehdotetun alku- ja maalipaikan - ja jopa nähdä ratkaisun näiden kahden välissä.

Tietoja Ellerin algoritmista

Ellerin algoritmin esitteli David Eller.

Algoritmi on merkittävä tehokkaan rivi riviltä tapahtuvan sokkeloiden luomisen lähestymistavansa ansiosta, mikä tekee siitä ihanteellisen äärettömille sokkeloille tai reaaliajassa luoduille sokkeloille. Sitä mainitaan yleisesti proseduraalisessa sisällön luomisessa ja sokkeloiden luomisessa, mutta en ole löytänyt alkuperäislähteitä, jotka yksityiskohtaisesti kuvaisivat sen alkuperäistä julkaisua.

Kuinka Ellerin algoritmi toimii sokkeloiden luomisessa

Ellerin algoritmi käsittelee yhden rivin kerrallaan, ylläpitäen ja muokkaaen yhdistettyjen solujen joukkoja. Se varmistaa yhdistettävyyden välttäen silmukoita ja laajentaa sokkeloa tehokkaasti alaspäin.

Sitä voidaan teoriassa käyttää äärettömien sokkeloiden luomiseen, mutta sen varmistamiseksi, että luotu sokkelo on todella ratkaistavissa, on jossain vaiheessa tarpeen vaihtaa "viimeisen rivin" logiikkaan sokkelon loppuun saattamiseksi.

Vaihe 1: Alusta ensimmäinen rivi

• Anna rivin jokaiselle solulle yksilöllinen joukko-ID.

Vaihe 2: Yhdistä joitakin vierekkäisiä soluja vaakasuunnassa

• Yhdistä vierekkäiset solut satunnaisesti asettamalla niille sama joukko-ID. Tämä varmistaa, että vaakasuoria kohtia on.

Vaihe 3: Luo pystysuorat yhteydet seuraavaan riviin

• Jokaista rivillä näkyvää joukkoa kohden vähintään yhden solun on oltava yhteydessä alaspäin (yhteyden varmistamiseksi).
• Valitse kustakin joukosta satunnaisesti yksi tai useampi solu yhteyden muodostamiseksi seuraavaan riviin.

Vaihe 4: Siirry seuraavalle riville

• Jatka pystysuuntaisia yhteyksiä määrittämällä sama joukko-ID vastaaville soluille alla.
• Määritä uudet joukko-ID:t kaikille määrittämättömille soluille.

Vaihe 5: Toista vaiheet 2–4, kunnes viimeinen rivi on saavutettu

• Jatka käsittelyä rivi riviltä.

Vaihe 6: Viimeisen rivin käsittely

• Varmista, että kaikki viimeisen rivin solut kuuluvat samaan joukkoon yhdistämällä mahdolliset jäljellä olevat erilliset joukot.

Lisälukemista

Jos pidit tästä postauksesta, saatat pitää myös näistä ehdotuksista:

• Kruskalin algoritmi sokkelogeneraattori
• Wilsonin algoritmin sokkelogeneraattori
• Jahtaa ja Tappaa Labyrintin Generaattori