Kollision

Gunnar Niebaum

Problemstellung

In der Szene befinden sich im Laufe des Spieles viele Objekte, die miteinander kollidieren und interagieren können. Das Spaceship soll in der Lage sein, Gegner und Asteroiden mit unterschiedlichen Projektilen abzuschießen. Ferner soll es Items einsammeln und mit Gegnern sowie Asteroiden kollidieren können. Die Gegner sollen miteinander und mit den Asteroiden zusammenstoßen können und in der Lage sein, den Spieler abzuschießen. Außerdem sollen die Asteroiden noch miteinander kollidieren können. Durch die Tatsache, dass sich der Großteil der Objekte in der Szene bewegt – und das mit teilweise drastisch unterschiedlichen Geschwindigkeiten – muss in jedem Render-Aufruf jedes in der Szene befindliche Objekt mit jedem weiteren, mit dem es potentiell kollidieren kann, auf Kollision geprüft werden. Aufgrund der hohen Dynaik in der Szene lohnt es sich nicht, die sich in der Nähe befindenden Objekte in einer Liste abzuspeichern, da diese in jedem Render-Aufruf neu sortiert werden müsste. Die Prüfung auf Kollision bringt also einen hohen Rechenaufwand ($\mathcal O(n^2)$) mit sich. Hinzu kommt, dass besonders die mit Blender erstellten Raumschiffe und Asteroiden ein hohes Maß an Komplexität aufweisen. Auch diese Tatsache kann bei der Kollisionsprüfung einen hohen Rechenaufwand zur Folge haben.

Hit-Objekte

Um die erforderliche Anzahl an Berechnungen pro Render-Aufruf zu senken, werden die Objekte in der Szene durch solche geometrische Formen approximiert, die einfacher auf mögliche Überschneidungen geprüft werden können. Diese werden von hier an als Hitobjekte bezeichnet. Die Menge $M$ enthält alle Geometrien, durch die die kollidierbaren Objekte approximiert werden:

$M = \{\text{Box}, \text{Sphere}, \text{Point}\}$

Die folgende Tabelle enthält die Objekte in der Szene sowie die zugehörigen Hit-Objekte.

Sowohl der Laser als auch die Raketen werden durch jeweils mehrere Punkte, die in dem jeweiligen Projektil liegen, repräsentiert. Diese Approximation bringt eine bessere Rechenleistung bei der Kollisionsprüfung als eine Annäherung durch eine Box, wie der folgende Abschnitt zeigen wird.

Kollisionsarten

Aufgrund der oben beschriebenen Kollisionsmöglichkeiten und Hit-Objekte ist es erforderlich, folgende Kollisionen zu prüfen:

$M \times M \setminus (\text{Point}, \text{Point})$

Um die Kollisionsbeschreibung zu vereinfachen, werden folgende Definitionen vorgenommen:

$a, b := \text{Box}$, $s := \text{Sphere}$, $p := \text{Point}$.

$maxX(o)$, $maxY(o)$, $maxZ(o) :=$ Der maximale Wert eines Objekts $o$ in x-, y-, z-Ausrichtung im Weltkoordinatensystem.

$minX(o)$, $minY(o)$, $minZ(o) :=$ Der minimale Wert eines Objekts $o$ in x-, y-, z-Ausrichtung im Weltkoordinatensystem.

Box-Box-Kollision

Zwei Boxen überschneiden sich, wenn

$minX(a) \leq maxX(b) \land maxX(a) \geq minX(b) \land \\ minY(a) \leq maxY(b) \land maxY(a) \geq minY(b) \land \\ minZ(a) \leq maxZ(b) \land maxZ(a) \geq minZ(b).$

Es gibt also in allen drei Dimensionen eine Überschneidung.

Point-Box-Kollision

Ein Punkt liegt in einer Box, wenn

$p.x \leq maxX(b) \land p.x \geq minX(b) \land \\ p.y \leq maxY(b) \land p.y \geq minY(b) \land \\ p.z \leq maxZ(b) \land p.z \geq minZ(b).$

Point-Sphere-Kollision

Wenn die euklidische Distanz des Punktes zum Zentrum der Sphere kleiner ist als der Radius der Sphere, liegt der Punkt innerhalb der Sphere.

Sphere-Box-Kollision

Zunächst wird der Punkt $p$ der Box berechnet, der sich am nähesten am Zentrum der Sphere befindet.

$p.x = \max{(minX(b), \min{(s.position.x, maxX(b)})} \\ p.y = \max{(minY(b), \min{(s.position.y, maxY(b))})} \\ p.z = \max{(minZ(b), \min{(s.position.z, maxZ(b))})}$

Mit diesem Punkt wird auf Point-Sphere-Kollision geprüft.

Sphere-Sphere-Kollision

Zwei Spheres überschneiden sich, wenn die euklidische Distanz zwischen ihren Mittelpunkten kleiner ist als die Summe ihrer Radien.

Rechenaufwand der Kollisionsarten

Zur Berechnung des maximalen oder minimalen Wertes einer Box in einer Dimension (z. B. $maxX$) muss über alle acht Vertices der Box iteriert werden. Dies geschieht in jedem Render-Aufruf. Im Laufe des Projektes hat sich gezeigt, dass es zu einer drastischen Reduzierung der FPS kommt, wenn der Laser durch eine Box approximiert wird. Durch eine Approximation über Punkte, die nahe genug aneinanderliegen, kann die Frame-Rate bei 30 FPS erhalten werden. Daher ist diese Art der Annäherung auch für die Rakete übernommen worden.

Interaktion nach der Kollision

Die Interaktionen zwischen den Objekten in der Szene geschehen, ausgenommen von dem Verhalten der Bots, ausschließlich durch das Erkennen einer Kollision. Fliegt beispielsweise der Spieler mit seinem Raumschiff durch ein Item, so wird in dem Render-Aufruf die Kollision der zugehörigen Hit-Objekte erkannt. Anschließend wird Rückmeldung an den Spieler gegeben, dass er durch ein Item geflogen ist und von welchem Typ dieses ist. Um die weitere Informationsverarbeitung kümmert sich der Spieler. Auch dem Item wird Rückmeldung gegeben, sodass eine Methode getriggert wird, die das Item aus der Szene entfernt. Auf entsprechende Art wird bei jeder erkannten Kollision jedem Kollisionspartner mitgeteilt, dass und womit er kollidiert ist. Die entsprechenden Methoden, die an den Kollisionspartnern aufgerufen werden, hängen dabei von dem jeweils anderen an der Kollision beteiligten Objekt ab.