j_uk_dev
30.12.09, 21:56
Kolizje, wypadki, zderzenia...
Tytuł wątku nawiązuje do starego artykułu traktującego o kolizjach w grach w
magazynie C&A. Nie bez powodu, bo tym razem postaram się omówić w jaki sposób
gry radzą sobie z kolizjami oraz odpowiem na kilka pytań dręczących graczy np.
skąd się biorą niewidzialne ściany.
Kolizje należą do jednych z bardziej zdradliwych elementów gier. Teoretycznie
proste, w praktyce to tam najczęściej gra potrafi pokazać "różki" w postaci
wypadnięcia bohatera za geometrię, zacięcia się między elementami itd.
Odszukanie wadliwych elementów ( które często nie wychodzą nawet na jaw w
momencie testów wewnętrznych ) nie należy do najprostszych.
1. Trochę historii.
Zacznijmy jednak od początku. Dawne platformy jak NES, C64, Amiga dysponowały
możliwością sprawdzania kolizji między elementami 2D po stronie hardware'u.
Odpowiedni układ był odpowiedzialny za sprawdzenie, czy dwa ruchome obiekty (
sprites ) na siebie nachodziły choćby jednym pikselem i raportował kolizję, po
czym gra obsługiwała to. Zwykle były dwa rodzaje takich kolizji - między
obiektami oraz obiekt-tło. Szybko jednak się okazało, że o ile zwalnia to
programistę od implementowania systemu kolizji ręcznie, ale również
ograniczało to bardzo sposób ich użycia. Nie można było zaraportować kolizji
"na życzenie" np. gdy obiekty już nachodzą na siebie, ale programista chciał
zachować pewien margines, gdy jeszcze nie następuje reakcja. Czasami również
chodziło o zwiększenie obszaru kolizji, gdzie obiekt nie posiadał żadnych
pikseli, a już mordęgą było sprawdzanie kolizji z "labiryntem" ( tak wówczas
określało się wszelkie levele w zręcznościówkach, bo i taką formę miały ),
gdzie kolizja z tłem ograniczała wygląd ścieżek ( po prostu nie mogło być tam
żadnej grafiki ). Rozwiązano to więc w prosty sposób, który jest prekursorem
obecnych kolizji - włożono wirtualnie każdy obiekt w tzw. "bounding box",
czyli prostokąt, który zawierał wewnątrz sprite'a. Poziomy natomiast zaczęto
sprawdzać nie za pomocą testów pixel-pixel, ale za pomocą wirtualnych map,
gdzie każdy "klocek" ( używamy do dziś terminu "tile" na określenie
pojedynczego "klocka" ) był również takim prostokątem. Kolizje więc dotyczyły
tylko prostokątów, które można było modyfikować dowolnie pod względem
wielkości, natomiast test był banalny, bo wystarczyło porównać odległości
między najbardziej oddalonymi od siebie punktami w pionie i w poziomie.
Warunkiem więc było, że odległość wierzchołków najbardziej wysuniętych w
pionie musiała być mniejsza niż suma wysokości obu sprite'ów oraz odległość
wierzchołków najbardziej wysuniętych w poziomie musiała być mniejsza niż suma
szerokości obu sprite'ów. Oba warunki musiały być spełnione by zaszła kolizja.
Hardware nie był już do niczego potrzebny, a matematyka zastosowana do testu
była prosta i nie odczuwało się problemów z wydajnością. Tak bardzo długo ( bo
aż do dziś ) system kolizji zachował się w grach 2D.
2. BBox i AABox ( również nazywany AABBox )
Gry 2D ewoluowały i pojawiły się tytuły, które mimo, że były jedynie
dwuwymiarowe, to była możliwość obracania świata gry o 360 stopni, prosta
matematyka już nie wystarczyła, bo sprawdzenie kolizji między obróconymi
"bounding box" (BBox) było nieco bardziej skomplikowane. Wtedy to programiści
pomyśleli, że skoro możemy obrócić BBox, to znamy położenie wszystkich jego
wierzchołków, więc może z nich zbudować kolejny BBox, tyle że zorientowany
zgodnie z osiami układu współrzędnych. Tak narodziły się AABox ( axis aligned
box ). Znaczne to upraszczało sprawę, bo nadal można było wykorzystać te same
algorytmy niezależnie od tego czy świat się obracał czy nie. Dyskusyjna była
dokładność tego rozwiązania, ale ponieważ większość spriteów i tak mieściła
się w prostokącie dumnie zwanym... "kwadratem", to niedokładność rozwiązania w
czasie gry nie dawała się we znaki. Przykład AABox stworzonego na bazie
obróconego BBox:
Oczywiście to nie koniec pomysłów. Jak widać na rysunku powyżej, AABox
pozwalało łatwo ustalić czy zachodzi kolizja, ale często powodowało to
zniekształcanie obszaru kolizji. Próby stworzenia AABox na podstawie pikseli
nie były również zbyt sensowne, stąd pomyślano o dwóch możliwościach. Albo
można było sprawdzić przecięcie między dowolnymi BBox'ami sprawdzając czy
krawędzie przecinają się, albo można było wykorzystać inne kształty, bardziej
odpowiadające naturze i wyglądowi sprite'a. W ten sposób zaczęto także
korzystać z okręgów, elips, trójkątów itp. Każda z figur dostała własne proste
algorytmy sprawdzania przecięć oraz wypracowano algorytmy sprawdzania
przecięć między różnymi typami figur, w jakie można było wpisać sprite'y.
Przykłądowo, sprawdzenie kolizji między okręgami oznaczało sprawdzenie
odległości od środków i porównaniu z sumą ich promieni, a właściwie z
kwadratem tej sumy, by uniknąć pierwiastkowania ( pierwiastek kwadratowy to w
programowaniu bardzo smutny pan, bo nikt po prostu go nie lubi

). Te
mechanizmy pozwoliły na lepsze opisanie obiektów i mimo, że nadal siedzieliśmy
w 2D, to techniki te stanowią podstawę tego co jest teraz. Małpę z obrazka
wyżej o wiele lepiej byłoby wpisać w okrąg, przy obrocie okrąg cały czas
pozostaje na swoim miejscu, a jego orientacja zawsze jest zgodna z osiami
układu świata ( właściwie to zgodna z każdymi osiami ).
3. Era 3D.
Nastała era 3D. To czego już się nauczyliśmy nie dało się wykorzystać tak po
prostu, bo trzeci wymiar miał swoje wymagania. Podstawową figurą geometryczną
opisującą płaszczyznę stał się trójkąt, bo tylko on gwarantował, że mieliśmy
do czynienia tylko i wyłącznie z jedną płaszczyzną ( z matematyki - 3 punkty
zawsze leżą w jednej i tylko jednej płaszczyźnie ). W grach 3D posunięto się
dosyć daleko i często sprawdzanie kolizji - postacie-świat oznaczało
dosyć dokładny test z każdym trójkątem w obszarze kolizji. AABox wszedł w erę
3D, postaci w grach zostały w niego "owinięte", to samo część elementów świata
gry. Jednak początkowy koncept świata 3D w grach FPP nie był zbyt lekki dla
testów kolizji. Testy kolizji ze ścianami często wymagały przewędrowania przez
drzewo zawierające rozbitą geometrię ( gry nie zawierały takich detali jak
teraz i można było pokusić się o dosłownie pocięcię sceny na trójkąty i
zbudowanie drzewa BSP ( później Quadtree i Octree ). Tak robiono, toteż główne
sprawdzanie kolizji polegało na przetestowaniu przecięć między trójkątami w
polu widzenia lub dobieranych na innej zasadzie ( zależnie od użytej metody
partycjonowania oraz testów widoczności ). Generalnie miało to zaletę.
Pamiętacie wszelkie pierwsze gry w prawdziwym 3D? Można było wejsć praktycznie
wszędzie, nie było nigdy niewidzialnych ścian w tamtych czasach, bo każdy
trójkąt z jakiego zbudowana była scena podlegał testowi kolizji. Miało to
swoje negatywne odbicie w wymaganiach, aczkolwiek testy przecięć trójkątów (
jeśli jesteśmy w stanie w miarę dobrze określić, które trójkąty biorą udział w
teście ) nie należą do skomplikowanych i można je wykonać bez żadnej
zaawansowanej matematyki. Oczywiście starsze techniki wykorzystujące bounding
boxy, sfery i cylindry również były w grze, ale dotyczyły one tylko niektórych
elementów. Liczyła się dokładność i im dokładniejszy system kolizji istniał w
grze, tym dla tej gry było lepiej.
(no i limit 8000 znaków osiągnięty

CDN za chwilę ).