Właściwa odpowiedź zależy trochę od rzeczywistej gry, którą projektujesz, a wybranie jednej z drugiej będzie naprawdę wymagało wdrożenia obu i przeprowadzenia profilowania, aby dowiedzieć się, która z nich jest bardziej wydajna pod względem czasu lub miejsca w konkretnej grze.
Wykrywanie siatki wydaje się dotyczyć tylko wykrywania kolizji między poruszającymi się obiektami a statycznym tłem. Największą zaletą tego jest to, że tło statyczne jest reprezentowane jako ciągła tablica pamięci, a każde wyszukiwanie kolizji to O (1) z dobrą lokalizacją, jeśli trzeba wykonać wiele odczytów (ponieważ jednostki pokrywają więcej niż jedną komórkę w siatce). Wadą, jeśli tło statyczne jest duże, jest to, że siatka może raczej marnować miejsce.
Jeśli zamiast tego reprezentujesz tło statyczne jako poczwórne, koszt pojedynczych wyszukiwań rośnie, ale ponieważ duże bloki tła zajmują niewielką ilość miejsca, wymagania pamięci spadają, a więc więcej tła może znajdować się w Pamięć podręczna. nawet jeśli potrzeba 10 razy więcej odczytów, aby wykonać wyszukiwanie w takiej strukturze, jeśli wszystko znajduje się w pamięci podręcznej, nadal będzie 10 razy szybsze niż pojedyncze wyszukiwanie z pominięciem pamięci podręcznej.
Gdybym miał wybór? Wybrałbym implementację gridu, ponieważ jest to głupie proste, lepiej spędzić czas na innych, bardziej interesujących problemach. Jeśli zauważę, że moja gra działa trochę wolniej, przeprowadzę profilowanie i zobaczę, co może pomóc. Jeśli wygląda na to, że gra spędza dużo czasu na wykrywaniu kolizji, wypróbuję inną implementację, na przykład quadree (po wyczerpaniu wszystkich łatwych poprawek) i sprawdzę, czy to pomogło.
Edycja: Nie mam pojęcia, w jaki sposób wykrywanie kolizji siatki odnosi się do wykrywania kolizji wielu mobilnych jednostek, ale zamiast tego odpowiem, w jaki sposób indeks przestrzenny (Quadtree) poprawia wydajność wykrywania w porównaniu z rozwiązaniem iteracyjnym. Naiwne (i zazwyczaj idealnie w porządku) rozwiązanie wygląda mniej więcej tak:
foreach actor in actorList:
foreach target in actorList:
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Ma to oczywiście wydajność wokół O (n ^ 2), przy n liczbie aktorów, którzy obecnie żyją w grze, w tym pociski, statki kosmiczne i kosmici. Może również obejmować małe przeszkody statyczne.
Działa to fantastycznie dobrze, o ile liczba takich przedmiotów jest stosunkowo niewielka, ale zaczyna wyglądać trochę słabo, gdy jest więcej niż kilkaset obiektów do sprawdzenia. 10 obiektów daje zaledwie 100 kontroli kolizji, 100 daje 10 000 kontroli. 1000 wyników w milion kontroli.
Indeks przestrzenny (podobnie jak drzewa czworokątne) może skutecznie wyliczyć elementy, które zbiera zgodnie z relacjami geometrycznymi. zmieniłoby to algorytm kolizji na coś takiego:
foreach actor in actorList:
foreach target in actorIndex.neighbors(actor.boundingbox):
if (actor != target) and actor.boundingbox intersects target.boundingbox:
actor.doCollision(target)
Wydajność tego (przy założeniu równomiernego rozkładu jednostek): zwykle wynosi O (n ^ 1,5 log (n)), ponieważ indeks zajmuje około porównań log (n) do przejścia, będzie około sqrt (n) sąsiadów do porównania i jest n aktorów do sprawdzenia. Jednak realistycznie liczba sąsiadów jest zawsze dość ograniczona, ponieważ jeśli dojdzie do kolizji, przez większość czasu jeden z obiektów jest usuwany lub odsunięty od kolizji. więc otrzymujesz tylko O (n log (n)). Dla 10 podmiotów robisz (około) 10 porównań, dla 100 robisz 200, dla 1000 robisz 3000.
Naprawdę sprytny indeks może nawet połączyć wyszukiwanie sąsiadów z iteracją zbiorczą i wykonać wywołanie zwrotne dla każdej przecinającej się jednostki. To da wydajność około O (n), ponieważ indeks jest skanowany raz, a nie pytany n razy.
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ć:
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.
źródło