Jak zoptymalizować silnik kolizji, w którym kolejność jest znacząca, a kolizja jest warunkowa w zależności od grupy obiektów?

Jeśli po raz pierwszy zastanawiasz się nad tym pytaniem, sugeruję najpierw przeczytać część wstępnej aktualizacji poniżej, a następnie tę część. Oto synteza problemu:

Zasadniczo mam silnik wykrywania i rozwiązywania kolizji z systemem podziału przestrzennego siatki, w którym ważna jest kolejność kolizji i grupy kolizji. Jedno ciało na raz musi się poruszyć, następnie wykryć kolizję, a następnie rozwiązać kolizje. Jeśli poruszę wszystkie ciała naraz, a następnie wygeneruję możliwe pary kolizji, jest to oczywiście szybsze, ale rozdzielczość psuje się, ponieważ nie przestrzega się kolejności kolizji. Jeśli poruszam jednym ciałem na raz, zmuszam ciała do sprawdzania kolizji, co staje się problemem ^ 2. Umieść grupy w miksie, a możesz sobie wyobrazić, dlaczego robi się bardzo wolno bardzo szybko z dużą ilością ciał.

Aktualizacja: Pracowałem nad tym naprawdę ciężko, ale nie byłem w stanie niczego zoptymalizować.

Z powodzeniem zaimplementowałem „malowanie” opisane przez Willa i zmieniłem grupy w zestawy bitów, ale jest to bardzo, bardzo niewielkie przyspieszenie.

Odkryłem również duży problem: mój silnik jest zależny od kolejności zderzeń.

Próbowałem zaimplementować unikalne generowanie par kolizji , które zdecydowanie przyspieszyły wszystko, ale złamałem kolejność kolizji .

Pozwól mi wyjaśnić:

• w moim oryginalnym projekcie (bez generowania par) dzieje się tak:

  1. porusza się jedno ciało
  2. po tym, jak się poruszy, odświeża komórki i dostaje ciała, z którymi się zderza
  3. jeśli pokrywa się z ciałem, przed którym musi rozwiązać, należy rozwiązać kolizję

  oznacza to, że jeśli ciało poruszy się i uderzy w ścianę (lub jakiekolwiek inne ciało), tylko ciało, które się poruszyło, rozwiąże jego kolizję, a drugie ciało pozostanie nienaruszone.

  Właśnie takiego zachowania pragnę .

  Rozumiem, że nie jest to powszechne w silnikach fizyki, ale ma wiele zalet w grach w stylu retro .

• w zwykłym projekcie siatki (generującym unikalne pary) dzieje się tak:

  1. wszystkie ciała się poruszają
  2. po przeniesieniu wszystkich ciał odśwież wszystkie komórki
  3. generować unikalne pary kolizji
  4. dla każdej pary obsługuj wykrywanie kolizji i rozdzielczość

  w tym przypadku jednoczesny ruch mógł spowodować nałożenie się dwóch ciał, a one jednocześnie rozwiązałyby - skutecznie powoduje to, że ciała „popychają się nawzajem” i psuje stabilność kolizji z wieloma ciałami

  Takie zachowanie jest powszechne w silnikach fizyki, ale w moim przypadku jest nie do przyjęcia .

Znalazłem też inny problem, który jest poważny (nawet jeśli nie zdarzy się to w rzeczywistości):

• rozważ ciała grupy A, B i W
• Zderza się i rozwiązuje przeciwko W i A.
• B zderza się i rozpatruje przeciwko W i B.
• A nie robi nic przeciwko B.
• B nie robi nic przeciwko A.

może wystąpić sytuacja, w której wiele ciał A i B zajmuje tę samą komórkę - w takim przypadku istnieje wiele niepotrzebnej iteracji między ciałami, które nie mogą reagować na siebie (lub tylko wykrywają kolizję, ale ich nie rozwiązują) .

Dla 100 ciał zajmujących tę samą komórkę jest to 100 ^ 100 iteracji! Dzieje się tak, ponieważ unikalne pary nie są generowane - ale nie mogę wygenerować unikalnych par , w przeciwnym razie uzyskałbym zachowanie, którego nie chciałbym.

Czy istnieje sposób na zoptymalizowanie tego rodzaju silnika kolizji?

Oto wytyczne, których należy przestrzegać:

• Kolejność kolizji jest niezwykle ważna!

  • Ciała muszą poruszać się pojedynczo , a następnie sprawdzać kolizje pojedynczo i rozpatrywać po ruchu pojedynczo .

• Ciała muszą mieć 3 grupy bitów

  • Grupy : grupy, do których należy ciało
  • GroupsToCheck : grupy, przeciwko którym ciało musi wykryć kolizję
  • GroupsNoResolve : grupy, z którymi ciało nie może rozstrzygać kolizji
  • Mogą wystąpić sytuacje, w których chcę tylko, aby kolizja została wykryta, ale nie rozwiązana

Aktualizacja wstępna:

Przedmowa : Zdaję sobie sprawę, że optymalizacja tego wąskiego gardła nie jest koniecznością - silnik jest już bardzo szybki. Jednak w celach rozrywkowych i edukacyjnych chciałbym znaleźć sposób na zwiększenie prędkości silnika.

Tworzę uniwersalny silnik C ++ 2D do wykrywania kolizji / reagowania, z naciskiem na elastyczność i szybkość.

Oto bardzo prosty schemat architektury:

Zasadniczo główną klasą jest World, która posiada (zarządza pamięcią) a ResolverBase*, a SpatialBase*i a vector<Body*>.

SpatialBase to czysto wirtualna klasa zajmująca się wykrywaniem kolizji w fazie szerokiej.

ResolverBase to czysto wirtualna klasa zajmująca się rozwiązywaniem kolizji.

Ciała komunikują się World::SpatialBase*z SpatialInfoprzedmiotami będącymi własnością samych ciał.

Obecnie istnieje jedna klasa przestrzenna: Grid : SpatialBasepodstawowa stała siatka 2D. To ma swój własny informacji klasę GridInfo : SpatialInfo.

Oto jak wygląda jego architektura:

GridKlasa posiada tablicę 2D Cell*. CellKlasa zawiera zbiór (nie będących własnością) Body*: a vector<Body*>, która zawiera wszystkie podmioty, które są w komórce.

GridInfo obiekty zawierają także nieposiadające wskaźników komórki, w których znajduje się ciało.

Jak już powiedziałem, silnik oparty jest na grupach.

• Body::getGroups()zwraca a std::bitsetwszystkich grup, których częścią jest ciało.
• Body::getGroupsToCheck()zwraca a std::bitsetwszystkich grup, z którymi ciało musi sprawdzić kolizję.

Ciała mogą zajmować więcej niż jedną komórkę. GridInfo zawsze przechowuje niepowiązane wskaźniki do zajętych komórek.

Po poruszeniu jednego ciała następuje wykrycie kolizji. Zakładam, że wszystkie ciała są obwiedniami wyrównanymi do osi.

Jak działa wykrywanie kolizji w fazie szerokiej:

Część 1: aktualizacja informacji przestrzennej

Dla każdego Body body:

1. • Obliczane są komórki zajmowane od góry po lewej stronie i komórki zajmowane od dołu po prawej stronie.
   • Jeśli różnią się od poprzednich komórek, body.gridInfo.cellssą usuwane i wypełniane wszystkimi komórkami zajmowanymi przez ciało (2D dla pętli od komórki znajdującej się w lewym górnym rogu do komórki znajdującej się w prawym dolnym rogu).

2. body ma teraz gwarancję, że wie, jakie komórki zajmuje.

Część 2: faktyczne kontrole kolizji

Dla każdego Body body:

• body.gridInfo.handleCollisions jest nazywany:

void GridInfo::handleCollisions(float mFrameTime)
{
    static int paint{-1};
    ++paint;

    for(const auto& c : cells)
        for(const auto& b : c->getBodies())
        {
            if(b->paint == paint) continue;
            base.handleCollision(mFrameTime, b);
            b->paint = paint;
        }
}

void Body::handleCollision(float mFrameTime, Body* mBody)
    {
        if(mBody == this || !mustCheck(*mBody) || !shape.isOverlapping(mBody->getShape())) return;

        auto intersection(getMinIntersection(shape, mBody->getShape()));

        onDetection({*mBody, mFrameTime, mBody->getUserData(), intersection});
        mBody->onDetection({*this, mFrameTime, userData, -intersection});

        if(!resolve || mustIgnoreResolution(*mBody)) return;
        bodiesToResolve.push_back(mBody);
    }

• Kolizja jest następnie rozstrzygana dla każdego ciała w bodiesToResolve.

• Otóż ​​to.

Od dłuższego czasu próbowałem zoptymalizować wykrywanie kolizji w fazie szerokiej. Za każdym razem, gdy próbuję czegoś innego niż obecna architektura / konfiguracja, coś nie idzie zgodnie z planem lub zakładam, że symulacja jest później nieprawdziwa.

Moje pytanie brzmi: w jaki sposób mogę zoptymalizować fazę szeroką silnika kolizji ?

Czy istnieje tutaj jakaś magiczna optymalizacja C ++?

Czy architektura może zostać przeprojektowana w celu zapewnienia większej wydajności?

• Rzeczywista implementacja: SSVSCollsion
• Body.h , Body.cpp
• World.h , World.cpp
• Grid.h , Grid.cpp
• Cell.h , Cell.cpp
• GridInfo.h , GridInfo.cpp

Wyjście Callgrind dla najnowszej wersji: http://txtup.co/rLJgz

getBodiesToCheck()

Mogą występować dwa problemy z getBodiesToCheck()funkcją; pierwszy:

if(!contains(bodiesToCheck, b)) bodiesToCheck.push_back(b);

Ta część to O (n ² ), prawda?

Zamiast sprawdzać, czy ciało jest już na liście, zamiast tego użyj malowania .

loop_count++;
if(!loop_count) { // if loop_count can wrap,
    // you just need to iterate all bodies to reset it here
}
bodiesToCheck.clear();
for(const auto& q : queries)
    for(const auto& b : *q)
        if(b->paint != loop_count) {
            bodiesToCheck.push_back(b);
            b->paint = loop_count;
        }
return bodiesToCheck;

Dereferentujesz wskaźnik w fazie zbierania, ale i tak byłbyś dereferencyjny w fazie testowej, więc jeśli masz wystarczająco dużo L1, to nic wielkiego. Możesz poprawić wydajność, dodając wskazówki kompilatora przed pobraniem, np. __builtin_prefetchChociaż jest to łatwiejsze w przypadku klasycznych for(int i=q->length; i-->0; )pętli.

To proste ulepszenie, ale moja druga myśl jest taka, że ​​może istnieć szybszy sposób na zorganizowanie tego:

Zamiast tego możesz przejść do korzystania z map bitowych i unikania całego bodiesToCheckwektora. Oto podejście:

Używasz już kluczy całkowitych do ciał, ale następnie przeglądasz je na mapach i rzeczach i przeglądasz ich listy. Możesz przejść do alokatora gniazd, który jest po prostu tablicą lub wektorem. Na przykład:

class TBodyImpl {
   public:
       virtual ~TBodyImpl() {}
       virtual void onHit(int other) {}
       virtual ....
       const int slot;
   protected:
      TBodyImpl(int slot): slot(slot_) {}
};

struct TBodyBase {
    enum ... type;
    ...
    rect_t rect;
    TQuadTreeNode *quadTreeNode; // see below
    TBodyImpl* imp; // often null
};

std::vector<TBodyBase> bodies; // not pointers to them

Oznacza to, że wszystkie rzeczy potrzebne do przeprowadzenia rzeczywistych kolizji znajdują się w liniowej pamięci przyjaznej dla pamięci podręcznej, a ty przechodzisz do specyficznego dla implementacji bitu i dołączasz go do jednego z tych gniazd, jeśli jest taka potrzeba.

Do śledzenia przydziałów w tym wektorze organów można użyć tablicę liczb całkowitych jako bitmapy i użytkowania bitowym twiddling lub __builtin_ffsitp Jest bardzo wydajny, aby przejść do gniazd, które są aktualnie zajęte, albo znaleźć niezajęte gniazdo w tablicy. Czasami możesz nawet zagęścić tablicę, jeśli staje się ona zbyt duża, a następnie partie są oznaczone jako usunięte, przesuwając je na końcu, aby wypełnić luki.

sprawdzaj tylko dla każdej kolizji jeden raz

Jeśli po sprawdzeniu, czy a zderza się z B , nie trzeba by sprawdzić, czy b zderza się z też.

Z używania liczb całkowitych wynika, że ​​unika się tych kontroli za pomocą prostej instrukcji if. Jeśli identyfikator potencjalnej kolizji jest mniejszy lub równy sprawdzonemu bieżącemu identyfikatorowi, można go pominąć! W ten sposób możesz sprawdzić każdą możliwą parę tylko raz; to ponad połowa liczby kontroli kolizji.

unsigned * bitmap;
int bitmap_len;
...

for(int i=0; i<bitmap_len; i++) {
  unsigned mask = bitmap[i];
  while(mask) {
      const int j = __builtin_ffs(mask);
      const int slot = i*sizeof(unsigned)*8+j;
      for(int neighbour: get_neighbours(slot))
          if(neighbour > slot)
              check_for_collision(slot,neighbour);
      mask >>= j;
  }

przestrzegać kolejności kolizji

Zamiast oceniać kolizję, gdy tylko para zostanie znaleziona, oblicz odległość do trafienia i zapisz ją na stosie binarnym . Te stosy są typowymi kolejkami priorytetowymi w wyszukiwaniu ścieżek, więc jest to bardzo przydatny kod narzędziowy.

Zaznacz każdy węzeł numerem sekwencyjnym, abyś mógł powiedzieć:

• A ¹⁰ uderza B ¹² na 6
• ¹⁰ trafień C ¹² z 3

Oczywiście po zebraniu wszystkich kolizji zaczniesz je usuwać z kolejki priorytetowej, najwcześniej. Więc pierwsze masz jest ¹⁰ hitów C ¹² na 3. Ty zwiększamy liczbę sekwencji każdego obiektu (do ¹⁰ bit), oceny kolizji, i obliczyć swoje nowe ścieżki i przechowywać swoje nowe kolizje w tej samej kolejce. Nowa kolizja to trafienie A ^11, B ^{12 o} godzinie 7. Kolejka ma teraz:

• A ¹⁰ uderza B ¹² na 6
• A ¹¹ uderza B ¹² na 7

Potem wyskakujesz z kolejki priorytetowej i jej A ¹⁰ uderza B ¹² o 6. Ale widzisz, że A ¹⁰ jest nieświeży ; A ma obecnie 11 lat, więc możesz odrzucić tę kolizję.

Ważne jest, aby nie zawracać sobie głowy próbą usunięcia wszystkich starych kolizji z drzewa; usuwanie ze sterty jest kosztowne. Po prostu odrzuć je, gdy je otworzysz.

siatka

Zamiast tego powinieneś rozważyć użycie quadtree. Jest to bardzo prosta struktura danych do wdrożenia. Często widzisz implementacje przechowujące punkty, ale ja wolę przechowywać rektyfikacje i przechowywać element w węźle, który go zawiera. Oznacza to, że aby sprawdzić kolizje, musisz wykonać iterację tylko nad wszystkimi ciałami i dla każdego z nich sprawdzić je względem tych ciał w tym samym węźle quad-tree (przy użyciu sztuczki sortowania przedstawionej powyżej) i wszystkich w nadrzędnych węzłach quad-tree. Quad-drzewo samo w sobie jest listą możliwych kolizji.

Oto prosty Quadtree:

struct Object {
    Rect bounds;
    Point pos;
    Object * prev, * next;
    QuadTreeNode * parent;
};

struct QuadTreeNode {
    Rect bounds;
    Point centre;
    Object * staticObjects;
    Object * movableObjects;
    QuadTreeNode * parent; // null if root
    QuadTreeNode * children[4]; // null for unallocated children
};

Przechowujemy ruchome obiekty osobno, ponieważ nie musimy sprawdzać, czy obiekty statyczne zderzą się z czymkolwiek.

Modelujemy wszystkie obiekty jako ramki ograniczające wyrównane do osi (AABB) i umieszczamy je w najmniejszym zawierającym je QuadTreeNode. Gdy QuadTreeNode ma wiele dzieci, możesz go dalej podzielić (jeśli obiekty te ładnie się rozdzielają na dzieci).

W każdej grze tykaj, musisz powracać do kwadratu i obliczać ruch - i kolizje - każdego ruchomego obiektu. Należy sprawdzić, czy nie ma kolizji z:

• każdy obiekt statyczny w swoim węźle
• każdy ruchomy obiekt w jego węźle, który jest przed nim (lub po nim; wystarczy wybrać kierunek) na liście movableObjects
• każdy ruchomy i statyczny obiekt we wszystkich węzłach nadrzędnych

To wygeneruje wszystkie możliwe kolizje, nieuporządkowane. Następnie wykonujesz ruchy. Musisz ustalić priorytety tych ruchów według odległości i „kto pierwszy” (co jest twoim specjalnym wymaganiem) i wykonać je w tej kolejności. Użyj do tego stosu.

Możesz zoptymalizować ten szablon quadtree; nie musisz właściwie przechowywać granic i punktu środkowego; to całkowicie pochodne, gdy idziesz po drzewie. Nie musisz sprawdzać, czy model mieści się w granicach, sprawdź tylko, po której stronie znajduje się punkt środkowy (test „osi oddzielenia”).

Aby modelować szybko latające rzeczy, takie jak pociski, zamiast przesuwać je na każdym kroku lub mieć osobną listę pocisków, którą zawsze sprawdzasz, po prostu umieść je w kwadracie z rektą lotu na pewną liczbę kroków w grze. Oznacza to, że poruszają się w quadtree znacznie rzadziej, ale nie sprawdzasz pocisków na odległych ścianach, więc jest to dobry kompromis.

Duże obiekty statyczne powinny być podzielone na części składowe; na przykład duża kostka powinna mieć oddzielnie każdą twarz.

Założę się, że po prostu masz mnóstwo braków w pamięci podręcznej podczas iteracji nad ciałami. Czy łączysz wszystkie swoje ciała razem, stosując jakiś schemat projektowania zorientowany na dane? Dzięki szerokofazowej fazie N ^ 2 mogę symulować setki setek ciał bez rejestrowania klatek w obszarach dolnych (mniej niż 60), a to wszystko bez niestandardowego alokatora. Wyobraź sobie, co można zrobić z odpowiednim użyciem pamięci podręcznej.

Wskazówka jest tutaj:

const std::vector<Body *>

To natychmiast podnosi ogromną czerwoną flagę. Czy przydzielasz tym organom nieprzetworzone nowe połączenia? Czy jest używany niestandardowy alokator? Najważniejsze jest, aby wszystkie ciała były w ogromnym układzie, w którym poruszasz się liniowo . Jeśli przejście przez pamięć liniowo nie jest czymś, co uważasz, że możesz wdrożyć, rozważ użycie zamiast tego natrętnie połączonej listy.

Dodatkowo wydaje się, że używasz std :: map. Czy wiesz, w jaki sposób alokowana jest pamięć w std :: map? Będziesz mieć złożoność O (lg (N)) dla każdego zapytania mapowego, i prawdopodobnie można ją zwiększyć do O (1) za pomocą tabeli skrótów. Ponadto pamięć przydzielona przez std :: map będzie również strasznie niszczyć pamięć podręczną.

Moim rozwiązaniem jest użycie natrętnej tabeli skrótów zamiast std :: map. Dobry przykład zarówno natrętnie połączonych list, jak i natrętnych tabel skrótów znajduje się w bazie Patricka Wyatta w jego projekcie coho: https://github.com/webcoyote/coho

Krótko mówiąc, prawdopodobnie będziesz musiał stworzyć dla siebie niestandardowe narzędzia, a mianowicie alokator i niektóre natrętne pojemniki. To najlepsze, co mogę zrobić bez profilowania kodu dla siebie.

Zmniejsz liczbę ciał, aby sprawdzić każdą klatkę:

Sprawdź tylko ciała, które mogą się faktycznie poruszać. Obiekty statyczne należy przypisać do komórek kolizji tylko raz po ich utworzeniu. Teraz sprawdzaj tylko kolizje dla grup, które zawierają co najmniej jeden obiekt dynamiczny. Powinno to zmniejszyć liczbę kontroli w każdej ramce.

Użyj czworokąta. Zobacz moją szczegółową odpowiedź tutaj

Usuń wszystkie przydziały z kodu fizyki. Możesz do tego użyć profilera. Ale analizowałem tylko przydział pamięci w C #, więc nie mogę pomóc z C ++.

Powodzenia!

W funkcji wąskiego gardła widzę dwóch problematycznych kandydatów:

Pierwsza to część „zawiera” - to prawdopodobnie główny powód wąskiego gardła. Iteruje przez już znalezione ciała dla każdego ciała. Może powinieneś raczej użyć jakiegoś hash_table / hash_map zamiast wektora. Następnie wstawianie powinno być szybsze (z wyszukiwaniem duplikatów). Ale nie znam konkretnych liczb - nie mam pojęcia, ile ciał jest tutaj iterowanych.

Drugim problemem może być vector :: clear i push_back. Clear może, ale nie musi, wywoływać realokację. Ale możesz tego uniknąć. Rozwiązaniem może być tablica flag. Ale prawdopodobnie masz wiele obiektów, więc nie ma pamięci, aby mieć listę wszystkich obiektów dla każdego obiektu. Inne podejście może być fajne, ale nie wiem jakie podejście: /

Uwaga: nic nie wiem o C ++, tylko Java, ale powinieneś być w stanie zrozumieć kod. Fizyka to uniwersalny język, prawda? Zdaję sobie również sprawę, że jest to roczny post, ale chciałem się tym wszystkim podzielić.

Mam wzorzec obserwatora, który zasadniczo po poruszeniu bytu zwraca obiekt, z którym zderzył się, w tym obiekt NULL. Po prostu:

( Przerabiam Minecraft )

public Block collided(){
   return World.getBlock(getLocation());
}

Powiedzmy, że wędrujecie po swoim świecie. za każdym razem, gdy zadzwonisz move(1), zadzwońcollided() . jeśli dostaniesz żądany blok, być może cząsteczki latają i możesz poruszać się w lewo, w prawo i do tyłu, ale nie do przodu.

Wykorzystując to bardziej ogólnie niż tylko Minecraft jako przykład:

public Object collided(){
   return threeDarray[3][2][3];
}

Po prostu miej tablicę, aby wskazać współrzędne, które dosłownie, jak robi to Java, używa wskaźników.

Korzystanie z tej metody nadal wymaga czegoś innego niż a priori metoda wykrywania kolizji. Możesz to zapętlić, ale to przeczy celowi. Możesz zastosować to do technik szerokiej, średniej i wąskiej kolizji, ale sam, to bestia, szczególnie gdy działa całkiem dobrze w grach 3D i 2D.

Teraz, gdy spojrzę jeszcze raz, oznacza to, że zgodnie z moją metodą kolizji minecrafta () skończę w bloku, więc będę musiał przenieść gracza poza niego. Zamiast sprawdzać gracza, muszę dodać ramkę ograniczającą, która sprawdza, który blok uderza w każdą stronę pola. Problem rozwiązany.

powyższy akapit może nie być tak łatwy w przypadku wielokątów, jeśli chcesz dokładności. Aby uzyskać dokładność, sugeruję zdefiniowanie obwiedni wielokąta, która nie jest kwadratem, ale nie jest mozaikowana. jeśli nie, to prostokąt jest w porządku.