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ć.
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:
- porusza się jedno ciało
- po tym, jak się poruszy, odświeża komórki i dostaje ciała, z którymi się zderza
- 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:
- wszystkie ciała się poruszają
- po przeniesieniu wszystkich ciał odśwież wszystkie komórki
- generować unikalne pary kolizji
- 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 astd::bitsetwszystkich grup, których częścią jest ciało.Body::getGroupsToCheck()zwraca astd::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:
- 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).
bodyma teraz gwarancję, że wie, jakie komórki zajmuje.
Część 2: faktyczne kontrole kolizji
Dla każdego Body body:
body.gridInfo.handleCollisionsjest 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()została wywołana 5462334 razy i zajęła 35,1% całego czasu profilowania (czas dostępu do odczytu instrukcji)