Kolize

raster/c.p.u., 2011

Každý programátor her se dříve či později musel setkat s otázkou, jak zjistit kolizi mezi herními objekty. Ve spoustě případů bývá hráčův objekt (raketka, panáček) realizován pomocí PMG, a tím pádem lze využít hardwareovou podporu - kolizní registry. Někdy však takové řešení není možné, nebo je nutné ho kombinovat se skutečným výpočtem kolizí na základě souřadnic a rozměrů herních objektů.

1. Aproximace tvaru

Raketka může mít po stranách křidélka a tvarem tak připomínat trojuhelník. Jiná nepřátelská potvora může být ještě tvarově složitejší, trčí jí třeba tykadélka a nožičky. Pokud bychom chtěli přesně ověřit kolizi takovýchto dvou objektů s ohledem na všechny jejich detaily, bylo by to hodně výpočetně náročné. A v té rychlosti hráč stejně většinou ani nepostřehne, jestli náhodou nezavadil jen špičkou křídel o tykadlo, případně můžeme prohlásit, že takhle malá kolize neublížila ani raketce ani příšeře.

Takže, tvary pro účel výpočtu kolizí zjednodušíme na obdélníky. Záleží jen na vás, jak moc budou obdélníky "vepsané".

 OOOOOO      XXXXXX
OO OO OO     XXXXXX
OOOOOOOO =>  XXXXXX
  O  O       XXXXXX
 OO  OO      XXXXXX

Původní  => Obdélník
 tvar         6x5

2. Vlastní výpočet kolize

Máme tedy dva obdélníky:

O1 s levým horním rohem na souřadnici X1,Y1 a rozměry S1,V1 (šířka,výška)
a
O2 s levým horním rohem na souřadnici X2,Y2 a rozměry S2,V2 (šířka,výška).

Ke kolizi dochází, jestliže platí:

0 < X2+S2-X1 < S1+S2

0 < Y2+V2-Y1 < V1+V2

Pro implementaci co nejrychlejšího výpočtu použijeme Assembler a pár optimalizačních triků. Řešení výše uvedené komplikované soustavy výrazů pak může vypadat takto:

   lda X2
   clc
   adc #S2
   sbc X1
   cmp #S1+S2-1
   bcs mimo
   lda Y2
   adc #V2
   sbc Y1
   cmp #V1+V2-1
   bcs mimo

   ;došlo ke kolizi

mimo

Poznámky:
Rozměry objektů S1,V1 a S2,V2 předpokládám konstantní, proto mohou být v kódu zadány napevno jako přímé hodnoty, stejně tak jejich součty snížené o jedničku S1+S2-1 a V1+V2-1.

Výpočet pro zjištění kolize trvá pouhých 14 taktů za první dimenzi a 12 taktů za druhou. Ve 2D je to tedy celkově maximálně 26 taktů. (Děkuji Fandalovi za upozornění na přehlédnutou nadbytečnou clc instrukci pro druhou dimenzi.)

Pro maximální optimalizaci bylo vynecháno ověřování záporného výsledku výrazu X2+S2-X1 (resp. Y2+V2-Y1), neboť v rámci doplňkového kódu se podtečením nuly dostaneme do vysokých kladných hodnot (255,254,...), které jsou zaručeně větší než S1+S2 (resp. V1+V2). Jediná podmínka cmp následovaná podmíněným skokem bcs nám tak ověří oba případy. Důsledkem toho však bude vyhodnocena kolize objektů i na opačných koncích intervalu 0,255. Objekt na pozici 0 se šířkou 10 tak bude například kolidovat s objektem na souřadnici 250 a šířkou 10. V praxi však většinou tak velký rozsah hodnot pozic nepoužíváme, takže to nijak nevadí. Pokud byste celý rozsah potřebovali, stačí jednoduše přidat do kódu za řádek "sbc X1" podmíněný skok "bcc mimo" a tentýž podmíněný skok také pro druhou dimenzi za řádek "sbc Y1".

Varianty této metody byly použity například v mých hrách Space Binvaders a Robix, dále je též úspěšně implementoval Fandal do své hry Mashed Turtles.