OpenSimplex triukšmas ir žemėlapių generavimas

:programavimas: :maps: :generative:

Mane žavi generuojamų dalykų programavimas. Dalykų tokių kaip muzika, piešiniai, žemėlapiai, ir pan. Šioje srityje neturiu beveik jokios patirties, tad gal todėl man tokie darbai atrodo apgaubti mistikos aura. Ir čia nekalbu apie linijas, pribraižytas tarp atsitiktinių skaičių generatoriaus išdėliotų taškų. Labiau apie tokius, kaip pvz. Here Dragons Abound autoriaus generuojami žemėlapiai.

Pirmas mano sugeneruotas žemėlapis buvo rougelike žaidimui, kurį gaminau pagal Rougelike Tutotrial in Rust. Šis žemėlapis labai paprastas - kambariai ir tuneliai požemyje. Principas maždaug toks:

1. Sugeneruojam keletą stačiakampių. Generuodami tikrinam, kad jie nepersidengtų. Jei sugeneravus matom, kad naujas kambarys persidengtu su jau esančiu - jo nededam į žemėlapį ir generuojam kitą.
2. Žemėlapis turi sujungti visus kambarius požemyje, kad būtų galima po juos vaikščioti. Tad visus kambarius dedam į “nesujungtų” kambarių sąrašą.
3. Atsitiktinai parenkam du kambarius iš sąrašo ir sujungiam juos tuneliu. Surandam, kuriuos stačiakampius naujas tunelis jungia ir juos pašalinam iš neaplankytų sąrašo.
4. Kartojam kol nebelieka neprijungtų kambarių.

Sprendimas paprastas. Rezultatas matomas žemiau. Paveikslėlyje nesimato kai kurių kambarių kraštų, nes žaidime įjungtas “rūkas”. T.y. neaplankytos vietos išlieka nežinomos. Bet iš aplankytų vietų turėtų būti aišku kokio tipo tai žemėlapis.

Šis požemis labai paprastas ir nereikalaujantis jokių papildomų algoritminių žinių. Esu tikras, kad pats būčiau kažką panašaus sugalvojęs. Bet kaip generuoti ne tokį kvadratinį žemėlapį? Su mažiau kampuotom formom, kalnais ir ežerais?

Triukšmo funkcijos

Atsakymas į ankstesnį klausimą atėjo susipažinus su gradientinio triukšmo funkcijomis. Šios funkcijos skirtos generuoti pseudo-atsitiktinį kelių dimensijų paviršių. Paprasčiau suprasti lyginant jas su pseudo-atsitiktinių skaičių generatoriumi. Jei generuotume 10 skaičių iš eilės su pastaruoju - reikšmės išsidėstytų be jokios tvarkos. Tuo tarpu gradientinio triukšmo funkcijose reikšmės, esančios viena šalia kitos yra sugeneruotos atsitiktinai, bet tuo pačiu artimos viena kitai. Tai suteikia tolygų perėjimą nuo vienos reikšmės, prie kitos. Taip pat šių funkcijų reikšmės yra gaunamos pagal koordinates. Jei funkcija dvimatė - pagal x ir y, jei trimatė - x, y ir z ir t.t. Šios savybės atspindi gamtoje esantį reljefą - nuo ežero dugno iki kalno viršūnės žemės paviršius kyla po truputį.

Viena iš tokių funkcijų yra OpenSimplex, kurios bibliotekų galima rasti bet kokiai programavimo kalbai. Pateikus koordinates, yra grąžinama float reikšmė nuo -1 iki 1. Ką su ja veikti?

Pirmieji bandymai

Pagriebiau vieną iš bibliotekų ir puoliau generuoti 1000x1000 pikselių paveikslėlį. Planas paprastas - prasukti x, y po 1000 kartų, paimti reikšmę iš OpenSimplex funkcijos pagal koordinates ir nupiešti juodą tašką, nustatant alpha (permatomumą) į normalizuotą reikšmę gautą iš funkcijos. Normalizuodamas aš tiesiog perskaičiavau reikšmę, kad ji būtų [0, 1] intervale vietoj [-1, 1].

Hmm, kažkas ne taip. Aš gi planavau generuoti žemėlapį, o iš šito nieko nesigaus. Pastebėjau, kad triukšmo funkcija parametrams tikisi ne int reikšmių, o float. Tai reiškia, kad savo koordinates turiu didinti ne po 1, o po mažesnę reikšmę, pvz. 0.1. Pabandom.

Čia jau kažkas panašaus ko tikėjausi. Dar sumažinęs žingsnį gaučiau dar labiau priartiną vaizdą. Dabar vietoj to, kad naudočiau alpha reikšmę, nusprendžiau tašką spalvinti juodai, jei normalizuota reikšmė iš funkcijos yra daugiau nei 0.7, o kitu atveju - baltai.

Paskui pradėjau dar žaisti. Eksperimentavau įvairiai: pridėdamas atsitiktinių skaičių generatorių, keisdamas žingsnius ir t.t. Žemiau esančiame pavyzdyje x žingsnis keičiamas po 0.5, o y - po 0.05. Gaunamas toks “ištemptas” rezultatas.

Žemėlapis

Kadangi triukšmo funkcija grąžina reikšmę intervale [-1, 1] (normalizavus nuo 0 iki 1) - galiu nuspręsti, kad jei reikšmė mažiau už 0.2, tai bus vanduo, nuo 0.2 iki 0.4 - smėlis, nuo 0.4 - pievos, nuo 0.6 - miškas ir t.t. Šiuos sluoksnius spalvinti atitinkamomis spalvomis, pvz. panaudojus Whittaker diagramą. Jei pvz. kuriam nors sluoksniui suteiksim mažesnį rėžį, tai jis taps siauresnis. Pvz. norint plačių paplūdimių, smėlio sluoksnį galime brėžti kai triukšmo reikšmė yra nuo 0.2 iki 0.6 (0.4) ir atvirkščiai. Sugeneruotas žemėlapis atrodo taip:

Kaip pradžiai, gal ir nieko. Yra keli dalykai ateičiai:

1. Nepatinka generavimo greitis. Kadangi generuoju 1000^2 pikselių atskirai - tai užtrunka. Žinoma, galima optimizuoti išlygiagretinant kodą, bet aš planuoju vietoj pikeslių panaudoti sprite’us. Sprite’ų ekrane bus mažiau, nei pikselių. Tada žingsnį galėsiu daryti didesnį ir nereiks piešti kiekvieno pikselio atskirai.
2. Objektai žemėlapyje labai išmėtyti - kalnas, ežeras, kalnas, ežeras… Norėčiau realistiškesnio reljefo, upių.
3. Šį patį žemėlapį norėčiau pamatyti 3D. Tai būtų ganėtinai nesunku, radus tinkamą biblioteką.