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:
Nyní obě rovnice obou úseček porovnáme. Tzn. x jedné se bude rovnat x druhé:
XA + u1t = XC + v1s
YA + u2t = YC + v2s
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!