W pełni dynamiczne drzewo KD vs. Quadtree?

Pracując nad moją grą, jestem w punkcie, w którym muszę śledzić wszystkie jednostki na świecie, aby móc wykonywać kontrole w walce z najbliższymi sąsiadami. Jest to gra podobna do RTS, w której poruszają się potencjalnie tysiące małych automatycznych jednostek.

Patrzyłem na KD-Drzewa i Quadtrees (szczególnie Point Quadtrees). Nadal próbuję poznać szczegóły ich działania, ale jak dotąd Point Quadtrees mają dla mnie jak najbardziej sens. Mam jednak wrażenie, że drzewka KD są szybsze do przeszukiwania, co jest ważne przy liczbie punktów, które będę mieć na drzewie.

Z drugiej strony w moim przypadku zamierzam śledzić ogromną liczbę jednostek, które zawsze się poruszają. Ich poszczególne klatki będą zawsze różne. Czterokąty są najwyraźniej szybsze do zrównoważenia niż KD-Drzewa, ale nie wiem, czy ma to zastosowanie, gdy przywracasz równowagę w każdym punkcie drzewa.

Zastanawiam się, czy byłoby lepiej w tym przypadku po prostu zeskrobać drzewo w każdej ramce i odbudować go od zera, zamiast próbować przywracać równowagę w każdym punkcie drzewa? Jeśli przywrócenie równowagi w Quadtree jest szybsze, czy oznacza to również, że można szybciej budować od zera? Jeśli tak, może to być ważniejsze dla wydajności niż szybkość wyszukiwania KD-Tree, w zależności od tego, jak ciężko jest stworzyć drzewo, ale nie wiem ...

Szczerze mówiąc, drzewa KD zdecydowanie nie są wystarczająco dynamiczne. Przeniesienie kilku jednostek może łatwo wymagać odbudowania całego drzewa KD. Dodatkowo drzewo KD jest bardzo wydajne w przypadku zapytań, ale nie tak bardzo w przypadku wyszukiwania sąsiadów.

Poczwórne drzewo jest z czasem bardziej elastyczne, ponieważ modyfikacje są przechowywane lokalnie. Wadą jest to, że jeśli masz wiele jednostek w jednym miejscu, które często się poruszają, może się za bardzo dzielić i wymagać wielu aktualizacji ze względu na ruch jednostek. Możesz ustawić próg, poniżej którego nie mogą wystąpić żadne poddziały. Ale uwaga, oznacza to, że wiele jednostek może potencjalnie znajdować się na tym samym placu.

Jeśli jednak chcesz znaleźć wszystkie jednostki w stałym promieniu r , nie potrzebujesz od razu drzewa czwórkowego i drzewa kd. Możesz po prostu utworzyć tablicę 2D komórek o boku ri ułożyć jednostki w każdej komórce zgodnie z ich pozycją. W ten sposób zawsze masz co najmniej 9 komórek do przeszukania. Tylko jeśli twoja mapa jest ogromna , taka siatka byłaby zbyt duża do wdrożenia.

Istnieją jeszcze dwie zupełnie różne struktury, o których nie mówiliśmy: hierarchiczne AABB i lokalna tabela skrótów. Jeśli pochodzenie każdego hierarchicznego AABB jest opisane w stosunku do nadrzędnego AABB, ma to tę zaletę, że jeśli duża grupa jednostek zachowuje swoją formację, nie trzeba aktualizować mniejszych AABB, ponieważ zachowują te same pozycje względne. Oczywiście obracanie formacji może powodować wiele aktualizacji, w takim przypadku użycie innych ograniczających objętości, takich jak kule lub zorientowane ramki ograniczające (OBB), może być bardziej wydajne.

Lokalne tabele skrótów skutecznie dają przybliżone rozwiązania, więc nie zawracałbym sobie nimi głowy.

Co bym zrobił ? Prawdopodobnie zacznę od prostej siatki, a kiedy będę go potrzebować, zaktualizuję go do czterokąta, a jeśli będę go potrzebować, połączę go z ograniczoną hierarchią woluminów poniżej pewnego progu: kwadraty działają dobrze na dużym skali, względne objętości graniczne działają dobrze na małą skalę. Robi to stopniowo, nie muszę spędzać godziny od początku, aby uzyskać najlepszą strukturę danych natychmiast .

Sugestie Lærne'a są świetne, ale sugerowałbym także dynamiczne drzewo objętości AABB. Koncepcyjnie dynamiczne drzewo woluminów ograniczających zachowuje zrównoważone drzewo węzłów, które można w dowolnym momencie zapytać o bliskie elementy, przekazując AABB i wyszukując nakładającą się parę. Drzewo nie jest przebudowywane w każdej ramce. Zamiast tego AABB każdego węzła jest nieco zawyżone po umieszczeniu w drzewie, a drzewo jest odbudowywane tylko wtedy, gdy rzeczywisty AABB węzła nie jest już zawarty w zawyżonym AABB. Używam go w silniku fizyki i działa świetnie.

Kod źródłowy Box2D ma świetną implementację.

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h

Oto dobry przegląd ich realizacji:

http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/