Ellerin algoritmin sokkelogeneraattori
Julkaistu: 16. helmikuuta 2025 klo 19.58.35 UTC
Labyrinttigeneraattori, joka käyttää Ellerin algoritmia täydellisen sokkelon luomiseen. Tämä algoritmi on mielenkiintoinen, koska se vaatii vain nykyisen rivin (ei koko sokkelon) säilyttämisen muistissa, joten sillä voidaan luoda erittäin suuria sokkeloita jopa hyvin rajoitetuissa järjestelmissä.Eller's Algorithm Maze Generator
Ellerin algoritmi on sokkeloiden luomisalgoritmi, joka tuottaa tehokkaasti täydellisiä sokkeloita (sokkeloita, joissa ei ole silmukoita ja yksi polku minkä tahansa kahden pisteen välillä) käyttämällä rivi riviltä -lähestymistapaa. Se tuottaa Kruskalin algoritmin kaltaisia sokkeloita, 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 menettelysisällön luomisessa.
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 huomattava tehokkaasta rivi riviltä -lähestymistavasta sokkeloiden luomiseen, mikä tekee siitä ihanteellisen äärettömiin sokkeloihin tai reaaliajassa luotuihin sokkeloihin. Se on yleisesti lainattu prosessisisällön luomisessa ja labyrinttisukupolven kirjallisuudessa, mutta en ole onnistunut löytämään primäärilähteitä, jotka kertoisivat sen alkuperäisestä julkaisusta.
Kuinka Ellerin algoritmi toimii sokkelosukupolvessa
Ellerin algoritmi käsittelee yhden rivin kerrallaan ylläpitäen ja muokkaaen yhdistettyjen solujen joukkoja. Se varmistaa liitettävyyden välttäen samalla 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 vaihdettava "viimeisen rivin" logiikkaan sokkelon viimeistelemiseksi.
Vaihe 1: Alusta ensimmäinen rivi
- Määritä jokaiselle rivin solulle yksilöllinen joukkotunnus.
Vaihe 2: Liity vierekkäisiin soluihin vaakasuunnassa
- Yhdistä viereiset solut satunnaisesti asettamalla niille sama sarjatunnus. Tämä varmistaa vaakasuorat käytävät.
Vaihe 3: Luo pystysuuntaiset yhteydet seuraavaan riviin
- Jokaisessa rivissä näkyvässä sarjassa vähintään yhden solun on muodostettava yhteys alaspäin (yhteyden varmistamiseksi).
- Valitse satunnaisesti yksi tai useampi solu jokaisesta joukosta muodostaaksesi yhteyden seuraavaan riviin.
Vaihe 4: Siirry seuraavalle riville
- Siirrä pystysuuntaiset yhteydet eteenpäin määrittämällä sama sarjatunnus vastaaviin alla oleviin soluihin.
- Määritä uudet joukkotunnukset kaikille määrittämättömille soluille.
Vaihe 5: Toista vaiheita 2–4, kunnes viimeinen rivi on saavutettu
- Jatka käsittelyä rivi riviltä.
Vaihe 6: Käsittele viimeinen rivi
- Varmista, että kaikki viimeisen rivin solut kuuluvat samaan joukkoon yhdistämällä kaikki jäljellä olevat erilliset joukot.