2D Kollisionserkennung - Teil 2: Rechteck vs Rechteck (AABB vs AABB)

21.07.2016 von Tim , zuletzt bearbeitet am 21.07.2016

In diesem Tutorial beschäftigen wir uns mit der Kollision zwischen zwei Rechtecken, welche parallel zu den Achsen liegen (Axis Aligned Bounding Box, kurz AABB). Diese Form der Kollisionserkennung ist recht schnell und wird deshalb oft auch genutzt um vorab festzustellen, welche Körper miteinander kollidieren könnten, um dann genauere Tests durchzuführen. Wollt ihr die Kollision zwischen Rechtecken erkennen, die nicht parallel zu den Achsen sind (OBB vs OBB), benötigt ihr ein anderes Verfahren z.B. SAT oder GJK. Nicht rechteckige Körper oder rotierte Körper können oft nur grob von einem AABB umschlossen werden:

AABB Rechteck Beispiel

Wie man sieht eignet sich ein AABB in diesem Fall nur um einen Vorabtest durchzuführen, da die Form der Schachfigur mit dem Rechteck nur sehr grob umschlossen werden kann. Bei diesen Objekten kann es aber trotzdem sinnvoll sein erst mal einen AABB Kollisions Test durchzuführen und falls eine Kollision vorliegt, mit aufwendigeren Algorithmen zu prüfen ob wirklich eine Kollision vorliegt. So muss man die rechenhungrigen Algorithmen nicht auf Objekte anwenden, bei denen eine Kollision schon vorher ausgeschlossen werden kann.

Handelt es sich bei euren Objekten ohnehin um Rechtecke, welche parallel zu den Achsen liegen (z.B. wen eure Welt aus rechteckigen Tiles besteht), ist ein AABB Kollision Test meist die richtige Wahl und liefert exakte Ergebnisse.

Ich gehe im Folgenden davon aus, dass das Rechteck mit einer Position, Breite und Höhe beschrieben ist. Der Ursprung liegt in den Beispielen in der Mitte des Rechtecks. Das Koordinatensystem hat eine getauschte Y-Achse, wie es in vielen Frameworks üblich ist. Das bedeutet der Y-Wert wird nach unten hin größer statt kleiner. Wen ihr ein anderes Koordinatensystem benutzt, müssen die hier verwendeten Beispiele etwas angepasst werden. Dies sollte aber kein Problem sein wen ihr die Funktionsweise der Kollisionsprüfung erst einmal verstanden habt.

Wenn eine Kollision vorliegt müssen folgende Bedingungen erfüllt sein:

  • Der untere Rand von ObjA muss größer oder gleich dem oberen Rand von ObjB sein
  • Der obere Rand von ObjA muss kleiner oder gleich dem unteren Rand von ObjB sein
  • Der linke Rand von ObjA muss kleiner oder gleich dem rechten Rand von ObjB sein
  • Der rechte Rand von ObjA muss größer oder gleich dem linken Rand von ObjB sein

Zur Veranschaulichung seht ihr unten ein Bild, welches einmal den Fall einer Kollision und einmal den Fall, wen keine Kollision vorliegt, zeigt. Es hilft auf jeden Fall die Bedingungen für beide Fälle mal durchzugehen und zu versuchen nachzuvollziehen warum im ersten Fall eine Kollision vorliegt und im zweiten nicht. Dabei müsst ihr beachten das die Bedingungen für den Fall gelten das die Y-Koordinaten nach unten hin größer werden. Im 1. Fall sind alle 4 Bedingungen erfüllt und es liegt eine Kollision vor. Im 2. Fall ist die letzte Bedingung nicht erfüllt, der rechte Rand ist nämlich kleiner als der linke Rand des zweiten Objektes. Deshalb liegt im 2. Fall keine Kollision vor.

 

Vergleic zwischen einer AABB Kollison und keiner Kollision

 Eine mögliche Implementierung könnte so aussehen:

private boolean isColliding(AABB objA, AABB objB) {			
	if (objA.getBottom() >= objB.getTop() &&
        objA.getTop() <= objB.getBottom() &&
        objA.getLeft() <= objB.getRight() &&
        objA.getRight() >= objB.getLeft()) {
		return true;
	}            
	return false;		
}

Source Code:

Kollision Source Code auf Github