In diesem Artikel geht es um 2D-Kollisionserkennung, also die Überprüfung, ob sich zwei Objekte berühren oder schneiden. Für Anwendungen, bei denen dies eine zentrale Rolle spielt, empfiehlt sich auch ggf. der Einsatz einer Physik-Engine. Eine Physik-Engine kann Kollisionen nicht nur sehr effizient erkennen, sondern auch physikalisch korrekt darauf reagieren.

Erkennung anhand geometrischer Figuren

Häufig werden Spielobjekte durch einfache geometrische Formen (Kreise, Rechtecke, Polygone) angenähert, da eine Kollisionserkennung für solche Formen einfacher bzw. schneller durchgeführt werden kann. Dabei nimmt man in Kauf, dass die physikalische Form des Objekts von seiner sichtbaren Form abweicht. Im Folgenden werden Kollisionstests für zweidimensionale Formen behandelt.

Kollision zwischen zwei achsenausgerichteten Rechtecken

Die Prüfung einer Kollision zweier achsenausgerichteten (nicht rotierten) Rechtecken kann sehr effizient durchgeführt werden. Aufgrund der daraus resultierenden hohen Geschwindigkeit kann diese Prüfung komplexeren Prüfungen voran gestellt werden, um zu testen, ob zwei Objekte nah genug aneinander sind, damit eine Kollision möglich ist. Dazu testet man die sie umgebenden Rechtecke (Bounding Rectangles) auf Kollision.

Wenn mindestens eine Kante eines Rechtecks ein anderes Rechteck überschneidet, dann liegt eine Kollision vor. Es werden die Positionen der einzelnen Eckpunkte der Rechtecke benötigt. In den Implementierungsbeispielen werden Rechtecke durch die Position der linken oberen Ecke, die Breite und die Höhe beschrieben.

bool rectangleCollision(const Vector& position1, float width1, float height1,
                        const Vector& position2, float width2, float height2)
{
    return position1.x < position2.x + width2  &&
           position2.x < position1.x + width1  &&
           position1.y < position2.y + height2 &&
           position2.y < position1.y + height1;
}

bool rectangleCollision(Vector position1, float width1, float height1,
                        Vector position2, float width2, float height2)
{
    return position1.x < position2.x + width2  &&
           position2.x < position1.x + width1  &&
           position1.y < position2.y + height2 &&
           position2.y < position1.y + height1;
}

def rectangleCollision(position1, width1, height1, position2, width2, height2):
    return position1[0] < position2[0] + width2  and
           position2[0] < position1[0] + width1  and
           position1[1] < position2[1] + height2 and
           position2[1] < position1[1] + height1

boolean rectangleCollision(float[] position1, float width1, float height1,
                           float[] position2, float width2, float height2) {
    return position1[0] < position2[0] + width2  &&
           position2[0] < position1[0] + width1  &&
           position1[1] < position2[1] + height2 &&
           position2[1] < position1[1] + height1;
}

Kollision zwischen zwei Kreisen

Wenn die Distanz zwischen den Mittelpunkten zweier Kreise kleiner ist als die Summe ihrer Radien, so liegt eine Kollision vor. Also benötigen wir zum Prüfen der Kollision die Positionen und Radien der beiden Kreise. Dabei rechnen wir mit Hilfe des Satz des Pythagoras die Distanz zwischen den beiden Kreisen aus und prüfen zum Schluss, ob diese kleiner ist als die Summe beider Radien.

bool circleCollision(const Vector& position1, float radius1,
                     const Vector& position2, float radius2)
{
    const float dx = position1.x - position2.x;
    const float dy = position1.y - position2.y;
    
    // Langsame Version, benötigt Wurzel:
    // return sqrt(dx * dx + dy * dy) <= radius1 + radius2;
    
    // Schnelle Version, vergleicht die Quadrate:
    const float radiusSum = radius1 + radius2;
    return dx * dx + dy * dy <= radiusSum * radiusSum;
}

bool circleCollision(Vector position1, float radius1,
                     Vector position2, float radius2)
{
    float dx = position1.x - position2.x;
    float dy = position1.y - position2.y;
    
    // Langsame Version, benötigt Wurzel:
    // return (Math.Sqrt(dx * dx + dy * dy) <= Convert.ToDouble(radius1) + Convert.ToDouble(radius2));
    
    // Schnelle Version, vergleicht die Quadrate:
    float radiusSum = radius1 + radius2;
    return dx * dx + dy * dy <= radiusSum * radiusSum;
}

def circleCollision(position1, radius1, position2, radius2):
    dx = position1[0] - position2[0]
    dy = position1[1] - position2[1]
    
    # Langsame Version, benötigt Wurzel:
    # return math.sqrt(dx * dx + dy * dy) <= radius1 + radius2
    
    # Schnelle Version, vergleicht die Quadrate:
    radiusSum = radius1 + radius2
    return dx * dx + dy * dy <= radiusSum * radiusSum

boolean circleCollision(float[] position1, float radius1,
                        float[] position2, float radius2) {
    float dx = position1[0] - position2[0];
    float dy = position1[1] - position2[1];
    
    // Langsame Version, benötigt Wurzel:
    // return Math.sqrt(dx * dx + dy * dy) <= radius1 + radius2;
    
    // Schnelle Version, vergleicht die Quadrate:
    float radiusSum = radius1 + radius2;
    return dx * dx + dy * dy <= radiusSum * radiusSum;
}

Kollision zwischen zwei Geraden

Auch wenn eine Kollisionsabfrage zwischen zwei Geraden für ein Spiel eher unüblich ist, werden wir diesen Fall betrachten, denn die Vorgehensweise können wir auch für andere Kollisionsabfragen verwenden. Falls zwei Geraden nicht parallel zueinander sind, so schneiden sie sich irgendwo, und somit liegt eine Kollision vor. In diesem Beispiel werden die Geraden durch zwei Punkte beschrieben (eine Darstellung mit einem Punkt und einer Richtung ist natürlich ebenso möglich). Angenommen zwei Punkte einer Geraden sind bekannt, so ist es möglich, einen beliebigen Punkt auf ihr wie folgt zu beschreiben:

§P_a = A_1 + u_a(A_2 - A_1)§

Wenn man nun die zwei Geraden mithilfe dieser Formel beschreibt und sie gleichsetzt (§P_a = P_b§), bekommt man folgende Gleichungen für §x§ und §y§ der Punkte §P_a§ und §P_b§:

§

\begin{align} x_{A_1} + u_a(x_{A_2} - x_{A_1}) & = x_{B_1} + u_b(x_{B_2} - x_{B_1}) \\ y_{A_1} + u_a(y_{A_2} - y_{A_1}) & = y_{B_1} + u_b(y_{B_2} - y_{B_1}) \end{align} §

Diese Gleichungen werden nun nach §u_a§ und §u_b§ aufgelöst:

§

\begin{align} u_a & = \frac{(x_{B_2} - x_{B_1})(y_{A_1} - y_{B_1}) - (y_{B_2} - y_{B_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \\ u_b & = \frac{(x_{A_2} - x_{A_1})(y_{A_1} - y_{B_1}) - (y_{A_2} - y_{A_1})(x_{A_1} - x_{B_1})}{(y_{B_2} - y_{B_1})(x_{A_2} - x_{A_1})-(x_{B_2} - x_{B_1})(y_{A_2} - y_{A_1})} \end{align} §

Man beachte nun die Nenner der beiden Gleichungen, denn sie sind identisch. Wenn nun der Nenner gleich Null ist, so sind §u_a§ und §u_b§ undefiniert, also sind die beiden Geraden parallel zueinander, und somit liegt keine Kollision vor. Beim Rechnen mit Fließkommazahlen muss man jedoch beachten, dass ein Vergleich mit Null nicht empfehlenswert ist, da es zu Ungenauigkeiten kommt. Darum sollte ein kleiner Grenzwert ε (im Code als Konstante EPSILON dargestellt) gewählt werden, unterhalb dessen die Geraden als parallel angenommen werden. Ein möglicher Wert wäre z.B. §10^{-8}§.

bool lineCollision(const Vector& a1, const Vector& a2,
                   const Vector& b1, const Vector& b2)
{
    const float denom = (b2.y - b1.y) * (a2.x - a1.x) -
                        (b2.x - b1.x) * (a2.y - a1.y);
    return abs(denom) > EPSILON;
}

bool lineCollision(Vector a1, Vector a2,
                   Vector b1, Vector b2)
{
    float denom = (b2.y - b1.y) * (a2.x - a1.x) -
                  (b2.x - b1.x) * (a2.y - a1.y);
    return Math.Abs(denom) > EPSILON;
}

def lineCollision(a1, a2, b1, b2):
    denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
            (b2[0] - b1[0]) * (a2[1] - a1[1])
    return abs(denom) > EPSILON

boolean lineCollision(float[] a1, float[] a2,
                      float[] b1, float[] b2)
{
    float denom = (b2[1] - b1[1]) * (a2[0] - a1[0]) -
                  (b2[0] - b1[0]) * (a2[1] - a1[1]);
    return Math.abs(denom) > EPSILON;
}

Kollision zwischen zwei Strecken

Die Kollisionsabfrage zwischen zwei Strecken ist wie bei den Geraden nicht so oft vertreten in Spielen, allerdings gibt es immer mal wieder Fälle bei denen es nötig ist. Die Vorgehensweise ist wie bei den Geraden, nur mit einem kleinen Zusatz, denn Strecken habe einen Start- und Endpunkt, deswegen werden Strecken auch als Geradenabschnitt bezeichnet. Es wird also wider überprüft ob die beiden Strecken parallel zu einander sind, wenn dies der Fall ist liegt keine Kollision vor. Falls dies nicht zutrifft muss noch überprüft werden ob die Strecken sich in den angegebenen Abschnitten schneiden. Nur wenn das zutrifft liegt eine Kollision vor.