Szerokofazowe metody wykrywania kolizji?

Alternatywą dla QuadTrees lub BSPTrees są SphereTrees (CircleTrees w 2D, implementacja byłaby mniej więcej taka sama). Zaletą SphereTrees jest to, że bardzo dobrze radzą sobie z dużymi ładunkami dynamicznych obiektów. Jeśli obiekty są stale w ruchu, BSPTrees i QuadTrees są znacznie wolniejsze w swoich aktualizacjach niż drzewo kuli / Okręgu.

Jeśli masz dobre połączenie obiektów statycznych i dynamicznych , rozsądnym rozwiązaniem jest użycie QuadTree / BSPTree dla statyki i drzewo Sfera/cykl dla obiektów dynamicznych. Pamiętaj tylko, że dla danego obiektu, musisz sprawdzić go na obu drzewach.

Polecam quadtree partycjonowanie. Jest to dość proste i działa naprawdę dobrze. Oto Flash demo wykrywania kolizji brute-force vs. quadtree collision detection. (Możesz powiedzieć, aby pokazać strukturę czworokąta. Czy zauważyłeś, że wykrywanie kolizji to tylko 3% brutalnej siły w tym demo?

Ponadto, jeśli poważnie myślisz o swoim silniku, Gorąco polecam wybraćwykrywanie kolizji w czasie rzeczywistym . Nie jest drogi i jest naprawdę świetna książka, która obejmuje wszystko, co chciałbyś wiedzieć. (W tym wykrywanie kolizji oparte na GPU.)

Wszystkie algorytmy przyspieszania zależą od użycia niedrogiego testu, aby szybko wykluczyć obiekty (lub grupy obiektów), a tym samym zmniejszyć liczbę kosztownych testów, które musisz wykonać. Algorytmy widzę w kategoriach, z których każda ma wiele odmian.

1. Podział przestrzenny. Miejsce i tanio wykluczyć kandydatów, którzy są w różnych regionach. Na przykład BSP, siatki, ośmiornice itp.

2. Partycjonowanie obiektów. Podobne do #1, ale skupianie skupia się bardziej na samych obiektach niż na przestrzeni, w której przebywają. Na przykład hierarchie obwiedni woluminów.

3. Metody sortowania i zamiatania. Uporządkuj obiekty przestrzennie i wyklucz kolizje między tymi, które nie sąsiadują.

1 i 2 są często hierarchiczne, rekurencyjne do każdej partycji w razie potrzeby. Za pomocą 3 można opcjonalnie iterację wzdłuż różnych wymiarów.

Kompromisy w dużej mierze zależą od geometrii sceny. Klaster obiektów Do czy są one równomiernie lub słabo rozłożone? Czy wszystkie są o tym samym rozmiarze, czy istnieją ogromne różnice w rozmiarze? Czy scena jest dynamiczna? Czy stać Cię na dużo czasu na wstępne przetwarzanie?

"niedrogie" testy są w rzeczywistości wzdłuż spektrum naprawdę-tanie do rodzaju-drogie. Wybór najlepszego algorytmu oznacza zminimalizowanie stosunku kosztów niedrogich testów do zmniejszenia liczby kosztownych testów. Poza problemami algorytmicznymi, dostajesz się do tuningu, jak martwiąc się o lokalizację pamięci podręcznej.

Alternatywą są zwykłe siatki, powiedzmy 20x20 lub 100x100 (w zależności od świata i wielkości pamięci). Implementacja jest prostsza niż rekurencyjna struktura, taka jak Quad / BSP-trees(lub drzewa sferyczne).

Obiekty przekraczające granice komórek są w tym przypadku nieco prostsze i nie ulegają degeneracji tak bardzo, jak mogłaby to zrobić naiwna implementacja bsp/quad/oct-tree.

Używając tego (lub innych technik), powinieneś być w stanie szybko wyłowić wiele par i uzyskać zestaw potencjałów kolizje, które wymagają dalszego dochodzenia.

Właśnie wymyśliłem rozwiązanie, które nie zależy od rozmiaru siatki i jest prawdopodobnie O (nlogn) (to jest optymalne, gdy nie ma kolizji), choć najgorsze w O(NNlogn) (gdy wszystko koliduje).

Zaimplementowałem i przetestowałem, oto link do źródła . Ale nie porównałem tego do rozwiązania brute force.

Opis Jak to działa: (Szukam kolizji prostokątów)

• Na osi x sortuję prostokąty według ich prawej krawędzi (O (nlogn) )

• Dla każdego rect na posortowanej liście biorę lewą krawędź i wykonuję wyszukiwanie binarne, aż znajdę krawędź po prawej stronie lewej krawędzi i wstawiam te prostokąty między tymi indeksami w możliwym zestawie_collision_on_x_axis(są to N prostokątów, logn dla wyszukiwania binarnego, N wstawia int zestaw o (log n)na insert)

• Na osi y robię to samo

• W każdym z zestawów mam teraz możliwość kolizje na x (w jednym zestawie) i na y (INT drugim), przecinam te zestawy i teraz mam kolizje na osi X i osi y (czyli biorę elementy wspólne) (O (n))

Przepraszam za kiepski Opis, Mam nadzieję, że lepiej zrozumiesz ze źródła, również przykład ilustrowany tutaj: obraz

Możesz sprawdzić, co Scott zrobił w wiewiórce z kosmicznym haszowaniem. Źródło jest dostępne bezpłatnie. Myślę, że użył podobnej techniki do Box-2D jeśli nie do kolizji, na pewno do utrzymywania kontaktu.

Jeśli przestrzeń, w której poruszają się Twoje obiekty, jest ograniczona, możesz użyć siatki do podzielenia obiektów. Umieść każdy obiekt w każdej komórce siatki, którą obiekt obejmuje (w całości lub częściowo). Aby sprawdzić, czy obiekt A koliduje z jakimkolwiek innym obiektem, określ, które komórki siatki obejmują obiekt A, a następnie uzyskaj listę unikalnych obiektów w tych komórkach, a na koniec przetestuj obiekt A przeciwko każdemu unikalnemu obiektowi. To podejście działa najlepiej, jeśli większość obiektów jest zwykle zawarta w jednej siatce cell.

Jeśli Twoja przestrzeń nie jest ograniczona, musisz zaimplementować jakąś dynamiczną siatkę, która może rosnąć na żądanie w każdym z czterech kierunków (w 2D).

Chciałbym polecić wprowadzenie do fizyki gry autorstwa Iana Millingtona, game Physics Engine Development. Ma świetną sekcję dotyczącą wykrywania kolizji fazowych z przykładowym kodem.

Użyłem quad-tree w większym projekcie, który jest dobry dla obiektów gry, które nie poruszają się zbytnio (mniej usuwania i ponownego wstawiania). Ta sama zasada dotyczy oktreów.

Podstawową ideą jest tworzenie rekurencyjnej struktury drzewa, która przechowuje 4(Dla quad) lub 8 (oct) obiektów potomnych tego samego typu co korzeń drzewa. Każdy węzeł w drzewie reprezentuje odcinek przestrzeni kartezjańskiej, na przykład -100 - > +100 na każdej odpowiedniej osi. każde dziecko reprezentuje tę samą przestrzeń, ale dzieli o połowę (bezpośrednie potomstwo przykładu reprezentowałoby na przykład-100->0 Na osi X i-100->0 Na osi Y).

Wyobraź sobie kwadrat lub płaszczyznę o danym zbiorze wymiarów. Teraz narysuj linię przez środek na każdej osi, dzieląc tę płaszczyznę na 4 mniejsze płaszczyzny. Teraz weź jeden z nich i rób to jeszcze raz, i jeszcze raz, aż osiągniesz punkt, w którym rozmiar segmentu płaszczyzny jest mniej więcej wielkości obiektu gry. Teraz masz swoje drzewo. Tylko obiekty zajmujące tę samą płaszczyznę, mogą możliwe zderzenie. Gdy ustalisz, które obiekty mogą zderzyć się, generujesz z nich pary możliwych kolizji. Na tym etapie szeroka faza jest kompletna i można przejść do wykrywania kolizji wąskich faz, gdzie są bardziej precyzyjne i kosztowne obliczenia.

Celem Broadphase, jest wykorzystanie niedrogich obliczeń do generowania możliwych kolizji, oraz wybieranie kontaktów, które nie mogą wystąpić, zmniejszając tym samym pracę wąskiej fazy algorytm musi z kolei działać, aby cały algorytm wykrywania kolizji był bardziej wydajny.

Więc zanim spróbujesz zaimplementować taki algorytm, jak ty:

Ile przedmiotów jest w mojej grze? Jeśli jest ich dużo, prawdopodobnie potrzebuję szerokiego zakresu. Jeśli nie, to Faza Nnarrow powinna wystarczyć. Czy mam do czynienia z wieloma ruchomymi przedmiotami?

Struktury drzew zazwyczaj są spowolnione przez poruszające się obiekty, ponieważ mogą zmieniać swoje położenie w drzewie nad czas, po prostu poruszając się. Wymaga to, aby obiekty były usuwane i ponownie wkładane do każdej klatki (potencjalnie), co jest mniej niż idealne.

Jeśli tak jest, byłoby lepiej z zamiatania i śliwki, który utrzymuje min / max stosy zakresu kształtów w swoim świecie. Obiekty nie muszą być ponownie wkładane, ale stosy muszą być przenoszone w każdej ramce, uważano, że jest to na ogół szybsze niż szerokie drzewo, Trawers z usuwaniem i ponownym wkładaniem.

W zależności od Twojego kodowania doświadczenie, jeden może być bardziej skomplikowany do kodowania nad innym. Osobiście odkryłem, że drzewa są bardziej intuicyjne w kodowaniu, ale mniej wydajne i bardziej podatne na błędy, ponieważ poruszają inne problemy, takie jak co zrobić, jeśli masz obiekt, który znajduje się bezpośrednio na osi lub na środku węzła głównego. Można to rozwiązać za pomocą luźnych drzew, które mają pewne przestrzenne nakładanie się, tak że jeden węzeł potomny jest zawsze priorytetowy nad innymi, gdy taki przypadek występuje.