Jak efektywnie znajdować wszystkie byty w promieniu?

Mam bardzo dużą liczbę podmiotów (jednostek). Na każdym kroku każda jednostka musi znać pozycje wszystkich jednostek w jej pobliżu (odległość jest mniejsza niż podana stała R ). Wszystkie jednostki poruszają się w sposób ciągły. To jest w 3D.

Średnio będzie 1% całkowitej liczby jednostek w pobliżu dowolnej innej jednostki o danych ograniczeniach.

Jak mogę to zrobić wydajnie, bez brutalizacji?

Użyj jednego z typowych algorytmów partycjonowania przestrzeni, takich jak Quadtree, Octree, drzewo BSP, a nawet prosty system grid. Każdy ma swoje zalety i wady dla każdego konkretnego scenariusza. Możesz przeczytać więcej o nich w tych książkach .

Ogólnie (przynajmniej tak słyszałem, nie jestem zbyt zaznajomiony z uzasadnieniem tego) Quadtree lub Octree lepiej pasują do środowisk zewnętrznych, podczas gdy drzewo BSP lepiej pasuje do scen w pomieszczeniach. Wybór między użyciem Quadtree lub Octree zależy od tego, jak płaski jest twój świat. Jeśli istnieje niewielka zmiana w osi Y, użycie Octree byłoby marnotrawstwem. Octree to w zasadzie Quadtree z dodatkowym wymiarem.

Wreszcie, nie lekceważ prostoty rozwiązania Grid. Wiele osób ignoruje fakt, że prosta siatka może czasem wystarczyć (a nawet bardziej wydajna) dla ich problemów, i zamiast tego przejść od razu do bardziej złożonego rozwiązania.

Korzystanie z siatki polega po prostu na podzieleniu świata na równomiernie rozmieszczone regiony i przechowywaniu bytów w odpowiednim regionie świata. Następnie, biorąc pod uwagę pozycję, znalezienie sąsiednich bytów byłoby kwestią iteracji po regionach, które przecinają twój promień poszukiwań.

Powiedzmy, że twój świat wahał się od (-1000, -1000) do (1000, 1000) w płaszczyźnie XZ. Możesz na przykład podzielić go na siatkę 10x10, tak jak:

var grid = new List<Entity>[10, 10];

Następnie umieściłbyś byty w odpowiednich komórkach w siatce. Na przykład byt z XZ (-1000, -1000) spadłby na komórkę (0,0), podczas gdy byt z XZ (1000, 1000) spadłby na komórkę (9, 9). Następnie, biorąc pod uwagę pozycję i promień na świecie, możesz określić, które komórki przecinają to „koło” i iterować tylko nad nimi, z prostym podwójnym dla.

W każdym razie poszukaj wszystkich alternatyw i wybierz tę, która wydaje się lepiej pasować do Twojej gry. Przyznaję, że wciąż nie mam wystarczającej wiedzy na ten temat, aby zdecydować, który z algorytmów będzie dla Ciebie najlepszy.

Edytuj Znalazłem to na innym forum i może ci pomóc w podjęciu decyzji:

Siatki działają najlepiej, gdy większość obiektów mieści się w kwadracie siatki, a rozkład jest dość jednorodny. I odwrotnie, czworoboki działają, gdy obiekty mają zmienne rozmiary lub są skupione w małych obszarach.

Biorąc pod uwagę twój niejasny opis problemu, również opieram się na rozwiązaniu sieciowym (tzn. Zakładając, że jednostki są małe i dość jednorodnie rozmieszczone).

Napisałem to jakiś czas temu. Jest teraz na stronie komercyjnej, ale możesz uzyskać źródło do użytku osobistego za darmo. Może to być przesada i jest napisane w Javie, ale jest dobrze udokumentowane, więc nie powinno być zbyt trudne do przycinania i przepisywania w innym języku. Zasadniczo wykorzystuje Octree, z drobnymi poprawkami do obsługi naprawdę dużych obiektów i wielowątkowości.

Odkryłem, że Octree oferuje najlepsze połączenie elastyczności i wydajności. Zaczynałem od siatki, ale niemożliwe było odpowiednie dopasowanie kwadratów, a duże plamy pustych kwadratów zajmowały miejsce i moc obliczeniową na nic. (I to było tylko w 2 wymiarach.) Mój kod obsługuje zapytania z wielu wątków, co znacznie zwiększa złożoność, ale dokumentacja powinna pomóc ci obejść ten problem, jeśli go nie potrzebujesz.

Aby zwiększyć efektywność, spróbuj trywialnie odrzucić 99% „jednostek”, które nie znajdują się w pobliżu jednostki docelowej, używając bardzo taniego pola wyboru. Mam nadzieję, że możesz to zrobić bez uporządkowania danych przestrzennie. Więc jeśli wszystkie twoje jednostki są przechowywane w płaskiej strukturze danych, możesz spróbować prześcignąć je od początku do końca i najpierw sprawdzić, czy bieżąca jednostka znajduje się poza ramką jednostki zainteresowania.

Zdefiniuj ponadgabarytową ramkę ograniczającą dla interesującej jednostki, tak aby mogła bezpiecznie odrzucać przedmioty, które nie mają szans na uznanie jej za „znajdujące się w pobliżu”. Sprawdzenie wyłączenia z obwiedni może być tańsze niż sprawdzenie promienia. Jednak w niektórych systemach, w których zostało to przetestowane, okazało się, że tak nie jest. Obaj działają prawie tak samo. To zredagowane po wielu debatach poniżej.

Po pierwsze: klips obwiedni 2D.

// returns true if the circle supplied is completely OUTSIDE the bounding box, rectClip
bool canTrivialRejectCircle(Vertex2D& vCentre, WorldUnit radius, Rect& rectClip) {
  if (vCentre.x + radius < rectClip.l ||
    vCentre.x - radius > rectClip.r ||
    vCentre.y + radius < rectClip.b ||
    vCentre.y - radius > rectClip.t)
    return true;
  else
    return false;
}

W porównaniu z czymś takim (w 3D):

BOOL bSphereTest(CObject3D* obj1, CObject3D* obj2 )
{
  D3DVECTOR relPos = obj1->prPosition - obj2->prPosition;
  float dist = relPos.x * relPos.x + relPos.y * relPos.y + relPos.z * relPos.z;
  float minDist = obj1->fRadius + obj2->fRadius;
  return dist <= minDist * minDist;
}.

Jeśli obiekt nie jest trywialnie odrzucony, wówczas przeprowadzasz droższy i dokładniejszy test kolizji. Ale szukasz tylko bliskości, więc test kuli nadaje się do tego, ale tylko dla 1% obiektów, które przetrwają banalne odrzucenie.

Ten artykuł obsługuje pole do trywialnego odrzucenia. http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

Jeśli to liniowe podejście nie zapewnia wymaganej wydajności, może być wymagana hierarchiczna struktura danych, taka jak mówiono o innych plakatach. R-Drzewa są warte rozważenia. Wspierają dynamiczne zmiany. Są BTree świata przestrzennego.

Po prostu nie chciałem, żebyś miał tyle kłopotów z wprowadzeniem takiej złożoności, gdybyś mógł jej uniknąć. A co z kosztem utrzymania tej złożonej struktury danych w czasie, gdy obiekty poruszają się kilka razy na sekundę?

Należy pamiętać, że siatka jest głęboką przestrzenną strukturą danych o jednym poziomie. Ten limit oznacza, że ​​nie jest w pełni skalowalny. W miarę, jak świat się powiększa, zwiększaj liczbę komórek, które musisz pokryć. W końcu sama liczba komórek staje się problemem wydajnościowym. Jednak w przypadku niektórych światów daje to ogromny wzrost wydajności w porównaniu z brakiem podziału przestrzennego.

Muszę odpowiedzieć na to pytanie, ponieważ nie mam punktów, aby komentować lub głosować. Dla 99% osób, które zadają to pytanie, ramką ograniczającą jest rozwiązanie opisane przez Ciarana. W skompilowanym języku odrzuci 100 000 nieistotnych jednostek w mgnieniu oka. Istnieje wiele kosztów ogólnych związanych z rozwiązaniami bez użycia siły; przy mniejszych liczbach (powiedzmy poniżej 1000) będą one droższe pod względem czasu przetwarzania niż sprawdzanie siły. I zajmą znacznie więcej czasu na programowanie.

Nie jestem pewien, co oznacza „bardzo duża liczba” w pytaniu lub co inni ludzie szukający tutaj odpowiedzi będą przez to rozumieć. Podejrzewam, że moje powyższe liczby są konserwatywne i można je pomnożyć przez 10; Osobiście jestem dość uprzedzony do technik brutalnej siły i jestem poważnie zirytowany tym, jak dobrze działają. Ale nie chciałbym, aby ktoś z, powiedzmy, 10 000 jednostek marnował czas na wymyślne rozwiązanie, gdy kilka szybkich linii kodu załatwi sprawę. W razie potrzeby zawsze mogą uzyskać fantazję.

Chciałbym również zauważyć, że sprawdzenie sfery ograniczającej wymaga zwielokrotnienia, gdy nie jest nią obwiednia. Mnożenie z natury zajmuje kilka razy więcej niż dodawanie i porównywanie. Musi istnieć pewna kombinacja języka, systemu operacyjnego i sprzętu, w której sprawdzanie sfery będzie szybsze niż sprawdzanie pola, ale w większości miejsc i czasów sprawdzanie pola musi być szybsze, nawet jeśli kula odrzuca kilka nieistotnych jednostek pudełko akceptuje. (A jeśli kula jest szybsza, bardzo prawdopodobne jest, że nowa wersja kompilatora / interpretera / optymalizatora to zmieni.)