2D Räumliche Partitionierungsalternativen zu räumlichen Hashes und Quadtrees

11

Ich habe versucht, einen räumlichen Partitionierungsalgorithmus in meinem Spiel zu implementieren, aber sowohl räumliche Hashes als auch Quadtrees sind nicht das, wonach ich suche.

Meine Levelgröße soll kein Limit haben (nur Int32-Limits). Ich benötige einen räumlichen Partitionierungsalgorithmus, der keine "Ebenenbreite" und keine "Ebenenhöhe" benötigt.

Ich habe viele sich bewegende physische Objekte. Der Algorithmus muss schnell genug sein, um mehr als 500 Objekte zu unterstützen.

Irgendeine Alternative?

c# collision-detection physics tree Vittorio Romeo
quelle

Antworten:

13

Dynamischer Baum

Box2D ist eine gut optimierte Engine, die von einem erfahrenen Physik- / Spielprogrammierer entwickelt wurde . Ursprünglich verwendete Box2D ein Hash-Raster, das eine feste Höhe und Breite erforderte.

Als Erin auf einen besseren Breitphasenalgorithmus umstieg, entschied er sich für Nathanael Pressons btDbvt. Dies ist die von Bullet Physics verwendete Breitphase. Erin modifizierte und optimierte den Algorithmus für 2d.

Sie können eine Übersicht auf Super-High-Level im Box2D- Handbuch lesen (§4.11 oder nach Dynamic Tree suchen).

Hier ist eine Ausnahme von der In- Code-Dokumentation (was sehr gut ist, wenn man bedenkt, dass es nicht Teil der öffentlichen API ist).

Eine dynamische AABB-Baum-Breitphase, inspiriert von Nathanael Pressons btDbvt. Ein dynamischer Baum ordnet Daten in einem Binärbaum an, um Abfragen wie Volumenabfragen und Ray Casts zu beschleunigen. Blätter sind Proxies mit einem AABB. In der Baumstruktur erweitern wir den Proxy-AABB um b2_fatAABBFactor, sodass der Proxy-AABB größer als das Client-Objekt ist. Dadurch kann sich das Client-Objekt um kleine Beträge bewegen, ohne eine Baumaktualisierung auszulösen.

Knoten sind gepoolt und verschiebbar, daher verwenden wir Knotenindizes anstelle von Zeigern.

Mein Verständnis des Algorithmus des dynamischen Baums ist dies. Der dynamische Baum ist die Kreuzung zwischen einem klassischen avl-Binärbaum und einem Quadtree. Der Endeffekt ist ein Quadtree, der nur jeden Knoten in zwei Hälften teilt und die Trennlinie nicht fest ist (die beiden Hälften sind nicht gleich groß wie ein Quad-Baum). AVL kommt ins Spiel, weil Quadree mit dynamischen Teilungen im Wesentlichen zu einer Liste (O (n) Suchgeschwindigkeit) ausarten kann. Die AVL wird verwendet, um Teilbäume neu auszugleichen, um die Suchgeschwindigkeit von O lg (N) sicherzustellen.

Das Beste ist, dass der Code MIT ist. Sie können ihn also kopieren / ableiten / schamlos stehlen / usw.

deft_code
quelle
Sieht ... komplex aus! Ich werde es mir aber ansehen. Jemand schlug mir vor, die Technik "Sweep and Prune" oder "Sort and Sweep" zu verwenden, aber ich konnte nichts über eine C # - oder .NET-Implementierung finden. Ich habe ein C ++ - Beispiel gefunden, aber es ist verwirrend und hat nicht funktioniert (ich habe trotzdem versucht, es zu implementieren). Denken Sie, dass SAP einfacher zu implementieren wäre? Gibt es eine .NET-Implementierung?
Vittorio Romeo
8

Dies kommt einer ähnlichen Frage sehr nahe, die hier bei Gamedev gestellt wird. Da Sie sich jedoch mit der Leistung und nicht mit der Speicherung von Dateien befassen, ist meine Antwort dort möglicherweise von größerem Nutzen für Sie. Der Vollständigkeit halber werde ich hier den Großteil davon aufnehmen, aber die ursprüngliche Antwort bietet etwas mehr Tiefe, wenn Sie sich damit befassen möchten.

Ich stieß auf ein ähnliches Problem und beschloss, eine eigene Struktur für den Umgang mit den Daten zu erstellen. Es basiert lose auf einem Quadtree, ist aber unendlich (mindestens so groß wie ein Int) in alle Richtungen erweiterbar. Es wurde entwickelt, um gitterbasierte Daten zu verarbeiten, die von einem zentralen Punkt aus erweitert wurden, ähnlich wie Minecraft es jetzt tut. Es ist platzsparend im Speicher und sehr schnell.

Mein Code kann gefunden werden hier . Der Code ist vollständig, getestet (Unit- und Load-Tests) und ziemlich optimiert. Das Innenleben ist jedoch noch nicht gut dokumentiert, aber alle öffentlichen Methoden sind so, dass es verwendbar sein sollte. Wenn jemand es ausprobieren möchte, kann er mich gerne mit Fragen oder Kommentaren kontaktieren.

dlras2
quelle
1

Wenn ich mit einer relativ kleinen Anzahl (<mehreren Tausend) kleinerer Objekte arbeite (die meisten Objekte sind nicht groß genug, um möglicherweise mit vielen anderen Objekten zu kollidieren), finde ich, dass eine einfache x-geordnete Liste von axial ausgerichteten Begrenzungsrahmen (AABBs) funktioniert ziemlich gut. Ich füge einfach die Objekte in eine Liste ein, dann sortiere ich jedes Bild nach dem Verschieben der Objekte schnell nach x-Werten und mache dann einen Durchgang durch die Liste, um die AABB-Nähe zu überprüfen. Für jedes Objekt überprüfe ich es mit den Objekten in der Liste, bis ich entweder das Ende der Liste oder ein Objekt erreiche, das außerhalb des x-Bereichs liegt. Das heißt, der x-Wert der linken Kante ist> x-Wert der rechten Kante des zu testenden Objekts. Grundsätzlich wird der Raum dynamisch in manchmal überlappende, AABB-x-breite Slices unterteilt. Es'

Shavais
quelle
0

Vielleicht ist der R-Tree-Algorithmus genau das, wonach Sie suchen.

Ich arbeite sehr gut für statische Geometrie, aber Sie können sie auch zum Verschieben von Objekten verwenden, indem Sie Objekte an ihren neuen Positionen entfernen und hinzufügen.

Faulenzen
quelle
Ich habe eine C # -Implementierung versucht, und die Leistung war viel zu schlecht, wenn "Objekte an ihrer neuen Position entfernt und hinzugefügt wurden".
Vittorio Romeo