Doufám, že Vás podivný nadpis příliš nevystrašil. Samotný obsah snad již tak strašidelný nebude... Jednoduše si ukážeme způsob, pomoci kterého jsme schopni zjístit, zda-li se několik objektů s určenými body neprotlo...
Nutnost vyřešit tento problém vyvstala během psaní hry Tuxes. Pro zběžné obeznámení jen zmíním, že se jedná o chodící tučňáky se schopností střílet do tučňáků ostatních pomocí rozmanitých zbraní :)
Když jsem měl k dispozici jen pistoli, problém moc složitý nebyl. Kulky z pistole letí rovnoměrně a případný zásah se dá odvodit pohým porovnáním souřadnic se souřadnicemi hráče. Vše se ale zkomplikovalo ve chvíli, kdy jsem hru spustil na pomalém počítači, který nedokázal vypočítat let kulky dostatečně rychle. Nastal nepříjmený efekt přestřeleného hráče. Při prvním snímku se kulka nacházela před hráčem, v druhém pak už za ním. Kulka by tedy měla hráče zasáhnout, ale program o tom neměl potuchy. Dalším podnětem pak byla dráha kulek, vystřelených z brokovnice. Jak všichni víme, dochází zde k "rozprsknutí" na všechny strany a dráha se stává nerovnoměrnou (tudíž nemohu použít metodu porovnávání souřadnic, která je možná jen v obdélnikovytých obrazcích).
Jako nejschůdnější řešení problému se pak jevilo spojit staré souřadnice s novými a propočítat průnik s hranami hráče na případný zásah. Obrázek bude názornější:
Předpokládejme tedy, že jak kulka tak hráč jsou určeny 4 body, které je ohraničují. Kulka i hráč jsou čtyřúhelníky. Průnik zjísíme tak, že porovnáme 2 rovnice přímek v parametrickém tvaru a stanovíme podmínku, že oba výsledky rovnic musí náležet do intervalu <0; 1>, což je podmínkou toho, aby se jednalo o průnik úseček, nikoliv přímek. Ten stejný postup opakujeme takovým způsobem, aby se každá úsečka z jednoho objektu, porovnala s každou úsečkou objektu druhého. Celkem budeme potřebovat vypočítat 4 * 4 * 2 rovnic (v tom horším případě), v tom lepším případě nám budou stačit výpočty 2, pakliže výsledek každého z nich bude v intervalu <0; 1>, pak budeme moci stanovit průnik - tedy průstřel objektu.
Dost bylo zamotané teorie. Nyní se podíváme jak na to, z pohledu matematiky. Příklad si ukážeme na 2 úsečkách, u kterých budeme zjíšťovat průnik. Parametricky je úsečka v rovině (2D) určena těmito rovnicemi:
x = X+u1t
y = Y+u2t
Kde X a Y je x-ová a y-ová souřadnice bodu, který leží na přímce a u1, u2 jsou souřadnice směrového vektoru přímky. Písmenko t je pak poloha na přímce. Právě toto t musí náležet do intervalu <0; 1>, začátek (0) a konec (1). Máme-li 2 body, které určují úsečku:
A = [XA; YA]
B = [XB; YB]
pak u1 = (XB-XA), u2 = (YB-YA)
Nechť máme 2 úsečky, z nihž ta první je tvořena body A, B a druhá body C,D:
A = [XA; YA], B = [XB; YB], u = (XB-XA; YB-YA)
C = [XC; YC], D = [XD; YD], v = (XD-XC; YD-YC)
Z předchozích řádků je patrné, že již máme 2 směrové vektory. Pro úsečku AB je to vektor u. Pro úsečku CD pak vektor v. Pro úplnost ještě napíši parametrickou rovnici úsečky AB:
x = XA + (XB-XA)t = XA + u1t
y = YA + (YB-YA)t = YA + u2t
Nyní obě rovnice obou úseček porovnáme. Tzn. x jedné se bude rovnat x druhé:
XA + u1t = XC + v1s
YA + u2t = YC + v2s
Je jasné, že dvě úsečky nemohou mít stejná písmenka t, proto jedne z nich přiřadíme t a druhé s. Pakliže bude s, t náležet do intervalu <0; 1>, usečky se protly. V opačném případě se protly přímky (pakliže nejsou rovnoběžné) a to my nechceme. Nyní už jen stačí pomocí algebraických úprav odvodit rovnici pro t a rovnici pro s tak, abychom za ně mohli dosadit libovolné body:
s = (u1*(YA-YC) - u2*(XA-XC)) / (u2*v1 - u1*v2)
t = (v1*(YA-YC) - v2*(XA-XC)) / (u1*v2 - u2*v1)
Všechny body známe, směrové vektory umíme vypočítat. Náše snaha je tedy u konce a ta má také :) Pokud někdo nalezne jednodušší způsob, nechť mě o něm informuje, rád se na něj podívám. Prozatím je toto jedinná a univerzální možnost, jak testovat průnik několika objektů tvořené několika body (tedy alespoň dvěmi). Jak můžete vidět, výpočet to není nikterak triviální, zvláště když vememe v potaz jeho častou iteraci. Kdybychom měly tři objekty a každý z nich by byl tvořen 5 body, museli bychom provést max. 250 výpočtů (!) než bychom zjístili, že se neprotly. To už je docela síla :) Proto programování a počítačům zdar!
