Ich habe seit Ewigkeiten nach einer Quadtree / Quadtree-Knotenimplementierung im Netz gesucht. Es gibt einige grundlegende Dinge, aber nichts, womit ich es wirklich ein Spiel benutzen könnte.
Mein Zweck ist es, Objekte in einem Spiel zu speichern, um Dinge wie Kollisionserkennung zu verarbeiten. Ich bin nicht 100% sicher, dass ein Quadtree die beste zu verwendende Datenstruktur ist, aber von dem, was ich gelesen habe, ist es. Ich habe bereits einen Rot-Schwarz-Baum programmiert, aber ich weiß nicht wirklich, ob die Leistung für mein Spiel gut genug wäre (das wird ein Abenteuer-3rd-Person-Spiel wie Ankh sein).
Wie würde ich eine einfache, aber vollständige Quadtree-Klasse (oder Octree) in C ++ schreiben? Wie würden Sie den Quad-Baum für Kollisionen verwenden?
Quadtrees werden verwendet, wenn Sie nur Dinge speichern müssen, die effektiv in einem Flugzeug liegen. Wie Einheiten in einem klassischen RTS, wo sie alle auf dem Boden oder nur ein wenig darüber sind. Im Prinzip hat jeder Knoten Links zu 4 Kindern, die den Raum des Knotens in gleichmäßig verteilte Viertel aufteilen.
Octrees machen das selbe, aber in allen drei Dimensionen und nicht nur in zweien, und daher haben sie acht Kindknoten und partitionieren den Raum in Achteln. Sie sollten verwendet werden, wenn die Spielobjekte gleichmäßiger auf alle drei Dimensionen verteilt sind.
Wenn Sie nach einem binären Baum - wie einem rot-schwarzen Baum - suchen, dann möchten Sie eine Datenstruktur verwenden, die als Binärraum-Partitionierungsbaum (BSP-Baum) oder eine Version davon, KD-Baum genannt, bezeichnet wird. Diese partitionieren den Raum durch eine Ebene in zwei Hälften, im KD-Baum sind die Ebenen orthogonal (auf den XZ-, XY-, ZY-Achsen) und manchmal funktioniert es besser in einer 3D-Szene. BSP-Bäume unterteilen die Szene mit Hilfe von Ebenen in beliebiger Ausrichtung, aber sie können sehr nützlich sein, und sie wurden so weit zurück verwendet wie Doom.
Jetzt, da du den Spielbereich partitioniert hast, musst du nicht mehr jede Spieleinheit gegen jede andere Spieleinheit testen, um zu sehen, ob sie kollidieren, was bestenfalls ein O (n ^ 2) -Algorithmus ist. Stattdessen fragen Sie die Datenstruktur ab, um die Spielobjekte innerhalb einer Unterregion des Spielraums zurückzugeben, und führen nur eine Kollisionserkennung für diese Knoten gegeneinander durch.
Dies bedeutet, dass die Kollisionserkennung für alle Spieleinheiten im schlimmsten Fall eine Operation n O (nlogn) sein sollte.
Ein paar zusätzliche Dinge, auf die Sie achten sollten:
Ein rot-schwarzer Baum ist kein räumlicher Index; Es kann nur nach einem einzelnen Ordinalschlüssel sortiert werden. Ein Quadtree ist (für zwei Dimensionen) ein räumlicher Index, der schnelles Suchen und Entfernen von Punkten ermöglicht. Ein Octree macht dasselbe für drei Dimensionen.
Der Grund für die Verwendung eines Quadtree ist, dass Sie dann auf x- und y-Koordinaten, einen Octree auf x, y und z aufteilen können, wodurch die Kollisionserkennung trivial wird.
Quadtree: Wenn ein Element nicht im oberen Teil ist, kollidiert es nicht mit einem nach oben, unten oder rechts.
Es ist eine sehr einfache Klasse, deshalb verstehe ich nicht, was Sie in Implementierungen, die Sie gefunden haben, vermissen.
Ich würde solch eine Klasse nicht schreiben, ich würde sie mir einfach aus einem Projekt mit einer passenden Lizenz ausleihen.
Ich empfehle Ihnen wärmstens, eine Rendering-Engine zu verwenden, zum Beispiel Ogre3D. Soweit ich weiß, unterstützt es Octrees für das Szenenmanagement. Aber Sie können die Octree-basierte Klasse beliebig erweitern. Ich habe das Zeug programmiert, das ich selbst brauchte, aber für komplexe Projekte ist es einfach nicht der richtige Weg.
Bäume im Allgemeinen sind insofern problematisch, als jeder eingefügte Gegenstand auf einer Grenze liegen kann, und alle Methoden, mit dieser Situation umzugehen, sind ziemlich unbefriedigend.
Wahrscheinlich werden Sie Ihre Objekte in bewegliche und statische Objekte sortieren und alles, was sich in einem bestimmten Rahmen gegen die statischen Objekte bewegt hat, überprüfen.
BSP-Bäume sind die akzeptierte Lösung für statische Geometrie (Grenzfälle, die durch Aufteilen des Objekts in zwei Teile behandelt werden), um etwas wie Sort and Sweep (auch bekannt als Sweep und Prune) zu versuchen.
Gerade jetzt ist STANN die beste Open-Source-Implementierung.