Post on 14-Jan-2020
transcript
UNIVERSITATEA „ALEXANDRU IOAN CUZA” IAŞI
FACULTATEA DE INFORMATICĂ
LUCRARE DE LICENŢĂ
Tanks’ Assault: Aplicarea tehnicilor
inteligenței artificiale în jocurile video şi
integrarea conceptului de fractal
Propusă de
Ungureanu Gh. Teodor-Alexandru
Sesiunea: Februarie, 2017
Coordonator știinţific
Asistent, dr. Vasile Alaiba
UNIVERSITATEA „ALEXANDRU IOAN CUZA” IAŞI
FACULTATEA DE INFORMATICĂ
LUCRARE DE LICENŢĂ
Tanks’ Assault: Aplicarea tehnicilor
inteligenței artificiale în jocurile video şi
integrarea conceptului de fractal
Ungureanu Gh. Teodor-Alexandru
Sesiunea: Februarie, 2017
Coordonator știinţific
Asistent, dr. Vasile Alaiba
DECLARAŢIE PRIVIND ORIGINALITATEA ŞI
RESPECTAREA DREPTURILOR DE AUTOR
Prin prezenta declar că Lucrarea de licență cu titlul „Tanks’s Assault: Aplicarea
tehnicilor inteligenței artificiale în jocuri” este scrisă de mine şi nu a mai fost
prezentată niciodată la o altă facultate sau instituţie de învățământ superior din
ţară sau străinătate. De asemenea, declar că toate sursele utilizate, inclusiv cele
preluate de pe Internet, sunt indicate în lucrare, cu respectarea regulilor de
evitare a plagiatului:
− toate fragmentele de text reproduse exact, chiar şi în traducere proprie din
altă limbă, sunt scrise între ghilimele şi deţin referinţa precisă a sursei;
− reformularea în cuvinte proprii a textelor scrise de către alţi autori deţine
referinţa precisă;
− codul sursă, imagini etc. preluate din proiecte open source sau alte surse
sunt utilizate cu respectarea drepturilor de autor şi deţin referinţe precise;
− rezumarea ideilor altor autori precizează referinţa precisă la textul
original.
Iaşi,
Absolvent Ungureanu Teodor-Alexandru
_________________________
(semnătura în original)
DECLARAŢIE DE CONSIMŢĂMÂNT
Prin prezenta declar că sunt de acord ca Lucrarea de licență cu titlul „Tanks’s
Assault: Aplicarea tehnicilor inteligenței artificiale în jocuri”, codul sursă al
programelor şi celelalte conţinuturi (grafice, multimedia, date de test etc.) care
însoţesc această lucrare să fie utilizate în cadrul Facultăţii de Informatică.
De asemenea, sunt de acord ca Facultatea de Informatică de la Universitatea
„Alexandru Ioan Cuza” Iași să utilizeze, modifice, reproducă şi să distribuie în
scopuri necomerciale programele-calculator, format executabil şi sursă, realizate
de mine în cadrul prezentei lucrări de licenţă.
Iaşi,
Absolvent Ungureanu Teodor-Alexandru
_________________________
(semnătura în original)
1
Cuprins
Cuprins 1
Introducere și motivație 2
0. Cuvânt înainte 2
1. Motivație 2
2. Context 3
3. Cerințe funcționale 6
4. Abordare tehnică 7
5. Zone de risc 7
Contribuții 8
Proiectare 9
0. Arhitectura aplicației 9
1. Șabloane pentru proiectare 12
1.0 Șabloane creaționale 13
1.1 Șabloane comportamentale 15
2. Salvarea datelor 23
Implementare 25
0. Niveluri de dificultate 25
0.1 Algoritmul A* Pathfinding 26
0.2 Curba lui Bézier, 33
1. Optimizare 42
1.0 Binary Heap 42
1.1 Object Pooling 44
2. Generarea Terenului 46
2.0 Fractali 46
2.1 Perlin Noise 48
2.3 Algoritmul Diamond-Square 55
Studiu de caz 58
Unity 62
Concluzii 63
Extensii 63
2
Introducere și motivație
0. Cuvânt înainte
Lucrarea de licență are drept centru de interes aplicarea unor tehnici de inteligență
artificială în conturarea comportamentului inamicilor dintr-un joc. Aplicația va fi disponibilă
exclusiv pe Microsoft Windows.
Tanks’ Assault este un joc video tridimensional, singleplayer1, de tip first-person
shooter, în cadrul căruia acțiunea se desfășoară prin ochii protagonistului. Utilizatorul
controlează un tanc, pe care îl poate mișca liber pe axele Ox și Oz ale unui sistem de
coordonate carteziene în spațiu cu originea în O și axele x, y, z. La începutul jocului este
plasat protagonistul în scenă și, odată cu acesta, și baza inamică, loc din care vor apărea
tancurile oponente de dificultăți diferite. Nivelurile de dificultate sunt începător, mediu și
avansat, fiecare având la bază anumiți algoritmi. Scenariul ideal presupune controlarea
eficientă și strategică a tancului, pentru a putea doborî cât mai mulți inamici. În plus față de
funcționalitatea fundamentală, utilizatorului îi este oferită posibilitatea de a se obișnui cu
controalele și de a se antrena înainte de o luptă propriu-zisă, plimbându-se cu tancul în zona
de training, pe o hartă generată aleator, multiplicată odată cu înaintarea protagonistului în
scenă pentru a crea impresia de spațiu infinit.
1. Motivație
Există o varietate de programe care folosesc inteligența artificială, precum sistemele
logistice, simulatoarele de piață sau planificatoarele economice. Aceste elemente includ
căutarea într-un arbore, rezolvarea unei probleme sau luarea unei decizii. Însă ramura
programării software care a folosit exponențial conceptele de inteligență artificială este cea a
jocurilor video.
Jocurile video au trecut prin îmbunătățiri drastice în ultima decadă. Odată cu creșterea
complexității, au devenit, de asemenea, mai interesante și mai palpitante. În acest context,
scenariile negative sunt ineluctabile, problema principală devenind optimizarea. Fiecare
arhitectură a unui joc se ocupă în mod diferit de această dificultate. În acest sens, lucrarea are
1 un joc video în care sunt așteptate datele de intrare de la un singur jucător pe tot parcursul sesiunii
3
ca scop aplicarea unor algoritmi și concepte informatice, pentru a putea îmbunătăți experiența
utilizatorului.
2. Context
Conform unui studiu realizat de către revista ”The Atlantic” 2
în anul 2011, vârsta
medie a unui jucător de jocuri video este de 34 de ani. În plus, graficele indică faptul că 60%
dintre consumatori sunt de genul masculin. Potrivit unei statistici realizate de către
Entertainment Software Association, în urma datelor oferite de către NPD Group - o
companie de studiu de piață -, industria jocurilor video a vândut 273 de milioane de produse
în anul 2009, ajungând la un profit surprinzător de 10.5 miliarde de dolari.
Un joc first-person shooter (FPS) este un gen al jocurilor video de tip shooter, în
cadrul căruia acțiunea se desfășoară din punctul de vedere al protagonistului. Acesta poate fi
jucat în două moduri, și anume campanie sau multiplayer. Modul campanie implică un singur
jucător în scenă, care evoluează odată cu trecerea timpului, crescând dificultatea într-un mod
progresiv. Modul multiplayer implică un grup de jucători participanți și poate avea mai multe
forme, precum ultimul supraviețuitor sau primul care capturează teritoriul.
Conceptul de FPS a fost regăsit pentru prima dată în anul 1992, într-un joc lansat de
către id Software. Wolfenstein 3D a impresionat prin grafica sa tridimensională, sunetul de o
calitate înaltă și stilul unic de joc. Protagonistul, un deținut de război, avea ca scop evadarea
dintr-un castel german.
Un an mai târziu, id Software a lansat un alt joc, care urma să devină foarte popular.
Doom aducea în plus o varietate mult mai mare de arme, dar și conceptul de multiplayer. De
această dată, protagonistul era un pușcaș marin, care trebuia să se lupte cu diverși inamici pe o
bază de pe planeta Marte.
A urmat o perioadă de impact, apărând conceptul de RPG (Role-Playing Game).
Câștigându-și titulatura de regele jocurilor FPS, id Software a lovit piața cu un nou joc. Lansat
în anul 1996, Quake era similar seriei Doom, însă era unul dintre primele FPS-uri care au
trecut de la inimici bidimensionali la modele complet tridimensionale.
2 http://www.theatlantic.com/technology/archive/2011/06/infographic-video-game-industry-statistics/239665/
4
Până în prezent, piața jocurilor video a escaladat foarte repede, apărând diverse idei
care mai de care mai interesante. Un concept aparte a fost propus și realizat de către studioul
indie Hello Games. Astfel că, după 6 ani de dezvoltare, pe 9 August 2016 a fost lansat No
Man’s Sky, un joc video de tip supraviețuire3, încadrat în genurile acțiune și aventură. Ideea
captivantă este că jocul se desfășoară într-o galaxie practic infinită generată de soft la run-
time. Numărul exact de planete din No Man’s Sky este 18.446.744.073.709.551.616, adică
mai mult de 18 miliarde de miliarde. Numărul acesta este atât de mare, încât, deși jocul este
multiplayer, sanșele de a întâlni un om real, și nu un AI, sunt infime. Hărțile au mărimea celor
din realitate, scopul principal al jocului fiind explorarea.
În cadrul No Man’s Sky putem regăsi diverse concepte implementate de inteligență
artificială. Santinelele, denumiți grădinarii galactici, sunt forme de viață mecanice, scopul lor
fiind acela de a se asigura că nimeni nu ia prea multe resurse de pe planeta lor. Dacă un
jucător încearcă să altereze mediul în timp ce ei sunt prin preajmă, nu vor ezita să își exercite
forța. Vor ataca un jucător care distruge ecosistemul planetei. De asemenea, o santinelă se va
apăra în momentul în care un jucător o atacă și va cere ajutorul celorlalte santinele din zonă.
Fiind un AI, o santinelă trece prin diferite stări, precum:
Pasivă
Nu este afectată de poziția jucătorului în raport cu propria poziție, până în momentul în
care protagonistul cauzează daune ecosistemului planetei. Jucătorul nu poate distruge o
santinelă aflată în această stare.
Activă
Cea mai întâlnită și obișnuită stare a unei santinele. Se va angrena într-o dispută cu
jucătorul atunci când acesta va omorî un animal care nu a fost provocat sau atunci când va
profita prea mult de resursele planetei.
Frenetică
Santinelele își distrug inamicul după ce l-au observat și scanat timp de 5 secunde.
3 joc care plasează de obicei jucătorul într-un context în care trebuie să adune resurse, să-și construiască diverse
unelte și adăposturi și să supraviețuiască cât mai mult posibil
5
Atentă
Santinele se comportă similar ca în starea Activă, însă cu o mișcare considerabil mai
rapidă și mai eficientă.
Agresivă
Santinele vor ataca întotdeauna jucătorul atunci când îl observă. Mișcarea este mult
mai rapidă, iar ținta mult mai eficientă.
Spre deosebire de No Man’s Sky, această lucrare de licență dorește să surprindă
importanța anumitor concepte de Computer Science în dezvoltarea unui joc. Un exemplu
concret ar fi utilizarea object pooling-ului pentru optimizare. No Man’s Sky și-a propus ca doi
utilizatori diferiți să traiască experiențe diferite în cadrul aceluiași joc. În acest sens,
producătorii au ales unicitatea în detrimentul optimizării. Din punct de vedere probabilistic, o
repetiție a unui element într-o proporție infimă nu afectează unicitatea în cadrul vederii de
ansamblu. În acest sens, jocul putea folosi elemente deja randate sau compilate și în alte
contexte, neschimbând în mod tragic rata unicității. Prin urmare, am ales această temă din
dorința de a face tranziția între noțiunile teoretice și proiectarea acestora în lumea virtuală.
Tanks’ Assault este un joc de tip first-person shooter, în variantă singleplayer.
Jucătorul controlează un tanc, misiunea lui fiind aceea de a împușca și doborî cât mai mulți
inamici. În tabăra adversă se regăsesc tancuri de niveluri diferite de dificultate, care apar în
scenă pe rând la o diferență de timp prestabiliă. Numărul de inamici aflați în același timp pe
terenul de luptă este unul predefinit și relativ mic (5), pentru a lăsa jucătorului șansa de a
gândi o strategie. Distrugerea fiecărui inamic este contorizată diferit, în funcție de dificultatea
acestuia. Scopul principal al jocului este acela de a strânge cât mai multe puncte, cu ajutorul
cărora pot fi îmbunătățile caracteristicile propriului tanc.
Asemănător cu No Man’s Sky, AI-urile din Tank’s Assault trec prin stări diferite în
funcție de context, însă acestea având un comportament diferit. La nivelul avansat poate fi
remarcat conceptul de curba lui Bézier cubică, care ar fi putut îmbunătăți remarcabil
dificultatea jocului No Man’s Sky și, odată cu asta, și experiența utilizatorului.
6
3. Cerințe funcționale
Aspecte funcționale ale părților implicate
Terenul (Training)
Tratat ca un fractal, acesta este generat într-un mod aleator înainte de începerea
antrenamentului protagonistului cu ajutorul unor algoritmi stocastici care să producă un
comportament fractal. Acest comportament simulează ideea de teren natural. Algoritmul
principal folosit este o variantă îmbunătățită a funcției Mathf.PerlinNoise prezentă în Unity,
punându-i valorile de ieșire în comparație cu valorile produse de algoritmul Diamond Square.
Protagonistul
Are o viață, o anumită viteză de deplasare și dispune de o armă (tunul tancului). Se
poate mișca liber, iar scopul lui este de a doborî cât mai mulți inamici.
Inamicii (AI-urile)
Au o viață, o anumită viteză de deplasare, dispun de mai multe arme, în funcție de
nivelul propriu de dificultate și apar la un interval de timp prestabilit. Sunt de trei tipuri:
începător, mediu și avansat, la fiecare nivel regăsindu-se diverse concepte, precum A*
Pathfinding, Curba lui Bézier.
Funcționalitățile generale
Funcționalitățile aplicației sunt, după cum urmează:
1 Posibilitatea de a salva jocul la un moment dat.
2 Posibilitatea de a începe jocul de la început sau dintr-un anumit punct în care
a ajuns anterior și pe care l-a salvat.
3 Posibilitatea de a alege dificultatea inamicilor.
4 Posibilitatea de a îmbunătăți specificațiile tehnice ale propriului tanc.
5 Posibilitatea de a verifica numărul de puncte strânse.
6 Posibilitatea de a te antrena într-un spațiu “infinit”.
7
4. Abordare tehnică
În următoarea secțiune sunt creionate tehnologiile folosite pentru realizarea lucrării.
Unity
Este un game engine capabil să fie folosit pe diferite tipuri de calculatoare sau cu
diferite pachete software. Versiunea motorului folosit în crearea jocului este ultima stabilă, și
anume Unity 5.
C#
Limbajul ales este C#, fiind cel mai avansat dintre cele prestabilite. De asemenea, este
cel mai optimizat și începe să devină limbajul standard pentru gaming pe plaforme multiple.
Este de menționat faptul că majoritatea jocurilor pe consola Xbox 360 sunt programate în C#.
5. Zone de risc
Performanța Prezența unor script-uri cu algoritmi de o complexitate ridicată, care să
îngreuneze jocul.
Soluția Aplicarea unor concepte (object pooling) sau folosirea unor structuri de date
(heap) care să își aducă aportul în optimizarea algoritmilor.
8
Contribuții
Luând în considerare dezvoltarea exponențială a inteligenței artificiale în industria
jocurilor video, optimizarea algoritmilor și introducerea unor noi concepte atractive par să fie
soluțiile ideale. În acest sens, o contribuție a lucrării Tanks’ Assault o constituie introducerea
conceptului de proiectil care, urmărind traiectoria unei curbe Bézier, agresează utilizatorul
până îl lovește.
De asemenea, o altă contribuție o reprezintă zona de antrenament a protagonistului. În
majoritatea structurilor organizaționale ale echipelor de producție a jocurilor video un punct
deosebit de important îl constituie aportul adus de designeri. Având în vedere faptul că pentru
crearea unui teren se pot consuma foarte multe resurse, renunțându-se de multi ori la
optimizările de timp sau spațiu, generarea acestuia procedural poate reprezenta un plus adus
tehnologiilor moderne. Privit ca un fractal, terenul din lucrarea Tanks’ Assault este generat cu
ajutorul funcției Mathf.PerlinNoise() din Unity, în comparație cu algoritmul Diamond-Square.
Lucrarea este divizată în două. În prima parte este descris scheletul aplicației și sunt
prezentate câteva concepte aplicate, în timp ce în a doua parte sunt conturați algoritmii
propriu-ziși, metode de optimizare ale acestora și un studiu de caz concentrat pe importanța
învățării automate în domeniul jocurilor video.
9
Proiectare
0. Arhitectura aplicației
Jocul Tanks’s Assault este împărțit în mai multe scene, denumite Capitole (Chapters)
în aplicația propriu-zisă.
Capitolul -1
În figura -1 de mai jos poate fi regăsit primul ecran de interacțiune cu utilizatorul.
Acesta va apărea atâta timp cât utilizatorul nu apasă butonul “Enter Game”. Odată apăsat
butonul, numele completat în câmpul “Your Name” va fi salvat într-un fișier, utilizatorul
având posibilitatea de a-l vedea în scena următoare.
Fig. -1 – Capitolul -1
Sursă: Tanks’ Assault
Capitolul 0
În figura 0 de mai jos poate fi regăsit meniul principal. În această scenă există un
coordonator (MainMenuManager) care se ocupă cu gestionarea butoanelor și a elementelor
10
grafice apărute prin apăsarea acestora. De asemenea, există și un coordonator
(ProfileManager) care se ocupă cu actualizarea scorului jucătorului.
Continue Continuarea de la ultima salvare. În cazul în care jocul nu a fost salvat
anterior, butonul se comportă ca New Game.
New Game Începerea unui joc nou.
Load Afișarea unei liste cu salvările precedente. Utilizatorul poate alege oricare
salvare pe care să o continue.
Tanks Afișarea unei liste cu tancurile disponibile. Utilizatorul poate cumpăra tancuri
cu caracteristici superioare folosindu-și punctele strânse.
Training Posibilitatea utilizatorului de a se obișnui cu controalele și de a se antrena.
Este un opțiune care îl plasează pe protagonist pe un teren generat aleator cu ajutorul funcției
Mathf.PerlinNoise() din Unity în comparație cu rezultatul algoritmului Diamond-Square.
Options Posibilitatea de a de seta dificultatea inamicilor.
Gold Numărul de puncte strânse până în acel moment.
Exit Închiderea aplicației.
Fig. 0 – Capitolul 0
Sursă: Tanks’ Assault
11
Capitolul 1
În capitolul 1 se regăsește jocul propriu-zis. În figura 1 de mai jos poate fi regăsită
diagrama cazurilor de utilizare, care conturează acțiunile principale. Tancul protagonistului
este poziționat pe hartă, iar baza inamică începe să producă noi AI-uri, în funcție alegerea
utilizatorului și de scorul pe care îl acumulează.
Fig. 1 - Diagramă use-case
Sursă: Tanks’ Assault
Capitolul 2
În capitolul 2 poate fi regăsită zona de antrenament a protagonistului. Acesta este
plasat în scenă pe un teren generat aleator cu ajutorul unor matrici de zgomote calculate de o
funcție Perlin Noise.
Observație: protagonistul se poate întoarce la capitolul 0 atât din capitolul 1, cât și din
capitolul 2.
12
1. Șabloane pentru proiectare
Ce este un șablon pentru proiectare?4,5
Christopher Alexander spune, “Fiecare șablon descrie o problemă care apare din nou și
din nou în contextul în care ne aflăm, după care descrie esențialul soluției la acea problemă
într-un asemenea mod care permite utilizarea soluției de nenumărate ori în contexte diferite”.
Cu toate că acest arhitect a lansat inițiativa folosirii unui limbaj bazat pe șabloane în contextul
proiectării clădirilor și orașelor, esența este aceeași. Așadar, un șablon reprezintă o soluție
comună a unei probleme într-o anumită conjunctură.
Învățarea acestor șabloane ajută dezvoltatorii neexperimentați să învețe design-ul
software într-un mod mai ușor și mai rapid.
Gang of Four6
În anul 1994, autorii Erich Gamma, Richard Helm, Ralph Johnson și John Vlissides au
publicat o carte intitulată Design Patterns – Elements of Reusable Object-Oriented
Software, care avea să inițieze conceptul de șablon pentru proiectare în dezvoltarea software.
Aceștia sunt cunoscuți sub numele de Gang of Four (GOF).
Arhitectura unui șablon pentru proiectare
Un șablon este descris de patru elemente:
Nume Este folosit pentru identificare. Numele descrie sintetic problema rezolvată de
șablon și soluția.
Problema Descrie când se aplică șablonul. Este descrisă problema și contextul.
Soluția Descrie elementele care constituie rezolvarea propriu-zisă, relațiile dintre ele,
responsabilitățile lor și colaborările dintre ele.
4 en. Design Pattern
5 Gang of Four: http://www.uml.org.cn/c++/pdf/DesignPatterns.pdf
6 http://www.tutorialspoint.com/design_pattern/design_pattern_overview.htm
13
Consecințe și compromisuri Aici sunt conturate implicațiile folosirii șablonului,
costurile și beneficiile. Poate fi analizat impactul asupra flexibilității, extensibilității sau
portabilității sistemului, dar se poate face referire și la aspecte ale implementării sau
limbajului de programare utilizat. Compromisurile sunt, de cele mai multe ori, legate de
spațiu și timp.
1.0 Șabloane creaționale
Singleton
Obiectivele acestui șablon sunt de a se asigura că o singură instanță a clasei este creată
și de a oferi un punct global de acces către obiect. Implementarea invocă un membru static în
clasa singleton, un constructor privat și o metodă statică (și publică) care returnează o
referință la membrul static.
În figura 2 de mai jos poate fi regăsită diagrama UML7 de clase a șablonului creațional
Singleton într-un context al jocului Tanks’ Assault. Clasa MainGameManager este clasa
Singleton, având rolul de a reține scorul jucătorului. Având în vedere faptul că există un
singur jucător cu un singur scor și că acesta trebuie modificat din diferite clase (clasa
EnemyManager în exemplul de mai jos), se poate remarca faptul că acesta constituie un
exemplu concret de problemă cu o rezolvare care poate fi regăsită în șablonul curent.
Remarcă: funcția changedHealthStatus(Transform, float) este apelată la distrugerea unui tanc
inamic, moment în care trebuie reînnoit și scorul jucătorului.
7 UML – Unified Modeling Language
14
Fig. 2 – Șablonul Singleton (diagramă de clase)
Sursă: Tanks’ Assault
Diagramă de clase: descrie structura unui sistem prin evidențierea claselor din sistem, a
atributelor lor și a relațiilor dintre clase.
Abstract Factory
Obiectivul acestui șablon este de a oferi o interfață pentru crearea familiilor de obiecte
înrudite sau dependente fără a specifica clasele lor concrete.
În figura 3 de mai jos poate fi observată clasa abstractă Enemy, clasele care o extind
(EasyAI, IntermediateAI, AdvancedAI) și clasa care se folosește de conceptul de Abstract
Factory (EnemyManager). În cadrul celei din urmă se regăsește o listă de inamici care, deși
vidă la început, este încărcată cu oponenți până la un număr maxim predefinit odată cu
apelarea funcției AddEnemy().
15
Fig. 3 – Șablonul Abstract Factory (diagramă de clase)
Sursă: Tanks’ Assault
1.1 Șabloane comportamentale8
Null Object9
Scopul acestui șablon este de a încapsula absența unui obiect oferind o alternativă care
oferă un comportament predefinit. Pe scurt, este folosit pentru a returna un obiect consistent
indiferent de datele de intrare. Acesta este cunoscut pentru ajutorul oferit la evitarea scrierii de
linii de cod inutile atunci când se verifică valorile null.
În figura 4 de mai jos poate fi observată clasa abstractă AbstractUser, clasele care o
implementează (RealUser, NullUser), clasa care creează AbstractUser (UserFactory) și clasa
care se folosește de conceptul de Factory (MainMenuManager).
8 www.habrador.com/tutorials/programming-patterns
9 https://sourcemaking.com/design_patterns/null_object
16
Fig. 4 – Șablonul Null Object (diagramă de clase)
Sursă: Tanks’ Assault
State
În cadrul acestui șablon sunt create obiecte care reprezintă diverse stări și un obiect
context al cărui comportament variază în funcție de schimbările de stare pe care le suferă
obiectele în cauză.
În figura 5 de mai jos poate fi regăsită diagrama UML de stări a șablonului
comportamental State într-un context al părții practice a proiectului de licență. Există o stare
inițială (Start), starea generală a obiectului (o compunere de stări intermediare) și două stări
finale (AI Destroyed și Player Defeated). În contextul curent, obiectul care tranzitează între
stările de mai jos este inamicul (mai precis, strategia de joc a acestuia – în cazul de față,
strategia este la nivelul cel mai înalt, și anume Avansat).
Stări intermediare: enum EnemyStates {Stay, Chase, Attack, Retreat, Find, Bézier}.
Variabile cu valori prestabilite: {attackRange – distanța maximă de la care inamicul
începe să atace, (minimumChaseRange, chaseRange] – intervalul în care începe să îl
urmărească pe jucător, findRange – distanța maximă de la care folosește o implementare a
algoritmului A* pathfinding pentru a-l detecta și a-l urmări pe jucător, retreatHealth –
17
valoarea maximă pentru viață la care se retrage, minimumHealth – valoarea minimă pentru
viață la care intră în luptă}.
În starea inițială, tancul inamic este creat și pus în scenă. Odată devenit activ, acesta
intră în starea Bézier. Aici există, în implementare, un alegere aleatoare între două numere (0
și 1), alegere realizată cu fiecare frame nou. Dacă valoarea rezultată este 0, rămâne în aceeași
stare și lansează un proiectil care urmărește adversarul folosind metoda curbei cubice a lui
Bézier. În caz contrar, inamicul intră în starea Find. Aici se regăsește un principiu
asemănător: se face o alegere aleatoare între aceleași două numere. Dacă valoarea este 1,
atunci intră în valoarea Bézier. În schimb, dacă valoarea este 0, poate intra în oricare dintre
stările {Stay, Chase, Attack, Find}
Fig. 5 – Șablonul State (diagramă de stări)
Sursă: Tanks’ Assault
Diagramă de stări: utilizată pentru a specifica posibilele stări prin care poate trece un obiect și
modul în care se poate trece de la o stare la alta. O stare reprezintă o etapă din
comportamentul unui obiect. Astfel, putem avea stări inițiale10
și stări finale11
.
10
starea în care se regăsește obiectul atunci când a fost creat pentru prima dată 11
nu mai trece prin nicio tranziție
18
În starea Stay, inamicul nu știe informații despre jucător. Totuși, îl așteaptă pe acesta
să îi intre în aria lui de control, pentru a putea adopta o strategie ofensivă. În starea Chase,
este îndreptat către jucător și merge pe direcția acestuia, până îl ajunge sau până se
îndepărtează atât de mult încât jucătorul să nu mai apară în raza sa de acțiune. În starea
Attack, inamicul începe să arunce cu gloanțe în oponent. În starea Retreat, se retrage, având în
vedere faptul că viața lui a scăzut foarte mult și poate fi doborât în orice moment. În starea
Find, inamicul își caută oponentul pe hartă folosind un algoritm de traversare a unui graf într-
un mod eficient.
Există două deznodământuri în cazul unui tanc inamic – fie este el distrus (situație în
care se intră pe ramura AI Destroyed), fie a distrus oponentul (situație în care se intră pe
ramura Player Defeated). În cazul ultimului scenariu, jocul se termină.
Implementarea acestui șablon a fost făcută după cum urmează:
Script-ul constă în crearea unei clase părinte Enemy și a trei clase copil (câte una
pentru fiecare tip de strategie). Va fi inițializat și un controller, care se va ocupa propriu-zis de
notificarea inamicului cu informații despre poziția curentă a oponentului. Ideea principală este
aceea de a înnoi starea inamicului verificând dacă este necesară această schimbare.
În figura 6 poate fi observată clasa Enemy, având ca atribut o enumerație de stări și ca
metode
protected void DoAction(Transform, EnemyStates) și:
public virtual void UpdateEnemy(Transform player, float health) {} – funcția poate fi
redefinită într-o clasă derivată, păstrând proprietățile de apelare prin intermediul referințelor;
cu “virtual” apare conceptul de late-binding12
.
12
metoda este căutată după nume la runtime
19
Fig. 6 – Enemy.cs
Sursă: Tanks’ Assault
În figura 7 poate fi remarcată moștenirea clasei Enemy și suprascrierea funcției
UpdateEnemy(Transform, float). La final este apelată funcția DoAction(Transform,
EnemyStates), a cărei implementare poate fi găsită în clasa părinte. În mod asemănător au fost
implementate și celelalte două clase (regăsite în scripturile EasyAI.cs și IntermediateAI.cs).
20
Fig. 7 – AdvancedAI.cs
Sursă: Tanks’ Assault
În figura 8 poate fi observat coordonatorul care se ocupă cu instanțierea inamicilor.
Acesta are în componență funcția Update, în interiorul căreia înștiințează inamicul cu
21
informații despre poziția jucătorului, urmând ca acesta să își schimbe sau nu ulterior starea în
funcție de ceea ce primește.
Fig. 8 – EnemyManager.cs
Sursă: Tanks’ Assault
22
ChooseEnemy() – în primul rând, face o cerere către instanța unică MainGameManager pentru
a putea afla numărul de puncte de experiență adunate de către inamici. În al doilea rând,
calculează o valoare aleatoare pentru a afla ce inamic să trimită la următoarea instanțiere.
Dacă experiența este peste 200, coordonatorul va face o alegere aleatoare între 3 numere,
fiecare făcând referire la unul dintre cele trei strategii (0 pentru Începător, 1 pentru
Intermediar, 2 pentru Avansat). În ultimul rând, apelează funcția care instanțiază propriu-zis
inamicul.
AddEnemy() – adaugă următorul inamic în scenă, dacă numărul acestora este mai mic decât
numărul maxim permis. În final, apelează Invoke(“ChooseEnemy”, 5f) pentru a invoca
metoda specificată ca prim parametru la un interval indicat de al doilea parametru (5
secunde).
Observer13
Șablonul Observer este un șablon în cadrul căruia un subiect menține o listă către toți
observatorii depedenți, notificându-i automat de orice schimbare de stare apelând una dintre
metodele lor. Contextul favorabil în care poate fi folosit este atunci când o mulțime de obiecte
trebuie să primească o nouă informație despre un obiect, atunci când acesta își schimbă starea.
Șablonul are în alcătuire două componente:
Subiectul Conține o listă cu toți observatorii interesați în a primi informare atunci când
intervine o schimbare și îi informează când un asemenea eveniment se întâmplă.
Observatorii Obiectele care sunt interesate în a face o acțiune după ce un eveniment a
avut loc.
În figura 9 de mai jos se regăsește scriptul care inițiază ideea de observatori (On
Enable din scriptul Health). De asemenea, se poate observa interfața Iobserver, implementată
de către ObserverManager, clasă care conține atât subiectul, cât și corpul funcției de
actualizare a observatorilor. Clasa abstractă Subject conține lista de observatori și funcțiile de
Atașare, Detașare și Notificare a unui observator din această listă.
13
http://www.habrador.com/tutorials/programming-patterns/3-observer-pattern/
23
Fig. 9 – Șablonul Observer (diagramă de clase)
Sursă: Tanks’ Assault
2. Salvarea datelor
Fiind o aplicație care rulează în modul offline, o bază de date complexă nu este
necesară. Reținerea informațiilor despre sesiunea utilizatorului pentru o eventuală reîncepere a
jocului de la o salvare anterioară sunt reținute în două fișiere “PlayerData.dat” și
“PlayerProfile.dat” (aflate la o adresă a unui folder de date persistente).
Application.persistentDataPath
În Unity există această funcție care returnează o variabila a cărei valoare este o adresă
a unui folder în cadrul căruia datele care așteaptă să fie persistente între rulări pot fi păstrate.
24
[System.Serializable]
Atașat unei clase, linia de cod de mai sus transmite engine-ului Unity că aceasta poate
fi serializată. Cu alte cuvinte, putem salva toate variabilele prezente în clasă.
Fig. 10 – Atributele clasei PlayerData
Sursă: Tanks’ Assault
BinaryFormatter
Această clasă serializează sau deserializează un obiect sau un graf întreg de obiecte
conectate în format binar.
Fig. 11 – Fișierul serializat în format binar PlayerData.dat
Sursă: Tanks’ Assault
25
Implementare
0. Niveluri de dificultate
Tanks’ Assault este un joc tridimensional în care utilizatorul conduce un tanc și are
misiunea de a doborî cât mai mulți inamici. Oponenții au diferite grade de dificultate și trec
prin diverse stări în funcție de pozitia relativă față de tancul protagonist.
Începător
Stay
Starea inițială în care se află un inamic. Comportamentul său este unul static.
Chase
Tancul utilizatorului apare în aria păzită de el și pornește în urmărirea lui.
Attack
Stare în care AI-ul intră din starea Chase atunci când se află la o distanță mică de
protagonist. Începe focul de arme.
Retreat
Stare în care AI-ul se află atunci când viața lui este aproape de zero. Se retrage, pentru
a se recupera.
Mediu
Comportamenul AI-ului este similar cu cel al unui AI începător. Ceea ce aduce în plus
este faptul că tancul inamic îl caută pe protagonist pe hartă la început, neașteptând ca acesta să
intre în raza lui de acțiune.
26
0.1 Algoritmul A* Pathfinding14
Are următoarele proprietăți:
1 Este complet. Va găsi întotdeauna o soluție dacă aceasta există.
2 Poate folosi o metodă euristică pentru a accelera semnificativ procesul.
3 Poate avea cost de deplasare variabil de la un nod la altul. Acest fapt permite ca
unele noduri sau drumuri să fie mai dificile de traversat.
4 Poate căuta în direcții diferite dacă este necesar.
Funcționare
Algoritmul presupune inițializarea a două liste: o listă cu nodurile nevizitate (en. Open
List) și o listă cu nodurile vizitate (en. Closed List). Scopul primei liste este de a reține cele
mai bune noduri pentru traversare care nu au fost luate în considerare până în acel moment,
începând cu nodul de start. Dacă lista ajunge goală, atunci nu există o cale de traversare
posibilă. Cea de-a doua listă începe goală și conține toate nodurile care au fost vizitate.
Principala buclă a algoritmului selectează nodul cu cel mai mic cost de a ajunge la
destinație din lista cu nodurile nevizitate. Dacă acesta nu este nodul destinație, atunci
algoritmul îi adaugă toți vecinii valizi în lista cu noduri nevizitate și repetă procesul. Partea
importantă a algoritmului este faptul că toate nodurile vizitate mențin o referință actualizată
către propriul părinte. În acest sens, o consecință este aceea cum că se poate ajunge înapoi la
nodul de start din orice nod vizitat în cadrul algoritmului.
Structură
Nodul
Un nod are în componență perechea (x, y) care îi indică poziția, o referință către
părintele lui și trei costuri asociate, prezentate mai jos. Acestea sunt folosite pentru a
determina alegerea unui nod.
14
http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
27
Costul G
Costul G este costul de bază al nodului și este calculat ca fiind costul incremental al
deplasării de la nodul de start.
( ) ( ) ( )
( )
Costul H (euristic – en. Heuristic)
Costul euristic este calculat ca fiind distanța dintre fiecare nod și nodul destinație.
Implementarea costului euristic poate varia în funcție de proprietățile grafului în care se caută.
În acest sens, cei mai comuni algoritmi euristici sunt:
Distanța Manhattan
Este cel mai simplu algoritm euristic și ideal pentru gridurile care permit o mișcare
doar în patru direcții (înainte, înapoi, stânga, dreapta).
( ) | | | |
Distanța Euclidiană
Acest algoritm euristic poate fi folosit atunci când mișcarea este posibilă în orice
direcție, dar poate fi costisitoare din punct de vedere al timpului de execuție.
( ) √( ) ( )
Distanța Diagonală (cost uniform)
Acest algorim euristic poate fi folosit pentru o mișcare posibilă în opt direcții
(direcțiile din distanța Manhattan plus diagonalele), în contextul în care costul deplasării pe
diagonală este același cu costul deplasării în celelalte direcții.
( ) (| | | |)
28
Distanța Diagonală
Acest algoritm euristic poate fi folosit pentru o mișcare posibilă tot în opt direcții), dar
atunci când costul deplasării pe diagonală este diferit de costul deplasării în celelalte direcții.
( ) ( )
(| | | |)
(| | | |)
√
Fig. 12 – Distanța Euclidian, Diagonală, Diagonală cu cost uniform, Mahnattan
Sursă: http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
Costul F
Este costul total al drumul prin nodul curent și are drept valoare suma dintre costul G
și costul H.
( ) ( ) ( )
29
În cadrul jocului Tanks’ Assault, costul pe diagonală va fi 14, iar pentru celelalte
direcții 10. Valorile vin din calcularea valorilor catenelor și ipotenuzei a unui triunghi
dreptunghic isoscel de latură 1, în care ipotenuza are valoarea rădăcinii pătrate a lui 2.
Pseudocod
Fig. 13 – Pseudocod reprezentând algoritmul A* Pathfinding.
Sursă: https://github.com/SebLague/Pathfinding
Arhitectura
În figura 14 de mai jos este conturată o diagramă de secvențe, care surprinde
interacțiunile dintre mai multe entități și ordinea în care mesajele sunt schimbate între acestea.
Inamicul de dificultate intermediară verifică disponibilitatea coordonatorului de găsire a unui
drum, iar dacă răspunsul este pozitiv, trimite date. Acesta, la rândul lui, trimite mai departe
anumite informații și îi solicită PathRequestManager-ului cel mai scurt drum care poate fi
parcurs de la nodul de start la nodul destinație. Așadar, PathRequestManager-ul se ocupă cu
tratarea cererilor de căutare a drumului cel mai scurt.
30
Fig. 14 – Diagramă de secvențe
Sursă: Tanks’ Assault
Implementare
În cadrul jocului Tanks’ Assault, un nod reține și atributul walkable de tip boolean,
care indică dacă nodul poate fi parcurs sau nu. Gridul, având o dimensiune și o rază
predefinite, este reprezentat printr-o matrice ale cărei elemente sunt noduri. Tot în clasa grid
se pot găsi funcțiile GetNeighbours(Node) – care conține nodurile vecine valide – și
NodeFromWorldPoint(Vector3) - care returnează nodul curent a cărui poziție este dată ca
parametru.
În momentul în care coordonatorul de inamici plasează în scenă un oponent cu nivelul
de dificultate mediu, este apelată UpdateEnemy(Transform, float) din clasa IntermediateAI,
care apelează o funcție din clasa părinte Enemy, numită DoAction(Transform, EnemyStates).
În același timp se apelează și funcția Start() din clasa PathfindingManager, care solicită
căutarea propriu-zisă a unui drum între inamicul curent și protagonist.
31
Fig. 15 – PathfindingManager.cs
Sursă: Tanks’ Assault
Așadar, în interiorul funcției Start() se apelează RequestPath(Vector3, Vector3,
Action<Vector3[], bool>), o funcție a cărei definiție este prezentă în clasa
PathRequestManager.
32
Fig. 16 – PathRequestManager.cs
Sursă: Tanks’ Assault
În figura 16 se poate observa implementarea funcției statice RequestPath. Ultimul
parametru este de tip Action și se comporta ca un callback. Este adăugată cererea într-o coadă
ținută la nivel de clasă și se încearcă procesarea următorului drum. După ce drumul a fost
găsit, se apelează funcția FinishedProcessingPath care apelează callback-ul din clasa
anterioară. Așadar, se apelează funcția OnPathFound(Vector3[], bool) din clasa
PathfindingManager. Dacă există un drum valid, atunci acesta este trimis către o corutină care
se ocupă de traseul inamicului.
Pentru a putea exista mai mulți inamici cu nivelul de dificultate mediu, corutina
FollowPath() conține linia de cod yield return null; care oprește mișcarea unui inamic până la
următorul frame, oferind ocazia celorlalți utilizatori de pathfinding să se apropie de destinație.
O comparație poate fi făcută cu firele de execuție.
33
Avansat
Comportamenul AI-ului este similar cu cel al unui AI mediu, însă cu starea Bézier în
plus. Un inamic în această stare trimite către protagonist un proiectil care urmează curba lui
Bézier, evitând obstacolele din jur pe care le întâlnește până la țintă.
0.2 Curba lui Bézier15,16
Remarcă: curba folosită pentru schițarea mișcării unui proiectil este de tip Bézier
cubică.
În analiza numerică, o curbă Bézier este o curbă parametrică cu importante aplicații în
grafica pe calculator și în domeniile asociate acesteia.
Din punct de vedere matematic, a curbă Bézier este descrisă de o funcție de parametru
t. Valoarea acestei funcții este un punct pe o curbă care depinde de parametrul t și de un set de
puncte, numite puncte de control. Primul și ultimul conturează extremitățile curbei. În
general, curba nu trece prin celelalte puncte de control.
În grafica vectorială, curbele Bézier constituie o unealtă importantă folosită pentru
modelarea curbelor derivabile și scalabile. Căile (en. paths), așa cum sunt ele denumite
adesea în programele de grafică vectorială sau de editare de imagini, cum ar fi Adobe
Illustrator sau Photoshop, sunt combinații de curbe Bézier interconectate.
Construcția și definiția unor curbe
Curbe liniare
Curbele liniare reprezintă cazul cel mai simplu de curbă Bézier. Având date două
puncte P0 și P1, o curbă Bézier liniară este linia care leagă cele două puncte. Expresia curbei
este dată de expresia ( ) ( ) ( ) și
15
http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/ 16
https://en.wikipedia.org/wiki/B%C3%A9zier_curve
34
este similară cu interpolarea liniară. În acest context, parametrul t poate fi considerat ca fiind
distanța la care se află B(t) de P0 și P1.
( ) , având
( )
( )
Fig. 17 – Curbă liniară
Sursă: http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/
Pentru a construi forme mai complexe și mai interesante, trebuie incluse mai multe
puncte de control. Așadar, acestea determină gradul curbei. Pentru o curbă de gradul doi,
denumită și curbă cuadratică, sunt necesare 3 puncte de control, în timp ce pentru o curbă de
gradul trei, denumită și curbă cubică, sunt necesare 4 asemenea puncte de control.
Curbe Bézier cuadratice
Având date punctele P0, P1 și P2, calea parcursă de funcția B(t) are denumirea de curbă
Bézier cuadratică. Expresia parametrică este următoarea:
( ) ( ) ( )
O curbă Bézier cuadratică este un segment de parabolă, în cadrul căreia se pot construi
punctele intermediare Q0 și Q1 astfel încât t să varieze de la 0 la 1:
Punctul Q0 variază de la P0 la P1 și desenează o curbă Bézier liniară.
Punctul Q1 variază de la P1 la P2 și desenează o curbă Bézier liniară.
Punctul B(t) variază de la Q0 la Q1 și descrie o curbă Bézier
cuadratică.
Fig. 18 – Curbă cuadratică
Sursă: http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/
35
În figura 19 de mai jos se pot observa exemple de curbe Bézier de gradul trei (sau
curbe Bézier cubice). De remarcat este faptul că liniile galbene sunt pe aceeași direcție ca
tangetele la capete. Așadar, cu cât sunt mai lungi aceste linii, cu atât curba este mai mult
îndreptată către tangentă.
Fig. 19 – Curbă cubică
Sursă: http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/
Curbe Bézier cubice
Pentru a defini o curbă Bézier cubică, sunt necesare 4 puncte de control P0, P1, P2 și P3
din plan sau din spațiul tridimensional. Traseul este următorul: curba începe la P0, merge
înspre P1 și ajunge la P3 din direcția lui P2. În general, nu trece nici prin P1 și nici prin P2,
aceste puncte existând doar pentru a specifica anumite informații despre direcție. Distanța
dintre P0 și P1 determină “cât de mult timp” se mișcă curba în direcția lui P2 înainte de a se
îndrepta spre P3.
Forma parametrică a curbei Bézier de gradul 3 este următoarea:
( ) ( ) ( ) ( ) ( )
Asemănător exemplului din figura 17 de mai sus, see construiesc punctele Q0, Q1 și Q2
care desenează curbe Bézier liniare, și apoi punctele R0 și R1 care descriu curbe Bézier
cuadratice.
36
Definiție generală
O curbă Bézier de gradul n se poate defini astfel: Având punctele de control P0, P1, ...,
Pn, curba are expresia:
( ) ∑ ( )
( ) ( ) ( )( )
.
Această formulă poate fi exprimată și recursiv astfel: Fie curba Bézier
determinată de punctele P0, P1, ..., Pn. Atunci:
( ) ( ) ( )
( ) ( ).
În concluzie, curba Bézier de gradul n este o interpolare liniară între două curbe Bézier
de gradul n-1. Luând în considerare polinoamele Bernstein de bază, expresia unei curbe
Bézier se poate scrie în următorul mod:
( ) ∑ ( ) , unde
( ) ( ) ( )
sunt polinoamele Bernstein de gradul n, în care t0 = 1 și (1 – t)
0 = 1.
Forma polinomială
În anumite contexte de aplicații sau situații este preferată o formă polinomială a curbei
Bézier în locul exprimării în sumă de polinoame Bernstein. În acest sens, o aplicare a
teoremei binomiale la definiția cubei, urmată de o rearanjare a termenilor, dă rezultatul
următor:
( ) ∑ , unde
( ) ∑
( )
( )
∏ ( )∑
( )
( )
.
Notă: Această formulare este eficientă dacă Cj poate fi calculat anterior evaluărilor lui
B(t).
37
Implementare
În figura 20 de mai jos se poate observa implementarea formulei (*) de mai sus.
Având valoarea parametrului t și a patru puncte de control, funcția returnează poziția
punctului.
Fig. 20 – Calcularea punctului Bézier
Sursă: Tanks’ Assault
Etapele algoritmului sunt următoarele:
1 Se începe de la extremități, adică de la punctele de pe curbă atunci când t = 0
și t = 1.
2 Se calculează punctul de mijloc, atunci când valoarea lui t = 0.5.
3 Se calculează unghiul format de cele segmente de dreaptă și, dacă acesta este
mai mic decât un anumit prag, se adaugă punctul pentru a fi desenat. Etapa se repetă în mod
recursiv cu fiecare jumătate de curbă. Algoritmul se oprește atunci când nu mai este posibilă
nicio împărțire sau atunci când segmentele de dreaptă ating o lungime minimă.
38
În figura următoare se pot observa etapele descrise mai sus.
Fig. 21 – Pașii algoritmului
Sursă: http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/
Notă: punctele finale sunt folosite la conturarea curbei.
O parte importantă în implementarea algoritmului o are inserarea punctelor care
urmează să fie desenate în listă astfel încât să rămână în ordinea potrivită. În acest sens, în loc
de verificarea directă a unghiului, este verficat produsul scalar al segmentelor normalizate.
Această verificare folosește o ordonare descrescătoare în inegalitate în loc de o ordonare
crescătoare în cazul cercetării directe a unghiurilor.
Fig. 22 – Punctele de adăugat
Sursă: Tanks’ Assault
39
Funcția din figura 23 de mai jos face apelul de bază către funcția recursivă.
Fig. 23 – FindDrawingPoints
Sursă: Tanks’ Assault
Observații:
1 Verificarea distanței minime este necesară pentru a preveni probleme cu
normalizarea vectorilor foarte mici. De asenemea, preveni și diferse calcule care nu sunt
necesare.
2 Valoarea pragului este foarte aproape de -1. În acest sens, o valoare bună de
început poate fi -0.99.
3 Algoritmul nu este eficient pentru curbe care conțin bucle sau inflexiuni. Un
astfel de exemplu în care rezultatul algoritmului este unul slab poate fi observat în figura 24
de mai jos. În acest caz, unghiul este mai mare decât pragul, astfel încât nu va apărea nicio
subdivizie. Segmentul de dreaptă rezultat este o reprezentare modestă a curbei.
Fig. 24 – Curbă cu inflexiuni
Sursă: http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/
40
Împreunarea curbelor. Drumul Bézier
Pentru a reprezenta o curbă mai complicată, există două opțiuni: fie va fi reprezentată
printr-o curbă Bézier cu gradul mare, fie va fi împărțită în mai multe segmente mici și va fi
folosită câte o curbă Bézier cu gradul mai mic pentru fiecare segment în parte. Această ultimă
metodă creionează un drum Bézier, care este, de obicei, mai simplă de implementat și mai
eficientă de folosit în detrimentul folosirii unor curbe cu grad mai ridicat. Implementată și în
cadrul jocului Tanks’s Assault, metoda folosită și descrisă în continuare este doar una dintr-o
varietate de posibilități de abordare.
Trimiși în scenă de către EnemyManager (la fel ca ceilalți oponenți), inamicii de nivel
avansat pornesc din starea Bézier, având un număr limitat predefinit de proiectile. Instanțierea
unui nou proiectil se face, așadar, doar în cazul în care această resursă mai este prezentă, iar
cel trimis anterior și-a atins ținta (în figura de mai jos).
Fig. 25 – Funcţia Update() a clasei BezierManager
Sursă: Tanks’ Assault
Odată lansată ghiuleaua, se trasează primele 4 puncte de control. Având un pas (step)
predefinit, reprezentând distanța de la un punct de control la următorul, se inițializează
punctele ca fiind în poziția precedentului, translatat cu o distanță step în direcția punctului
destinație. După această etapă, se trasează câte o linie imaginară din fiecare punct în
următorul, pentru a se verifica dacă nu există vreun obstacol. În acest sens, se poate observa în
figura 26 de mai jos funcția Physics.Raycast(Vector3, Vector3, out Raycast, float), care
primește ca parametru poziția curentă, direcția în care se îndreaptă (primii doi parametri) și
lungimea razei (ultimul parametru) și returnează o valoare de tip boolean. Dacă aceasta este
41
pozitivă, informațiile despre obstacolul întâlnit pot fi regăsite în parametrul de ieșire de tip
Raycast (al treilea parametru al funcției). Se poate observa că atunci când este găsit punctul
destinație, ghiuleaua este proiectată în acel loc, în timp ce, în caz contrar, punctele următoare
de control sunt translatate pe axa Y pentru a evita obstacolul.
Procesul se repetă și pentru restul punctelor de control până în momentul în care s-a
găsit destinația. Dacă aceasta nu a fost găsită, se adaugă punctele de control și se construiește
traiectoria pe care proiectilul o va urma. De remarcat este faptul că atunci când nu a fost găsit
niciun obstacol între punctele de control, algoritmul mai face un pas, calculând aceleași
informații și pentru un al cincilea punct de control, pentru a evita întâlnirea unui obstacol
brusc și nereușirea depășirii lui.
Fig. 26 – Funcţia FireRocket() din fişierul BezierManager.cs
Sursă: Tanks’ Assault
42
1. Optimizare
1.0 Binary Heap17
Un binary heap este un arbore binar cu proprietatea heap. Valoarea fiecărui nod este
mai mare sau egala cu valoarea părintelui. Există două moduri principale de reprezentare a
unui arbore binar: folosind obiecte de tip nod, care păstrează referințele către copiii lor, sau
printr-un vector, manipulând indexul nodului pentru a-i găsi copiii. Această ultimă abordare
poate fi regăsită și în lucrarea Tanks’ Assault.
Fig. 27 – Reprezentarea prin vector
Sursă: http://www.growingwiththeweb.com/data-structures/binary-heap/overview/
Remarcă: indexul copilului stâng al nodului poate fi calculat cu ajutorul formulei 2 * i + 1, în
timp ce indexul copilului drept cu formula 2 * i + 2, unde i este indexul părintelui.
De asemenea, indexul unui părinte poate fi găsit cu [(i – 1) / 2].
Deși un binary heap este un arbore binar, nu este neapărat și un arbore binar de căutare
(en. BST – Binary Search Tree). Spre deosebire de un binary heap, care reține în copii doar
noduri cu valori mai mari decât ale părinților, într-un arbore binar de căutare copilul stâng are
o valoare mai mică decât a părintelui, iar cel drept mai mare.
Inserarea
Inserarea unui element presupune adăugarea acestuia la finalul arborelui și schimbarea
recursivă cu nodul părinte, până când este găsit un părinte cu o valoarea mai mică.
17
http://www.growingwiththeweb.com/data-structures/binary-heap/overview/
43
F ig. 28 –Funcția SortUp(T), apelată după adăugarea unui nou nod
Sursă: Tanks’ Assault
Extragerea minimului
F ig. 29 –Funcția SortDown(T), apelată după extagerea nodului cu costul cel mai mic
Sursă: Tanks’ Assault
44
Având în vedere faptul că minimul este păstrat mereu în rădăcină, este foarte ușor de găsit.
După extragerea acestuia, ultimul element din arbore este adus și plasat ca rădăcină. Ultimul
pas este mutarea acestuia pe poziția sa potrivită. Așadar, în mod recursiv, este comparat cu
copiii săi și schimbat cu cel mai mic dintre aceștia.
Tabel complexități
Fig. 30 – Complexitățile operațiilor în cadrul diferitelor structuri de date
Sursă: http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
În cadrul algoritmului A* Pathfinding prezent în lucrarea de licență Tanks’s Assault,
optimizarea principală constă în alegerea structurii de date eficiente pentru lista deschisă. Deși
poate fi reținută în orice structură, cea mai bună decizie ar fi o listă ale cărei operații de
inserare și extragere sunt minime din punct de vedere al timpului de execuție. Performanța
operației de inserare este mai importantă decât a celei de extragere având în vedere faptul că
algoritmul în principiu nu extrage toate nodurile aflate în lista deschisă, excepție constituind
scenariul în care nu există un drum.
1.1 Object Pooling18
Făcând parte din categoria șabloanelor de proiectare creaționale, object pooling-ul
poate oferi o creștere semnificantă a performanței. Eficiența sa este conturată cel mai bine în
situațiile în care costul instanțierii unei clase este mare. Scopul principal este de a controla
păstrarea obiectelor într-un anumit spațiu, precum memoria cache. Un client cu acces la acest
18
https://sourcemaking.com/design_patterns/object_pool
45
grup de instanțe poate evita crearea unui nou obiect întrebând dacă nu cumva există unul
dispoinibil deja pus în scenă. De obicei, acest grup (pool) va fi unul în continuă creștere.
Fig. 31 –ObjectPoolerScript.cs
Sursă: Tanks’ Assault
În figura 31 de mai sus se poate observa instanțierea unei liste de obiecte pentru pool.
Atunci când este instanțiat un glonte, este apelată funcția GetPooledScript() din clasa Shoot.
46
Aceasta returnează toate obiectele active și la final, dacă este necesar, mărește acest pool,
instanțiind un nou obiect și adăugându-l.
2. Generarea Terenului
2.0 Fractali19
Fractalii sunt forme geometrice fragmentate sau frânte, care pot fi divizate în mai
multe părți, astfel încât fiecare dintre acestea să fie o copie a întregului.
Caracteristici
Auto-similitudinea Prin mărirea oricărei porțiuni dintr-un fractal, se va obține un
fractal similar cu cel întreg.
Definiția simplă și recursivă Pe scurt, poate fi considerat ca fiind mulțimea alcătuită
din valorile x, f(x), f(f(x)), f(f(f(x))) etc.
Detalierea și complexitatea infinită Are o structură fină la scări infinit de mici.
Esența fractalilor este dată de auto-similitudine. Un exemplu ar putea fi un țărm văzut
din spațiu. Acesta poate fi examinat de la diferite distanțe și, chiar dacă imaginile nu sunt în
totalitate identice, nu se poate spune dacă sunt doar o apropiere a unei zone sau întregul țărm.
Prin urmare, principala caracteristică a fractalilor în natură este faptul că obiectele pot fi
diferite în detaliu, dar totuși să arate similar.
Un teren fractal este o suprafață generată folosind un algoritm stocastic creat pentru a
produce un comportament fractal care să reproducă ideea de teren natural. Altfel spus,
rezultatul procedurii nu este o suprafață fractală deterministă, ci mai mult o suprafață
aleatoare care expune un comportament fractal.
Conceptele modelate în această lucrare se concentrează pe modelarea specificațiilor
macroscopice ale terenurilor. În acest sens, ideea este de a crea un teren cât mai realistic, lipsit
19
http://www.artacunoasterii.ro/curiozitati/fractali
47
însă de acuratețea terenurilor prezente în viața reală. Procedurile folosite în cadrul lucrării
Tanks’ Assault utilizează numere aleatoare pentru a oferi rezultate unice. Însă asignând
numere aleatoare la întâmplare nu constituie un scenariu favorabil, fiindcă se așteaptă ca două
puncte apropiate să aibă altitudini asemănătoare. Așadar, este necesară prezența unor
algoritmi care să ia în calcul proximitatea a două puncte atunci când sunt repartizate
înălțimile. Datele de ieșire ale acestor algoritmi constituie o mulțime de altitudini într-o
matrice.
Majoritatea jocurilor video folosesc matrici de înălțimi (en. heightmaps) pentru a
reține și a genera datele despre construcția terenurilor. În cadrul lucrării Tanks’ Assault,
această matrice de înălțime este generată folosind Perlin Noise și, pentru comparație,
algoritmul Diamond Square.
În figura 32de mai jos se poate observa o asemenea matrice construită pe o scară alb-
negru (stânga), împreună cu terenul generat în urma corespondenței valorilor din matrice
(dreapta).
Fig. 32 – Grayscale HeightMap (stânga),
Terenul generat corespondent valorilor din HeightMap (dreapta)
Sursă: Computer Landscape Generation and Smoothing
Se poate observa că, în cazul imaginilor alb-negru, intensității fiecărui pixel îi
corespunde o altitudine pentru fiecare punct din spațiu. În algorimul următor, în cadrul căruia
apare conceptul de Perlin Noise, terenul va fi reprezentat de matrici de altitudini cu valori de
tip float, cuprinse între 0 și 1.
48
Zgomot Coerent (en. Coherent Noise)
Este un tip de zgomot pseudoaleator. Generat de o funcție de tip zgomot coerent, are
trei proprietăți importante:
1 Introducând aceleași date de intrare, se vor obține aceleași date de ieșire.
2 O schimbare mică în datele de intrare va produce o schimbare mică în valorile
de ieșire.
3 O schimbare complexă în datele de intrare va produce o schimbare aleatoare
în valorile de ieșire.d
2.1 Perlin Noise
Este un tip de zgomot coerent, fiind un amalgam de funcții de zgomot coerent de
creștere a frecvențelor și de descreștere a amplitudinilor. Fiecare astfel de funcție este numită
o octavă. Fenomenul mai este numit Sinteza Spectrală. Fiind un caz de zgomot coerent,
înseamnă că schimbările au loc gradual. Luând în considerare faptul că pentru valorile întregi,
funcția returnează valori identice, în această lucrare de licență vor fi luate în considerare doar
date de intrare în intervalul [0,1).
Un zgomot de tip Perlin este un fractal în natură. O secțiune mărită a zgomotului tinde
să arate la fel ca originalul.
Unity oferă o funcție care generează un zgomot de tip Perlin. Aflată în structura Mathf
din UnityEngine, are forma Mathf.PerlinNoise(float, float) și returnează o valoare de tip float
din intervalul [0, 1].
Amplitudinea (Y axis) Valoarea maximă pe care o funcție de tip zgomot coerent o
poate avea.
Frecvența (X axis) Numărul de cicluri pe unitate pe care o funcție de tip zgomot
coerent le poate avea.
49
Lacunaritatea Un multiplicator care determină cât de repede crește frecvența pentru
fiecare octavă succesivă într-o funcție de tip Perlin Noise. Frecvența fiecărei octave succesive
este egală cu produsul dintre frecvența octavei precedente și valoarea lacunarității.
Persistența Un multiplicator care determină cât de repede este diminuată amplitudinea
pentru fiecare octavă succesivă într-o funcție de tip Perlin Noise. Amplitudinea fiecărei octave
succesive este egală cu produsul dintre amplitudinea octavei precedente și valoarea
persistenței. Creșterea persistenței duce la producerea unui zgomot nefinisat.
În figura 33 de mai jos pot fi observate două heightmap-uri dintr-un context al lucrării
Tanks’ Assault. În partea stângă se pot distinge datele de ieșire după aplicarea Perlin Noise-
ului, în timp ce în dreapta au fost aplicate culori pe diferite intervale.
Fig. 33 – Grayscale HeightMap PerlinNoise din joc
Sursă: Tanks’ Assault
În figura 34 de mai jos poate fi observată funcția GenerateNoiseMap(int, int, int, float, int,
float, float, Vector2), care primește ca date de intrare dimensiunile terenului, un seed, un
parametru de scalare, numărul de octave, valorile persistenței și lacunarității, dar și un vector
de deviere (en. offset). Această procedură calculează mapa de altitudini și o returnează la
final.
50
Fig. 34 – GenerateNoiseMap(int, int, int, float, int, float, float, Vector2)
Sursă: Tanks’ Assault
51
Fig. 35 – Octave
Sursă: https://github.com/SebLague/Procedural-Landmass-Generation
Notă: lacunaritate = 2, persistență = 0.5
Octava 1 (munții): frecvență = lacunaritate0 = 1, amplitudine = persistență
0 = 1
Octava 2 (dealurile): frecvență = lacunaritate1 = 2, amplitudine = persistență
1 = 0.5
Octava 3 (stâncile mici): frecvență = lacunaritate2 = 4, amplitudine = persistență
2 = 0.25
Combinația acestor octave duce la următorul rezultat:
Fig. 36 – Rezultat obținut din combinarea octavelor
Sursă: https://github.com/SebLague/Procedural-Landmass-Generation
Pentru a obține o valoare de deviere aleatoare pentru fiecare octavă, se folosește
parametrul seed, alegându-se o valoare în intervalul [-100000, 100000). Acest lucru este
necesar, luând în considerare faptul că funcția Mathf.PerlinNoise dă aceeași valoare pentru
aceleași date de intrare.
După generarea heightmap-ului, urmează construirea propriu-zisă a terenului. Apare
conceptul de Mesh în Unity, fiind o clasă care permite crearea sau modificarea rețelei de
noduri din cod.
52
Fig. 37 – Clasa MeshData
Sursă: Tanks’ Assault
În figura 37 de mai sus se poate observa faptul că, pentru construirea unei rețele de
noduri, sunt necesare trei elemente: un vector care să conțină pozițiile nodurilor, un vector
pentru triunghiuri și un vector pentru uv-uri (coordonatele texturii de bază a Mesh-ului). Este
de menționat faptul că Mesh-urile sunt formate din triunghiuri.
Numărul total de noduri este de width * height.
Numărul total de triunghiuri este (width – 1) * (height – 1) * 6.
În figura alăturată se pot observa două triunghiuri formate.
Primul este (i, i+w+1, i+w), iar al doilea (i+w+1, i, i+1) – unde i este
poziția curentă,, iar w reprezintă lungimea. Așadar, vectorul de triunghiuri va fi (i, i+w+1,
i+w, i+w+1, i, i+1, ...).
53
Fig. 38 – Funcția GenerateTerrainMesh(float[,], float, AnimationCurve,
levelOfDetail)
Sursă: Tanks’ Assault
Terenul generat în urma funcției GenerateTerrainMesh()
Fig. 39 – Terenul generat
Sursă: Tanks’ Assault
54
Unity Error
„A mesh may not have more than 65000 vertices”
De fapt, valoarea este 65025 (2552). Așadar, dimensiunea maximă a unui Mesh generat
prin intermediul unui script este de 255x255. Fiind un număr relativ mic, soluția ar fi
generarea mai multor astfel de secțiuni, care să se lege și să formeze un univers “infinit”.
Introducerea chunck-urilor (a bucăților de teren) pare inevitabilă, în cazul în care o generare a
unui teren de dimensiuni mari ar duce la „înghețarea” editorului și, implicit, a jocului.
Pentru a optimiza această generare, Mesh-urile vor fi create odată cu mișcarea
protagonistului în scenă, fiecare într-un thread diferit. De asemenea, vor fi puse în scenă doar
chunck-urile din aria de vizibilitate a utilizatorului. În acest sens, apare și conceptul de LOD
(en. level of detail20
), care rezolvă problema supraîncărcării inutile. Prin urmare, Mesh-urile
de lângă protagonist vor fi foarte detaliate, în timp ce bucățile de teren din aria vizuală
îndepărtată vor fi randate cu un număr mai mic de noduri, reducând astfel claritatea, dar și
eficientizând fluxul jocului.
Dacă am avea 7 noduri pe o linie (numerotate de la 0 la 6), am avea nivelurile de
detaliere: 1 – atunci când se merge din nod în nod, 2 – se sare un nod, 3 – se trece prin
nodurile (0, 3, 6) și 6 – primul și ultimul nod. Prin urmare, dimensiunea perfectă pentru o
bucată de teren este acea dimensiune care este divizibilă cu cât mai multe numere. Numărul
ales este 241, având în vedere că este aproape de numărul maxim (255) și că (width – 1) este
divizibil cu toate numerele pare până la 12 (6 niveluri de detaliere). Continuând pe această
idee, numărul de noduri pe fiecare linie poate fi aflat folosind formula (width – 1) / i + 1,
unde i este indexul care arată nivelul de detaliere.
În figura de mai jos se poate observa terenul generat pe 3 niveluri de detaliere.
20
Niveluri de detaliere
55
Fig. 40 – Nivelul 0, 3 și 6
Sursă: Tanks’ Assault
2.3 Algoritmul Diamond-Square21
Algoritmul Diamond-Square este o metodă de generarea a heightmap-urilor. Mai este
cunoscut sub denumirile de fractalul cu deplasarea aleatoare a punctului de mijloc (en.
random midpoint displacement fractal), fractalul de nori (en. the cloud fractal) sau fractalul
plasmatic (en. the plasma fractal) pentru efectul de plasmă produs atunci când este aplicat.
În cadrul procedurii, fiecare punct depinde de nodurile din patru direcții. Pașii de
parcurs:
1 Asignarea de altitudini aleatoare celor patru noduri din colțurile grid-ului.
2 Pasul Diamond: Calcularea mediei celor patru noduri din colțuri și adăugarea
unui perturbator aleator distribuit în mod egal între –ri și r
i. Asignarea acestuia punctului din
mijlocul celor patru noduri.
3 Pasul Square: Pentru fiecare “Diamond” produs, se calculează media celor
patru colțuri și se adaugă o perturbare aleatoare cu aceeași distribuție.
4 Repetarea pașilor 2 și 3 de un număr de iterații stabilit.
21
Algorithms for Generating Fractal Landscapes, Keith Stanger
56
Notă: valoarea r reprezintă parametrul de nefinisare, în timp ce i indică iterația
curentă. Următoarele diagrame ilustrează punctele adăugate în pașii Diamond și Square
pentru primele două iterații:
Fig. 41 – Primele două iterații ale pașilor Diamond și Square
Sursă: Algorithms for Generating Fractal Landscapes
Fig. 42 – Algoritmul Diamond
Sursă: Tanks’ Assault
57
În figura de mai jos poate fi observată implementarea algoritmului Diamond-Square în
cadrul lucrării Tanks’ Assault.
Fig. 43 – Algoritmul Diamond- Square
Sursă: Tanks’ Assault
58
Studiu de caz – Învătarea automată în dezvoltarea jocurilor22
Industria jocurilor
Învățarea automată a fost privită cu prudență de către dezvolvatorii de jocuri încă de la
început, neregăsindu-se până în prezent în niciun proiect de o complexitate ridicată. Întrebarea
din spatele acestei atitudini precaute ar fi dacă un utilizator obișnuit va aprecia avansul
semnificativ în această direcție sau va fi iar o altă risipă de timp și de bani? În acest sens,
multe companii contemporane se concentrează asupra creării de jocuri care să altereze
tacticile și strategia jucătorului, în locul dezvoltării abilităților oponentului. Tentația
dezvoltatorilor este aceea de a crea o impresie falsă de învățare, modalitate întâlnită frecvent
în industria jocurilor.
Reinforcement Learning
Agentul poate vedea rezultatul acțiunilor sale, dar nu îi este spus în mod direct ce ar fi
putut face în loc.
Crearea unei entități(agent) care învață
Pentru a crea o astfel de entitate, trebuie luați în considerare o serie de factori care îi
vor influența performanța. În cadrul jocului Tanks’ Assault, un asemenea factor ar putea fi
terenul, aflându-se poziționat între cele două tabere adverse și, astfel, putând fi folosit în
avantajul agentului.
Pe de altă parte, în comportamentul fiecărui agent trebuie să existe un element secret,
pentru a evita apariția unui șablon și a ușura munca utilizatorului în găsirea unei tactici.
O entitate care învață este compusă din câteva părți fundamentale:
Factorul de învățare - Partea agentului care îi modifică comportamentul și conturează
îmbunătățiri.
Factorul de performanță – Responsabil pentru alegerea acțiunilor externe, decizie
luată pe baza percepțiilor primite (a informațiilor primite).
Factorul de curiozitate – Responsabil pentru alegerea unei soluții mai bune. În cadrul
jocului Tanks’ Assault, un astfel de scenariu ar putea fi întalnit atunci când atât tancul
22
http://ai-depot.com/GameAI/Learning.html
59
protagonist, cât și agentul au viața pe terminate. În mod normal și din experiențele din trecut,
entitatea ar trebui să se retragă, pentru a-și reîncărca viața, lucru care ar duce la o performanță
adecvată. Totusi, factorul de curiozitatea intervine și sugerează ca acesta sa iasă și să tragă în
adversar, pentru ca scopul lui este de a-l doborî, nu de a rămâne cât mai mult în viață. Așadar,
acest context ar putea duce la împușcarea agentului, dar, tot cu aceeași probabilitate, ar putea
atinge un scop mult mai benefic. După, va rămâne la latitudinea analizatorului de performanță
și a factorului de învățare dacă există un beneficiu în această schimbare de strategie.
Analizatorul de performanță – Judecă performanța agentului în raport cu câteva repere
adecvate de performanță. În cadrul jocului Tanks’ Assaul, un astfel de reper ar putea fi cât de
aproape este agentul de a fi lovit de utilizator. Performanța trebuie examinată pe baza
acelorași percepții ca cele primite de către factorul de performanță. În urma analizei de
performanță, agentul trebuie să decidă dacă un scenariu mai bun ar putea fi ales în viitor în
aceleași împrejurări. După, decizia este înmânată factorului de învățare, care decide asupra
alterării potrivite a comportamentului în viitorul apropiat, modificând elementul de
performanță în concordanță.
Probleme cu învățarea
În ciuda potențialului imens pe care învățarea îl oferă lumii jocurilor, trebuie folosit cu
atenție pentru a evita anumite capcane. Mai jos sunt câteva exemple de probleme des întâlnite
în construcția un AI care învață:
Copierea unui AI cu un comportament plin de nonsens – Atunci când dezvoltatorul
învață un AI să copieze strategia unui utilizator, acest lucru poate duce la rezultate slabe.
Acest lucru se întâmplă atunci când un jucător nu este familiarizat cu jocul. În această situație,
a funcție de reset este necesară pentru a aduce jucătorul AI înapoi la starea inițială.
Overfitting – Poate apărea atunci când o entitate învață doar o parte a jocului și se
așteaptă ca aceasta să arate un comportament inteligent bazat pe propria experiență. De
exemplu, un agent care a învățat din propria experiență la un anumit nivel va întâlni probleme
când va ajunge la un nou nivel, având în vedere faptul că ar putea interveni scenariul în care
acesta să nu fi învățat corect din propria performanță.
Local Optimality – Când este ales un parametru pe care se bazează învățarea agentului,
să fie unul care nu are nicio dependență față de acțiunile trecute.
60
Set Behaviour – Odată ce un agent are un set de rezultate ale comportamentului său
din trecut și analiza performanței rezultată, se oprește și alege un comportament care l-a ajutat
să ajungă la un scenariu pozitiv sau încearcă noi metode în dorința de a se dezvolta?
Tipuri de învățare
Există două tipuri de învățare automată folosită în jocuri. Una este învățarea la design-
time, unde rezultatele învățării sunt aplicate înaintea lansării jocului; cealaltă este învățarea la
runtime, particularizată pentru un anumit jucător sau sesiune.
Un exemplu de învățarea la runtime este jocul Black and White (1 și 2), unde animalul
de companie al protagonistului învață ce să facă prin răscumpărare și pedepsire.
Black & White23
Într-un studiu realizat de site-ul AiGameDev.com24
, cel mai popular joc din punct de
vedere al inteligenței artificiale folosite este Black & White. Lansat în anul 2001 de către
Lionhead Studios, Black & White este un joc care include elemente de simulare artificială a
unei vieți și câteva strategii. Jucătorul conduce o insulă populată de diverse triburi și își învață
animalul de companie să îi facă munca. Inovații:
Gameplayul este concentrat pe interacțiunea cu o creatură inteligentă (AI) care învață
din exemple și primește recompense sau pedepse.
Designul integrează o viață artificială în contextul unui joc strategic.
Motorul folosește o arhitectură solidă AI, cu rădăcini în știința cognitivă, cunoscută
sub numele de belief-desire-intention (BDI).
Tehnici de învățare automată precum arborii de decizie sau rețelele neuronale sunt
folosite cu mare succes.
Majoritatea AI-urilor prezente în jocuri au anumite comportamente specifice. Fie că
sunt fixe de la începutul jocului, sau trec prin mai multe stări comportamentale pe care le
23
http://www.eurogamer.net/articles/2015-07-26-black-and-white-combined-the-sublime-with-the-stupid 24
https://aigamedev.com/open/highlights/top-ai-games/
61
folosesc prin rotație în funcție de context, ele pot fi înțelese de utilizator. Jocurile adeptă acest
model din diferite motive, având nevoie ca AI-ul să fie într-un anumit sens previzibil, astfel
încât jucătorul să învețe cum să își înfrângă inamicul. Chiar și Black & White folosește acest
concept tradițional pentru săteni. De exemplu, chiar dacă maestrul aruncă cu pietre în casele
lor, ei nu vor învăța să nu mai ceară mâncare.
Însă, tot în același joc, AI-ul creaturii este diferit. Acesta combină conceptul tradițional
cu noțiuni interesante precum arborii de decizie, care creează o hartă ierarhizată a credințelor
AI-ului, făcându-l să ia anumite decizii, sau rețelele neuronale, care în termeni simpli lasă
creatura să facă anumite presupuneri despre propriul comportament și fie să continue sau să
schimbe aceste presupuneri depinzând de răspunsuri externe.
Rezultatul final este un AI care poate învăța și își poate dezvolta noi abilități urmărind
acțiunile utilizatorului sau ale sătenilor și să le aplice acolo unde este nevoie. Așadar, poate
ajuta sătenii să aducă resurse în magazia satului sau să folosească stropitori pe terenurile
arabile pentru a ajuta la dezvoltarea materiilor prime. Poate, de asemenea, să își altereze
comportamentul în funcție de relația cu utilizatorul (dacă este pedepsit sau răsplătit) atunci
când gândește sau se comportă într-un anumit fel, care îi va afecta moralul, deseori reflectând
personalitatea maestrului.
Creatura nu este perfectă. Această învață repede, pentru a evita scenariul în care
utilizatorul se plictisește. Prin urmare, poate fi învățat într-un anumit fel repetând același lucru
într-un interval de cinci minute.
Ca încheiere a acestui studiu de caz, se poate concluziona că există un potențial foarte
mare pentru învățarea automată în jocurile video, însă aceasta trebuie folosită cu atenție. În
ciuda prețului dezvoltării acestui tip de software, pare că învățarea va avea de jucat un rol
foarte important în următoarea generație de jocuri video.
62
Unity
În vederea lansării unui joc, există o serie de pași care trebuie urmați. Primul ar fi
alegerea unui game engine, în funcție de propriile preferințe. Câteva puncte cheie în
conturarea acestei decizii ar putea fi gradul de utilizare (cât de ușor este de lucrat cu el),
funcționalitatea (ce poate face concret motorul) și prețul. Cele mai populare la momentul
actual sunt Unity, Unreal Engine 4 și CryENGINE. Toate aceste trei game engine-uri sunt
foarte puternice și fiecare are propriile puncte forte.
Unity este considerat “Goliatul” dezvoltării de jocuri indepedente, fiind folosind de
multe studiouri importante. Are o interfață prietenoasă, care îi oferă dezvoltatorului
posibilitatea de a coordona totul eficient încă de la început. Dispune de versiuni gratuite,
oferind utilizatorului ocazia de a-și folosi propria creație pe anumite platforme fără a avea
nevoie de o licență. Această remarcă conturează, în mare parte, motivul pentru care am ales
Unity pentru a-mi construi lucrarea de licență.
Conform unui studiu realizat de venturebeat.com25
, dezavantajele folosirii motorului
Unity ar fi la nivel de unelte (acestea fiind limitate) și de complexitate timp (consum mare de
timp pentru a realiza un proiect complex cu diverse efecte).
25
http://venturebeat.com/2014/08/20/the-top-10-engines-that-can-help-you-make-your-game/
63
Concluzii
Luând în considerare importanța jocurilor video în viața cotidiană și dorința
utilizatorilor de a trăi experiențe în care să fie nevoiți să gândească eficient și repede diverse
strategii, lucrarea Tanks’ Assault aduce un plus industriei, combinând diverse idei cu
proiectarea inovatoare a unor algoritmi în scenă și optimizarea lor. Partea culminantă a
aplicației o constituie situația în care utilizatorul trebuie să își gestioneze resursele și să
găsească o strategie pentru a rămâne în viață și pentru a doborî cât mai mulți oponenți.
Prezența șabloanelor de proiectare impune o claritate în structura codului, delimitând
foarte bine anumite părți participante.
De asemenea, este de remarcat viziunea lucrării asupra ideii de teren. Privit ca un
fractal, acesta este generat aleator cu diferiți algoritmi și repetat pe măsură ce protagonistul
înaintează, creând ideea de spațiu infinit. Spre deosebire de alte jocuri video în care terenul
este generat la începutul scenei și sunt finit delimitate, terenul din Tanks’ Assault poate
constitui un punct de plecare pentru generarea unor forme de relief mult mai complexe și
realiste, dar cu mult mai puține resurse.
Nu în ultimul rând, comparația tehnică dintre algoritmul Diamond-Square și Perlin
Noise se face la nivel subiectiv. În timp ce algoritmul Diamond-Square produce valori mai
compacte, exprimându-se în forme de relief mai muntoase, Perlin Noise conturează mai bine
fluiditatea terenului.
Extensii
1 Adăugarea unui mod storyline.
2 Posibilitatea de a juca multiplayer.
64
Referințe
A* Pathfinding Algorithm. (2012, 06 03). Retrieved from growingwiththeweb.com:
http://www.growingwiththeweb.com/2012/06/a-pathfinding-algorithm.html
Blasterzone. (2012, 06 01). Retrieved 11 28, 2016, from blasterzone.ro:
http://www.blasterzone.ro/istoria-jocurilor-first-person-shooter-fps
Binary Heap. (2016, 12 25). Retrieved from growingwiththeweb.com:
http://www.growingwiththeweb.com/data-structures/binary-heap/overview/
No Man's Sky. (2016, 07 12). Retrieved 11 28, 2016, from computergames.ro:
http://computergames.ro/no-mans-sky/
No Man's Sky. (2016). Retrieved 11 28, 2016, from wikipedia.org:
https://en.wikipedia.org/wiki/No_Man's_Sky
Bezier Curve. (n.d.). Retrieved from wikipedia.org: https://en.wikipedia.org/wiki/B%C3%A9zier_curve
Champandard, A. J. (2007, 09 12). Top AI Games. Retrieved from aigamedev.com:
https://aigamedev.com/open/highlights/top-ai-games/
Coherent Noise Glossary. (n.d.). Retrieved from libnoise.sourceforge.net:
http://libnoise.sourceforge.net/glossary/
Design Patterns. (n.d.). Retrieved from tutorialspoint.com:
http://www.tutorialspoint.com/design_pattern/design_pattern_overview.htm
Diamond Square Algorithm. (n.d.). Retrieved from en.wikipedia.org:
https://en.wikipedia.org/wiki/Diamond-square_algorithm
Fractali. (n.d.). Retrieved from artacunoasterii.ro: http://www.artacunoasterii.ro/curiozitati/fractali
Gamma, E., Helm, R., Johnson, R., & Vlissides, J. (n.d.). Design Patterns Elements of Reusable Object-
Oriented Softawre.
Jackson, N. (2011, 06 03). Infographic Video Game Industry Statistics. Retrieved from
theatlantic.com: http://www.theatlantic.com/technology/archive/2011/06/infographic-
video-game-industry-statistics/239665/
Jasani, T. (2014, 08 20). The Top 10 Engines That Can Help You Make Your Game. Retrieved from
venturebeat.com: http://venturebeat.com/2014/08/20/the-top-10-engines-that-can-help-
you-make-your-game/
Lague, S. (n.d.). Pathfinding. Retrieved from github.com: https://github.com/SebLague/Pathfinding
Lague, S. (n.d.). Procedural Landmass Generation. Retrieved from github.com:
https://github.com/SebLague/Procedural-Landmass-Generation
65
Lane, R. (2015, 07 25). Black And White. Retrieved from eurogamer.net:
http://www.eurogamer.net/articles/2015-07-26-black-and-white-combined-the-sublime-
with-the-stupid
Macklem, G. (2003). Computer Landscape Generation and Smoothing.
No Man's Sky Sentinel. (n.d.). Retrieved 11 28, 2016, from nomanssky.gamepedia.com:
http://nomanssky.gamepedia.com/Sentinel
Null Object Design Pattern. (n.d.). Retrieved from sourcemaking.com:
https://sourcemaking.com/design_patterns/null_object
Palmer, N. (n.d.). Game AI Learning. Retrieved from ai-depot.com: http://ai-
depot.com/GameAI/Learning.html
Programming Patterns. (n.d.). Retrieved from habrador.com:
http://www.habrador.com/tutorials/programming-patterns/
Stanger, K. (2006). Algorithms for Generating Fractal Landscapes.
Tulleken, H. (2011, 04 05). Bezier Curves Tutorial. Retrieved from devmag.org.za:
http://devmag.org.za/2011/04/05/bzier-curves-a-tutorial/
Unity 3D. (n.d.). Retrieved from docs.unity3d.com: https://docs.unity3d.com
Zahirovic, N., & Schjerlund, J. (2015). Diamond Square Algorithm Visualization.