Folosirea generării procedurale în industria jocurilor [622010]

Folosirea generării procedurale în industria jocurilor
pentru a realiza medii realiste
Galea Ștefan -Andrei
Universitatea Transilvania din Brașov, Facultatea de Matematică și Informatică,
Profilul Informatică Aplicată, anul 1

Abstract
Jocurile pe calculator reprezintă o categorie de aplicații software care s -a dezvoltat substan țial
în ultimii ani, astfel încat a devenit una dintre cele mai profitabile industrii. Acest referat
prezintă dezvoltarea unui algoritm de bază folosit p entru generarea unui teren cu scopul de a
crea peisaje realiste.

1
Cuprins
Introducere ………………………….. ………………………….. ………………………….. ………………………….. …………………… 1
Conținut ………………………….. ………………………….. ………………………….. ………………………….. ……………………….. 2
Algoritmul Perlin Noise ………………………….. ………………………….. ………………………….. ……………………….. 2
Aplicarea algoritmului Noise pe un plan ………………………….. ………………………….. …………………………. 4
Diviziunea în regiuni și secțiuni ………………………….. ………………………….. ………………………….. …………… 5
Implementarea biomurilor ………………………….. ………………………….. ………………………….. ………………….. 6
Aplicarea texturilor pe teren ………………………….. ………………………….. ………………………….. ……………….. 7
Generarea vegetației ………………………….. ………………………….. ………………………….. ………………………….. . 8
Optimizări și procesul final de generare ………………………….. ………………………….. …………………………. 9
Concluzie ………………………….. ………………………….. ………………………….. ………………………….. ……………………. 11
Bibliografie ………………………….. ………………………….. ………………………….. ………………………….. …………………. 12

1

Introducere
Jocurile pe calculator reprezintă în momentul actual una dintre cele mai mari industrii datorită
numărului mare de utilizatori. Una dintre cele mai mari inova ții în acest domeniu se consideră
generarea aleatorie a mediului înconjurător deoarece jucătorul nu mai observă constant
același mediu și este determinat să descopere noi peisaje. Cea mai mare influen ță în
dezvolt area acestei tehnologii o are Ken Perlin, deoarece el a dezvoltat algoritmul Perlin Noise
pentru a crea ,,reprezentări foarte convingătoare de nori, foc, apă, stele…” [1]. Acest algoritm
are scopul de a genera valori pseudo -aleatorii cu regula că valorile vecine unui punct ales sunt
apropiate de acesta . (Fig. 1 .a).
Știind că orice obiect dintr -un joc tridimensional este format din o multitudine de poligoane de
diferite rota ții și dimensiuni, dezvoltatorii au reușit să implementeze algoritmul lui Perlin
pentru a genera teren de diferite dimensiuni creând un pătrat divizat î n triunghiuri la care
fiecare vârf este mutat în înăl țime cu 𝑁𝑜𝑖𝑠𝑒 (𝑥,𝑦) unită ți (Fig. 1.b), unde Noise este algoritmul
lui Ken Perlin.
Am decis să dezvolt tehnica de mai sus prin combinarea a mai multor nivele de Noise și
adăugarea de reguli de generare în func ție de biom, înăl țime, materialul terenului plus
generarea vegeta ției în fiecare dintre situa țiile prezentate. Implementarea algor itmilor va fi
realizată în limbajul C# cu ajutorul programului Unity.

Fig. 1 .a – Valori Aleatorii vs Valori Perlin
Fig. 1.b – Noise() aplicat pe un plan [16]

2
Conținut
Algoritmul Perlin Noise
K. Perlin reușește în articolul ,,Improving Noise’’ [2] să își îmbunătățească algoritmul ini țial
creat. Noul algoritm acceptă ca parametrii 2 coordonate x și y, apoi returnează o valoare
inclusă în intervalul [−1,1]. Inițial, se definesc 2 variabile X, Y care primesc ca valoare
𝐹𝑙𝑜𝑜𝑟𝑇𝑜𝐼𝑛𝑡 (𝑥)1, respecti v 𝐹𝑙𝑜𝑜𝑟𝑇𝑜𝐼𝑛𝑡 (𝑦) pentru a afla coordonatele întregi ale pătratului în
care se află punctul 𝐼𝑛𝑝𝑢𝑡 (𝑥,𝑦). După aceea, x și y primesc 𝑥 𝑟𝑒𝑠𝑝𝑒𝑐𝑡𝑖𝑣 𝑦−
𝐹𝑙𝑜𝑜𝑟 (𝑥 𝑟𝑒𝑠𝑝𝑒𝑐𝑡𝑖𝑣 𝑦) , cu scopul de a afla distanța relativă de la punct la coordonatele
pătra tului. Urmează să se creeze variabilele u și v care primesc valoarea returnată de funcția
𝐹𝑎𝑑𝑒 (𝑣𝑎𝑙) cu inputul x, apoi y. Perlin definește în articolul său această funcție ca fiind
rezultatul polinomului 6𝑡5−15𝑡4+10𝑡3. Aceast a are rolul de realiza ,,o tranziție lină între 2
valori diferite’’ [3]. Următorul pas îl reprezintă definirea a 2 valori A și B care primesc valori din
tabloul 𝑝𝑒𝑟𝑚 [] în funcție de X, la care se adună Y, cu scopul de a avea valori unice pentru 2
coordonate diferite. Perlin definește perm un tablou de 256 spații care conține pe fiecare
poziție un număr din mulțimea [0,255 ]∩ ℕ, cu proprietatea că toate valorile din acest tablou
sunt diferite între ele. Spre final, se creează 4 vectori cu originea în cele 4 colțuri ale pătratului
și direcții pseudo -aleatorii folosind funcția 𝐺𝑟𝑎𝑑 (ℎ𝑎𝑠ℎ,𝑥,𝑦). Ultimul pas îl reprezintă
calcularea unei medii ponderate între cei 4 vectori descriși mai sus , împreună cu di stanțele
relative u și v, pentru a returna o valoare din intervalul [−1,1].
Respectând indicațiile autorului, algoritmul poate fi implementat în limbajul C# după cum se
poate observa mai jos. Având la dispoziție Perlin Noise, urmează folosirea acestuia pentru a
modifica o suprafață plană dreaptă cu scopul de a obține un aspect de teren natural.

1 Funcție care calculează partea întreagă a numărului introdus ca parametru . [9]

3
Implementare în C# folosind Unity [4]:
public static class Perlin
{
static int[] perm = {
// Cele 256 numere aleatorii
}

static float Grad(int hash, float x, float y)
{
return ((hash & 1) == 0 ? x : -x) + ((hash & 2) == 0 ? y : -y);
}

static float Fade(float t)
{
return t * t * t * (t * (t * 6 – 15) + 10);
}

static float Lerp(int t, int a, int b)
{
return a + t * (b – a);
}

public static float Noise(float x, float y)
{
int X = Mathf.FloorToInt(x) & 0xff ;
int Y = Mathf.FloorToInt(y) & 0xff;
x -= Mathf.Floor(x);
y -= Mathf.Floor(y);
float u = Fade(x);
float v = Fade(y);
int A = (perm[X] + Y) & 0xff;
int B = (perm[X + 1] + Y) & 0xff;
return Lerp(v, Lerp(u, Grad(perm[A ], x, y ), Grad(perm[B ], x -1, y )),
Lerp(u, Grad(perm[A+1], x, y -1), Grad(perm[B+1], x -1, y-1)));
}
}

4

Fig 2.2.a Plan Fig 2.2. c Noise aplicat pe plan [6] Aplicarea algoritmului Noise pe un plan
Primul pas este crearea unui pătrat de lungime 𝑠𝑖𝑧𝑒 care se divizează în pătrățele de lungime
1 conform Fig 2.2.a . Dacă în acest pătrat se aplică pentru fiecare vârf al unei diviziuni cu
coordonatele (𝑥,𝑦) înălțimea de 𝑁𝑜𝑖𝑠𝑒 (𝑥,𝑦), se obține un teren cu diferite forme și înălțimi,
dar care va arăta prea lin și lipsit de detalii. Pentru soluționarea acestei probleme , autorul
canalului de YouTube intitulat Sebastian Lague [5] propune următoarea metodă: se introduc 4
variabile noi: 𝑠𝑐𝑎𝑙𝑒 , 𝑜𝑐𝑡𝑎𝑣𝑒𝑠 , 𝑝𝑒𝑟𝑠𝑖𝑠𝑡𝑎𝑛𝑐𝑒 și 𝑙𝑎𝑐𝑢𝑛𝑎𝑟𝑖𝑡𝑦 , unde 𝑠𝑐𝑎𝑙𝑒 controlează mărimea
sunetului, 𝑜𝑐𝑡𝑎𝑣𝑒𝑠 reprezintă numărul de nivele de noise aplicate unul peste cel ălalt,
𝑝𝑒𝑟𝑠𝑖𝑠𝑡𝑎𝑛𝑐𝑒 controlează scăderea amplitudinii iar 𝑙𝑎𝑐𝑢𝑛𝑎𝑟𝑖𝑡𝑦 modifică creșterea frecvenței
nivelelor conform Fig 2.2.b . Cu aceste noi variabile, se creează o matrice 𝑚𝑎𝑝 de mărimea
𝑠𝑖𝑧𝑒 ∗𝑠𝑖𝑧𝑒 , apoi pentru fiecare dintre indicii 𝑥,𝑦← 0,𝑠𝑖𝑧𝑒 −1 ̅̅̅̅̅̅̅̅̅̅̅̅̅̅ se definesc variabile le 𝑠𝑋,𝑠𝑌 și
ℎ𝑒𝑖𝑔ℎ𝑡 la care pentru fiecare nivel 𝑖 ←0,𝑜𝑐𝑡𝑎𝑣𝑒𝑠 −1 ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅; 𝑠𝑋,𝑠𝑌 ←𝑥 𝑟𝑒𝑠𝑝𝑒𝑐𝑡𝑖𝑣 𝑦
𝑠𝑐𝑎𝑙𝑒∗
𝑙𝑎𝑐𝑢 𝑛𝑎𝑟𝑖𝑡𝑦𝑖+𝑅𝑎𝑛𝑑𝑜𝑚 .𝑅𝑎𝑛𝑔𝑒 (𝑚𝑖𝑛𝑉𝑎𝑙 ,maxVal ). Funcția 𝑅𝑎𝑛𝑑𝑜𝑚 .𝑅𝑎𝑛𝑔𝑒 () ,,returnează o
valoare aleatorie din intervalul [𝑚𝑖𝑛𝑉𝑎𝑙 ,𝑚𝑎𝑥𝑉𝑎𝑙 )’’ [9] și are scopul de a genera nivele diferite
pentru aceleași coordonate. După aceea se definește variabila 𝑝𝑒𝑟𝑙𝑖𝑛𝑉𝑎𝑙 ←𝑁𝑜𝑖𝑠𝑒 (𝑠𝑋,𝑠𝑌)∗
2−1 ∈[−1,1] care este folosită pentru a afla ℎ𝑒𝑖𝑔ℎ𝑡 ← 𝑝𝑒𝑟𝑙𝑖𝑛𝑉𝑎𝑙 ∗ 𝑝𝑒𝑟𝑠𝑖𝑠𝑡𝑎𝑛𝑐𝑒𝑖 care
este atribuită lui 𝑚𝑎𝑝 𝑥,𝑦. Pasul final este atribuirea pentru fiecare vârf de coordonate (𝑥,𝑦) al
oricărui pătrățel, înălțimea de 𝑚𝑎𝑝 𝑥,𝑦 unități , astfel generând unui teren de mă rime 𝑠𝑖𝑧𝑒 ∗𝑠𝑖𝑧𝑒
care arată natural (Fig. 2.2. c) . Urmează divizarea terenului în regiuni și secțiuni cu scopul de a
mări eficiența de creare a terenului.

Fig 2.2. b Combinarea mai multor nivele de Noise

5

Fig 2. 3.a Diviz iunea în regiuni și secțiuni
Generarea unui singur teren de dimensiuni uriașe ar fi extraordinar de ineficient ă și ar scădea
substanțial performanța jocurilor, așadar dezvoltatorii de jocuri precum Minecraft au rezolvat
această problemă prin divizarea hărții în secțiuni și regiuni. În acest joc, secțiunile sunt ,,metoda
folosită de gener atorul de teren pentru divizarea hărții în bucăți ce pot fi procesate cu ușurință’’
[7] iar regiunile sunt ,,o formă de reținere a informațiilor desp re o secțiune de teren formată
din o grupă de 32×32 secțiuni’’ [8]. În acest referat, o secțiune va fi considerată un pătrat de
latură N unități pe care se aplică algoritmul Noise descris în capitolul anterior și care are ca
poziție centrul pătratului, iar o regiune va fi un grup de 𝑀∗𝑀 secțiuni.
Dacă se generează 2 s ecțiuni alăturate, se observă următoarea problemă: marginile acestora
nu se unesc din cauza naturii aleatorie a algoritmului 𝑁𝑜𝑖𝑠𝑒 (𝑥,𝑦). În videocli purile intitulate
,,Procedural Landmass Generation’’ [5], Sebastian soluționează această problemă adăugând
un inel de vârfuri în plus, situate de -a lungul laturilor pătratului (Fig. 2.3.a) . Pentru simplificare,
unirea dintre 2 vârfuri din 2 secțiuni diferite notate 𝐴(𝑥𝑎,𝑦𝑎,𝑧𝑎) și 𝐵(𝑥𝑏,𝑦𝑏,𝑧𝑏) se va face în
vârful 𝐶(𝑥𝑎+𝑥𝑏
2,𝑦𝑎+𝑦𝑏
2,𝑧𝑎+𝑧𝑏
2) conform Fig 2.3.b cu precizarea că tranziția dintre 2 secțiuni va fi
din ce în ce mai naturală și mai lină cu cât se adaugă mai multe vârfuri între A și B. Astfel,
folosind această metodă, terenul generat nu prezintă goluri la îmbinările dintre bucățile
acestuia.
Pasul următor îl reprezintă modificarea generatorului de secțiuni în funcție de ecosistemul în
care se află prin implementarea biomurilor.

A
Secțiune 1
B
Secțiune 2
C
Fig 2. 3.b

6
Implementarea biomurilor
Un biom reprezintă ,,un complex de ecosisteme, având un teritoriu mare, factori abiotici
specifici și o floră și o faună specifică’’ [10] . În industria jocurilor, biomurile sunt folo site pentru
a decide tipul de teren, vegetația și fauna într -o anumită locație.
Inițial, se definește o clasă 𝐵𝑖𝑜𝑚𝑒 care conține informațiile descrise mai sus. Pentru
controlarea reliefului, fiecare instanță a clasei conține 3 variabile care decid fre cvența, numărul
de nivele de Perlin Noise și amplitudinea terenului în biomul curent. De exemplu, într -o zonă
muntoasă este necesar un sol accidentat și greu accesibil , față de o câmpie care necesită
tranziții line între zonele diferite ale acesteia. Acest lucru se poate realiza modificând cele 3
valori atunci când se generează terenul.
Urmează ca pentru fiecare ecosistem să se definească tipul de vegetație, fauna și texturile care
trebuie folosite în acesta. Într -o zonă muntoasă se vor folosi de exemplu te xturi de iarbă, roci
sau zăpadă, iar ca vegetație poate predomina pădurea de conifere și animalele specifice
acestei zone. Pentru fiecare ecosistem diferit, trebuie modificați acești parametrii până la
obținerea unui rezultat bun și conform cu realitatea.
Pasul final îl reprezintă generarea unui noise -map2 𝑏𝑖𝑜𝑚𝑒𝑠 care va decide pentru fiecare
secțiune de teren ce biom se va folosi. Acest lucru se realizează adăugând fiecărui biom un
identificator numeric unic din intervalul [−1,1]. Având un ID unic pentru fiecare biom, se poate
afla pentru orice secțiune de teren ce ecosistem se va aplica peste aceasta.
Prin acest proces s -a realiz at implementarea de ecosisteme aleatoriu generate care au
proprietăți diferit e conform cu realitatea . Urmează aplicarea texturilor pe terenul generat.

2 Un noise -map reprezintă o matrice care conține valori ale funcției Noise în funcție de indicii acesteia.

7
Aplicarea texturilor pe teren

Texturile sunt ,,imagini care sunt transferate către GPU și sunt aplicate obiectului în faza finală
de redare a ecranului’ ’’ [12] . H. Serrano explică metoda de aplicare a unei texturi pe un obiect:
acesta este tăiat astfel încât să se poată așeza pe un spațiu 2D, apoi fiecare vârf al rezultatului
este așezat pe textură ca programul să știe pentru fiecare poligon al obiectului ce parte din
textură să aplice [12] .
În momentul actual, terenul generat are forma dorită însă este lipsit de orice fel de culoare.
Pentru a soluționa această problema, pe acesta trebuie aplicate texturi în funcție de ecosistem ,
înălțime și cât e ste de abrupt.
Primul pas este definirea unui vector de texturi pentru fiecare biom . Pentru fiecare element al
vectorului, se va alege o imagine corespunzătoare ecosistemului curent. De exemplu , un peisaj
muntos va avea nevoie de texturi precum iarbă, roci și zăpadă.
Pentru fiecare textură se definește înălțimea și panta3 maxime la care aceasta poate să apară,
apoi, pentru fiecare secțiune de teren, se aplică texturile biomului curent, acestea respectând
proprietățile descrise mai sus.
Folosind această tehnică, s -a reușit aplicarea texturilor pe teren astfel încât acesta s ă aibă un
aspect natural. Urmează să se dezvolte o metodă de generare a vegetației în funcție de
ecosistemul curent , lucru care este discutat în capitolul următor.

3 Panta reprezintă înclinația într -un punct al terenului.

8
Generarea vegetației
Vegetația reprezintă un element foarte important în aspectul unui ec osistem. Pentru fiecare
biom în parte, se definesc în clasa 𝐵𝑖𝑜𝑚𝑒𝑠 tipurile de plante prezente în ecosistem și frecvența
acestora . Pentru copaci, tufișuri și alte plante de dimensiuni mari, se vor folosi obiecte create
în programe de 3D Computer Grap hics, precum Blender.
În multe ecosisteme întâlnim iarbă sau plante mici și dese care nu pot fi reprezentate prin
obiecte tridimensionale complexe . În articolul ,,Chapter 7. Rendering Countless Blades of
Waving Grass’’ [11] , K. Pelzer și P. Bytes descriu o metodă de generare eficientă a acestora.
Aceștia aplică textura plantei pe mai multe poligoane, apoi le așază î n formă de stea, cum se
poate observa în Fig 2. 6. Pasul final este adăugarea multor forme de acest fel pe teren pentru
obținerea unui rezultat realist precum cel din Fig 2. 6.
Pentru obiectele de dimensiuni mari, se va folosi un noise -map pentru fiecare tip de plantă și
se va alege o valoare 𝑝𝑙𝑎𝑛𝑡𝐼𝐷 din intervalul [−1,1] care să reprezinte punctul în care să apară
aceasta. Astfel, pentru fiecare 𝑛𝑜𝑖𝑠𝑒𝑀𝑎𝑝 𝑖,𝑗==𝑝𝑙𝑎𝑛𝑡𝐼𝐷 , se va amplasa planta respectivă pe
teren.
Implementând și vegetația, s -a obținut un teren complet, detaliat și natural. Ultimul pas în
procesul total de generare îl reprezintă creșterea eficienței de creare și redare a acestuia .
Fig 2. 6 [11]

9
Optimizări și procesul final de generare
Folosind tehnicile descrise mai sus, s -a obținut un teren foarte asemănător cu realitatea, însă
proces ul de creare se poate optimiza folosind trei concepte: threading , LODs și render distance .
Threading este tehnica de programare care permite ca ,,diferite sarcini să se exec ute în paralel’’
[13] , opus de programarea simplă, la care o instrucțiune se execută abia după ce anterioara s –
a finalizat. În procesul de generare a reliefului, se va folosi această metodă pentru a crea
secțiunile de teren în paralel (Fig. 2.7.a) . Astfel, generarea se realizează mult mai rapid și
eficient.
A doua optimizare este implementarea LOD -urilor (level of detail) . Acestea ,,reprezintă
complexitatea reprezentării unui obiect 3D. LOD poate fi simplificat după cum se depărtează
obiectul de cameră’’ [14] (Fig 2.7.b) . Pentru a mări eficiența jocului, se va genera pentru fiecare
secțiune de teren un număr 𝑙𝑜𝑑𝑠𝐶𝑜𝑢𝑛𝑡 de nivele de detalii, astfel încât cu cât se mărește
distanța dintre o secțiune și cameră, va scădea numărul de poligoane din componența
obiectului.
Ultima metodă de creștere a eficienței este definirea unei variabile 𝑟𝑒𝑛𝑑𝑒𝑟𝐷𝑖𝑠𝑡𝑎𝑛𝑐𝑒 care să
controleze numărul maxim de secțiuni care vor fi redate în jurul camerei. Folosind această
tehnică în combinație cu celelalte două, eficie nța aplicației crește semnificativ.

Fig 2.7. b LODs [15]
Start
Generare secțiune 1
Generare secțiune 2
Generare secțiune 3
Fig 2.7. b Threading

10
Având toate etapele de generare a unui teren, mai lipsește programarea procesului complet
de creare a mediilor înconjurătoare. Acesta începe cu generarea regiunii de 𝑁∗𝑁 secțiuni în
care se află jucătorul. Pentru aceasta, se va genera noise -map -ul biomurilor, apoi se creează
fiecare bucată de teren din regiune în paralel. Fiecare secțiune are nevoie de 𝑙𝑜𝑑𝑠𝐶𝑜𝑢𝑛𝑡
reprezentări ale terenului, acestea având un număr din ce în ce mai mic de poligoane. Urmează
aplicarea texturilor pe fiecare obiect. După aceea, fiecare secțiune din regiune trebuie
conectată cu vecinii acesteia ca să nu existe goluri între ele. Pasul final îl reprezintă popularea
terenului cu vegetație, separat pe fiecare bucată din acesta. Schema procesului se poate
observa în Fig. 2.7.c .

Creare
regiune
Generare
𝑐ℎ𝑢𝑛𝑘1,1
Generare
𝑐ℎ𝑢𝑛𝑘𝑁,𝑁
Creare harta
biomuri
Conectare
secțiuni
Generare vegetație
𝑐ℎ𝑢𝑛𝑘1,1
Generare vegetație
𝑐ℎ𝑢𝑛𝑘𝑁,𝑁
Fig 2.7. c Schemă generare teren

11
Concluzie
Referatul acesta a demonstrat cum Perlin Noise, un algoritm destul de simplu, se poate
dezvolta și combina cu alte procedee cu scopul de a genera procedural un mediu înconjurător
natural . Terenul generat are un aspect realist, în care s -au incorporat ecosisteme și vegetație
specifică acestora, oferind rezultatul dorit. Totodată, procesul de creare este optimizat și
eficient, lucru care este foarte important p entru industria jocurilor. Rezultatul final se poate
observa în imaginile de mai jos [17] .

12
Bibliografie
[1]. Ken Perlin, ,,An Image Synthesizer ’’, Vol. 19, Nr. 3, 1985
[2]. Ken Perlin, ,,Improving Noise’’ , 2002
[3]. https://adrianb.io/2014/08/09/perlinnoise.html
[4]. https://github.com/keijiro/PerlinNoise/blob/master/Assets/Perli n.cs
[5]. https://www.youtube.com/channel/UCmtyQOKKmrMVaKuRXz02jbQ
[6]. https://www.scratchapixel.com/lessons/procedural -generation -virtual –
worlds/perlin -noise -part -2/perlin -noise -terrain -mesh
[7]. https://minecraft.gamepedia.com/Chunk
[8]. https://minecraft.gamepedia.com/Region_file_format
[9]. https://docs.unity3d.com/ScriptReference/
[10]. https://ro.wikipedia.org/wiki/Biom
[11]. https://developer.nvidia.com/gpugems/gpugems/part -i-natural -effects/chapter -7-
rendering -countless -blades -waving -grass/
[12]. Harold Serrano, ,,Applying textures in Computer Graphics’’, 2014
[13]. https://en.w ikipedia.org/wiki/Thread_(computing)#Threading_models/
[14]. https://en.wikipedia.org/wiki/Level_of_detail/
[15]. http://vda.univie.ac.at/Teaching/Vis/14s/LectureNotes/09_reduce_navigation.pdf
[16]. https://blog.hirnschall.net/perlin -noise/
[17]. https://cs.brown.edu/courses/cs123/lectures/CS123_23_Final_Project_Topics_2
019.pdf /