2D Kollisionsabfragen

[Xin]

Bzgl der QuadTree Geschichte, wüsste ich jetzt spontan online nichts. Aber letztendlich... halt ein Baum mit vier statt zwei Kindern, die ein quadratisches Gebiet in vier Unterquadrate unterteilen!? Also das selbe wie ein binäre Baum im eindimensionalen!?

Ja soweit isses mir klar. Effektiv bekomme ich das auch hin, Objekte hinzuzufügen und den Baum dynamisch zu erweitern. Nur fehlt mir die richtige Herangehensweise, wenn ich für einen gegebenen Kreis die Kollisionen haben will.

Die Idee eines Quadtrees ist ja auch nicht, irgendwelche Kreise zu beschreiben, sondern die vielen Objekte, die sich nicht im Radius befinden möglichst schnell auszuschließen - also die Menge zu reduzieren, mit denen Du abgleichen musst. Du musst also alle Objekte überprüfen, die innerhalb des Quads liegt, dass gerade eben Deinen Radius enthält, also dein Mittelpunkt nicht soweit am Rand liegt, dass Du den Quad verlassen würdest. Alle Blätter dieses Astes sind potentielle Treffer. Je nach Auflösung hast Du damit 99% der Objekte ausgefiltert.

[Glocke]

Alle Blätter dieses Astes sind potentielle Treffer. Je nach Auflösung hast Du damit 99% der Objekte ausgefiltert.

Also hat ein Quadtree immer eine Höhe n? Ich habe Erklärung gefunden in der jede Node maximaln 4 Elemente erhält beim Anfügen weiterer das Quad unterteilt wird.

Ich habe mal ein Python-Skript gebaut, was einen Quadtree der Höhe n realisiert.

quadtree.py.zip

(Ich darf keine py-Files anhängen, daher als Zip)

Der wird mit n=5 erstellt und mit 600 zufälligen Kreisen gefüttert. Zusätzlich wird mit den gleichen Kreisen eine Liste gefüllt. Im Anschluss wird für den gleichen Kreis einmal mit Quadtree und einmal mit der Liste gesucht und die notwendige Zeit ausgegeben.

Entspricht das so ca. dem, was du unter einem Quadtree verstehst?

Mit der Geschwindigkeit bin ich schon ganz zufrieden. Ich denke mal, wenn ich das dann in C++ umsetze, werde ich noch etwas mehr Speed rausholen können:

Code: Alles auswählen

Strukturen (Liste und Quadtree der Tiefe 4) mit 5000 Objekten wurden binnen 2.72023701668s erstellt.

Kreis <1.5,1.5:0.1> (mit Quadrat <1.4,1.4;0.2,0.2>) Kollisionen:
		--> 321 Objekte gefunden
Zeit Quadtree:		0.00606107711792

Kreis <1.5,1.5:0.1> (mit Quadrat <1.4,1.4;0.2,0.2>) Kollisionen:
		--> 321 Objekte gefunden
Zeit lineare Liste:	0.0397760868073

LG Glocke

[Xin]

Alle Blätter dieses Astes sind potentielle Treffer. Je nach Auflösung hast Du damit 99% der Objekte ausgefiltert.

Also hat ein Quadtree immer eine Höhe n? Ich habe Erklärung gefunden in der jede Node maximaln 4 Elemente erhält beim Anfügen weiterer das Quad unterteilt wird. Jetzt bin ich verwirrt xD

Nehmen wir ein Feld von 100x100m. An Position 25/25, 52/52, 77/80 und 85/85 befinden sich Objekte. Sie haben jeweils einen Kollisionsradius von 5.
Jetzt fängst Du an das Feld mit einem Quadtree zu unterteilen: Du erhältst vier Felder je 50/50. Im Feld "oben links" steht "25/25", "oben rechts" und "unten links" sind leer. "unten rechts" finden sich "52/52", "77/80" und "85/85". Es lohnt also "unten rechts" weiter zu unterteilen. Du bekommst für "unten rechts" einen neuen Knoten, der vier Felder enthält: "ur/oben links" mit "52/52", "ur/oben rechts" und "ur/unten links" sind leer, "ur/untenrechts enthält "77/80" und "85/85". Wenn Du nun wissen möchtest, ob "85/85" kollidiert, dann hast Du in dem Quad eine Bounding Box: 75/75 bis 100/100. "85/85" berührt keine Ränder, also reicht es, dieses eine Quad zu untersuchen. Das Quad hat keine Kinder, im Quad liegt nur noch "77/80", also ein Objekt zu prüfen, der Rest ist definitiv zu weit weg.

Bei der Frage, ob "77/80" kollidiert, haben wir zunächst wieder das Quad "ur/unten rechts", aber hier berühren wie die Grenze. Wir müssen also zum übergelagerten Quad. Hier finden wir "52/52" und "85/85". Wir könnten jetzt optimieren, denn wir berühren ja nur den linken Rand, also können wir uns auf "ur/rechts unten" und "ur/links unten" konzentrieren. "ur/links unten" ist leer, also müssen wir nur gegen "85/85" abgleichen.

Bei "52/52" ist die Sache schwieriger. In "ur/oben links" gibt es sonst nichts, wie berühren aber die grenzen nach oben und links", wir müssen also das darüberliegende, das links liegende und links oben liegende Quad untersuchen. Die sind nicht unterteilt worden, also bekommen wir "oben links", "oben rechts" und "unten links", in "oben links" müssen wir also gucken, ob "25/25" und "52/52" kollidieren.
Das sind 4 Einheiten auf 100m^2. Kleinkram.

Wenn der Spielplan groß genug ist, also sagen wir mal 10000x10000, dann sind das 100000000m^2, bei 4 Einheiten pro 100qm sind das 4 Millionen Objekte. Da ist es schon praktisch, wenn man pro Verästelung im Schnitt die Anzahl der Einheiten vierteln kann...

[Glocke]

Nehmen wir ein Feld von 100x100m. An Position 25/25, 52/52, 77/80 und 85/85 befinden sich Objekte. Sie haben jeweils einen Kollisionsradius von 5.

Soweit hab ich es verstanden. Nur was, wenn ein Kollisionsradius z.B. 20 ist? Füge ich dieses "große" Objekt dann in alle Quads ein, die der Kollisionsradius mit berührt? Wenn ja, ist meine Implementierung (siehe Edit meines Posts darüber) gar nicht so weit davon weg

Da ist es schon praktisch, wenn man pro Verästelung im Schnitt die Anzahl der Einheiten vierteln kann...

Definitiv

Was ich jetzt (noch) nicht (eindeutig) rausgelesen habe: Ist der Baum überall gleich groß? Ich meine: erzeuge ich den Baum mit Höhe n erstmal "Leer" oder erstelle ich beim Einfügen von Objekten weitere Unter-Quads?

Ich würde zu "mit Höhe n erzeugen" tendieren, denn:

• Bewegen sich die Objekte, muss ich neue Äste anlegen. Sind die schon da spare ich imho Zeit.
• Den Quadtree erstelle ich einmal, wenn die Map geladen wird. Da kommt es imho nicht auf ein paar Millisekunden an.

LG Glocke

[Xin]

Nehmen wir ein Feld von 100x100m. An Position 25/25, 52/52, 77/80 und 85/85 befinden sich Objekte. Sie haben jeweils einen Kollisionsradius von 5.

Soweit hab ich es verstanden. Nur was, wenn ein Kollisionsradius z.B. 20 ist? Füge ich dieses "große" Objekt dann in alle Quads ein, die der Kollisionsradius mit berührt? Wenn ja, ist meine Implementierung (siehe Edit meines Posts darüber) gar nicht so weit davon weg

Ich würde sie nur da einfügen, wo der Mittelpunkt ist. Wird das Objekt dann gefragt, muss man halt gucken, ob man weitere Quads aus der Nachbarschaft berührt und diese ggfs. untersuchen.

Was ich jetzt (noch) nicht (eindeutig) rausgelesen habe: Ist der Baum überall gleich groß? Ich meine: erzeuge ich den Baum mit Höhe n erstmal "Leer" oder erstelle ich beim Einfügen von Objekten weitere Unter-Quads?

Das würde ich in Abhängigkeit der Anzahl der Objekte innerhalb eines Quads handhaben.
So könnte ich mir am Anfang einer Schlacht, wenn die Kämpfer links und rechts in den Bildschirm eintreten vorstellen, dass sich links und rechts hochauflösende Quads befinden und in der Mitte des Bildschirms großflächige Bereiche - da rennt ja noch keiner rum.

Ist die Schlacht im vollen Gange, sieht die Sache andersrum aus: Hochaufgelöst in der Mitte, große Flächen am Rand, die vielleicht noch ein zwei vergessene Einheiten beinhalten.

Der Quadtree verändert sich also laufend. Du kannst in C++ Memorypools verwenden, um Speicherallokation drastisch zu beschleunigen. Aber das würde ich erst nachrüsten, wenn Dein Schlacht im Prinzip läuft. Du musst nur darauf achten, gleichartige Objekte zu erzeugen, so dass diese eine (ungefähr) fixe Größe haben.

[Glocke]

Ich würde sie nur da einfügen, wo der Mittelpunkt ist. Wird das Objekt dann gefragt, muss man halt gucken, ob man weitere Quads aus der Nachbarschaft berührt und diese ggfs. untersuchen.

Und wie definiere ich die Nachbarschaft? Dazu muss ich wissen, wie groß die maximal sein kann - und müsste im Bezug auf die Kreise ein Maximum für den Radius herrschen. Oder?

So könnte ich mir am Anfang einer Schlacht, wenn die Kämpfer links und rechts in den Bildschirm eintreten vorstellen, dass sich links und rechts hochauflösende Quads befinden und in der Mitte des Bildschirms großflächige Bereiche - da rennt ja noch keiner rum.

Ist die Schlacht im vollen Gange, sieht die Sache andersrum aus: Hochaufgelöst in der Mitte, große Flächen am Rand, die vielleicht noch ein zwei vergessene Einheiten beinhalten.

Also müsste ich beim Entfernen dann auch gucken: "Ist hier noch jemand?". Wenn in allen 4 Quads keiner ist, kann ich die entfernen und zum parent zurückkehre. Meinst du das so?

[Xin]

Ich würde sie nur da einfügen, wo der Mittelpunkt ist. Wird das Objekt dann gefragt, muss man halt gucken, ob man weitere Quads aus der Nachbarschaft berührt und diese ggfs. untersuchen.

Und wie definiere ich die Nachbarschaft? Dazu muss ich wissen, wie groß die maximal sein kann - und müsste im Bezug auf die Kreise ein Maximum für den Radius herrschen. Oder?

Nachbarschaft sind alle Blätter, die in eine Bounding Box passt, die durch den Positionspunkt und den Radius gegeben ist.
Wobei ein Quad eben entweder eine Liste mit Objekten ist (ein Blatt) oder ein Knoten des Quadtrees, der vier andere Quads verwaltet, den man entsprechend wieder Deine Bounding Box verpassen muss.

So könnte ich mir am Anfang einer Schlacht, wenn die Kämpfer links und rechts in den Bildschirm eintreten vorstellen, dass sich links und rechts hochauflösende Quads befinden und in der Mitte des Bildschirms großflächige Bereiche - da rennt ja noch keiner rum.

Ist die Schlacht im vollen Gange, sieht die Sache andersrum aus: Hochaufgelöst in der Mitte, große Flächen am Rand, die vielleicht noch ein zwei vergessene Einheiten beinhalten.

Also müsste ich beim Entfernen dann auch gucken: "Ist hier noch jemand?". Wenn in allen 4 Quads keiner ist, kann ich die entfernen und zum parent zurückkehre. Meinst du das so?

Richtig, wobei Du sie auch schon bei einer Person entfernen kannst, da die Kollisionsabfrage mit einer Person vermutlich schneller geht, als vier Quads zu interviewen... die genaue Grenze musst Du empirisch bestimmen.

[Glocke]

Nachbarschaft sind alle Blätter, die in eine Bounding Box passt, die durch den Positionspunkt und den Radius gegeben ist.
Wobei ein Quad eben entweder eine Liste mit Objekten ist (ein Blatt) oder ein Knoten des Quadtrees, der vier andere Quads verwaltet, den man entsprechend wieder Deine Bounding Box verpassen muss.

Alle Blätter, die in meine Bounding Box passen, die durch meinen Positionspunkt und meinen Radius gegeben ist... dann weiß ich aber nicht, ob ein anderes Objekt (das außerhalb meiner Bounding Box liegt), vielleicht einen viel größeren Radius hat, so dass sie meine Box schneidet aber ich davon gar nix mitbekomme. Dann würde mir diese Kollision bei der Betrachtung verloren gehen. Also quasi dieser Fall:

bsp.png

Also ich wäre K1 und der andere K2. Du willst ja nur die Mittelpunkte in die Quads einfügen, richtig? Dann lägen er und ich in verschiedenen Quads und aufgrund meines kleinen Kollisionsradius würde ich keine anderen Objekte prüfen. Also weiß ich von K2 nichts, obwohl seine Bounding Box (und genauer auch der Bounding Circle) meinen schneidet.

Ich würde von jedem Objekt einen Pointer auf ihn in die Quads legen, die die Bounding Box des Objektes schneiden, d.h.

• Oben Links: Zeiger auf K1, K2
• Oben Rechts: Zeiger auf K2
• Unten Rechts: Zeiger auf K2
• Unten Links: Zeiger auf K2

Damit würde ich dann wissen: "okay ich sitze oben links und dort gibt es noch K2" und kann mich dann fragen "schneidet der mich?"

Ich vermute trotzdem, dass wir da in irgendeinem Detail aneinander vorbei reden

Richtig, wobei Du sie auch schon bei einer Person entfernen kannst, da die Kollisionsabfrage mit einer Person vermutlich schneller geht, als vier Quads zu interviewen... die genaue Grenze musst Du empirisch bestimmen.

Oki

[Xin]

Ich vermute trotzdem, dass wir da in irgendeinem Detail aneinander vorbei reden

Nein, Deine Kritik ist berechtigt und eine supertolle Lösung habe ich für Objekte mit unterschiedlichen Kollisionsradien so spontan nicht.

Von Deiner Lösung halte ich aber auch nix weil das sehr aufwendig ist, wenn sich viele Objekte bewegen.

[Glocke]

Nein, Deine Kritik ist berechtigt.

Okay, also brauche ich eine Lösung dafür
Btw ist das das Problem was ich ganz am Anfang mal angesprochen hatte - irgendwie war das aber zu unverständlich von mir formuliert

Von Deiner Lösung halte ich aber auch nix weil das sehr aufwendig ist, wenn sich viele Objekte bewegen.

Naja aufwendig nur, wenn sich viele große Objekte bewegen, da mit jedem großen Objekt mehr Zeiger auf dieses Ding im Quadtree rumliegen. Aber du hast schon recht .. toll ist anders