Siedem

Célra tartás


A radar után a következő, matematikai jellegű kihívás, amivel a Siedem programozása közben szembesültem, a célkövetés és a célra tartás. Mindkettő tipikus 3D feladat, amire az ember nem is gondol elsőre, amíg egyszercsak bele nem fut.

A célkövetés alatt a következőt értem: van egy űrhajó, adott fordulékonysággal és sebességgel; oldjuk meg, hogy egy adott pontba elrepüljön. Ez azért hasznos, mert a robot űrhajóink majd idővel szeretnének valahova menni, valamit támadni, tesz-vesz, odamegy, igazából mindenhez ez kell, kivéve a céltalan röpködéshez. Amit csinálni kell, az nyilván az, hogy célba kell venni az adott pontot, és utána repülni feléje, amíg ott nem vagyunk; ebből a célbavétel az izgalmas. Több nehézség is felmerül: melyik a legkisebb ív, mi van, ha mozog a célpont, stb. Aztán jönnek a Quaterniók megint, és az ember egyszercsak legyűri, aztán meg álmélkodik, ahogy a képernyőjén a robot úrhajók repkednek a céljuk felé.

A másik, a célra tartás, még izgalmasabb: adva van egy mozgó célpont jelenlegi helye és sebessége, valamint adva van a lövedékünk sebesséve. A feladat: hova kell lőni ahhoz, hogy eltaláljuk? Élünk azzal a feltételezéssel, hogy a célpont ugyanarra repül majd tovább, főleg mivel jobb tippünk ezen a ponton nincsen, szóval valahova elé akarunk lőni. Mint a régi jó Quake-ben: megy az emberünk, eléje küldjük a rakétát, nézzük ahogy repül.

Első blikkre a következő egyenletet kapjuk:

Unknown magic content: 'mathml'

:`vec["shotDirection"] * "weaponspeed" * "t" = vec["hisPosition"] + vec["hisSpeed"] * "t"`

A shotDirection az 1 hosszúságú vektor (normálvektor), amerre lőnünk kell, a T pedig az idő, amíg eltaláljuk majd a csókát. Egy egyenlet – 4 ismeretlen (T és a shotDirection három dimenziója), mi van már ma?? Ja várjunk, mégsem: egyrészt ez egy 3D vektor egyenlet, vagyis valójában három egyenletre bomlik szét, másrészt meg a shotDirection valójában 2 ismeretlen csak, mert a hosszát tudjuk (az 1). Ha kiszámoljuk 2 tengelyét, akkor a harmadik Pythagorasz tétellel kiszámolható.

Összességében ez egy negyedfokú egyenlet, fúúúj! Nem lehet ennél jobbat? Aztán egyszercsak jön az ötlet: számoljuk ki azt a teljesen érdektelen adatot, hogy milyen messze van az a pont, ahol a lövedékünk majd eltalálja az antagonistát!

`||vec["hisPosition"] + vec["hisSpeed"] * t || = t * "laserSpeed"`

Lássuk, mi is ez! A `||vec["vektor"]||` egy vektor hosszát jelöli. Ebből az egyenletből sikerrel eltűnt a shotDirection, vagyis az, amit ténylegesen keresek. Hurrá, érdektelen az egyenlet! Vagyis várjunk csak? Egy ismeretlenünk van (T), és ez, bár nem látszik rajta, valójában egy másodfokú egyenlet. Méghozzá azért, mert a baloldal valójában egy négyzetgyökös kifejezés. Ha az egészet négyzetre emelem, akkor meg egy irdatlan sok tagú valami lesz, ami T-ben másodfokú. (Ha valakit véletlenül érdekelnek a másodfokú tagjai, az számolja ki maga, vagy nézze meg a kódban.)


ŰRISTEN, MI VOLT A MÁSODFOKÚ EGYENLET MEGOLDÓ KÉPLETE?!?
ŰRISTEN, ENNYIRE RÉG VOLT AZ EGYETEM????
Ja várjunk.. persze...
`(-b +- root()(b^2 - 4 a c)) / (2a)`
Ha egyszer gyerekem lesz, ez lesz neki az estimese, egy életen át, minden nap.

Kész vagyunk? Kész vagyunk! Ugyanis T-t behelyettesítve az első, gagyi egyenletünkbe, szépen megkapjuk, hogy hol lesz az ellen, amikor majd eltaláljuk, vagyis durr neki oda, most most MOST! Megyek aludni...

Búcsúzóul a kód, kicsit egyszerűsítve az olvashatóság kedvéért: a = hisSpeed.x * hisSpeed.x + hisSpeed.y * hisSpeed.y + hisSpeed.z * hisSpeed.z - laserSpeed * laserSpeed; // remélhetően negatív b = ( hisSpeed.x * offset.x + hisSpeed.y * offset.y + hisSpeed.z * offset.z ) * 2; c = offset.x * offset.x + offset.y * offset.y + offset.z * offset.z; det = sqrt(b * b - 4 * a * c); t1 = (-2 * b + det ) / (2 * a); t2 = (-2 * b - det ) / (2 * a);

Mi van, ha két T jön ki, ami másodfokú egyenletben elő is tud fordulni? Hát, lehet hogy az egyik negatív T lesz, vagyis mi lett volna, ha x másodperccel ezelőtt hátrafelé lövök. Azt ki is hagyhatjuk akár, a másik T viszont finom...

Utoljára módosította UPi 2010.V.18 10:18-n
Bejegyzés módosítása | PermaLink
Votes disabled.

Hozzászólások (19)

UPi hozzászólása 2010-05-18 09:45-kor


Grizli hozzászólása 2010-05-18 10:17-kor

(Válaszképp erre)

CSá Upi! hiányzik a Siedemnek a d3dx9_42.dll ... ez miért is? DirectX? Ok közben meguglizom, nehogy valaki le UTFG-zzen.

<blockquote> Kipróbálható itt: http://apocalypse.rulez.org/mp3/siedem2.zip </blockquote>


Grizli hozzászólása 2010-05-18 10:18-kor

Közben megnéztem. Tényleg direktix. átugrik a game fullscreen modeba vagy kisablakos ablakos megoldás egyenlőre?


UPi hozzászólása 2010-05-18 10:19-kor

Griz, szedd ki a a plugins.cfg-ből a directx 9-et, és akkor menni fog, talán. Másik lehetőség, hogy tegyél fel directx-et...


UPi hozzászólása 2010-05-18 10:19-kor

Az elején be lehet állítani, van egy fullscreen paraméter.


Grizli hozzászólása 2010-05-18 10:30-kor

elég volt kiszedni.

Cool, bár még nehezen irányítottam. Az űrhajót nem tudtam lelőni.


UPi hozzászólása 2010-05-18 10:40-kor

Ja, izé, az irányítás: mouse scroll gyorsít / lassít, balgomb meg lő. Azt el se kell engedni. :)


SurBa hozzászólása 2010-05-18 15:13-kor

UPi, mennyire segítene, ha egyenletek helyett mátrixokkal számolgatnád ugyanezt? (kicsi, 2x2-esekkel elégnek tűnik)


UPi hozzászólása 2010-05-18 15:15-kor

Nem tudom. Fel tudod írni ugyanezt mátrixokkal?


SurBa hozzászólása 2010-05-18 15:48-kor

3D-ben egy forgatást keresünk, és a képzetes kvaterniók eléggé szépen alkotnak csoportot ott (mint "forgatások"). Őket komplex mátrixokkal lehet ábrázolni (ai+bj+ck=\begin{pmatrix} ci & -a-bi \\ a-bi & -ci \end{pmatrix}), szerintem van szebb lehetőség is, de remélem ráér kicsit később :)


Wigy hozzászólása 2010-05-18 16:19-kor

Én is a mátrixokon töprengtem, de eléggé elabsztraktosodik tőlük a feladat. Rögtön lesz 3 tér és 1 idő koordinátád.

Ha egyenesvonalú egyenletes mozgást feltételezünk a célpontról, akkor a teljes pályája egy 4D egyenesen lesz, aminek ismered 1 pontját és az irányvektorát. Vektoriális szorzat kell a felírásához, amit determinánssal lehet számolni.

A lövedék lehetséges helyei egy hiperkúpon vannak ebben a 4D térben, aminek az egyenletéről most inkább ne is beszéljünk.

A lövedék és a célpont közös helyen azonos időben azokban a 4D koordinátákban lesz, ami mindkét egyenletet kielégíti. Végül optimalizálgatod a felírást és ott fogsz kilyukadni, mint a UPi.

Annyit még talán lehet optimalizálni, hogy az idők és távolságok négyzetével számolva talán nem kell végül gyököt vonni. De ennek még nem néztem utána.


SAdam hozzászólása 2010-05-18 16:20-kor

OK, szóval 3D forgatásokat sztem legegyszerűbben 2x2-es 1-determinánsú unitér mátrixokkal lehet felírni (más néven az SU(2) csoport elemeivel). Ezek amúgy is izomorfak a kvaterniókkal. Ha C/C++ban implementálod a cuccot, az azért előny, mert akkor tudsz használni olyan optimalizált függvénykönyvtárakat a mátrixműveletek végrehajtásához, mint pl. a BLAS/LAPACK (utóbbi FORTRANul van, de elérhető Cben és C++ban is).


UPi hozzászólása 2010-05-18 16:59-kor

Köszönöm a tippeket, de igazából képleteket ha tudnátok írni, az jobb lenne. A mátrixokról már korábban hallottam valahol. :)

Tipp: MathML képleteket itt lehet kipróbálni. Pl, `e^(i pi)=-1`


Descant hozzászólása 2010-05-18 18:33-kor

Directx nálam sem működik ami azért zavaró mert van fenn nálam 9.0c és az Unreal 3 sem nagyon vernyog. Csak opengl grrr

Mi a kilépésgomb?

Miért a TV megjelenítőn jelenik meg mindig?

Milyen formátumú legyen az űrhajó amit tervezek?


UPi hozzászólása 2010-05-18 23:08-kor

Pontosan mit jelent a "nem működik"?

Kilépésgomb az Alt+F4 :)

Mi van a TV-vel?

Az kira lesz, ha csinálsz űrhajót. Legjobb az lenne, ha valami olyan formátum lenne amit Ogre tud importálni. Eddigi tapasztalataim szerint a 3DS Max jó, a Google Sketchup viszont nem 100%-os. Részletek itt.


Descant hozzászólása 2010-05-19 09:25-kor

d3dx9_42.dll hiányolja nekem is

két megjelenítő van csatlakoztatva a gépemhez a TV és a monitorom és mindig a TV-n nyitja meg siedemet pedig a monitoron kéne


UPi hozzászólása 2010-05-19 13:08-kor

Próbáld meg telepíteni a DirectX 9-et, letölthető innen: http://www.microsoft.com/downloads/details.aspx?FamilyID=2da43d38-db71-4c1b-bc6a-9b6652cd92a3&displaylang=en

Ha működik, akkor a program indulásakor ki tudod választani, hogy melyik képernyőn jelenjen meg a játék. (Ezt OpenGL-nél valamiért nem lehet kiválasztani, GOLLAM!) Ne add fel!


Descant hozzászólása 2010-05-21 11:14-kor

Ez furcsamód működött ami azért különös mert nem egy játék van a gépemen ami directx 9.0c-t használ meg telepítette meg minden és nem azoknak nem volt baja. Ez valami olyan lehet, hogy csak egy bizonyos részét használja és csak azokat telepíti föl?


UPi hozzászólása 2010-05-21 11:20-kor

Ez csakugyan különös! Sajnos még nem ismerem a DirectX lelkivilágát elegendően, de majd igyekszem fényt deríteni.

Tagek: