In dem folgenden Beitrag möchten wir etwas näher auf 2D Collision Detection im 2D-Raum eingehen. Um ihnen diese Thematik etwas genauer veranschaulichen zu können, werden wir ein Beispiel nutzen. In diesem Beispiel möchten wir Kugeln dazu bringen, Schiffe zu treffen und zu versenken.
2D Collision Detection.
Bevor wir dieses Tutorial beginnen, müssen wir zunächst klären, wie mit der 2D Collision Detection umgegangen werden muss. Es gibt viele Algorithmen, mit denen man erkennen kann, wenn sich zwei Objekte in einem 2D Raum berühren. Für unser einfaches Signal müssen wir keinen komplexen Erkennungsalgorithmus implementieren, da Videospiele diesen nur einigermaßen gut einschätzen müssen. Daher werden wir für unsere Collision Detection einen Bounding-Box-Test verwenden.
Ein Bounding Box Collision Detection Algorithmus nimmt zwei Objekte und überprüft, ob die Grenzen des ersten Objekts innerhalb der Grenzen des zweiten Objekts liegen. Es erfordert vier Prüfungen, eine für jede Kante der Bounding Box.
Um die Collision Detection umzusetzen, können wir diesen Algorithmus einfach in eine Schleife legen und jedes Objekt gegen jedes andere Objekt prüfen. Denke jedoch darüber nach, wie viele Objekte in unserem Spiel vorhanden sind. Zu jeder Zeit kann es 18 Feinde, ein Spielerschiff, bis zu 30 Spielerkugeln und bis zu 50 generische Kugeln geben. Das sind fast 100 Objekte, die auf einmal auf dem Bildschirm sein könnten.
Wenn wir diesen Algorithmus wie oben beschrieben in einer Schleife ausführen würden, müsste das Spiel etwa 5.000 Prüfungen durchführen, nur um zu überprüfen, ob zwei Objekte kollidieren. Und da wir unseren Collision Detection-Algrothmus in jedem Frame ausführen müssen, kann er das Spiel wirklich verlangsamen. Was wir also tun müssen, ist, die Collision Detection zu beschleunigen.
2D Collision Detection verbessern.
Allein die Verbesserung des Bounding-Box-Algorithmus wird uns nicht helfen, die Collision Detection zu beschleunigen, da das Hauptproblem die Anzahl von Prüfungen durch den Algorithmus ist. Daher ist der beste Weg, die Collision Detection zu beschleunigen, die Anzahl der Prüfungen zu reduzieren, die der Algortihmus durchführen muss. Dazu verwenden wir eine Technik, die als räumliche Partitionierung bekannt ist.
Kurzes Update.
Dieser Beitrag hat in letzter Zeit viel Aufmerksamkeit erregt, mit einer Menge Diskussion über den Einsatz von räumlcher Partitionierung für ein so einfaches Spiel. Wir möchten diese Themen ansprechen, da sie gute Punkte hatten, die Sie meiner Meinung nach kennen sollten.
Es sollte bekannt sein, dass die räumliche Partitionierung nicht der einzige Weg ist, die Collision Detection zu beschleunigen. Es gibt viel einfachere Möglichkeiten, dies zu realisieren. Sie könnten sich einfach alle feindlichen Kugeln vornehmen und jede einzelne gegen nur das Spielerschiff und anschließend alle Spielerkugeln gegen jeden Feind überprüfen. Dies ist nur ein Beispiel und würde den gleichen Effekt erzielen, wenn die Anzahl der Collision Checks reduziert würde.
Die Verwendung der räumlichen Aufteilung für ein so einfaches Spiel ist natürlich übertrieben. Räumliche Partitionierung wird normalerweise in viel größeren Spielen verwendet, bei denen der Aufwand für die Collision Detection größer ist als bei der Verwendung eines Quadtrees. Aus den folgenden zwei Gründen haben wir uns für die räumliche Partitionierung entschieden.
Der erste Grund ist, dass Entwickler häufig auf das Problem stoßen, dass Spiele immer langsamer werden, umso mehr Objekte (z.B. Kugeln und Feinde in unserem Beispiel) hinzugefügt werden. Wir entdeckten, dass das Spiel aufgrund der Durchführung einer Vielzahl von Collision Detection mit so vielen Objekten verzögert wurde. Nach langer Recherche haben wir uns für einen Quadtree entschieden und konnten dann 60FPS beibehalten. Räumliche Partitionierung und Vierecke waren für uns am Anfang schwer zu verstehen und es war im Grunde genommen nur ein Trail-and-Error-Versuch, sie dazu zu bringen, für uns zu arbeiten. Es wäre schön gewesen, wenn uns jemand deren Funktionsweise hätte erläutern können.
Der zweite Grund, warum wir die räumliche Partitionierung erklären wollten, ist, dass dieses Spiel als Sprungbrett gedacht war und wir wollten, dass Entwickler den Code nehmen und für ihre eigenen Spiele erweitern. Wir neigen dazu, Code mit Blick in die Zukunft zu entwickeln, also entschieden wir uns dafür, dass es eine gute Idee war, den Entwicklern eine Methode zur Collision Detection beizubringen, die ihnen Zeit und mögliche Kopfschmerzen in der Zukunft ersparen könnte.
Daher werden wir für dieses Tutorial die räumliche Partitionierung verwenden. Es ist nur ein einziges Werkzeug in einer Entwickler-Toolbox, das wir für wissenswert halten. Ein guter Entwickler zu sein bedeutet zu wissen, wann man jedes Tool richtig einsetzen muss. Wir hoffen, Sie verstehen die Nachteile der Verwendung von räumlicher Partitionierung, aber wir hoffen auch, dass Sie unsere Argumentation verstehen, sie zu verwenden. Wir möchten noch einmal darauf hinweisen, dass die Verwendung von Quadtrees und die räumliche Partitionierung für kleine Spiele unnötig ist, da man bessere Lösungen für weniger Overhead erreichen kann. Aber das Spiel behält 60FPS sogar mit einer Quadtree-Implementierung bei, so dass der Overhead für ein so kleines Spiel die Leistung nicht beeinträchtigt.
Räumliche Partitionierung.
Räumliche Partitionierung nimmt einen engen Raum und unterteilt ihne in mehrere kleine Räume. Durch die Unterteilung des Raumes können wir schnell feststellen, welche Objekte zum gleichen Bereich gehören und müssen nur die Collision Detection gegen diese Objekte durchführen. Jedes Objekt, das nicht in den gleichen Raum gehört, kann nicht kollidieren, so dass wir keine Überprüfung verschwenden müssen.
Durch die Aufteilung des Raumes können wir unsere Prüfung der Collision Detection von 5.000 auf etwa 100 pro Frame reduzieren – das ist eine enorme Verbesserung. Um diese Technik zu implementieren, werden wir eine Datenstruktur verwenden, die als Quadtree bezeichnet wird.
Ein Quadtree indiziert alle Objekte im Spiel in Nodes und Subnodes. Alle Objekte innerhalb eines Nodes könnten potentiell kollidieren, daher werden wir nur diese Objekte auf Kollision prüfen. Mit dem Quadtree in der Hand sind wir fast bereit, die Collision Detection in unserem Spiel zu implementieren.
Die Objekte für Collision Detection updaten.
Es bleibt noch eine Sache zu tun, bevor wir die 2D Collision Detection umsetzen. Nicht jedes Objekt kann mit jedem anderen Objekt kollidieren. Zum Beispiel wird ein Schiff nicht mit seiner eigenen Kugel kollidieren, das gleiche gilt für ein feindliches Schiff. Daher müssen wir prüfen, ob die beiden Objekte kollidieren sollten, bevor wir prüfen, ob sie kollidieren. Das bedeutet, dass jedes Objekt eine Liste von Objekten enthält, mit denen es kollidieren kann und der Collision Detection Algorithmus vergleicht diese Liste mit dem Typ der anderen Objekte.
Um mit der Implementierung der Collision Detection zu beginnen, werden wir das Drawable-Objekt bearbeiten.
Das Objekt erhält zwei neue Variablen: collidableWith und isColliding sowie eine neue Funktion isCollidableWith(), um zu testen, ob das Objekt mit dem angegebenen Objekt kollidieren kann. Die Variable isColliding sagt uns, wann ein Objekt kollidiert und sollte nicht neu auf das Canvas gezeichnet werden.
Mit der Notwendigkeit, eine Liste von kollidierbaren Objekten zu haben, muss jedes Objekt in unserem Spiel diese Änderung umsetzen. Beginnen wir mit dem Bullet-Objekt.
Lediglich die Funktionen draw() und clear() müssen geändert werden. Die Zeichenfunktion fügt die Prüfung hinzu, um zu sehen, ob das Objekt kollidiert. Wenn ja, kehren Sie true zum Objektpool zurück, um ihm mitzuteilen, dass die Kugel wiederverwendet werden kann. Die Clear-Funktion setzt die Variable isColliding einfach auf false zurück.
Das nächste Objekt, das wir aktualisieren werden, ist das Schiffsobjekt.
Das Schiffsobjekt setzt seinen Typ und ist mit feindlichen Kugeln kollidierbar. In der draw() Funktion werden wir das Schiff nur neu zeichnen und feuern lassen, wenn es nicht mit etwas kollidiert.
Als nächstes kommt das feindliche Objekt.
Das feindliche Objekt setzt seinen Typ und ist mit den Spielerkugeln kollidierbar. Es wird nur neu gezeichnet und geschlossen, wenn es nicht kollidiert und die Funktion clear() setzt die Variable isColliding zurück.
Das Letzte zu bearbeitende Objekt ist das Pool-Objekt:
Für jede Art von Kugel, die Spielerkugeln und die feindlichen Kugeln, werden wir den Typ und die Kollidierbarkeit mit entsprechenden Variablen entsprechend einstellen. Wir fügen auch eine neue Funktion hinzu, getPool(), um alle lebenden Objekte im Pool als Array zurückzugeben, das dann in den Quadtree eingefügt wird.
Da alle unseren Objekte aktualisiert wurden, sind wir fast bereit, eine Collision Detection zu implementieren.
Der letzte Schritt.
Um den Quadtree in unserem Spiel zu implementieren, fügen wir nur eine Zeile am Ende des Spielobjekts hinzu, kurz bevor wir true zurückgeben:
Als nächstes können wir die Funktion animate() aktualisieren, um den Quadtree zu verwenden.
Das Erste, was wir tun, ist den Quadtree zu löschen und alle Objekte hinzuzufügen. Sobald alle Objekte dem Quadtree hinzugefügt wurden, führen wir unseren Collision Detection Algorithmus in detectCollision() aus. Zum Schluss bewegen und animieren wir alle Objekte auf dem Bildschirm. Diese Reihenfolge stellt sicher, dass alle Objekte, die im Frame kollidieren, nicht am Ende des Frames neu gezeichnet werden.
Das letzte Bit des Codes ist die detectCollision() Funktion.
Die Funktion ruft zunächst alle Objekte im Quadtree ab und speichert sie in einem einzigen Array. Anschließend wird jedes Objekt in dem Array durchlaufen und ein anderes Array von Objekten abgerufen, mit denen das Objekt kollidieren könnte. Schließlich führt es den Collision Detection Algorithmus gegen diese Objekte aus, um zu sehen, ob sie kollidieren.
Wir haben jetzt ein Spiel, das in der Lage ist, bei 60FPS auf Kollisionen zu prüfen. Es brauchte ein wenig Refractoring, um dorthin zu gelangen, aber am Ende hat sich das alles gelohnt.
Schlußfolgerungen.
Wir mussten fast jedes Objekt und jede Funktion im Spiel aktualisieren, aber jetzt implementiert es due 2D Collision Detection ziemlich schnell. Wir haben auch eine gute Technik gelernt, um die Collision Detection zu beschleunigen, indem wir einen Quadtree zur Reduzierung von Collision Checks implementiert haben.
Vielen Dank für ihren Besuch.