PostHeaderIcon Detekcja kolizjiCollision detection

Ponieważ na scenie występuje pokaźna liczba obiektów, nierozsądne byłoby sprawdzanie kolizji pomiędzy wszystkimi z nich, zwłaszcza, że niektóre z nich mogłyby być oddalone od siebie na dosyć znaczną odległość. W tym celu przeprowadza się dwie fazy detekcji kolizji: tzw. test ogólny i szczegółowy (broad and arrow phase).

Test ogólny

Ogólny test sprawdzania kolizji używa algorytmu spatial hashing. Polega on na tym, że scenę dzieli się na siatkę X x X kwadratowych sektorów (gdzie X wynosi numSectors*2 + 1) o boku sectorDivisions każdy. Numeracja rozpoczyna się w lewym górnym rogu od 0 i przebiega pionowo do numSectors*2, itd. Każdy sektor zawiera informacje o tym, ile oraz które trójkąty przechodzą przez ten sektor.
Dany obiekt może znajdować się w więcej niż w jednym sektorze, a maksymalnie w czterech (zakłada się, że rozmiar obiektu jest nie większy od sectorDivisions). Należy więc dla każdego ruchomego obiektu skonstruować w każdym kroku czasowym minimalny prostokąt rozpinający.
Za wykonanie tego testu odpowiada metoda FindAABB() z klasy Body. Nie ma potrzeby wykonywać tej funkcji dla obiektów statycznych sceny, gdyż informacje o tym, w których sektorach znajdują się trójkąty są już zaszyte na stałe w pliku mapy.
Następnie w każdym kroku czasowym przechodzimy się po wszystkich elementach ruchomych, sprawdzamy, gdzie leżą ich wierzchołki rozpinające i wstawiamy numer ciała, który posiada te wierzchołki do odpowiedniego sektora (do tablicy zbiorów – mhashTable). Tablica m_hashTable jest typu vector<list<Body *> >. Każdy element zawiera listę, ponieważ w jednym sektorze może znajdować się kilka elementów.
Są dwie tablice hashujące: jedna zawiera informacje o obiektach statycznych, druga o ruchomych.

\begin{figure}
\includegraphics[scale=0.5]{imgs/grid}
\end{figure}

Test szczegółowy
Test szczegółowy używa algorytmu SAT

Wszystkie elementy sceny są wielokątami wypukłymi. Do obsługi kolizji służy metoda zwana Separating Axis Theorem (SAT). Stwierdza ona, że jeśli między dwoma obiektami można umieścić prostą, to te obiekty nie przecinają się.
Algorytm przedstawia się ona następująco:
1. Dla wszystkich boków wielokąta wyznaczamy wektory normalne (prostopadłe). Ponieważ elementy statyczne (w tym wypadku są to jedynie trójkąty reprezentujące mapę) nie wykonują żadnego ruchu, można obliczenia o ich wektorach normalnych wykonać na samym początku lub wartości tych wektorów umieścić w pliku mapy. Tak też właśnie zrobiono w grze Soldat.
– Dla danej normalnej wykonaj rzuty każdego boku obu obiektów na prostą zawierającą wektor prostopadły
– Powtarzaj krok drugi dla każdej normalnej do momentu, gdy rzuty boków będą się pokrywać. Gdy choć w jednym rzucie boki się nie pokrywają (patrz rys. 1), oznacza to, że obiekty ze sobą nie kolidują. W przeciwnym wypadku (rys. 2) obiekty kolidują.

Leave a Reply