A lövöldözős játékokban milyen algoritmussal nézik meg a golyó útját mutató egyenes mikor van benne a hitboxban és a metszéspontokat?

Egyenesekkel csak akkor kell számolni, ha a lövedék sebessége végtelen. HA a lövedék útja egyszerű egyenes ÉS a hitbox egyszerű gömb, akkor csak az egyenes és a játékosok hitbox középpontjának távolságát kell kiszámolni. Középiskolás anyag, nagyon gyorsan kiszámolható. Ha a hitbox kapszula alakú, akkor nem a középpont, hanem a "középszakasz" és az egyenes távolságát kell számolni. Ha a távolság kisebb, mint a gömb sugara, akkor eltaláltuk a célpontot. A régebbi játékoknál ez volt a tipikus megoldás, mert gyors és egyszerű. A mai játékoknál sajnos nem ez a helyzet, az egyenes (vagy inkább görbe) csak a lövedék útját határozza meg, a kompetitív játékoknál a hitbox pedig jellemzően nem gömb/kapszula alakú.

Minden egyes időpillanatban megállapítjuk a lövedék formájával és az előző időpillanatban megtett úttal meghatározott hengert. Ez tekinthető a másik hitboxnak, ami találkozhat a játékosokéval. Ha a lövedék pontszerű, akkor henger helyett egyszerű szakasszal számolunk. Ha elég lassú a lövedék, akkor minden időpillanatban magával a lövedék hitboxával kell számolni.

A hitboxok összeütközésére hasonló algoritmust használunk, mint amikor megrajzolunk két egymásba érő testet. Azonban a hitboxokat nem kell megrajzolni, ezért az ismert algoritmus gyorsítható, speciális esetben teljesen ki is kerülhető.

Először is meghatározzuk, hogy melyik hitbox melyik másikkal tud interakcióba lépni, azaz halmazokba soroljuk őket. A legtöbb játékban a karakterek át tudnak szaladni egymáson, vagy ha nincs friendly fire, akkor meghatározzuk, hogy az adott golyó melyik frakcióhoz tartozik, ekkor még ezzel se kell számolni, így minden egyes időpillanatban kevesebb összehasonlítást kell végezni.

Ha elég nagy a játéktér és elég sok a karakter, akkor az algoritmus tovább gyorsítható, ha régiókra bontjuk a játékteret, ekkor a golyónak csak az azonos vagy a szomszédos régiókban található hitboxokat kell vizsgálni. Kisebb régiókat is lehet definiálni, például a tetőről nehéz a pincében lelőni valakit.

Amennyiben találunk elérhető régióban "ellenséges" hitboxot, akkor távolságmérést végzünk. A módszer ugyanaz, mint amikor az egyenes és a gömb távolságát nézzük. Ha az összes hitbox gömb alakú, akkor megoldottuk a problémát. A legtöbb mai játékban kapszula alakú a hitbox, amihez nem kell sokkal több művelet (ugyanis a kapszula nem középpontot definiál, hanem egy "középszakaszt", amivel ugyanúgy könnyű számolni).

Tehát eddig ott tartunk, hogy minden időpillanatban minden aktív golyónál kiszámítjuk, az elérhető régiókban található "ellenséges" hitboxok távolságát. A sok gyorsításnak hála, hogy ezzel teljesen megspóroljuk a két test átfedésénél használt algoritmust. Azonban ma már egyre nagyobb az igény arra, hogy szofisztikáltabb hitboxa legyen minden karakternek. Ekkor a kritikus távolságon belül további számolásra van szükség. Több módszer szerint számolhatunk:

1. Újabb gömb/kapszula alakú hitboxot definiálunk minden egyes végtagra, ekkor a kritikus távolságon belül a golyó hitboxát összehasonlítjuk az összes ilyen hitboxal a fentebb már részletezett módszerrel. A mai lövöldözős játékoknál ezt szokták használni.

2. A hitbox maga a karakter teste, azaz ennél a módszernél nincs olyan, hogy nem találod el a karaktert és mégis meghal. A probléma, hogy egy karakter egy nagyon bonyolult, háromszögekkel összerakott poliéder, ekkor minden egyes háromszöget össze kell vetni a másik test minden egyes háromszögével. Az összehasonlítás nagyon költséges, speciális vágásokkal gyorsítható.

TLDR

0. lépés: Minden egyes karakterhez tartozik egy frakció és egy régió (ingyen van, mert nem valós időben végezzük).

1. lépés: Kiszámítjuk a lövedék megtett útját (szakasz) az előző időpillanathoz képest (nagyon olcsó).

2. lépés: Meghatározzuk az elérhető frakciójú (ellenséges) és régiójú (közeli) karaktereket, mint potenciális célpontokat (még mindig nagyon olcsó).

3. lépés: Kiszámoljuk a szakasz és potenciális célpontok közötti távolságot (olcsó, ha az előző lépésekben jól szűrtünk). Ha a kritikus távolságon belül található, akkor eltaláltuk, egyébként nem. Az algoritmus itt véget ér, kivéve, ha nem primitív hitbox (gömb/kapszula), akkor találat esetén tovább lépünk.

4. lépés: A hitbox implementációjától függ, hogy mennyire költséges műveletet hajtunk végre. Ha minden egyes végtaghoz rendelünk egy egy gömböt/kapszulát, akkor minden egyes hitboxhoz ki kell számolni a távolságot, hogy meghatározzuk, hogy melyik végtagot találtuk el, ha eltaláltunk valamit.

[link]

[link]