Jak efektywnie znajdować wszystkie byty w promieniu?


14

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?


7
Będziesz potrzebować pewnego rodzaju systemu partycjonowania przestrzennego: en.wikipedia.org/wiki/Space_partitioning
Tetrad

Odpowiedzi:


15

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).


Dziękuję za szczegółową odpowiedź. Tak, wydaje się proste Rozwiązanie gridowe jest dla mnie wystarczająco dobre.
OCyril

0

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.


0

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.


1
OP konkretnie powiedział, że chce uniknąć brutalnej siły, co dokładnie opisano w pierwszym akapicie. W jaki sposób, jak uważasz, czek z ogranicznikiem jest tańszy niż czek z ogranicznikiem ?! Po prostu źle.
notlesh

Tak, wiem, że chce uniknąć brutalnej siły, której można by uniknąć poprzez wprowadzenie hierarchicznej struktury danych do jego aplikacji. Ale to może być duży wysiłek. Jeśli jeszcze tego nie chce, może wypróbować podejście liniowe, które jest brutalną siłą, ale może nie działać tak źle, jeśli jego lista nie jest zbyt duża. Spróbuję edytować powyższy kod, aby umieścić w mojej funkcji 2D trywialną ramkę graniczną funkcję odrzucania. Nie sądzę, że się myliłem.
Ciaran

Link do GDnet jest zerwany, ale test kuli kanonicznej jest bardzo prosty, bardzo tani i nie rozgałęzia się:inside = (dot(p-p0, p-p0) <= r*r)
Lars Viklund

Zamiast tego wkleiłem powyższy kod. Wygląda na coś taniego w porównaniu do obwiedni.
Ciaran

1
@Ciaran Szczerze mówiąc, ten artykuł wydaje się naprawdę zły. Przede wszystkim nie wykonuje testów z realistycznymi danymi, ale używa ciągle tych samych wartości. Nie jest to coś, co można spotkać w prawdziwym scenariuszu. I nie, zgodnie z artykułem BB jest szybszy tylko wtedy, gdy nie ma kolizji (np. Sprawdzenie kończy się niepowodzeniem przy pierwszym ifstwierdzeniu). Również niezbyt realistyczne. Ale całkiem szczerze, jeśli zaczynasz optymalizować takie rzeczy, to zdecydowanie zaczynasz w złym miejscu.
bummzack

0

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.)


Chociaż w Twojej odpowiedzi nie ma nic złego, nie odpowiadasz na pytanie. Został specjalnie poproszony o podejście „bez przemocy”. Wydajesz się także powtarzać to, co już napisał Ciaran, i przeprowadziliśmy długą dyskusję na temat testów AABB vs. testy koła. Różnica wydajności jest po prostu nieistotna. Lepiej wybierz objętość graniczną, która pasuje do większości twoich kandydatów na kolizję, ponieważ zmniejszy to liczbę rzeczywistych testów w fazie wąskiej .. co będzie miało większy wpływ na ogólną wydajność.
bummzack
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.