2D Kollisionen und Quadtrees?

Ich hab die letzten Stunden damit verbracht Informationen über Quadtrees zu finden.
Hab auch interessante Artikel gefunden:
http://archive.gamedev.net/reference/programming/features/quadtrees/
http://www.kyleschouviller.com/wsuxna/quadtree-source-included/

Das Grundprinzip ist mir bekannt - man teilt den Raum in kleinere auf um so eine schnellere Kollisionsentdeckung zu haben.
Okay, mal ein Gedankenspiel:

Meine Basisklasse für mathematische Operationen bei Sprites ist NLBoundingBox.
Die enthält die Daten für das Sprite und auch einige Funktionen zur Kollissionsabfrage wie isPointInside() und intersects().
Diesen "Teil" vom Sprite würde ich natürlich in den Tree werfen.
Wie genau geht das nun von statten?
Mein Gedankenspiel:
Ein "Masterliste" enthält alle Objekte, die getestet werden sollen.
Ich sortiere in der Update-Funktionen nun alle Objekte in die Leafs ein, wo sie hingehören bzw wo sie gerade sind.
Wenn ich jetzt alle Objekte durchlaufe, wird jedes Sprite nur durch das eigene Leaf und die Kinder dieses Leafs geschickt die unterhalb von dem sind, wo sich das Sprite aktuell befindet?
Oder wird es von "ganz oben" durchgeschickt?
Sorry mir ist das gerade nicht so ganz klar und hoffe, dass mir das jemand näher bringen kann.
Links zu ausführlicheren Artikeln sind mehr als gerne gesehen.

rapso

Scorcher24 schrieb:

Meine Basisklasse für mathematische Operationen bei Sprites ist NLBoundingBox.
Die enthält die Daten für das Sprite und auch einige Funktionen zur Kollissionsabfrage wie isPointInside() und intersects().
Diesen "Teil" vom Sprite würde ich natürlich in den Tree werfen.

was?

Wie genau geht das nun von statten?
Mein Gedankenspiel:
Wenn ich jetzt alle Objekte durchlaufe, wird jedes Sprite nur durch das eigene Leaf und die Kinder dieses Leafs geschickt die unterhalb von dem sind, wo sich das Sprite aktuell befindet?

ein leaf hat per definition keine childs mehr, da es das ende vom baum ist. ich steh auch auf dem schlaf was du mit mit durchschicken meinst und wozu.

Oder wird es von "ganz oben" durchgeschickt?

es wird schwer mit der kommunikation wenn du deine eigenen begriffe erfindest, vielleicht kannst du ein wenig genauer sagen was du meinst. sonst kann ich dir nur antworten "ich wuerde sie von links pendeln" und dann hast du eine antworte die fuer dich so void ist wie deine frage fuer uns (oder bin das nur ich der nicht peilt was du sagst?)

Sorry mir ist das gerade nicht so ganz klar und hoffe, dass mir das jemand näher bringen kann.
Links zu ausführlicheren Artikeln sind mehr als gerne gesehen.

Ein "Masterliste" enthält alle Objekte, die getestet werden sollen.
Ich sortiere in der Update-Funktionen nun alle Objekte in die Leafs ein, wo sie hingehören bzw wo sie gerade sind.

an sich brauchst du keine masterliste, lass die objekte doch einfach im baum, wenn du ein "update" machst, wirst du schon rausfinden, ob ein objekt noch unter der node sein kann wo es vorher war, falls es sich bewegt hat, zu 99% duerfte das der fall bleiben und ich denke im normalfall bewegen sich zudem 99% aller objekte nicht, von daher waere es unnoetiger overhead sie jedesmall neu einzusoertieren und eine masterliste zu haben.

[edit] tags fix

dot

Scorcher24 schrieb:

Wie genau geht das nun von statten?

Ich würde mal sagen das hängt davon ab was du eigentlich machen willst...

Scorcher24 schrieb:

Mein Gedankenspiel:
Ein "Masterliste" enthält alle Objekte, die getestet werden sollen.
Ich sortiere in der Update-Funktionen nun alle Objekte in die Leafs ein, wo sie hingehören bzw wo sie gerade sind.
Wenn ich jetzt alle Objekte durchlaufe, wird jedes Sprite nur durch das eigene Leaf und die Kinder dieses Leafs geschickt die unterhalb von dem sind, wo sich das Sprite aktuell befindet?
Oder wird es von "ganz oben" durchgeschickt?

Das hängt natürlich auch wieder ganz davon ab was du machen willst. Vielleicht solltest du uns also mal mitteilen für was genau du eigentlich gedenkst diesen Quadtree zu verwenden. Eine Sache sollte man aber vielleicht festhalten: Einer der Gründe warum man normal überhaupt einen Quadtree verwenden will ist dass man eben genau nicht immer alle Objekte anfassen muss...

Okay, nachts keine Beiträge mehr schreiben. Notiert :D.

Also, ich will den Quadtree zur Kollisionsabfrage verwenden, hab ich ja geschrieben.
Meine worst case Annahme:
* Alle vorhanden Akteure bewegen sich jeden Frame. Beispiel: 2D Space Shooter

Ich stell am besten eine Frage nach dem anderen:
* Wie sortiert sich der Baum wenn sich alle Objekte bewegen? Ich muss ja dann zwangsläufig alle anfassen.
* Wie testet man genau auf Kollisionen? Nimmt man ein einzelnes Objekt und schaut ob dieses im Baum irgendwo kollidiert? Aber dann müsste man ja wieder alles anfassen.

Ich hab so nen Baum noch nie geschrieben, ich habe grade keine Vorstellung davon, wie man das programmiertechnisch am besten Umsetzt. Ich brauch nich die ganze Bibel aber mal das erste Kapitel oder viel mehr das zweite.

rapso

Scorcher24 schrieb:

Meine worst case Annahme:
* Alle vorhanden Akteure bewegen sich jeden Frame. Beispiel: 2D Space Shooter

und ich schrieb dazu "ob ein objekt noch unter der node sein kann wo es vorher war, falls es sich bewegt hat, zu 99% duerfte das der fall bleiben", denn die objekte werden sich ja koherent bewegen und nicht wild in der welt rumbeamen (esseiden du hast 0.1fps, dann vielleicht :D)

* Wie sortiert sich der Baum wenn sich alle Objekte bewegen? Ich muss ja dann zwangsläufig alle anfassen.

du pruefst ob es noch innerhalb der aktuellen node ist, falls
-ja -> pruefe ob es komplett innerhalb einer child node ist und falls ja, sortiere es ein und mach rekursiv weiter
-nein -> uebergeb das objekt an die parent-node und pruef rekursiv weiter

* Wie testet man genau auf Kollisionen? Nimmt man ein einzelnes Objekt und schaut ob dieses im Baum irgendwo kollidiert? Aber dann müsste man ja wieder alles anfassen.

ein objekt kann nicht mit einem objekt in einer nachbar node kollidieren, es muss also mit einem objekt in der selben node oder einer child node kollidieren, dagegen musst du dann pruefen, das sollte in den allermeisten faellen ein bruchteil der welt sein.

btw. falls du wirklich ein weltraumspiel machst wo sich alles bewegt, dann kann es guenstiger sein einfach nur eine liste von objekten zu machen die in einer achse sortiert sind, denn dann ersparst du dir das traversieren das oct oder quad trees und testest in den meisten faellen gegen ein paar wenige nachbaren.

dot

Ich würd mir überlegen ob du nicht lieber einfach ein Grid oder eine BVH oder sowas verwendest statt einen Quadtree. Der macht vermutlich alles nur unnötig kompliziert.