Raumunterteilung mit Quadtrees: bewegliche Objekte, welche Art von Quadtree?

Hallo,

ich frage mich gerade, welche Art von Quadtree für meinen Anwendungsfall am besten ist. Ich habe Objekte, die sich fortbewegen können, die allermeisten Objekte jedoch befinden sich an einer festen Position. Welche Art von Quadtree ist für mich geeignet? Meine aktuellen Überlegungen betreffen die Bucket-Größe (oft nimmt man scheinbar 1) und die Fragestellung, ob ich den Raum in gleich große Kinder aufteilen (Region-Quadtree) soll oder nach Aufenthaltsort der Objekte (Point-Quadtree).

Die regelmäßige Aufteilung hat den Vorteil, dass sie leicht und effizient durchzuführen ist. Man kann allerdings oft beobachten, dass wegen nur eines Objekts gleich eine vielfache Teilung eines größeren Knoten auftreten kann. Insbesondere sich bewegende Objekte, die gerade erst in einen Bereich kommen, stehen ja ziemlich am Rand und dürften eine hohe Aufteilung verursachen.
Die unregelmäßige Aufteilung an den Koordinaten des Objekts hat aber bei sich bewegenden Objekten irgendwie auch Probleme zur Folge, weil man dann die Aufteilung verschieben müsste.

Soll ich verschiedene Trees für diese zwei Kategorien von Objekten machen? Oder soll ich, falls ich regelmäßige Aufteilung nehme, im selben Baum für sich bewegende Objekte nur bis zu einer bestimmten (größeren) Mindestgröße aufteilen? Oder für sich bewegende Objekte eine größere Bucket-Größe wählen?

Ich muss am Ende in diesem Baum effizient nach benachbarten Objekte innerhalb eines gegeben Radius suchen können, außerdem möchte ich anhand der verschiedenen Ebenen des Baums die Wegfindung in verschieden groben Stufen ablaufen lassen.

rapso

es würde sich anbieten deinen anwendungsfall zu nennen, wenn du dafür eine empfehlung haben möchtest.

Naja ich habe die Anforderungen wie am Ende des Postings erwähnt. Es geht um ein Echtzeit-Strategiespiel, bei dem mir jetzt vor allem die beweglichen Objekte Sorgen machen. Ich muss Objekte in der Nähe von anderen Objekten schnell finden können und Objekte bestimmen können, die auf dem geraden Weg von A nach B im Weg liegen könnten. Mein Problem mit beweglichen Objekten ist, dass der Quadtree wahrscheinlich recht häufig umorganisiert werden müsste, zusammenfassen von Kinder oder wieder aufteilen...

Es gibt viele Arten von Quadtrees aber irgendwie schreibt niemand so richtig, welcher was besser kann. Für manche Quellen scheint es sogar nur "den" Quadtree zu geben, der einen Knoten in gleich große Quadrate teilt. Das hilft mir bei der Entscheidung dann auch nicht. Primär interessiert mich jetzt mal, ob ich einen Knoten beim splitten in 4 gleich große Kinder aufteilen sollte oder entlang eines Teilpunkts, wie ich eine möglichst geringe Tiefe erreiche, ohne häufig umorganisieren zu müssen. Was genau musst du noch wissen?

rapso

für deinen fall sind trees suboptimal, die sollte man benutzen für statische dinge, zum auffinden von nahen objekten (besondesr wenn man mit dem radius arbeitet) eignen sich KD-Trees.

für dynamische dinge nimmt man sweep&prune.

Ich möchte in meinem nächsten Spiel im Gegensatz zum letzten wirklich große Karten ermöglichen.

Der größte Teil der Objekte ist unbeweglich und steht in einem relativ groben Raster (128 mal die Größe des kleinstmöglichen Ortsunterschieds), das auch die kleinste Raumunterteilungs-Einheit vorgibt. Statische Objekte werden so zwischen 3x3 und 10x10 dieser Rasterpunkte belegen. Ich habe mich bei den statischen Objekten jetzt erstmal für das scheinbar einfachste entschieden. Wahrscheinlich werde ich einen einfachen Quadtree für die statischen Objekte verwenden, der den Raum regelmäßig teilt und wo die Tiefe eines Blatts maximal so weit herunter geht, dass eine Rasterzelle ausgefüllt wird.

Wenn die Höhe wegen dem Quadtree um 2 Level größer ist als beim vielleicht optimaleren Kd-Tree, werd ich das erstmal ignorieren, Hauptsache O(log n) in Bezug auf die Kartengröße. Wenn es blöd läuft, muss ich ihn halt doch durch eine andere Datenstruktur ersetzen, wenn es ausreicht, hätte ich mir umsonst zu viel Aufwand gemacht.

Danke für den Hinweis auf Sweep & Prune. Ich werde wohl tatsächlich getrennte Datenstrukturen für sich bewegende und für unbewegliche Objekte nehmen müssen und mit den beweglichen wird's vielleicht noch happig. (Am besten, ich bau in mein Spiel keine Einheiten ein, die sich fortbewegen können )

rapso

für das auffinden möglichst naher objekte zu einem beliebigen punkt im raum ist KDtree meist optimal, aber so wie sich das bei dir anhört wäre ein reguläres grid eventuell besser, nicht sonderlich hoch aufgelöst, und in dem grid dann wenn nötig, dann die aufteilung in nen tree.

wobei sich immer die frage stellt, wofür man es verwendet, pathfinding, collisions, frustumculling mögen zwar den anschein auf relativ gleiche anforderungen intendieren, sind aber dann doch vollkommen anders.

bei pathfinding verwendet kaum jemand trees, wenn, dann 2 oder 3 ebenen an grids, weil es viel zu aufwendig wäre durch ne hierarhchy z.b. A* durchzuführen, und ebenfalls wohl langsam.

bei collisiondetection zwischen dynamischen objekten verwendet man hingegen coherenzalgorithmen, weil man n gegen n testen müßte und trees wären dafür suboptimal, denn entweder müßte man sie bis zur letzten rekursion ausbauen, das wäre dann also ein sehr aufwendiges grid, oder man baut den baum einmal und hat dann das problem, das alles zusammenbricht, wenn mal viele objekte an einer stelle sind an der es eine große zelle gibt, oder man baut den baum halt die ganze zeit, aber das würde sehr viel zeit fressen, da ist sweep&prune mit O(n) von der laufzeit her wohl das beste.

bei frustumculling wiederrum gibt es meist nur ein objekt das gegen alle anderen testet, da ist ein tree recht gut, weil durch einfache entscheidungen oft sehr viele objekte als "in" bzw "out" erkannt werden können. die wenigsten sind dann genau auf der edge.

bei pathfinding geht man oft davon aus, dass objekte die größe eines gridpunkts haben, bei collision oft die größe des convexen bounding körpers und bei frustum oft von der AABBox.

du mußt also schon abwegen wofür du es nutzt und was wohl das zeitkritischte ist bzw wo du abstriche machen kannst.

Cpp_Junky

Hab auch mal angefangen eine RTS Engine zu basteln, für klassische 2D Spiele wie die ersten C&C Teile z.B. Ich habe dort ein riesen Raster mit Zellen der Größe des kleinsten Tiles angelegt und diese wiederrum in "Cluster" unterteilt die jeweils so gross sind wie ein Bildausschnitt und einzelne Zellen beinhalten. Das ist sehr speicher-intensiv bei grossen Karten, aber es vereinfacht Dinge wie Collision-Detection und Pathfinding sehr. Weil alle Zellen und Cluster gleich gross sind, kann man anhand der Objektposition die dazugehörige Zelle und den Cluster ohne Probleme errechnen und dann mit den dort "angemeldeten" Objekten wasauchimmer anstellen.

Cpp_Junky schrieb:

Hab auch mal angefangen eine RTS Engine zu basteln, für klassische 2D Spiele wie die ersten C&C Teile z.B. Ich habe dort ein riesen Raster mit Zellen der Größe des kleinsten Tiles angelegt und diese wiederrum in "Cluster" unterteilt die jeweils so gross sind wie ein Bildausschnitt und einzelne Zellen beinhalten. Das ist sehr speicher-intensiv bei grossen Karten, aber es vereinfacht Dinge wie Collision-Detection und Pathfinding sehr. Weil alle Zellen und Cluster gleich gross sind, kann man anhand der Objektposition die dazugehörige Zelle und den Cluster ohne Probleme errechnen und dann mit den dort "angemeldeten" Objekten wasauchimmer anstellen.

rapso schrieb:

aber so wie sich das bei dir anhört wäre ein reguläres grid eventuell besser, nicht sonderlich hoch aufgelöst, und in dem grid dann wenn nötig, dann die aufteilung in nen tree.

Das hab ich in meinem jetzigen Spiel auch (EDIT: also die regelmäßige Aufteilung in nicht zu große Gebiete). Das Problem ist, dass ich große unbegehbare Gebiete habe und vor allem jetzt plane zu haben (wo es also wirklich nur ein paar verwinkelte Pfade gibt) und da ist es glaub ich extrem unweich, alles zu durchzurastern. Im Grunde möchte ich nur eine etwas intelligentere Alternative und ich werde jetzt mal schaun, was der Quadtree mir bringt.

Ich habe auch meine Anforderungen noch ein bisschen modifiziert: Ich möchte den Graphen für die Wegfindung billig anpassen können, wenn man ein Haus baut oder einen Baum fällt. Ich denk mir, dass ich mit den Quadtrees einige Verbindungen vor-aussuchen kann zum neu überprüfen - hoffe ich. Jedenfalls kann ich mir das beim Kd noch weniger vorstellen.

Für bewegliche Einheiten nehme ich mir aber auf jeden Fall sweep&prune vor, das sieht schon gut aus.

Danke für alle Informationen schon mal.