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 :-)