Czy istnieje sposób na zwiększenie wydajności kontroli kolizji systemu n obiektów?

Tworzę grę, która składa się z wielu obiektów na ekranie, z których jednym jest gracz. Muszę wiedzieć, które obiekty kolidują podczas każdej iteracji.

Zrobiłem coś takiego:

for (o in objects)
{
   o.stuff();
   for (other in objects)
      if (collision(o, other))
          doStuff();

   bla.draw();
}

Ma O (n ^ 2), co, jak mi powiedziano, jest złe. Jak mogę to zrobić bardziej efektywnie, czy to w ogóle możliwe? Robię to w Javascripcie, a n zwykle będzie niższe niż 30, czy będzie problem, jeśli pozostanie taki sam?

Mając maksymalnie 30 obiektów, nie powinieneś potrzebować żadnej optymalizacji poza tym, aby nie sprawdzać tych samych dwóch par więcej niż jeden raz na klatkę. Obejmuje to poniższy przykład kodu. Ale jeśli interesują Cię różne optymalizacje, z których skorzystałby silnik fizyki, czytaj dalej resztę tego postu.

Potrzebna będzie implementacja partycjonowania przestrzennego , taka jak Octree (dla gier 3D) lub Quadtree (dla gier 2D). Dzielą świat na podsekcje, a następnie każda podsekcja jest dalej dzielona na ten sam dwór, dopóki nie zostaną podzielone na minimalny rozmiar. Pozwala to bardzo szybko sprawdzić, które inne obiekty znajdują się w tym samym regionie świata co inny, co ogranicza liczbę kolizji, z którymi musisz się zmierzyć.

Oprócz partycjonowania przestrzennego zaleciłbym utworzenie AABB ( obwiedni wyrównanej do osi ) dla każdego z twoich obiektów fizycznych. Umożliwia to sprawdzenie AABB jednego obiektu względem drugiego, co jest znacznie szybsze niż szczegółowe sprawdzenie poszczególnych obiektów między obiektami.

Można to zrobić o krok dalej w przypadku skomplikowanych lub dużych obiektów fizycznych, w których można podzielić siatkę fizyki, dając każdemu pod-kształtowi własny AABB, który można sprawdzić tylko wtedy, gdy AABB dwóch obiektów się nakładają.

Większość silników fizykalnych dezaktywuje aktywną symulację fizyki na ciałach fizycznych po ich zatrzymaniu. Kiedy ciało fizyki jest dezaktywowane, musi tylko sprawdzić kolizję z jego AABB w każdej ramce, a jeśli coś zderzy się z AABB, wówczas ponownie się aktywuje i przeprowadzi bardziej szczegółową kontrolę kolizji. To skraca czas symulacji.

Ponadto wiele silników fizyki korzysta z „wysp symulacyjnych”, w których grupa ciał fizycznych znajdujących się blisko siebie jest zgrupowana. Jeśli wszystko na wyspie symulacji jest w spoczynku, sama wyspa symulacji dezaktywuje się. Zaletą wyspy symulacyjnej jest to, że wszystkie znajdujące się w niej ciała mogą przestać sprawdzać kolizje, gdy wyspa jest nieaktywna, a jedynym sprawdzeniem w każdej ramce jest sprawdzenie, czy coś dostało się do AABB wyspy. Tylko wtedy, gdy coś wejdzie do AABB wyspy, każde ciało na wyspie będzie musiało sprawdzić, czy nie ma kolizji. Wyspa symulacyjna reaktywuje się również, jeśli którekolwiek z jej ciał zacznie się ponownie poruszać. Jeśli ciało porusza się wystarczająco daleko od centrum grupy, jest usuwane z wyspy.

Na koniec masz coś takiego (w pseudokodzie):

// Go through each leaf node in the octree. This could be more efficient
// by keeping a list of leaf nodes with objects in it.
for ( node in octreeLeafNodes )
{
    // We only need to check for collision if more than one object
    // or island is in the bounds of this octree node.
    if ( node.numAABBsInBounds > 1)
    {
        for ( int i = 0; i < AABBNodes.size(); ++i )
        {
           // Using i+1 here allows us to skip duplicate checks between AABBS
           // e.g (If there are 5 bodies, and i = 0, we only check i against
           //      indexes 1,2,3,4. Once i = 1, we only check i against indexes
           //      2,3,4)
           for ( int j = i + 1; j < AABBNodes.size(); ++j )
           {
               if ( AABBOverlaps( AABBNodes[i], AABBNodes[j] ) )
               {
                   // If the AABB we checked against was a simulation island
                   // then we now check against the nodes in the simulation island

                   // Once you find overlaps between two actual object AABBs
                   // you can now check sub-nodes with each object, if you went
                   // that far in optimizing physics meshes.
               {
           }
        }
    }
}

Poleciłbym również, aby nie mieć tak wielu pętli w takich pętlach, powyższa próbka była po prostu, abyś wpadł na pomysł, podzielę ją na wiele funkcji, które zapewniają taką samą funkcjonalność jak coś takiego, jak pokazano powyżej.

Pamiętaj również, aby nie zmieniać kontenera AABBNodes podczas jego przechodzenia, ponieważ może to oznaczać brak kontroli kolizji. Może to zabrzmieć jak zdrowy rozsądek, ale byłbyś zaskoczony, jak łatwo jest reagować na kolizje, powodując zmiany, których nie spodziewałbyś się. Na przykład jeśli kolizja spowodowała, że ​​jeden z kolidujących obiektów zmienił pozycję na tyle, aby usunąć je z AABB sprawdzanego węzła Octree, może to zmienić ten kontener. Aby rozwiązać ten problem, zalecam prowadzenie listy wszystkich zdarzeń kolizji, które mają miejsce podczas kontroli, a następnie po zakończeniu wszystkich kontroli przejrzyj listę i wyślij wszystkie zdarzenia kolizji.

Twój przykład testuje każdą parę obiektów wiele razy.

Weźmy bardzo prosty przykład z tablicą zawierającą 0,1,2,3

Za pomocą kodu otrzymujesz:

• W pętli 0 testujesz względem 1, 2 i 3
• W pętli 1 testujesz względem 0, 2 i 3 ===> (0-1 już przetestowane)
• W pętli 2 testujesz względem 0, 1 i 3 ===> (0-2 / 1-2 już przetestowane)
• W pętli 3 testujesz względem 0, 1 i 2 ===> (0-3 / 1-3 / 2-3 już przetestowane)

Teraz zobaczmy następujący kod:

for(i=0;i<=objects.length;i++)
{
    objects[i].stuff();

    for(j=i+1;j<=objects.length;j++)
    {
        if (collision(objects[i], objects[j]))
        doStuff();
    }

    bla.draw();
}

Jeśli ponownie użyjemy tablicy zawierającej 0,1,2,3, mamy następujące zachowanie:

• W pętli 0 testujesz względem 1, 2, 3
• W pętli 1 testujesz względem 2, 3
• W pętli 2 testujesz na 3
• W pętli 3 testujesz na niczym

W drugim algorytmie mamy 6 testów kolizji, podczas gdy poprzedni poprosił o 12 testów kolizji.

Zaprojektuj algorytm zgodnie z potrzebami, ale zachowaj szczegółowość danych dotyczących implementacji. Nawet w języku Javascript obowiązują podstawowe koncepcje OOP.

Dla N =~ 30, O(N*N)nie jest problemem, a przeszukiwanie liniowe może być tak samo szybko, jak tam jakiejkolwiek alternatywy. Ale nie chcesz zapisywać w kodzie założeń. W pseudokodzie miałbyś interfejs

interface itemContainer { 
    add(BoundingBox);
    remove(BoundingBox);
    BoundingBox[] getIntersections();
}

To opisuje, co może zrobić twoja lista przedmiotów. Następnie możesz napisać klasę ArrayContainer, która implementuje ten interfejs. W Javascript kod wygląda następująco:

function ArrayContainer() { ... } // this uses an array to store my objects
ArrayContainer.prototype.add = function(box) { ... };
ArrayContainer.prototype.remove = function(box) { ... };
ArrayContainer.prototype.getIntersections = function() { ... };

function QuadTreeContainer { ... } // this uses a quadtree to store my objects
... and implement in the add/remove/getIntersections for QuadTreeContainer too

A oto przykładowy kod, który tworzy 300 obwiedni i pobiera wszystkie skrzyżowania. Jeśli poprawnie zaimplementowałeś ArrayContainer i QuadTreeContainer, jedyną rzeczą, którą musisz zmienić w kodzie, jest zmiana var allMyObjects = new ArrayContainer()na var allMyObjects = QuadTreeContainer().

var r = Math.random;
var allMyObjects = new ArrayContainer();
for(var i=0; i<300; i++)
    allMyObjects.add(new BoundingBox(r(), r()));
var intersections = allMyObjects.getIntersections();

Poszedłem dalej i ulepszyłem implementację standardowego ArrayContainer tutaj:

http://jsfiddle.net/SKkN5/1/

Należy również wziąć pod uwagę rodzaje obiektów, które mogą rozsądnie kolidować.

Na przykład gracz prawdopodobnie musi zostać sprawdzony pod kątem kolizji ze wszystkim oprócz własnych kul. Jednak wrogowie mogą wymagać tylko sprawdzenia przeciwko kulom gracza. Kule prawie na pewno nie muszą się ze sobą zderzać.

Aby skutecznie to zaimplementować, prawdopodobnie chcesz przechowywać osobne listy obiektów, po jednym dla każdego typu obiektu.