Kiedy cztero-drzewo jest lepsze od haszowania przestrzennego?

Tworzę platformówkę 2D z dużą ilością obiektów jednocześnie. Wszystkie wykryto kolizję AABB. Najpierw próbowałem poczwórnie zmniejszyć liczbę obiektów do sprawdzenia, wypróbowałem kilka różnych konfiguracji, ale nie okazało się to tak skuteczne, jak potrzebowałem. Zaimplementowałem hash przestrzenny i jest on znacznie wydajniejszy, liczba obiektów do sprawdzenia dla każdej kolizji drastycznie spadła.

Czy istnieje przypadek, w którym wykrywanie kolizji 2D przy użyciu kwadratu jest lepsze niż mieszanie przestrzenne? Według moich testów wydaje się, że haszowanie przestrzenne zawsze kończy się na mniejszej liczbie obiektów do przetestowania pod kątem kolizji?

Nie skończyłem mierzenia czasu nad algorytmami, ale czy mieszanie jest po prostu bardzo drogie lub trudne do wdrożenia, gdy np. Kodujesz w C? Warto zauważyć, że piszę grę w javascript, w której masz skrót „za darmo”.

Oto porównanie, czy coś przeoczyłem? http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

Główną zaletą drzewa quad jest to, że pozwala ono bardzo szybko odrzucić całe grupy wiader.

Załóżmy na przykład, że mam drzewo quad z sześcioma poziomami. Na najniższym poziomie są to pudełka 32x32; 1024 pola zawierające ten dolny, najbardziej szczegółowy poziom. Dla porównania weźmiemy również pod uwagę „skrót przestrzenny” - płaską siatkę, która zawiera również pola 32 x 32, łącznie 1024 pola. (drzewo quad ma łącznie ponad 1024 pola, ponieważ zawiera również większe pola na wyższych poziomach)

Załóżmy, że w systemie nie ma kolidujących obiektów - wszystkie pudełka naszego drzewa quad i naszej płaskiej siatki są całkowicie puste.

Jeśli testujesz kolizje czegoś, co jest wystarczająco duże, aby jego obwiednia przecinała wszystkie te pola i używasz płaskiej siatki, musisz sprawdzić każde z tych 1024 pól, aby zobaczyć, czy coś w tym jest im.

Ale jeśli używasz zagnieżdżonego drzewa quad, najwyższy poziom może powiedzieć, że w systemie nie ma żadnych innych obiektów, więc wystarczy spojrzeć na to pojedyncze pole, aby wiedzieć, że nie znajdziesz kolizji głębiej w drzewie - możesz natychmiast przerwać testowanie.

Podobnie, jeśli obiekty istnieją tylko w niektórych regionach drzewa quad, drzewo quad w naturalny sposób poprowadzi twoje wyszukiwanie tylko potencjalnie odpowiednich pól, podczas gdy siatka wymaga sprawdzenia każdego pojedynczego przecinającego się pola, ponieważ nie masz możliwości wcześniejszego poznania które kwadraty siatki będą zawierać w nich obiekty. Jeśli znaczna część twojego drzewa quad jest pusta i wykonujesz duże, skomplikowane zapytania (powiedzmy, ogromne frustum z kamery zamiast małych, prostych prostokątów), może się okazać, że iterujesz w sumie o wiele mniej pól, jeśli wykonasz swoje testuje na czymś przy użyciu struktury drzewa zamiast płaskiej siatki. I to może mieć dużą różnicę.

Wszystko to nie oznacza, że ​​struktura drzewa jest zawsze właściwym wyborem. Płaskie siatki są idealne do sytuacji, którą masz na swoim przykładzie - gęste chmury obiektów rozmieszczone są prawie równomiernie na całym świecie, a my wykonujemy proste, niedrogie testy zderzeniowe. Absolutnie siatka będzie w takim przypadku optymalnym podejściem!