AI

Kursuse raames on teil tarvis enda mängule lisada ka mõni AI komponent. Kõige parem viis alustada mõne AI komponendi loomisega, kui enne kogemust pole, ongi lisada mängu non-playable-characterid (NPC-sid), kes liiguvad mängus ringi nii nagu teie mäng ette näeb.

NB! Siin materjalides on näitel kasutusel Kryonet. Kui te kasutate mingit muud library-t, siis peaksite järgima selle dokumentatsiooni.

Näiteks võivad need NPC-d jälitada mängijat, või hoopis proovida võita mängijat mõnes labürindi tüüpi mängus.

Siin vaatamegi, kuidas panna AI serverisse niimoodi, et kõik mängijad näeksid seda mängus ligikaudu samas asukohas, ning lisame sellele ka A* teekonnaplaneerimise.

NB! Kindlasti tutvu ka antud materjaliga: Introduction to the A* Algorithm.

Teie AI komponent peaks jooksma serveris sellepärast, et tegu on multiplayer mänguga. Multiplayer mängudes keskendub kliendi pool üldiselt renderdamisele ja enamus loogika on serveris.

Klasside loomine

Esiteks oleks mõistlik luua iga mängu jaoks eraldi objekt, mis võimaldab mänge lihtsasti eraldi hallata ning hoiab need üksteisest sõltumatuna. Kui teil on ka terve serveri peale ainult 1 mängu objekt, siis pole ka see probleem. See tähendab, et teil läheb vaja mängu klassi.

Teiseks oleks vaja luua mingi NPC klass serverisse, näiteks nii:

Sellel klassil peaks kindlasti olema muutujad x ja y koordinaatide hoidmiseks. Samuti peaksime igale NPC-le andma ka unikaalse id. Selleks on lihtne viis kasutada staatilist suurima id muutujat ning seda suurendada kui uue objekti loome. Lisasin klassile ka meetodi moveThread, et AI alustaks oma tegevust kohe, kui objekt luuakse. Praegu võib see meetod jääda tühjaks, kuid varsti jõuame selle juurde tagasi.

Kolmandaks võiks teil olla mingi list kõigist hetkel mängus olevatest NPCdest ja meetod NPC-de loomiseks, eeldatavasti võiksid need asuda teie mängu klassis. Võiksite oma Game klassis teha midagi sarnast:

Neljandaks peaksite samamoodi looma NPC klassi ka kliendi poolele, ning kusagil hoidma ka listi kõigist renderdavatest NPC-dest. Selle juurde, kuidas NPC liikumisi kliendi poolel renderdada, jõuame hiljem.

A* pathfinding ja liikumine

A* algoritmi tööpõhimõte

Erinevaid algoritme, mis leiavad tee mingist alguspunktist mingisse lõpppunkti on palju, aga kõige parem mängude jaoks on A*. Selle algoritmi plussid on näiteks kiirus, et ta leiab alati kõige lühema tee ning et ta on efektiivne.

Lühidalt öeldes töötab A* pathfinding nii:

1. Anname ette mingi alguspunkti- ja lõpppunkti koordinaadid.

2. Salvestame alguspunkti meie koordinaatide järjekorda, prioriteediga 0.

3. Hakkame loopima koordinaatide järjekorda, valime kõige väiksema prioriteediga koordinaadi ning kustutame selle.

4. Leiame hetkese punkti naabrid, kuhu saame liikuda (pole collisionit) (x - 1, y - 1, x + 1, y + 1).

5. Arvutame iga koordinaadi jaoks prioriteedi (kaugus lõpppunktist + kui palju me liikunud oleme alguspunktist).

6. Lisame leitud naabrid koos prioriteediga koordinaatide järjekorda.

7. Kordame 4-6.punkti kuni oleme jõudnud lõpppunkti või kuni järjekorras pole enam ühtegi punkti (ei leidnud teed).

A* algoritm Javas

1. Loome serverisse AStar klassi

Selgituseks: AStar klassi loomisel tuleb kaasa anda kaardi kahedimensiooniline int massiiv. See võimaldab A* algoritmil määrata, kus asuvad seinad, millest läbi minna ei saa, ning määrata kaardi mõõtmed (maxX ja maxY). Näites on see kahedimensiooniline massiiv veergude massiividest. Massiivis tähistab täisarv 1 takistust (collision'it):

2. Loome AStar klassi Node klassi

Node klassis tähistab hScore kaugust lõpppunktist, ning gScore tähistab seda, kui palju me liikunud oleme, et sinna punktini jõuda.

3. Loome meetodi findPath, leidmaks teed alguspunktist lõpppunkti

Meetod findPath tagastab teekonna lõpppunktist alguspunkti.

Võiksite selle koodi läbi lugeda ja natuke analüüsida, et saaksite aru mis toimub.

Võite testida, kuidas see algoritm töötab, näiteks nii:

Liikumine kasutades A* algoritmi

NPC-de lisamine mängu

Esiteks oleks meil vaja NPC-d kuidagi mängijate kaartidele saada. Selleks võiks luua mõne packet'i klassi, millega saata infot AI kohta (tema id ning algne asukoht)

See võiks olla midagi sellist:

Lihtsustatult öeldes oleks meil vaja igale uuele mängijale, kes mängu satub, saata iga NPC kohta infot. NPC-d saame eristada id järgi ning hiljem anname selle NPC id kaasa ka liikumise packet'itega.

Õige lähenemine oleks järgnev: kui mingi mängija satub mängu -> loopi kõik NPCd serveris läbi -> saada OnSpawnNpc objekt sellele mängijale

Kliendi poole NPC-de haldamine

Edasi peaksime selle packet'i kliendis ka vastu võtma ja nagu eelpool sai mainitud, võiks meil ka kliendi poolel olla eraldi NPC klass ja samuti ka list kõigist mängus olevatest NPC-dest. Võtame OnSpawnNpc packet'i kliendi poolel vastu, ja teeme iga kord uue NPC objekti, kuhu anname kaasa packet'iga saadud x ja y koordinaadid ning id, mida on hiljem liikumiseks vaja.

Näide NPC klassist kliendi poolel

OnSpawnNpc paketi vastu võtmine, ning meetod, kus lisame uue NPC listi

Kuna kliendi poolel meie NPC klass extendib Sprite klassi, siis lisame ka update() ja draw() meetodid.

NPC-de renderdamine kliendis

Liigume renderdamise juurde. Klassis, kus jookseb teie põhiloogika ning kus renderdate ka teisi asju, tuleks nüüd hakata renderdama ka NPC-sid.

Selleks oleks hea lisada eraldi meetod

renderNpcs() meetodi väljakutsumine tuleks panna teie render meetodi alla, kus renderdate ka kogu muu mängu.

Nüüd peaksid vähemalt kõik NPC-d kaardile tekkima. Nende algsed asukohad oleks vaja serveris ette anda vastavalt, kuidas teie mäng ette näeb. Kui lõime NPC klassi serverisse, lisasime sinna ka x ja y koordinaadid, ning need oleks vaja kaasa anda vastavalt teie mängule. Muidugi tuleks jälgida, et need teie kaardist välja ei läheks. Üks soovitus kuidas seda teha, on näiteks see, et te võtate oma kaardi piirid (kõige alumine vasak punkt ning kõige ülemine parem punkt) ja kontrollite, et asukoht jääks nende kahe koordinaadi vahele.

Tuleb ka silmas pidada seda, et pathfindingus kasutame tile-de koordinaate. Ehk kui 1 tile suurus on 32x32, siis tuleks NPC x ja y koordinaat korrutada 32-ga.

NPC-de liikumise haldamine serveris

Liigume tagasi serverisse. Alguses tegime serverisse NPC klassi ning ka meetodi moveThread, see võiks olla meetod, mis töötab mingi teatud aja tagant, ning muudab meie NPC asukohta.

Loome alguses klassi NPC liikumise saatmiseks. See võiks olla ka arusaadavalt nimetatud, näiteks OnNpcMove

Anname kaasa selle NPC id, et kliendis teada, millist NPC-d peame liigutama, ja samuti ka x ja y koordinaadid, kuhu NPC peaks liikuma.

Liigume moveThread meetodi juurde. Me soovime, et seda meetodit kutsutaks välja konstantselt teatud aja tagant. Selle jaoks on Javas olemas ScheduledExecutorService.

Natuke koodi selgituseks: loome uue ScheduledExecutorService ning paneme botRunnable Runnable jooksma iga 300 millisekundi tagant ning see hakkab jooksma 2 sekundit pärast väljakutset.

Nüüd on meil olemas runnable, mis läheb käima iga 300 millisekundi tagant. Hiljem te võite seda kiirust muidugi muuta.

Ja veel peaksite te ka sinna looma uue AStar klassi, kus annate kaasa oma mängu kaardi (collision'ite jaoks), et hiljem kasutada findPath meetodit tee leidmiseks.

Nüüd peaksime serverisse NPC klassi lisama path listi (list Nodedest mis saime tagastuseks findPath meetodist)

Loome muutuja path, mis on selle NPC hetkene teekond, mida ta läbib.

private ArrayList<AStar.Node> path;

Nüüd saame moveThread meetodis vaadata, et kui meie path on kas null, või tema pikkus on 0, siis leiame uue teekonna A* abil

Siin võtame mingi suvalise asukoha kaardil ning kui selle asukoha collision on 0, ehk sinna on võimalik minna, siis leiame me teekonna NPC praegusest x ja y koordinaatidest sinna asukohta järgneva reaga:

path = aStar.findPath((int) yCur, (int) xCur, (int) y, (int) x);

Muutujad minX, maxX, minY ja maxY võite kas ise defineerida, või valida minimaalseks x-ks ja y-ks 0 ja maksimaalseks x-ks ja y-ks teie mängu kaardi kõige suurema võimaliku asukoha.

While loopi kasutame sellepärast, et me otsime kaardil mingit täiesti suvalist asukohta nii kaua, kuni me oleme leidnud asukoha, kus collisionit pole.

Nüüd kui meil on olemas asukohta path list, mille järgi liikuda, asume nende asukohtade saatmise juurde. Nagu enne sai ära märgitud, siis findPath tagastab teekonna tagurpidi, ehk ülalpool andsime teekonna ette nii, et praegune asukoht on justkui see, kuhu minna tahame ja asukoht, kuhu me tegelikult minna tahame, on siis algne asukoht. Muidugi on võimalik ka list tagurpidi pöörata, aga see oleks antud lahenduse juures ebavajalik.

Kui meie path ei ole null ja tema pikkus ei ole samuti 0, teeme järgmist:

Võtame path listist 0 indeksiga elemendi ja eemaldame selle. Loome OnNpcMove objekti saatmiseks kõigile mängus olevatele mängijatele, kuhu lisame selle NPC id ja x ja y koordinaadid, kuhu ta liigub ning lõpuks saadame selle.

Meetod sendEveryone saadab siin näiteks packet'i igale mängijale sendTCP meetodi abil. See on kasutusele võetud sellepärast, et kui meil jookseb mitu mängu serveris paralleelselt, siis ei saa me kasutada kryoneti sisseehitatud funktsiooni sendTCPAll.

Meil on igal Game objektil oma id, ning iga game objekt sisaldab listi hetkel sees olevatest mängijatest.

Multithreading

Kui te otsustate packet'ide saatmise lahendada sarnaselt selle näitega, siis tuleb tähele panna seda, et me kutsume meetodit sendEveryone välja mitmelt erinevalt threadilt. Main threadilt, kus võtame vastu klientide poolt saadetud packet'e ning nüüd ka NPC klassi moveThreadilt, sellepärast, et executor loob uue threadi, et mitte takistada seda, mis toimub main threadil. Nüüd on väga oluline, et meetodit sendEveryone me ei käivitaks samal ajal mitmelt erinevalt threadilt, kuna siis võib juhtuda situatsioon, kus see meetod ei lõppegi kunagi ära, vaid jääb käima. See juhtub sellepärast, et me loeme samu muutujaid mitmelt erinevalt threadilt. See võib tunduda hetkel keeruline, aga lihtsalt tasuks praegu meelde jätta, et multithreading on ohtlik ning sellega tuleb olla ettevaatlik.

Selle jaoks on Javas olemas selline asi nagu Lock.

private final ReentrantLock lock = new ReentrantLock();

lock.lock();
try {
    //do something
} finally {
    lock.unlock();
}

Kasutame meetodis sendEveryone muutujat ReentrantLock lock ning meetodi välja kutsega lukustame selle. Sisuliselt tähendab see seda, et kui lock on juba mingi teise threadi poolt hõivatud (lukustatud), siis teine thread, mis ka sama meetodit välja kutsus, niikaua ootab.

Nüüd, kuna me loopime listi players (list kõigis mängus olevatest mängijatest) ja me muudame seda listi kahel juhul - kui keegi mängu tuleb või kui keegi mängust lahkub, siis me peaksime ka sinna lisama selle sama muutuja lock. Ehk siis kui keegi tuleb mängu, teeme lock.lock(), lisame mängiija listi, ning peale seda vabastame luku lock.unlock(). Samamoodi ka mängust lahkumisega. Seda on vaja teha sellepärast, et muidu võib juhtuda selline asi, et näiteks saadame ühelt NPC threadilt uusi asukohti sendEveryone meetodiga, ja täpselt samal ajal ka keegi lahkub mängust. Juhtub selline asi nagu ConcurrentModificationException. Me loopime listi samal ajal, kui me seda muudame ning sellega tekib palju probleeme. Ehk siis kui te kasutate sama meetodit nagu siin näites, kasutage locke nendes kohtades.

Muidugi te võite huvi pärast katsetada, et mis juhtub siis kui te ei kasuta lock-i. Suur tõenäosus, et midagi ei juhtugi, kui teil palju mängijaid mängus ei ole.

Kui teil on vaid 1 mängu seanss, ja muidu saadate ka kõikki packette Kryonet-i sendTCPAll meetodiga, siis seda võite vabalt otse välja kutsuda mitmelt erinevalt threadilt. See ei tohiks probleem olla, vähemalt Kryonetis.

Liikumise andmete uuendamine kliendi poolel

Nüüd peaks meil NPC-de liikumise saatmisega olema kõik, ja saame liikuda kliendi poolel renderdamise juurde.

Meil peaks kliendis NPC klassis olema hetkese asukoha koordinaadid (x ja y) ning asukoha koordinaadid kuhu me hetkel liigume (moveX ja moveY).

Võtame OnNpcMove packeti vastu, ja muudame vastavalt sellele kindla NPC klassi moveX ja moveY muutujat

Te võite selle ka omamoodi lahendada ning juhul kui te ei kasuta Kryonetti, toimub pakettide vastuvõtmine teistsugusel viisil.

Nüüd oleks vaja NPC klassi lisada 2 uut muutujat:

private long receiveDifference = 0;
private long lastReceive = 0;

Ja samuti ka meetodisse, kus muudate NPC asukohta:

See on selle jaoks, et me saaks sujuvalt renderdada NPC-sid niimoodi, et kõik näeksid neid umbes enam-vähem samal kohal samal ajal. Salvestame ära vahe millisekundites praeguse ja eelmise NPC move packet'i vahel.

Ja viimaks liigume NPC klassi ning lõpetame draw() ja update() meetodid:

double speed = (deltaTime / ((float)this.getReceiveDifference())) * 1000;

Siin jagame deltaTime praeguse packet'i ja eelmise packet'i vahega ning lõpuks korrutame 1000-ga. Niimoodi ei teki teil ka probleeme, kui näiteks tahate liikumiskiirust muuta, siis te lihtsalt muudate serveri poolel executori aja ära. Siin näites oli ta 300 millisekundit.

Ja peale seda liigume vastavalt siis hetkesest x ja y koordinaadist moveX ja moveY koordinaati, ehk siis lõppkoordinaati.

Nüüd peaks teil mingi algeline AI enda mängus olemas olema. Mõned teemad nagu näiteks threading võivad tunduda täiesti tundmatud, kuid siin projektis te ei peagi palju teadmisi nende kohta omama.