Szybsze wykrywanie kolizji 2D

Ostatnio pracowałem nad szybką strzelanką 2D i natknąłem się na ogromny problem. Wykrywanie kolizji. Jasne, działa, ale działa bardzo wolno. Moim celem jest: mieć na ekranie wielu wrogów i nie dotykać się nawzajem. Wszyscy wrogowie ścigają gracza. Większość z nich ma tę samą prędkość, więc prędzej czy później wszyscy zajmują to samo miejsce, ścigając gracza. To naprawdę obniża współczynnik zabawy, ponieważ dla gracza wygląda to tak, jakbyś był ścigany tylko przez jednego wroga. Aby zapobiec zajmowaniu tej samej przestrzeni, dodałem wykrywanie kolizji (bardzo podstawowe wykrywanie 2D, jedyna znana mi metoda), które jest.

Enemy class update method
    Loop through all enemies (continue; if the loop points at this object)
        If enemy object intersects with this object
            Push enemy object away from this enemy object

To działa dobrze. Tak długo, jak mam tylko <200 wrogich istot. Kiedy zbliżam się do 300-350 wrogich istot, moja częstotliwość klatek zaczyna spadać. Najpierw pomyślałem, że to źle renderuje, więc usunąłem ich call draw. To wcale nie pomogło, więc oczywiście zdałem sobie sprawę, że to metoda aktualizacji. Jedyną dużą częścią ich metody aktualizacji jest ta część, w której każdy wróg zapętla się przez każdego wroga. Kiedy zbliżam się do 300 wrogów, gra wykonuje krokową iterację 90000 (300 x 300). My my ~

Jestem pewien, że musi istnieć inny sposób podejścia do wykrywania kolizji. Chociaż nie mam pojęcia jak. Strony, które znajduję, dotyczą tego, jak faktycznie wykonać kolizję między dwoma obiektami lub jak sprawdzić kolizję między obiektem a płytką. Te dwie rzeczy już wiem.

tl; dr? Jak podejść do wykrywania kolizji między WIELKIMI podmiotami?

Szybka edycja: jeśli to pomoże, używam C # XNA.

Już trafiłeś w sedno swojego problemu, każdy byt sprawdza się w stosunku do każdego innego bytu. To, czego będziesz chciał, to jakiś system „Poziomu szczegółów” (jest to w zasadzie bardzo prosty wykres sceny, po prostu używasz go do innych celów niż renderowanie :)) tam, gdzie możliwe jest wybranie kandydatów na kolizję.

Generalnie wykonuję trzy kolekcje dla takich systemów. A kiedy mówisz o liczbie encji, które chcesz mieć, być może będziesz musiał użyć pełnego wykresu scen w tym celu, ponieważ dane śledzenia (3 listy na encję z wpisem dla każdej innej encji) mogą szybko wyjść kontroli.

Zasadniczo masz trzy listy. Pierwszą powinna być bardzo mała lista podmiotów, które będziesz sprawdzać za pomocą interakcji w każdej ramce. Określasz to, ponieważ znajdują się w zakresie X danego elementu. Jak wspomniano, celem tej listy jest zawarcie każdej jednostki, która może rozsądnie kolidować z inną tą ramką.

Następna lista zawiera te, które byłyby w zakresie bufora, który mógłby przenieść się w zakres bytu bez większego wysiłku. Będziemy nazywać ten zakres X * 1.5 tylko ze względu na argument. Jest to podzielona na czas lista, w której aktualizujesz tylko kilka z nich na klatkę, ale upewniasz się, że przeglądasz je wystarczająco szybko, aby zachować sprawny wygląd rzeczy.

Trzecia lista jest listą „wszystko inne” i sposobem na uniknięcie jej może być warto (Przeszukując całą listę encji i być może sprawdzając, czy znajduje się ona na jednej z innych list, zanim przejdziesz dalej? Może w zależności od wielkości listy może działać, a nawet pogorszyć sprawę.) Obiekty na tej liście są sprawdzane co najmniej, ponieważ zdecydowanie powinno to zająć więcej niż kilka ramek na jednej z pozostałych dwóch list.

Aby to utrzymać, musisz także wykonać testy kolizji, upewnij się, że zaktualizowałeś listę, w której znajdują się jednostki. Te, które się przemieszczają poza zasięg, powinny zostać obniżone, a te, które zbliżają się, powinny zostać uaktualnione do lista aktywniej sprawdzana.

Zakładając, że wszystko jest proste, powinno to odpowiadać Twoim potrzebom. Jeśli możesz dodać dodatkowe informacje do istniejącego grafu sceny renderowania (zakładając, że go masz), możesz zapytać go, aby uzyskać listę encji, które znajdują się w rozsądnym zakresie, nawet lepiej, ponieważ jest to cały punkt wykresu sceny w każdym razie (szybki dostęp do listy odpowiednich danych na podstawie pozycji). Potencjalnie wymagałoby to więcej pracy i zawsze powinieneś rozważyć to, co musisz zrobić, a nie to, co powinieneś zrobić praktycznie.

Mam nadzieję że to pomoże.

Musisz poradzić sobie z kolizjami z posortowaną strukturą danych, więc możesz mieć n * log (n) razy zamiast strasznego n ^ 2. A n * log (n) jest prawie liniowy, jak być może wiesz. Jednym (klasycznym) przykładem jest quadtree, jest tu dość prosty i dobrze napisany samouczek z grafiką i kodem (Java):

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Rq: dość łatwo jest znaleźć implementację dla QuadTrees w dowolnym języku. Musisz jednak pomyśleć o właściwej „ziarnistości” drzewa, a im większy rozmiar drzewa, tym więcej mamy elementów, które nie mieszczą się w węźle.
Rq 2: ponieważ partycjonowanie przestrzeni odbywa się tylko w celu wykrycia kolizji, masz doskonałą swobodę w dzieleniu przestrzeni, jak chcesz. Na przykład nie podzieliłbym się na cztery części, ale raczej użyłbym baricentrum bytów obecnego poziomu jako centrum nowego podziału. 1) algorytm wciąż jest n * log (n), 2) tracisz możliwość „przebudowania” sceny z drzewa - ale nie obchodzi cię to - i 3) masz drzewo o wiele bardziej zrównoważone, mniej narzutów .
Rq3: Po utworzeniu drzewa „kolizja” między ekranem a bytami daje… widoczne byty !! w czasie bardziej przypominającym log (n), więc dlaczego nie, jeśli n jest duże? (najgorszy przypadek to oczywiście czas in dla tego podejścia).

drzewo partycji przestrzeni binarnej, drzewo czwórkowe, oktawa (dla 3D) to możliwe drzewa, które można wygenerować (lub utrzymać, jeśli jesteś ambitny) przy każdym wywołaniu aktualizacji dla każdego obiektu, który chcesz zastosować w kolizji.

Jestem dość naiwny, gdy mówi się o quadach lub ośmiornicach. Myślę jednak, że ta metoda powinna:

Będziesz musiał zmodyfikować strukturę / klasę gracza. Dodaj tablicę / wektor wskaźników do innej struktury gracza.

Co sekundę sprawdzaj odległość między dwoma graczami. Jeśli jest tak niska, że ​​można osiągnąć w ciągu 1 sekundy, dodaj wskaźnik tego gracza do tablicy kolizji bieżącego gracza.

Teraz sprawdź tylko kolizję między graczami na liście pozostałych.