QuadTree: przechowujesz tylko punkty lub regiony?

Pracuję nad quadtree, aby śledzić ruchome obiekty w celu wykrycia kolizji. Każdy obiekt ma kształt ograniczający, powiedzmy, że wszystkie są okręgami. (Jest to gra 2D z góry)

Nie jestem pewien, czy zapisać tylko pozycję każdego obiektu, czy całego ograniczającego kształtu.

W przypadku pracy z punktami wstawianie i dzielenie jest łatwe, ponieważ obiekty nigdy nie będą obejmować wielu węzłów. Z drugiej strony zapytanie zbliżeniowe dla obiektu może pomijać kolizje, ponieważ nie bierze ono pod uwagę wymiarów obiektów. Jak obliczyć region zapytania, gdy masz tylko punkty?

Jeśli pracujesz z regionami, jak obsługiwać obiekt obejmujący wiele węzłów? Czy powinien zostać wstawiony do najbliższego węzła nadrzędnego, który całkowicie go zawiera, nawet jeśli przekracza to pojemność węzła?

Dzięki.

Jeśli przechowujesz rozszerzone obiekty (regiony) w czterokrzewie, do obiektu należy się odwoływać ze wszystkich dotkniętych węzłów liści. Nie starałbym się znaleźć najmniejszego przodka i przechowywać go tam, ponieważ wtedy np. Mały obiekt, który przekroczy granicę wysokiego poziomu, znajdzie się w bardzo wysokim węźle i musi zostać przetestowany na wszystko inne w tym dużym , węzeł wysokiego poziomu podczas wykonywania zapytań kolizyjnych itp.

Trzeba jednak również zachować ostrożność, ponieważ do dużych obiektów mogą odwoływać się odniesienia z wielu węzłów, co powoduje, że ich aktualizacja jest kosztowna, gdy się poruszają, i powoduje, że są one wielokrotnie sprawdzane pod kątem kolizji itp. W zależności od przypadku użycia być może warto zastosować jakąś heurystykę do przechowywania dużych obiektów na wyższym poziomie w drzewie, ale to skomplikowałoby algorytmy, więc prawdopodobnie nie zawracam sobie głowy, chyba że ustalisz, że to naprawdę problem z wydajnością w twoim konkretnym przypadku.

Podobnie, aby wykonać zapytanie o region, zapytanie powinno obejmować wszystkie węzły liści dotknięte przez region, którego dotyczy zapytanie.

Zasadniczo używają tego samego algorytmu, który rozpoczyna się od regionu i przepycha go w dół drzewa, aby znaleźć dotknięte węzły liści. Jest to przejście przez głębokość, ale w każdym węźle można przycinać wszystkie dzieci, które nie dotykają regionu. Musisz utrzymywać stos, aby śledzić miejsce, w którym przebywasz.

Musisz przechowywać go w najmniejszym węźle, który całkowicie go zawiera - nawet jeśli przekracza to pojemność (użyj pojemnika o zmiennym rozmiarze).

Dodałbym to jako komentarz w odpowiedzi na odpowiedź @ Natana Reeda, z wyjątkiem tego, że jest zbyt duży, aby być komentarzem, i być może w każdym razie zasługuje na osobną odpowiedź.

Robiliśmy dokładnie to, co zaproponowano w jego odpowiedzi, i faktycznie mieliśmy komentarz w źródle prowadzącym do tej strony. W przeważającej części działało to bardzo dobrze, z tym wyjątkiem, że raz na dwa lub trzy miesiące losowo traciliśmy serwer, który przestał odpowiadać z powodu ogromnego czasu trwania zapytań.

Przyczyna problemu zwróciła moją uwagę podczas sprawdzania wydajności, aby dowiedzieć się, co było przyczyną tego problemu. Jest to prawdopodobnie tylko problem, jeśli pozwalasz na nakładanie się obiektów. W naszej grze tak się dzieje, aw najgorszym przypadku może to czasami doprowadzić do gwałtownego wzrostu wydajności.

Mieliśmy jedną skrzynkę, w której około 100 obiektów, wszystkie z ograniczającymi dyskami, było skupionych w bardzo bliskiej odległości. Doprowadziło to do problemu bardzo głębokiego skoku w drzewie, ponieważ doszliśmy do punktu, w którym obiekty były większe niż obszar objęty przez quadtree węzły, więc każdy nowy obiekt pojawiał się w wielu węzłach, co prowadzi do masywnego podziału drzewo, dzięki czemu problem wymyka się spod kontroli.

Wynika to z tego, że jeśli pozwalasz na nakładanie się obszarów obiektów, uważnie obserwuj rzeczy, jeśli otrzymujesz ciasne skupiska obiektów, aby mieć pewność, że twoje drzewo nie będzie zbyt głębokie.

Rozwiązaniem, które obecnie badam, jest przechowywanie obiektów jako punktów, a następnie podczas wyszukiwania zwiększyć granice prostokąta wyszukiwania o maksymalny promień przechowywany w drzewie. To powinno dla nas zadziałać, ponieważ drzewo jest wyszukiwaniem pierwszego przejścia, a następnie przeprowadzamy sprawdzanie zasięgu w oparciu o prawdziwe koło, a także kilka innych kryteriów, aby dodatkowe fałszywe alarmy zostały odfiltrowane.

Rzeczywisty przebieg może się różnić.