Matematičko savršenstvo i pilotiranje

Projekt svemirske simulacije sporo se kreće, primarno jer skoro uopće ne radim na njemu, baveći se umjesto toga obiljem drugih stvari (koje, eto, ipak nisu društvenog i sportskog tipa). Zadnji put sam pisao o filozofskim i praktičnim problemima rada na 3D AI-ju. Ono malo što radim na njemu, pokazuje kako, za razliku od naziva ovog bloga, to baš i ne radi.

Pa o čemu se radi?

Kako (valjda) rekoh i prije, jako se treba paziti na svaki detaljčić, i borba protiv kolizije postaje jednako bitna kao i sama borba. Niti ne pokušavam pokriti slučaj gdje brod svojim skretanjem može udariti u drugi brod koji, eto, nailazi istim putem. Zasad bi to bilo previše za jedan projektić koji radim u slobodno vrijeme. Naravno, možemo razmišljati o raznim teoretskim rješenjima kao "ajde prođi sve pod kutem prema kojem se krećeš, i ako ti je tamo prepreka, odluči ići negdje drugdje". No prvo treba napraviti rješenje da brod uopće dođe do jednog odredišta prema kojem je odlučio letiti, a bez da se zaleti u neki drugi komad metala koji lebdi.

Slijedi opis moje ideje za AI, a nakon toga daljnja osobna gnjavaža.

Eksperimentalni AI

Naš AI nazovimo Pilotom koji rješava Zadatke.

 Dakle Pilot odluči koje zadatke će vršiti paralelno, i nakon što se oni odvrte, koji će se zatim početi rješavati. Očito, pilot ima listu zadataka koji idu jedan iza drugoga -- to jest, nakon što jedan završi, odmah se pokrene sljedeći na listi. Svaki zadatak ima listu paralelnih zadataka. Sam zadatak nije gotov dok i svi njegovi paralelni zadaci nisu gotovi.

Pilot može biti agresivac, pasivac, kukavica, trgovac -- uglavnom, možemo za različite karakterne osobine imati različite klase s definicijom koda pilota (PilotTrgovac, PilotAgresivan). Naravno, ne moramo; sve to mogu biti mali parametri. Također, možemo imati i nazovi-apstraktnog pilota, a to je PilotMrezni odnosno PilotIgrac, ili pak PilotDaljinskiUpravljan. Trenutno ne implementiram igrača kao pilota koji prima input, ali teoretski mogu i čak je moguće da ću to odraditi. Ovi ostali piloti očito neće imati tipične zadatke i tipično odlučivanje. PilotMrezni recimo uistinu ne treba imati zadatke, kao ni PilotIgrac, ali PilotDaljinskiUpravljan prima konkretne precizne naredbe od igrača.

A kakvi zadaci mogu postojati? Primjer jednog zadatka je ZadatakLeti (JobFly). Ovaj zadatak je trenutno jedini koji implementiram, a trenutno sadrži i kod za odlazak na neko odredište, ali i kod za slijediti nekoga. Planiram uskoro razdvojiti ovaj zadatak u dva: ZadatakLeti i ZadatakSlijedi.  Također, može postojati i ZadatakPucajDoPrilaska, ZadatakPucajStojecki, i slično. Zadaci ne sadrže pametno odlučivanje.

Trenutno u svojem jedinom zadatku implementiram detekciju prevelikog približavanja meti, detekciju potencijalne kolizije i slično. Konceptualno, to je krivo, i to leti van iz koda, odnosno o tome će odlučivati Pilot. Naime, Pilot može uistinu željeti zaletiti se u odredište. Takav je Pilot, primjerice, projektil. Stoga, svi zadaci trebaju biti vrlo jednostavni. Možemo uistinu implementirati dio kontrole kada je ona uistinu korisna (ZadatakPucajDoPrilaska), odnosno onda kada nam uistinu odgovara naslagati nekoliko naredbi za redom, no zadatak ne smije sam određivati paralelne zadatke ili one koji slijede nakon njega.

E sad, kako najavih, prelazimo na jadanje.

Programersko prigovaranje

Pilot i jedini implementirani zadatak, kao što je par puta rečeno,  trenutno imaju nekoliko gadnih konceptualnih propusta. Zadatak pokušava previše odlučivati, a Pilot to radi premalo. Sve to je tako jer je AI eksperimentalan i work-in-progress. Da nisam ovo napravio, ne bih ni znao da postoji kriv način izrade AI-ja.

Trenutno AI bi trebao implementirati napadački mentalitet. AI pokuša letiti prema igraču, no odluči da će se sudariti i izbjegava ga tako da predaleko odleti. Zatim se vrati, i počne kružiti u blizini igrača, gotovo nikada ga ne naciljajući  zastvarno jer, jednostavno, kruži preblizu. Najvažnije pitanje je ovdje, otkuda AI-ju ideja da tako daleko odleti, a zatim da ne ponavlja to ponašanje?

 Spomenuo sam u naslovu matematičko savršenstvo. To se odnosi na pilotovo izbjegavanje.

Tu je ključna bila detekcija točne točke kolizije ako se pilot nastavi gibati po istom pravcu. Svaki objekt sastavljen je od više sudarnika (collidera). Sudarnik može biti ili kugla, ili trokut. Relevantne točke (jedna ili tri) definirane su relativno u odnosu na objekt u svemiru.

Imam veliku sreću da sam naletio na odlični ozcollide ruskog programera Igora Kravčenka koji je odradio velik dio prvog ciklusa gradiva Matematike 2, a i više. Ova biblioteka (il' što bi neki profesori rekli, "knjižnica" ... brrrr) uvelike mi je olakšala koliziju kugle i trokuta, te trokuta i trokuta. Štoviše, biblioteka za neke od kombinacija predviđa i udaljenost do sudara za zadani vektor brzine -- točno ono što meni treba!

No biblioteka ne pokriva kombinaciju kugla-kugla. A ja sam, kako je poznato, vrlo ... kržljav što se tiče matematike. Stoga sam potrošio velik dio razmišljanja u zadnjih par "sessiona" bavljenja igrom upravo na razmišljanje i pokušaje implementacije gore navedenog. S obzirom da sam vrlo sklon greškama u implementaciji imalo složenijih fora od y=x+5, tu sam zapeo, no uz ideju i određenog "rješavača" matematičkih formula koji nosi ime po prvom grčkom slovu, te uz odvojeni mali frameworkić za testiranje koji sam si složio, i to sam implementirao. Je, vraga. Treba paziti i na jezik u kojem se radi, na svako moguće dijeljenje i množenje, da ne bi ispalo cjelobrojno ... vražji C/++ :-)

I eto, dobijem točku gdje se kugla premjesti da bi udaljenost centara bila točno R1+R2, i zatim povučem liniju između dvije kugle, shvatim kao vektor, normaliziram je i pomnožim s R1. Konačno dodam na onaj "odredišni" (x,y) gdje će kugla biti. Voila! Riješeno.

Za referencu, rješava se ova formulica:

[(x_1 + t v_x) - x_2]^2 +  [(y_1 + t v_y) - y_2]^2 + [(z_1 + t v_z) - z_2]^2 = (R_1 + R_2)^2

(Lakše ćete je pročitati ako je kopirate u OpenOfficeov matematički modul. Osim toga... skoro pa je TeX :-) )

Za lakše shvaćanje, i lijeva i desna strana su kvadrirane. Lijeva bi trebala biti pod korijenom i time dati udaljenost između točke (x_1+tv_x, y_1+tv_y, z_1+tv_z) i točke (x_2, y_2, z_2). Ta udaljenost treba biti R_1+R_2, te kada to izjednačimo dobijemo parametar t -- odnosno njih dva -- pomoću kojeg možemo odrediti odredišnu točku, tj. prvu od dvije koje sam napisao u ovom odlomku.

U rješenju računam da brzina postoji, tj. da bar jedan od v_x, v_y i v_z nije 0. Inače se kolizija nikako ne događa. To rješava problem nule u nazivniku. Također, dobivamo dva rješenja -- jedno na ulazu, a drugo na izlazu iz kolizije. Ako uzmemo ono bliže, to je to. Po iskustvu, to bi trebalo biti ono kod kojeg nemamo negativni predznak.

I sve to računanje...

Poanta ove priče je ... rezultantna formula je podulja, uključuje mnogo kvadriranja, jedan korijen jedno dijeljenje. Bez nekih benchmarka, iznijet ću ono što se može vidjeti u kodu Ogre3d
enginea: sqrt() je skup. Ogre3d zbog toga ima getSquaredDistance() u vektoru, koji ga izbjegava.

Što bi mogli napraviti? Da li bi bilo brže napraviti nekakav fiksan set koraka koji gleda kvadriranu udaljenost i procjenjuje da li je dovoljno daleko udaljeno, i lupiti aproksimiranu brojku?

Iskreno, za ovo uopće nemam ideje kako to gluplje i brže izvesti. Osim toga, ovo se queryja kao zadnji korak -- ako objekti nisu dovoljno blizu da bi se skoro mogli kolidirati, onda uopće ne moramo razmišljati o tome koliko ovo traje.

Zašto uopće pričam o jednostavnijim rješenjima? Jer sam nedavno imao gadnih problema s jednom malom 2D igrom koju je trebalo napraviti. Umjesto da posegnem za što jednostavnijim rješenjem (povuci liniju, gledaj gdje se prvo kolidira, ograniči pomak do tamo), igrao sam se s pravim, matematičkim rješenjem sličnim ovom gore. Nažalost, cijela logika igre je umirala, a zbog neadekvatno delimitiranih objekata (što-je-tu-je) koje nisam mogao srediti na jednostavan način, postojala je hrpa rupa i nedozvoljenih poteza koje je igrač ipak mogao raditi. Nakon tjedan i pol rješavanja svega toga, nisam bio ništa bliže rješenju. To matematičko rješenje je na kraju odbačeno, i sad igra radi čudno, loše, ali bar igrač ne može raditi nedozvoljene poteze.

U predikciji odnosno predviđanju sudara kugli, formula ispada tako jednostavna. Dugačka, ali jednostavna i čista. Meni na sramotu je što mi je dugo trebalo da to izvedem kako spada.

Uz nadu da sljedeći post neće biti tek za 2 mjeseca, lijep pozdrav, i ne zaboravite čitati EmPov primarni blog (link sa strane). A tko zna, možda se pojavi i koji Kramerijanski post :-)

AI u letačkim simulacijama

Ako se radi 3D space sim, može biti gadno raditi AI. Prvi obstacle? Predviđanje kolizije i adekvatno reagiranje. Dakle imamo svemirski brod. On treba negdje letjeti. Možemo imati cilj prema kojem želimo letjeti, i recimo da je lako i riješeno kako se brod treba tamo okrenuti. (Ako ništa drugo -- sfejka se.) I tako mi letimo... i sad treba predvidjeti da ako odmah ovaj čas istog trenutka ne krenemo skretati, bit će sudar, udar i neće biti dobro .Još ako pričamo o roju brodova koji se bore, treba paziti da se ne udare međusobno. Treba vrlo pametno odlučivati.

Po čemu se to razlikuje od ostalih AIjeva? Pa prvo, po količini prostorne matematike. Za svaku, ama baš svaku sitnicu, treba očekivati rad sa hrpom vektora, kuteva, sinusića i kosinusića. Nema tu "Hm, točno iznad mene je? Ok, idem lijevo" -- ne, zato što prvo treba odlučiti što točno znači "iznad mene" i što točno znači "lijevo", te kako postići "idemo u lijevo".

2D račun je relativno jednostavan. U 3D računu se petljaju dodatne mogućnosti. Recimo, upravo to -- što znači skrenuti ulijevo? Ako imamo rotaciju baziranu na kvaternionima, lako je skrenuti ulijevo bazirano na naš viewport... a ako računamo za AI, malčice je teže predvidjeti što točno jest skretanje ulijevo i da li ćemo na taj način ustvari lupiti u nekoga.

Uglavnom, I'm having fun! :-)

Pričam ti priču

Sjećam se koliko sam kao klinac bio fasciniran pričama u nekim igrama. Mislim da slobodno mogu reći da je to zato što uistinu igre sredinom devedesetih pa do prve polovice prvog desetljeća novog milenija proživljavaju zlatno doba grafičkog storytellinga. Zaboravimo li na one prave, stare avanture, mislim da možemo reći da su u to doba (1995-2005) igre imale najbolju kombinaciju zanimljivih priča ugodne grafičke izvedbe. Vrlo vjerojatno jednostavno nisam u toku (ali i to nešto govori o svemu), ali jednostavno ne mogu se sjetiti nove igre koja mi je istovremeno bila i zanimljiva po priči, nije ostavljala dojam MTV-generacije, a da je još uvijek i lijepo izgledala. Zadnja je Half Life 2, koji je već lagano i ostario.

Vidio sam nedavno Prototype kod kolege na laptopu. Zaintrigiralo me, no nemam dojam da ta igra ima “ono nešto”, odnosno da je u njoj duh Quakea II (koji puca, ali ima i, doduše neistaknutu, priču), da je u njoj duh jednog Black&Whitea (koji ima fantastičnu priču i setting, finu premisu, i nadasve originalan gameplay). Posebice nema duh Half Lifea 1. Nema čak ni duh jednog Star Trek Voyager: Elite Forcea, niti Star Trek: Armade (fine trekijevske pričice uz jako finu igru; nipošto savršeno, ali fino).

Igre 1995-2005 imale su fine priče. No što im je to vrijedilo kad sam ja bio faca i imao sam cijele svoje male svjetove koje sam htio pretočiti u “tako savršene” igre, ne znajući išta o pravom game developmentu i smatrajući ga magijom :-)

Pred par dana, javio mi se jedan stranac zainteresiran za jedan projekt koji radim. O tom projektu, na net sam stavio par demo filmića i par skrinšota (naravno, namještenih tako da pokazuju projekt u najboljem svjetlu).

Ponudio je – priču. Zatim je istaknuo da nema teksture, da nema modele, da nema muziku, da nema ustvari ništa osim priče, ali da bi jako volio surađivati na igri baziranoj na mom engineu, jer, kakti, priča mu je hiper kul i originalna, pa bi mi mogli surađivati.

Pa sam mu odgovorio poprilično podulji mail o načinu rada na igrama, o smrti srednjeg tržišta za igre (preživljavaju casual i high-end retail). Pisah mu o tome kako za omanju igru vjerojatno treba bar 6 mjeseci programiranja i artistiranja, i to fulltime. Naravno, govorim o relativno indie developmentu. Ako se to pretoči samo u cijenu pojedene hrane i popijenih pića za to vrijeme za manji tim dolazimo do prebolesnih cifri.

A to je samo izrada enginea i grafike!

A sad slijedi moja slobodna procjena za to koliko treba full time rada da bi se napravile misije, odnosno priča.

Recimo, dva tjedna.

Pa usporedite koliko je bitan prinos priča, za komercijalno izdavanje igre, ako su vam osnovni constraint nedostatak grafičara, programera, vremena, financijskih sredstava. Odmah ću otkriti tajnu: to je stvarno tako sporedna stvar da to ne mogu dovoljno naglasiti koristeći samo ljudski jezik (a pogotovo pisani).

Napominjem da se tu ne radi o story-intensive igri, kao što su avanture ili RPGovi, nego o igri s misijama. Zaključak: Priča je nebitna, setting se da nabrzinu osmisliti, misije se daju naštancati.

Ljeto vrije, a mi se kuhamo

Vidim ja, evo, kolega EmP je i dalje radio preko ljeta :-)

Ja, s druge strane, nemam čime da se hvalim bez da otkrivam tko sam i što sam (jer Kramer ipak nisam ^^). U firmi smo skoro pa završili novu igru: izdavač čini se ne otkriva više nove bugove i ide se na snimanje voiceovera. Falimtebože da imamo izdavača, jer bi inače bili bez voiceovera.

S druge strane, moji vlastiti projekti stoje. Malo radim na Javascript igri, no došao sam toliko daleko da imam fascinantan fadein/fadeout i loading. To govori o tome koliko treba čovjeku da na relativno novoj platformi napravi osnovne stvari: sati i sati. Mislim da sam preko 6 sati utrošio na to da nemam niti to da se osnovna mapa vidi.

Istovremeno space-sim na kojem radim stoji. Zadnje sam stavio job-sustav kao osnovicu za AI, i prebacio dosadašnje "slijedi brod" u taj sustav. Odmah sam napravio da pokuša biti pametan pa se približiti do nekakvog radijusa, i zatim odletiti iza svoje mete. No, i dalje se uspijeva zabijati u svoju metu. Neke ideje mi se vrzmaju po glavi (možda da prvo ode na (leftvector*radius) pa zatim dalje?) no vidjet ćemo.

Ništa, idem proučavati Unity engine. Tutoriali za interface od IDEa su vrlo, što bi naši prekobarni susjedi rekli, compelling, i preporučam da se pogledaju. Skriptiranje izgleda interesantno i moćno... ali idemo probati sada stvaron napisati pokoju skripticu!

Živjeli lijeni programeri!