Przepraszam za wskrzeszenie starożytnego wątku, ale zwykłe stare siatki IMHO nie są używane wystarczająco często w takich przypadkach. Siatka ma wiele zalet, ponieważ wstawianie / usuwanie komórek jest tanie. Nie musisz zawracać sobie głowy uwalnianiem komórki, ponieważ siatka nie ma na celu optymalizacji pod kątem rzadkich reprezentacji. Mówię, że skróciwszy czas na zaznaczanie, wybrałem kilka elementów w starszej bazie kodu z ponad 1200 ms do 20 ms, po prostu zastępując drzewo czworokątne siatką. Szczerze mówiąc, to drzewo quad zostało naprawdę źle zaimplementowane, przechowując osobną tablicę dynamiczną dla węzła liścia dla elementów.
Innym, który uważam za niezwykle przydatny, jest to, że twoje klasyczne algorytmy rasteryzacji do rysowania kształtów mogą być używane do wyszukiwania w siatce. Na przykład możesz użyć rasteryzacji linii Bresenhama do wyszukiwania elementów przecinających się linii, rasteryzacji ze skanowaniem, aby znaleźć komórki przecinające wielokąt itp. Ponieważ dużo pracuję w przetwarzaniu obrazu, naprawdę fajnie jest móc używać dokładnie tego samego zoptymalizowany kod Używam do kreślenia pikseli na obrazie, gdy używam do wykrywania przecięć przeciwko ruchomym obiektom w siatce.
To powiedziawszy, aby siatka była wydajna, nie powinieneś potrzebować więcej niż 32-bitów na komórkę siatki. Powinieneś być w stanie przechowywać milion komórek w mniej niż 4 megabajtach. Każda komórka siatki może po prostu zindeksować pierwszy element w komórce, a pierwszy element w komórce może następnie zindeksować następny element w komórce. Jeśli przechowujesz coś w rodzaju pełnego pojemnika z każdą komórką, to szybko staje się wybuchowe w użyciu pamięci i przydziałach. Zamiast tego możesz po prostu zrobić:
struct Node
{
int32_t next;
...
};
struct Grid
{
vector<int32_t> cells;
vector<Node> nodes;
};
Tak jak:
Okej, więc do wad. Podchodzę do tego co prawda z uprzedzeniami i preferencjami do siatek, ale ich główną wadą jest to, że nie są rzadkie.
Dostęp do konkretnej komórki siatki z określoną współrzędną jest stały i nie wymaga schodzenia w dół drzewa, które jest tańsze, ale siatka jest gęsta, a nie rzadka, więc możesz w końcu sprawdzić więcej komórek niż to konieczne. W sytuacjach, w których dane są bardzo słabo rozmieszczone, siatka może wymagać sprawdzenia znacznie więcej, aby dowiedzieć się, które elementy przecinają się, np. Linia lub wypełniony wielokąt, prostokąt lub okrąg ograniczający. Siatka musi przechowywać tę 32-bitową komórkę, nawet jeśli jest całkowicie pusta, a gdy wykonujesz zapytanie o przecięcie kształtu, musisz sprawdzić puste komórki, jeśli przecinają twój kształt.
Główną zaletą quad-tree jest naturalnie jego zdolność do przechowywania rzadkich danych i dzielenia tylko tyle, ile potrzeba. To powiedziawszy, trudniej jest wdrożyć naprawdę dobrze, szczególnie jeśli masz rzeczy poruszające się wokół każdej klatki. Drzewo musi bardzo skutecznie dzielić i zwalniać węzły potomne w locie, w przeciwnym razie rozkłada się w gęstą siatkę marnującą narzuty w celu przechowywania łączy rodzic-> potomek. Bardzo możliwe jest zaimplementowanie wydajnego drzewa quad przy użyciu bardzo podobnych technik do tego, co opisałem powyżej dla siatki, ale ogólnie będzie to wymagać więcej czasu. A jeśli zrobisz to tak, jak ja w siatce, niekoniecznie będzie to również optymalne, ponieważ doprowadziłoby to do utraty zdolności do zagwarantowania, że wszystkie 4 potomki węzła quad-tree są przechowywane w sposób ciągły.
Również drzewo czworokątne i siatka nie wykonują wspaniałej pracy, jeśli masz wiele dużych elementów, które obejmują większą część całej sceny, ale przynajmniej siatka pozostaje płaska i nie dzieli się w tym przypadku na n-ty stopień . Drzewo czworokątne powinno przechowywać elementy w gałęziach, a nie tylko liście, aby rozsądnie obsługiwać takie przypadki, w przeciwnym razie będzie chciał podzielić się jak szalony i bardzo szybko obniżyć jakość. Jest więcej patologicznych przypadków, takich jak ten, z którymi musisz sobie poradzić za pomocą drzewa czworokątnego, jeśli chcesz, aby obsługiwał jak najszerszy zakres treści. Na przykład innym przypadkiem, który może naprawdę potknąć się o drzewo czworokątne, jest posiadanie mnóstwa przypadkowych elementów. W tym momencie niektórzy ludzie po prostu stosują limit głębokości dla swojego drzewa czworokątnego, aby zapobiec nieskończonemu podziałowi. Siatka ma apel, że wykonuje przyzwoitą robotę,
Stabilność i przewidywalność jest również korzystna w kontekście gry, ponieważ czasami niekoniecznie chcesz najszybszego możliwego rozwiązania dla zwykłego przypadku, jeśli czasami może prowadzić do czknięć w liczbie klatek w rzadkich przypadkach w porównaniu z rozwiązaniem, które jest dość szybkie dookoła, ale nigdy nie prowadzi do takich czkawek i utrzymuje płynność klatek płynną i przewidywalną. Siatka ma tego rodzaju ostatnią cechę.
Po tym wszystkim, naprawdę myślę, że to zależy od programisty. Mając takie rzeczy jak grid vs. quad-tree lub octree vs. kd-tree vs. BVH, głosuję na najbardziej płodnego programistę z rekordem w tworzeniu bardzo wydajnych rozwiązań bez względu na to, jakiej struktury danych używa. Na poziomie mikro jest też wiele, takich jak wielowątkowość, SIMD, układy pamięci przyjazne dla pamięci podręcznej i wzorce dostępu. Niektóre osoby mogą rozważyć te mikro, ale niekoniecznie mają one wpływ mikro. Takie rzeczy mogą mieć 100-krotną różnicę w zależności od jednego rozwiązania. Pomimo tego, jeśli otrzymałem osobiście kilka dni i powiedziano mi, że muszę wdrożyć strukturę danych, aby szybko przyspieszyć wykrywanie kolizji elementów poruszających się po każdej ramce, lepiej w tym krótkim czasie wdrożyłbym siatkę niż quad -drzewo.