Alternatywne partycjonowanie przestrzenne 2D do skrótów przestrzennych i czworokątów

11

Próbowałem zaimplementować algorytm partycjonowania przestrzennego w mojej grze, ale zarówno skróty przestrzenne, jak i kwadraty nie są tym, czego szukam.

Rozmiar mojego poziomu nie powinien mieć limitu (tylko limity Int32). Potrzebuję algorytmu podziału przestrzennego, który nie potrzebuje „szerokości poziomu” i „wysokości poziomu”.

Mam wiele ruchomych obiektów fizycznych. Potrzebuję algorytmu, aby był wystarczająco szybki, aby obsługiwać ponad 500 obiektów.

Jakaś alternatywa?

c# collision-detection physics tree Vittorio Romeo
źródło

Odpowiedzi:

13

Drzewo dynamiczne

Box2D to dobrze zoptymalizowany silnik zaprojektowany przez doświadczonego programistę fizyki / gier . Pierwotnie Box2D używał siatki mieszającej, która wymagała stałej wysokości i szerokości.

Kiedy Erin zaktualizował do lepszego algorytmu szerokofazowego, poszedł z btDbvt Nathanaela Pressona. Jest to faza szerokopasmowa używana przez Bullet Physics. Erin zmodyfikowała i zoptymalizowała algorytm dla 2d.

Możesz przeczytać przegląd bardzo wysokiego poziomu w instrukcji Box2D (§4.11 lub poszukać drzewa dynamicznego).

Oto wyjątek od dokumentacji w kodzie (co jest bardzo dobre, biorąc pod uwagę, że nie jest częścią publicznego API).

Dynamiczne drzewo AABB w szerokiej fazie, zainspirowane btDbvt Nathanaela Pressona. Dynamiczne drzewo porządkuje dane w drzewie binarnym w celu przyspieszenia zapytań, takich jak zapytania woluminów i rzutowania promieniowe. Liście są proxy z AABB. W drzewie rozwijamy proxy AABB o b2_fatAABBFactor, aby proxy AABB było większe niż obiekt klienta. Umożliwia to obiektowi klienta poruszanie się w niewielkich ilościach bez uruchamiania aktualizacji drzewa.

Węzły są pule i można je przenosić, dlatego używamy raczej wskaźników węzłów niż wskaźników.

Rozumiem algorytm drzewa dynamicznego. Drzewo dynamiczne to skrzyżowanie klasycznego drzewa binarnego avl z drzewem czwórkowym. Efektem końcowym jest poczwórne drzewo, które dzieli tylko każdy węzeł na pół, a linia podziału nie jest stała (dwie połówki nie są równej wielkości jak drzewo poczwórne). Pojawia się AVL, ponieważ quadree z dynamicznymi podziałami może zdegenerować się zasadniczo do prędkości wyszukiwania listy (O (n)). AVL służy do ponownego równoważenia poddrzewa, aby zapewnić szybkość wyszukiwania O lg (N).

Najlepszy ze wszystkich kodów jest MIT, więc kopiuj / wyprowadzaj / bezwstydnie kradnij / itp.

deft_code
źródło
Wygląda ... skomplikowane! Jednak przyjrzę się temu. Ktoś zasugerował mi użycie techniki „zamiatania i przycinania” lub „sortowania i zamiatania”, ale nie mogłem znaleźć niczego na temat implementacji C # lub .NET. Znalazłem przykład c ++, ale jest mylący i nie zadziałał (mimo to próbowałem go zaimplementować). Czy uważasz, że SAP byłby łatwiejszy do wdrożenia? Czy istnieje implementacja .NET?
Vittorio Romeo
8

Jest to bardzo podobne do podobnego pytania zadanego tutaj na Gamedevie, ale biorąc pod uwagę, że martwisz się wydajnością, a nie przechowywaniem plików, być może moja odpowiedź przyda ci się bardziej. Zamieszczę większość tego tutaj dla kompletności, ale oryginalna odpowiedź zapewnia nieco więcej głębi, jeśli chcesz się temu przyjrzeć.

Zetknąłem się z podobnym problemem i postanowiłem stworzyć własną strukturę do obsługi danych. Opiera się luźno na poczwórnym drzewie, ale ma nieskończoną (przynajmniej tak dużą jak Int) rozszerzalność we wszystkich kierunkach. Został zaprojektowany do obsługi danych opartych na siatce, które rozszerzyły się z centralnego punktu, podobnie jak teraz Minecraft. Zajmuje mało miejsca w pamięci i jest bardzo szybki.

Mój kod można znaleźć tutaj . Kod jest kompletny, przetestowany (testy jednostkowe i obciążenia) i dość zoptymalizowany. Wewnętrzne funkcjonowanie nie jest jednak jeszcze zbyt dobrze udokumentowane, ale wszystkie publiczne metody są, więc powinno być użyteczne. Jeśli ktoś zdecyduje się go wypróbować, skontaktuj się ze mną z pytaniami lub komentarzami.

dlras2
źródło
1

Podczas pracy ze stosunkowo niewielką liczbą (<kilka tysięcy) małych obiektów (większość obiektów nie jest wystarczająco duża, aby potencjalnie zderzyć się z wieloma innymi obiektami), stwierdzam, że działa prosta lista uporządkowana w osi X (AABB) całkiem dobrze. Po prostu umieszczam obiekty na liście, a następnie każdą ramkę po przeniesieniu obiektów, szybko sortuję listę według wartości x, a następnie wykonuję jedno przejście przez listę w poszukiwaniu bliskości AABB. Dla każdego obiektu sprawdzam go względem obiektów znajdujących się przed nim na liście, dopóki nie dojdę do końca listy lub obiektu, który jest poza zakresem x; to znaczy, że jego wartość x lewej krawędzi wynosi> x wartość prawej krawędzi testowanego obiektu. Zasadniczo dynamicznie dzieli przestrzeń na czasami nakładające się plastry wielkości AABB-x. To'

Shavais
źródło
0

Może algorytm r-drzewa jest tym, czego szukasz.

Pracuję naprawdę dobrze w przypadku geometrii statycznej, ale możesz jej również używać do przenoszenia obiektów, usuwając i dodając obiekty w ich nowych pozycjach.

Leniuchować
źródło
Wypróbowałem implementację w języku C #, a wydajność była o wiele za słaba, gdy „usuwano i dodawano obiekty w ich nowej pozycji”.
Vittorio Romeo