Volldynamischer KD-Tree vs. Quadtree?

Wenn ich an meinem Spiel arbeite, bin ich an dem Punkt angelangt, an dem ich alle Einheiten der Welt verfolgen muss, damit ich die nächsten Nachbarn für den Kampf überprüfen kann. Dies ist ein RTS-ähnliches Spiel, bei dem sich möglicherweise Tausende kleiner automatisierter Einheiten bewegen.

Ich habe mich mit KD-Bäumen und Quadtrees (insbesondere Point Quadtrees) befasst. Ich versuche immer noch, die Details ihrer Funktionsweise zu erfahren, aber bisher sind Point Quadtrees für mich am sinnvollsten. Ich habe jedoch den Eindruck, dass KD-Bäume schneller zu suchen sind, was bei der Anzahl der Punkte, die ich im Baum habe, wichtig ist.

Andererseits werde ich in meinem Fall eine große Anzahl von Einheiten verfolgen, die sich immer bewegen. Von Bild zu Bild sind ihre Positionen immer unterschiedlich. Quadtrees lassen sich anscheinend schneller neu ausgleichen als KD-Bäume, aber ich weiß nicht, ob dies zutrifft, wenn Sie jeden Punkt im Baum neu ausgleichen .

Ich frage mich, ob es in diesem Fall besser wäre, den Baum in jedem Frame zu verschrotten und von Grund auf neu zu erstellen, als zu versuchen, jeden einzelnen Punkt im Baum neu auszugleichen. Wenn ein Quadtree schneller neu ausbalanciert werden kann, bedeutet das auch, dass er schneller von Grund auf neu erstellt werden kann? Wenn ja, ist dies möglicherweise wichtiger für die Leistung als die Suchgeschwindigkeit des KD-Tree, je nachdem, wie aufwändig das Erstellen des Baums ist, aber ich weiß nicht ...

KD-Bäume sind definitiv nicht dynamisch genug, um ehrlich betrachtet zu werden. Wenn Sie einige Einheiten verschieben, müssen Sie möglicherweise den gesamten KD-Baum neu erstellen. Außerdem ist ein KD-Baum sehr effizient für Abfragen, aber weniger für die Suche nach Nachbarn.

Ein Quadtree ist im Laufe der Zeit flexibler, da die Änderungen lokaler beibehalten werden. Der Nachteil ist, dass wenn Sie viele Einheiten an einem Ort haben, die sich häufig bewegen, diese möglicherweise zu stark unterteilt werden und aufgrund der Bewegung der Einheiten viele Aktualisierungen erforderlich sind. Sie können einen Schwellenwert festlegen, unter dem keine Unterteilungen auftreten können. Beachten Sie jedoch, dass sich möglicherweise viele Einheiten im selben Blattquadrat befinden.

Wenn Sie jedoch nur alle Einheiten innerhalb eines konstanten Radius r finden möchten, benötigen Sie nicht sofort Quadtree und KD-Tree. Sie können einfach ein 2D-Array von Zellen mit der Seite r erstellen und Ihre Einheiten in jeder Zelle entsprechend ihrer Position stapeln. Auf diese Weise müssen Sie im schlimmsten Fall immer 9 Zellen durchsuchen. Nur wenn Ihre Karte riesig ist , wäre ein solches Raster zu groß, um es zu implementieren.

Es gibt zwei völlig unterschiedliche Strukturen, von denen wir nicht gesprochen haben: hierarchische AABBs und lokal sensible Hash-Tabellen. Wenn der Ursprung jedes hierarchischen AABB relativ zum übergeordneten AABB beschrieben wird, hat dies den Vorteil, dass Sie die kleineren AABBs nicht aktualisieren müssen, wenn eine große Gruppe von Einheiten ihre Formation beibehält, da sie dieselben relativen Positionen beibehalten. Natürlich kann das Drehen der Formation viele Aktualisierungen verursachen. In diesem Fall kann die Verwendung anderer Begrenzungsvolumina wie Kugeln oder orientierter Begrenzungsrahmen (OBB) effizienter sein.

Lokal sensible Hash-Tabellen liefern nur effiziente Näherungslösungen, sodass ich mich nicht darum kümmern würde.

Was würde ich tun ? Ich würde wahrscheinlich mit einem einfachen Raster beginnen, und wenn ich es brauche, würde ich es auf einen Quadtree aktualisieren und wenn ich es brauche, werde ich es mit einer begrenzten Volumenhierarchie unter einem bestimmten Schwellenwert kombinieren: Quadtrees funktionieren im Großen und Ganzen gut Im Maßstab funktionieren relative Begrenzungsvolumina im kleinen Maßstab gut. Wenn ich es schrittweise mache, muss ich nicht von Anfang an eine Stunde aufwenden, um sofort die beste Datenstruktur zu erhalten .

Lærnes Vorschläge sind großartig, aber ich würde auch einen dynamischen Begrenzungsvolumenbaum von AABBs vorschlagen. Konzeptionell behält der dynamische Begrenzungsvolumenbaum einen ausgeglichenen Knotenbaum bei, der jederzeit nach nahen Elementen abgefragt werden kann, indem ein AABB übergeben und ein überlappendes Paar abgerufen wird. Der Baum wird nicht in jedem Frame neu erstellt. Stattdessen wird der AABB jedes Knotens beim Einfügen in den Baum leicht aufgeblasen, und der Baum wird nur dann neu erstellt, wenn der tatsächliche AABB des Knotens nicht mehr im aufgeblasenen AABB enthalten ist. Ich benutze es in meiner Physik-Engine und es funktioniert großartig.

Der Box2D-Quellcode hat eine großartige Implementierung.

https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h

Hier ist ein guter Überblick über ihre Implementierung:

http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/