Im Zuge meiner Entwicklung eines Spiels bin ich letztens an ein unangenehmes Limit gestoßen. Ich wollte eignetlich nur mal schauen was passiert wenn ich x fliegende Objekte platziere die jeweils eine Kollisionserkennung haben und somit an jedem Objekt abprallen können.

Jedes der Objekte mit jedem anderen Objekt pro Tick zu prüfen ist natürlich sehr übertrieben aber wenn man dann sieht das man bei so ziemlich genau 3333 Objekten plötzlich 0 Frames hat dann ist das nicht mehr so prickelnd. Ich glaube nicht das in dem aktuellen Spiel jemals so viele Objekte gleichzeitig zu sehen sein werden ABER ich wollte schon immer mal die Quadtrees verstehen und umsetzen und genau deshalb bietet sich das hier als eine gute Gelegenheit an, ob ich mit meinem Algorithmus später eventuell mehr FPS bei mehr Objekten bekomm steht noch im Raum, ich selbst hoffe es natürlich. ^^

Quadtree

Was ist denn eignetlich ein Quadtree? Ein Quadtree ist eine Baum-Struktur in der jeder Innere-Knoten vier Kinder hat. Ich möchte an dieser Stelle das Bild eines Quadtrees aus Wikipedia euch zeigen:

Quelle: http://de.wikipedia.org/w/index.php?title=Datei:Quadtree.png&filetimestamp=20080202170336

Aber was hat das ganze denn mit Kollisionserkennung zu tun? :S Naja eigentlich ganz einfach, stellt euch mal die Frage: “Wieso sollte man ein Objekt das oben rechts ist auf Kollision mit einem Objekt in der unteren linken Ecke prüfen, bzw. mit allen Objekten in der unteren linken Ecke?” – Richtig … eigentlich völliger schwachsinn, unsere ach so liebe CPU mit solch einer Prüfung zu konfrontieren wenn man eh vorne weg sagen kann, das eine Kollision nicht/nie stattfindet.

Also gehen wir nun her und legen unser eines Objekt in die obere rechte Ecke (grüner Bereich) und legen zwei weitere Objekte in den unteren linken Bereich (gelb). Wenn wir an der Stelle im Programm sind das Objekt auf der grünen Fläche zu malen, wird hier dann nur geprüft ob er eine Kollision mit anderen Objekten im grünen Bereich hat. Somit würde eine Kollisionsprüfung auf die zwei Objekte im unteren linken Bereich komplett entfallen. Je tiefer man den Baum strickt desto genau auch die Kollisionserkennung aber vorsicht mit der tiefe, wir bekommen bei jeden neuen Tiefe 4 weitere Quads dazu, daraus resultiert

anzahl = 4 ^ tiefe
anzahl = 4 ^ 4 = 4*4*4*4 = 256
anzahl = 4 ^ 6 = 4*4*4*4*4*4 = 4096

Ich habe in meiner Entwicklung eine maximale Tiefe von 6 eingestellt, d.h. bis zu 4096 Quads. Jetzt bin ich aber hingegangen und habe nicht gleich alle Quads generiert … wozo auch in eine Tiefe von 6 gehen wenn man dort evtl. gar keine Objekte liegen hat. Also habe ich eine weitere Konstante eingeführt die sagt wieviel Objekte auf einem Quad liegen müssen bevor sich dieses wieder teilt. In meinem Fall liegt dies bei drei d.h. erst wenn drei Objekte vorhanden sind, soll er sich teilen um eine genauere Kollision zu berechnen. Anbei ein kleiner Screenshot aus meine Testumgebung

Ich bin in meinem Urlaub jetzt leider noch nicht weiter gekommen als das was ihr da sehen könnt. Es gilt jetzt noch zu prüfen ob ein Objekt mit einem anderen Objekt aus seinem Bereich eine Kollision hat und ganz wichtig, wenn ein Objekt sich aus seinem Quad bewegt, muss dies neu zugeteilt wird. Ich hänge euch hier im rechten Seitenbereich mal die Anwendung an, aber bitte, durch das wecheln der Farben des Quads (zufalls Farben) in jedem Tick, kann man davon sehr schnell Kopfschmerzen bekommen :D also vorsicht und auf eigene Gefahr.

Ich werde euch über den Rest auf dem laufenden halten ;)

Über den Autor:

Vor mehr als 7 Jahren habe ich mein Hobby zum Beruf gemacht. Seit her bekommt mich kein Problem so schnell in die Knie, ich bin sehr verbissen und arbeite solange an einem Problem bis es gelöst ist.

Ähnliche Artikel:

• Mainloop, FPS, Framebremse und VSync …
• WinAPI C++ Das erste Fenster unter Windows
• Frozen Bubble Clone
• Mein erstes Spiel – Pong