spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Der Englische Wikipedia Artikel ist sicher ein guter Anfang.

Im Grunde genommen teilst du dein Spielfeld in Quadrate (Rechtecke funktionieren allerdings auch). Objekte, die sich über den Raster bewegen werden dann jeweils in das kleinst mögliche verfügbare Quadrat gesteckt. Sobald zu viele Objekte im gleichen Quadrat sind, wird das Quadrat aufgeteilt in vier gleich grosse Quadrate. Diese Quadrate sind die Kindknoten des grossen Quadrates (von daher auch Quadtree).

Wie soll das nun die Kollisionsabfrage beschleunigen?

Einfach gesagt musst du nun nurnoch Kollisionen zwischen Objekten, die im gleichen Quadrat sind überprüfen.
Objekte aus anderen Quadraten sind nicht nahe genug am Objekt, um mit ihm zu kollidieren.
"Einfach gesagt", weil du natürlich auch noch Grenzfällle wie z.B. Objekte, die sich auf Kanten von Quadraten befinden, behandeln musst.

Ich hoffe ich habe hier keinen Mist erzählt. Der Wikipedia Artikel erklärts eigentlich zur genüge.

Zitat von »Darkrel«

Einfach gesagt musst du nun nurnoch Kollisionen zwischen Objekten, die im gleichen Quadrat sind überprüfen.
Objekte aus anderen Quadraten sind nicht nahe genug am Objekt, um mit ihm zu kollidieren.
"Einfach gesagt", weil du natürlich auch noch Grenzfällle wie z.B. Objekte, die sich auf Kanten von Quadraten befinden, behandeln musst.

Ich hoffe ich habe hier keinen Mist erzählt. Der Wikipedia Artikel erklärts eigentlich zur genüge.

Prinzipiell ja, aber ich würde es wahrscheinlich so erklären, dass man eine Hierarchische suche nach Objekten macht, die mit dem aktuellen kollidieren.

Als Beispiel hast du ein Feld mit ein Haufen Kreisen. Wenn du jetzt einen beliebigen Kreis nimmst und wissen willst mit welchen er kollidiert, dann fängst du mal ganz oben an. Also befindet sich der erste Kreis im Spielfeld -> Ja, also befindet er sich im ersten Quadranten -> Nein, befindet er sich im zweiten Quadranten -> Ja (als Beispiel). Dann musst du nur noch in diesem Quadranten weiter suchen ob es ein Objekt gibt usw. Das erfordert, dass man vorher eben einen sogenannten Quadtree aufbaut, der diese Felder und die darin befindlichen Kreisen in den Blättern hat.
Wenn man Pech hat kann das aber dazu führen, dass alle Kreise im gleichen Quadrant sind und man nichts gewonnen hat, aber die Wahrscheinlichkeit dafür ist bei Spielen üblicherweise klein und es gibt Alternativen.