Kollisionserkennung in Spielen: AABB, Kreise und Raster

Kurz: Kollisionserkennung prüft, ob sich zwei Objekte berühren; einfache Formen wie Rechtecke und Kreise sind schnell berechnet, ein Raster spart Vergleiche bei vielen Objekten.

Genauer: Spielfiguren, Geschosse und Wände dürfen sich nicht einfach durchdringen. Dazu prüft das Spiel in jedem Frame, ob sich Formen überschneiden. Pixelgenaue Vergleiche wären zu langsam, also nutzt man vereinfachte Hüllen (Hitboxen).

Im Detail

Rechteck gegen Rechteck (AABB)

AABB steht für „Axis-Aligned Bounding Box“, ein Rechteck ohne Drehung. Zwei Rechtecke überlappen, wenn sie sich auf beiden Achsen überlappen:

function treffen(a, b) {
  return a.x < b.x + b.w &&
         a.x + a.w > b.x &&
         a.y < b.y + b.h &&
         a.y + a.h > b.y;
}

Sehr schnell und für viele 2D-Spiele ausreichend.

Kreis gegen Kreis

Zwei Kreise berühren sich, wenn der Abstand ihrer Mittelpunkte kleiner ist als die Summe der Radien. Man vergleicht Quadrate (ohne Wurzel):

const dx = a.x - b.x, dy = a.y - b.y, r = a.r + b.r;
return dx*dx + dy*dy < r*r;

Kreis gegen Rechteck: den nächsten Punkt des Rechtecks zum Kreismittelpunkt bestimmen und dessen Abstand prüfen.

Viele Objekte: Broad Phase und Narrow Phase

Alle Paare zu prüfen kostet n² Vergleiche. Eine Broad Phase sortiert zuerst grob: Raster (Spatial Hash) teilt die Welt in Zellen, geprüft wird nur innerhalb derselben oder benachbarter Zellen. Auch Quadtrees (2D) und Octrees (3D) teilen den Raum hierarchisch. Danach prüft die Narrow Phase genau (AABB, Kreis, Polygon).

Reaktion und Fallstricke

Nach einer Kollision wird das Objekt aus der Wand herausgeschoben (kleinste Überlappung) oder prallt ab. Tunneling: Sehr schnelle Objekte springen in einem Frame durch dünne Wände; Abhilfe sind kleinere Zeitschritte oder Strahltests (Raycasts) entlang der Bewegung. Für gedrehte Formen nutzt man SAT (Separating Axis Theorem). Physik-Engines (Box2D, Matter.js, Rapier) übernehmen vieles davon.

Siehe auch: Game Loop und Deltazeit, Kollision, Game Engine