Jak jsem bojoval s kolizemi

Doufám, že sem následující vyčerpávající text patří. Není to tolik o gamedesignu, ale spíš o praktické stránce programování, která dokáže pořádně vydeptat. 😀

Dostal jsem ve škole za úkol udělat jednoduchou bludišťovitou hru, jako byl kdysi ten screensaver. Nebo tak něco na ten způsob. Zkrátka tu máš openGL a udělej něco, co by se dalo nazvat FPS bez toho S. Myslel jsem si, že to bude sranda, jenže ono ejhle, musel jsem si vlastně udělat engine se vším všudy.

Začal jsem kamerou, což se nakonec ukázalo, že s trochou goniometrie a představivosti půjde snadno (openGL má funkci lookAt – bod odkud, bod kam a nějaký upVector, kdyby měl někdo zájem, můžu přihodit, jak jsem to naimplementoval).

Pak jsem začal přemýšlet nad tím, jak vlastně bude vypadat svět, jakým způsobem budou tvořeny stěny bludiště a jak budu řešit kolize. V tu chvíli už je docela jedno, jestli dělám s openGL nebo s čím, takže jsem se rozhodl vzít to matematicky a co nejjednodušeji (mj. taky se snahou udělat co nejmenší výpočetní náročnost).

Zkusím svůj postup nějak pochopitelně popsat, třeba mě někdo nějak doplní, nebo se to bude někomu hodit.

Následujících několik odstavců můžete kdyžtak přeskočit, popisují nepříliš dobrý a nepříliš funkční přístup.

Nejdřív jsem se rozhodl, že svět bude čtvercová síť a stěny budou vždycky pravoúhlé. Tím pádem by mi stačilo při kolizi s blokem stěny (starý dobrý přístup z Game Makeru 😀 ) vrátit xPrevious, resp. yPrevious. Udělal jsem tedy třídu bloku stěny o rozměru 1×1 (přesunuto z 3D do 2D při pohledu shora, prostě takový pěkný plánek světa) a dále pak v ní pomyslné čtyři body north, east, south a west ve středu každé hrany bloku.

V každém snímku hry pak zeď kontroluje svojí vzdálenost k hráči a ve chvíli, kdy je hráč dost blízko, začne kontrolovat, jestli nedochází ke kolizi. To provádím tak, že kontroluji vzdálenost k výše zmíněným čtyřem bodům, které reprezentují hrany čtvercového bloku stěny. Pochopitelně je-li hráč na vzdálenost poloviny délky hrany k jednomu bodu, nebude ke druhému. Přesněji řečeno zjišťuji v cyklu, ke kterému bodu mám nejblíže a pak patřičně podle světové strany jestli X či Y hráče souřadnice není již vevnitř v bloku, nebo spíš na jeho hranici. Když je, tak jí vrátím o krok zpět a vyřešeno.

Tenhle krkolomný způsob má ale problém, když dokloužu po stěně až na její roh, tak se dostanu jakoby dovnitř do stěny kolmé na tu, po které jsem klouzal, a zaseknu se. To jsem vyřešil tak, že když (na příkladu) se jedná o hranu, která by měla kontrolovat příchod zprava, ale moje předchozí X nasvědčuje příchodu zleva nebo odnikud, tak si hodnotu předchozího X „přehodím“ přes současné X na opačnou stranu a posunu se tam. V podstatě místo kroku zpět udělám krok kupředu, nebo čistě od stěny.

Po tomhle to sice funguje, ale hráč se stále občas na spoji dvou stěn na chvilku zasekne a navíc, jde to použít jen na čtvercovou síť, což mi nebylo dost cool.

Odtud už můžete zase číst, tady jsem našel řešení, které zatím funguje, jak chci. 😀

K řešení použitelném pro stěny pod jakýmkoliv úhlem, mě inspiroval spolubydla. Udělal jsem si novou třídu stěny (tentokrát skutečně jen tenký list nastojato 😀 ), která je reprezentována vektorem pozice, vektorem směru (pomyslný bod na ní ležící spočítaný z úhlu pomocí goniometrie – jednotková kružnice) a délkou. Pochopitelně vynásobením vektoru směru délkou a přičtení výsledku k vektoru pozice dostanu bod, kde zeď končí. Jenom poznamenám, že si opět v každém snímku kontroluji vzdálenost ke hráči od středu stěny, a až je-li dost blízko, začínám si složitě počítat s vektory. 🙂

V tuhle chvíli nastává nejzajímavější magie, protože si musím spočítat vzdálenost hráče k přímce na kolmici a zarazit ho, je-li už tak blízko, že by narazil. Na to mám krásnou metodu, která vypadá nějak takhle:

Vezmeme počátek zdi a konec zdi, jako vektory a označíme třeba v, resp. w. Pak pochopitelně ještě pozici hráče jako vektor p (připomínám, že v daný moment je vše 2D).  Pak spočítáme rovnici, která vrátí hodnotu, která vlastně pořádně nevím, co znamená, ale hodí se. 😀

t = ((p – v) ∙(w – v)) / |w – v |2

Kde symbol je skalární součin vektorů, takže výsledkem rovnice je číslo, které má velice zajímavé vlastnosti. Totiž, je-li menší než nula, kolmice spuštěná od hráče na stěnu by dopadla mimo stěnu jakoby před její začátek a je-li větší než jedna, tak by kolmice dopadla za její konec. Čili ve chvíli, kdy je t mimo rozsah <0, 1> vrátí metoda vzdálenost od p v, resp. w, což se hodí, aby nám hráč nenaběhl do stěny její koncovou hranou, která vlastně není hrana (a také pro místa, kde se dvě stěny napojují). Pokud je t v rozsahu, pak musíme skutečně položit kolmici a zjistit vzdálenost k bodu dopadu. Ten dostaneme následovně:

d = v + ((w – v) * t)

Výsledek d je vektor, takže stačí spočítat vzdálenost od pd a vrátit jí.

Pochopitelně pak zeď porovnává výsledek z výpočtu vzdálenosti s nějakým minimem, a je-li překročeno, provede s hráčem jinou magii. Vzhledem k tomu, že už nejsme v čtvercové síti, tak je mi skákání na xPrevious a yPrevious k ničemu. Takže opět nastupují vektory.

Aby se hráč při kolizi se stěnou nepřestal prostě pohybovat, ale trošku realističtěji po ní klouzal, musíme ho odrazit jako míček (o jeden malilinký krok, takže žádné citelné skákání se nekoná). Zákony odrazu od roviny tu vysvětlovat nebudu. 😀 Na to potřebujeme z vektoru „dopadu“ spočítat vektor „odrazu“. Takže vezmeme vektory reprezentující zeď a spočítáme její normálu n (prohodit X za Y a u jednoho změnit znaménko 🙂 ). Pak ještě trocha počítání (v je vektor dopadu, spočítaný odečtením předchozích souřadnic hráče od současných, tj. těch, ve kterých je ve chvíli kolize se stěnou a nemá tam co pohledávat):

o = v – 2 * ( n * (( v ∙ n ) / ( n ∙ n )) )

Teď stačí vzít výsledný vektor o a přičíst ho k pozici hráče, čímž ho posuneme na místo, kam by se odrazil.

Tadá, po několika dnech a vztekání jsem takto sesmolil velice funkční systém kolizí hráče se stěnou, která může být jakkoliv natočená a svírat s jinou jakýkoliv úhel (nebo aspoň doufám, zatím testování proběhlo v pořádku 😀 ). A neptejte se mě, co přesně se v těch rovnicích děje, protože často nemám nejmenší tušení. 😀

Přijímám nápady, návrhy, podněty, připomínky a dotazy. Případně můžu zveřejnit i kód.

10.4.2014 – Boj stále trvá

Potřebuji radu. Když zdi svírají ostrý úhel (a je jedno, jestli jsem k němu zvenku nebo zevnitř), tak je hráč schopný tímto rohem projít. Chyba si myslím, že vím, kde vzniká, ale netuším, jak jí předcházet…

Děje se to, že hráč jakoby klouže po stěně, která si ho přehazuje pokaždé o kousíček dopředu podél sebe, až si ho najednou v tom ostrém úhlu přehodí za další stěnu tak těsně, že ta druhá jí v tom ještě pomůže a uvrhne hráče do zapomnění… Jenže co s tím?

Ještě doplním ilustrací.

Ilustrace problému kolizí se stěnami

 

Červená a žlutá plocha jsou plochy, kde zdi reagují na kolizi. Hráč se snaží udělat krok ve směru modré šipky, což by způsobilo vstup do prostoru jak červené, tak žluté stěny. Červená stěna se tedy snaží hráče odrazit nahoru ve směru červené šipky, žlutá ve směru žluté. Výsledkem je jakýsi pingpong, který není nijak znát, kromě toho, že se najednou hráč ocitne na konci zelené šipky. A teď babo raď, co s tím. 😀