Kuinka koodata oma menettelytapasi karttasuunnittelija Random Walk -algoritmin avulla

Teknologian kehittyessä ja pelien sisällön muodostuessa entistä algoritmisemmin, ei ole vaikea kuvitella luomista elämällisestä simulaatiosta, jolla on jokaiselle pelaajalle ainutlaatuiset kokemukset.

Teknologiset läpimurtot, kärsivällisyys ja hienostuneet taidot saavat meidät sinne, mutta ensimmäinen askel on ymmärtää menettelysisällön tuottaminen.

Vaikka karttojen luomiseen on olemassa monia valmiita ratkaisuja, tämä opetusohjelma opettaa sinua tekemään oman kaksiulotteisen vankityrmäkarttageneraattorin tyhjästä JavaScriptin avulla.

Kaksiulotteisia karttatyyppejä on monia, ja kaikilla on seuraavat ominaisuudet:

1. Esteetön alue ja esteettömät alueet (tunnelit ja seinät).

2. Yhdistetty reitti, jonka soitin voi navigoida.

Tämän opetusohjelman algoritmi on peräisin Random Walk Algorithmista, joka on yksi yksinkertaisimmista ratkaisuista kartan luomiseen.

Tehtyään ruudukkoisen seinäkartan, tämä algoritmi alkaa satunnaisesta kohdasta kartalla. Se jatkaa tunnelien tekemistä ja ottaa satunnaisia ​​käännöksiä halutun määrän tunneleita suorittamiseksi.

Jos haluat nähdä esittelyn, avaa alla oleva CodePen-projekti, napsauta karttaa luodaksesi uuden kartan ja muuta seuraavia arvoja:

  1. Mitat: kartan leveys ja korkeus.
  2. MaxTunnels: eniten kierroksia, joita algoritmi voi tehdä karttaa luotaessa.
  3. MaxLength: Kunkin tunnelin suurin pituus, jonka algoritmi valitsee ennen vaaka- tai pystysuuntaista käännöstä.

Huomaa: mitä suurempi maxTurn on verrattuna mittoihin, sitä tiheämpi kartta on. Mitä suurempi maxLength on verrattuna mittoihin, sitä “tunnelin y” se näyttää.

Seuraavaksi käydään läpi kartanmuodostusalgoritmi nähdäksesi kuinka se:

  1. Tekee seinämien kaksiulotteisen kartan
  2. Valitsee satunnaisen lähtöpisteen kartalla
  3. Tunnelien lukumäärä ei ole nolla
  4. Valitsee satunnaisen pituuden suurimmasta sallitusta pituudesta
  5. Valitsee satunnaisen suunnan kääntyäksesi (oikealle, vasemmalle, ylös, alas)
  6. Piirrä tunneli siihen suuntaan välttäen kartan reunoja
  7. Vähentää tunneleiden määrää ja toistaa samalla silmukan
  8. Palauttaa muutosten kartan

Tämä silmukka jatkuu, kunnes tunnelien lukumäärä on nolla.

Algoritmi koodissa

Koska kartta koostuu tunneli- ja seinäsoluista, voisimme kuvata sitä nolla- ja kaksidimensionaalisessa taulukossa seuraavasti:

kartta = [[1,1,1,1,0],
       [1,0,0,0,0],
       [1,0,1,1,1],
       [1,0,0,0,1],
       [1,1,1,0,1]]

Koska jokainen solu on kaksiulotteisessa taulukossa, voimme käyttää sen arvoa tuntemalla sen rivin ja sarakkeen, kuten kartta [rivi] [sarake].

Ennen algoritmin kirjoittamista tarvitset auttajatoiminnon, joka ottaa merkin ja ulottuvuuden argumentteina ja palauttaa kaksiulotteisen taulukon.

createArray (numero, mitat) {
    var-matriisi = [];
    varten (var i = 0; i 

Aseta Random Walk -algoritmi asettamalla kartan mitat (leveys ja korkeus), themaxTunnels-muuttuja ja themaxLength-muuttuja.

createMap () {
 olkoot mitat = 5,
 maxTunnels = 3,
 maksimipituus = 3;

Seuraavaksi tee kaksiulotteinen taulukko käyttämällä ennalta määritettyä auttajatoimintoa (niistä kaksiulotteinen ryhmä).

anna map = luodaArray (1, mitat);

Aseta satunnainen sarake ja satunnainen rivi luodaksesi satunnainen lähtökohta ensimmäiselle tunnelille.

anna currentRow = Math.floor (Math.random () * mitat),
    currentColumn = Math.floor (Math.random () * mitat);

Diagonaalisten käännösten monimutkaisuuden välttämiseksi algoritmin on määritettävä vaaka- ja pystysuunta. Jokainen solu istuu kaksiulotteisessa taulukossa ja se voidaan tunnistaa rivillä ja sarakkeilla. Tämän vuoksi ohjeet voitaisiin määritellä vähennyksinä ja / tai lisäyksinä sarake- ja rivinumeroihin.

Voit esimerkiksi siirtyä soluun solun [2] [2] ympärillä suorittamalla seuraavat toiminnot:

  • mennä ylöspäin, vähennä 1 sen riviltä [1] [2]
  • mennä alas, lisää 1 sen riville [3] [2]
  • mennä oikealle lisäämällä sarakkeeseen 1 [2] [3]
  • mennä vasemmalle, vähennä 1 sen sarakkeesta [2] [1]

Seuraava kartta kuvaa näitä toimintoja:

Näytetään reittiohjeet kartalla.

Aseta nyt suuntamuuttuja seuraaviin arvoihin, joista algoritmi valitsee ennen jokaisen tunnelin luomista:

laske ohjeet = [[-1, 0], [1, 0], [0, -1], [0, 1]];

Lopuksi aloita randomDirection-muuttuja pitämään satunnainen arvo suuntajoukosta ja aseta lastDirection-muuttuja tyhjäksi taulukkoksi, joka pitää vanhemman randomDirection-arvon.

Huomaa: lastDirection-taulukko on tyhjä ensimmäisellä silmukalla, koska vanhaa randomDirection-arvoa ei ole.

anna lastDirection = [],
    randomDirection;

Seuraavaksi varmista, että maxTunnel ei ole nolla ja mitat ja maxLengthvalues ​​on saatu. Jatka satunnaisten ohjeiden löytämistä, kunnes löydät sellaisen, joka ei ole käänteinen tai identtinen lastDirection-ohjeen kanssa. Tämän tekeminen silmukan avulla estää äskettäin piirretyn tunnelin korvaamisen tai kahden tunnelin vetämisen vastakkain.

Esimerkiksi, jos lastTurn on [0, 1], do while -silmukka estää toimintoa siirtymästä eteenpäin, kunnes randomDirection on asetettu arvoon, joka ei ole [0, 1] tai päinvastainen [0, -1].

tee {
randomDirection = suunnat [Math.floor (Math.random () * direction.length)];
} while ((randomDirection [0] === -lastDirection [0] &&
          randomDirection [1] === -lastDirection [1]) ||
         (randomDirection [0] === lastDirection [0] &&
          randomDirection [1] === lastDirection [1]));

Silmukka-do-silmukassa on kaksi pääehtoa, jotka jaetaan ||: lla (TAI) -merkki. Ehdon ensimmäinen osa koostuu myös kahdesta ehdosta. Ensimmäinen tarkistaa, onko randomDirection'n ensimmäinen kohde viimeisen Direction'in ensimmäisen alkion käänteinen. Toinen tarkistaa, onko randomDirectionin toinen kohta viimeisen käännöksen toisen kohdan kääntöpiste.

Havainnollistaakseni, jos lastDirection on [0,1] ja randomDirection on [0, -1], ehdon ensimmäinen osa tarkistaa, onko randomDirection [0] === - lastDirection [0]), joka vastaa 0 == = - 0, ja on totta.

Sitten se tarkistaa onko (randomDirection [1] === - lastDirection [1]), joka vastaa (-1 === -1) ja onko totta. Koska molemmat ehdot ovat totta, algoritmi palaa takaisin löytääkseen toisen satunnaisen suunnan.

Ehdon toinen osa tarkistaa onko molempien taulukkojen ensimmäinen ja toinen arvo samat.

Kun olet valinnut ehdot täyttävän satunnaisen suunnan, aseta muuttuja valitsemaan satunnaisesti pituus maxLength: stä. Aseta tunnelLength-muuttuja nollaan palvelimelle iteraattorina.

anna randomLength = Math.ceil (Math.random () * maxLength),
    tunnelipituus = 0;

Tee tunneli kääntämällä solujen arvo yhdestä nollaan, kun tunnelin pituus on pienempi kuin randomLength. Jos silmukan sisällä tunneli osuu kartan reuniin, silmukan tulisi katketa.

while (tunnelLength 

Muuta asettaa kartan nykyisen solun nollaksi käyttämällä currentRow ja currentColumn. Lisää arvot randomDirection-taulukkoon asettamalla currentRow ja currentColumn, missä niiden on oltava tulevassa silmukan iteraatiossa. Nyt lisää tunnelinpituuden iteraattoria.

else {
  kartta [currentRow] [currentColumn] = 0;
  currentRow + = randomDirection [0];
  currentColumn + = randomDirection [1];
  tunnelLength ++;
 }
}

Kun silmukka on muodostanut tunnelin tai murtunut osumalla kartan reunaan, tarkista, onko tunneli vähintään yhden lohkon pituinen. Jos näin on, aseta viimeiseen suuntaan randomDirection ja pienennä maxTunnels ja mene takaisin tekemään uusi tunneli toisella randomDirection.

if (tunnelLength) {
 lastDirection = randomDirection;
 maxTunnels--;
}

Tämä IF-lauseke estää for-silmukan, joka osuu kartan reunaan ja joka ei ole luonut ainakin yhden solun tunnelia maxTunnelin pienentämiseksi ja viimeisen suunnan muuttamiseksi. Kun näin tapahtuu, algoritmi etsii toisen randomDirection-toiminnon jatkaakseen.

Kun se lopettaa tunneleiden piirtämisen ja maxTunnels on nolla, palauta tuloksena oleva kartta kaikilla kierroksillaan ja tunneleihinsa.

}
 paluukartta;
};

Voit nähdä täydellisen algoritmin seuraavasta katkelmasta:

Onnittelut tämän oppaan lukemisesta. Sinulla on nyt hyvät valmiudet tehdä oma kartan luominen tai parantaa tätä versiota. Tutustu projektiin CodePenissä ja GitHubissa reagointisovelluksena.

Älä unohda jakaa projektiasi kommenttiosioon. Jos pidit tästä projektista, anna sille joitain claps ja seuraa minua samanlaisia ​​opetusohjelmia.

Erityiset kiitokset Tomille (@ moT01 Gitterillä) tämän artikkelin kirjoittamisesta.