Teil 15: Kollisionsabfrage

Wir werden uns bei der Kollision auf einfache Bounding Rectangle Kollision beschränken. Das bedeutet, dass wir unsere Objekte mit einem Rechteck umschliessen, und diese Rechtecke gegeneinander testen.

Hier seht ihr, was genau man sich unter Bounding Rects vorstellen muss:

ProjektE Kollisionsbeispiel

Der Gleiter wird von dem roten Rechteck umschlossen, das Schrottteil vom grünen. Und, das ist nicht zu übersehen, die beiden überschneiden sich – für unser Spiel könnte das bedeuten, dass der Gleiter jetzt Schaden nehmen wird und der Schrott in einer grossen Explosion zu tausend Teilen zerfällt.

Was benötigen wir also? Zunächst einmal die Koordinaten der beiden Objekte. Diese haben wir schon als m_fX, m_fY, m_fZ in CEntity festgehalten. Zusätzlich benötigen wir die Breite und Höhe eines Objekts. Hierfür legen wir zusätzlich zwei Variablen WORD m_usWidth; und WORD m_usHeight; in CEntity an. Diese Variablen werden in unseren bisherigen beiden Spielobjekten im Constructor mit Werten gefüllt (CGlider: 100/42, CScrap: 50/50 und 25/25).

Mit Kenntnis dieser Rechtecke können wir diese gegeneinander auf Überlappung testen. Da sie nicht rotiert sind, ist das Verfahren hierfür relativ einfach. Zunächst nehmen wir an, dass unsere Rechtecke jeweils durch den linken oberen und den rechten unteren Punkt gegeben sind. Mit unseren Variablennamen wäre ein Rechteck damit definiert durch die zwei Punkte (m_fX, m_fY) und (m_fX + m_usWidth, m_fY + m_usHeight) (weil die Rechtecke immer in der XY-Ebene liegen, lasse ich Z weg). Weil das etwas mühsam zu schreiben wäre, benenne ich die linke obere Ecke des ersten Rechtecks einfach mal als (x1,y1) und die rechte untere Ecke mit (x2,y2). Ebenso heissen die Ecken des zweiten Rechtecks (x3,y3) und (x4,y4). Durch die Konstruktion wissen wir also schon: x1<x2, x3<x4, y1<y2, y3<y4. Normalerweise stellt man die Überlappung fest, indem man prüft, ob eine Ecke des ersten Rechtecks sich im zweiten Rechteck befindet, und umgekehrt. Als Pseudocode sähe das etwa so aus:

WENN ( ( x3 < x1 < x4 ) UND ( y3 < y1 < y4 ) )
ODER ( ( x3 < x2 < x4 ) UND ( y3 < y2 < y4 ) )
ODER ( ( x1 < x3 < x2 ) UND ( y1 < y3 < y2 ) )
ODER ( ( x1 < x4 < x2 ) UND ( y1 < y4 < y2 ) ) DANN
 Überlappung

Da durch unsere festgelegte Anordnung der Koordinaten einige dieser Bedingungen sowieso erfüllt sind, lässt sich diese Bedinung vereinfachen:

WENN ( x1 < x4 ) UND ( x3 < x2 ) UND ( y1 < y4 ) UND ( y3 < y2 ) DANN
 Überlappung

Zum besseren Verständnis ist es vielleicht ratsam, sich einfach mal zwei Rechtecke in unterschiedlichen Situationen aufzuzeichnen und daran die Bedingung zu überprüfen.

Die Bedingung implementieren wir ebenfalls in einer Funktion in CEntity. Wir nennen sie bool CollidesWith( CEntity* pEntity );. Als Parameter wird ein zweites Objekt übergeben, gegen das getestet werden soll. Die Funktion prüft die oben genannte Bedingung anhand der Attribute m_fX, m_fY, m_usWidth, m_usHeight der beiden Entities und gibt “true” zurück, wenn eine Kollision erkannt wurde.

Den Test Objekt 1 gegen Objekt 2 wird eine Funktion in CEntityManager übernehmen (CEntityManager::TestCollisions()). Diese durchläuft einfach alle Objekte in zwei verschachtelten Schleifen und ruft jeweils den Test gegeneinander auf. Findet eine Kollision statt, muss nun nur noch darauf reagiert werden. Hierzu fügen wir eine letzte neue Funktion in CEntity ein und nennen sie HandleCollision( CEntity* pEntity );. Dass jedes Objekt seine Kollisionen selbst behandelt hat den Vorteil, dass es sich nur um die Kollisionen kümmern muss, die es auch interessiert. Normalerweise kollidieren Feinde z.B. nicht mit dem Weltraumschrott und können auch keine Powerups aufnehmen. Das bleibt dem Gleiter vorbehalten. Stattdessen verliert ein Gegner aber sehr wohl Energie, wenn er von einem Schuss des Gleiters getroffen wurde.

Eine entsprechende Abfrage kann z.B. anhand der Enumeration stattfinden, die ja eh beim Erstellen an die EntityFactory weitergegeben wird. Die Entität müsste also nur noch ihre eigene ID kennen – diese übergeben wir einfach beim Aufruf der Initialize Methode.

Da sich heute ‘ne Menge geändert hat, poste ich hier den gesamten Code. Wer ein bisschen üben will sollte auf jeden Fall versuchen, die hier besprochenen Änderungen selbst zu implementieren und dann nur kurz mit dem Code vergleichen. Zusätzlich gibt’s im aktuellen Paket eine kleine Bitmap-Font-Klasse im Unterprojekt gui.

Wir benutzen hier zum Kollisionstest eine “Brute Force” Methode – jedes Objekt wird gegen jedes Objekt getestet, ohne dabei in Anbetracht der Performance von vornherein Objekte auszuschliessen, die nicht kollidieren können. Eine Optimierung wäre z.B., nur die Objekte zu testen, die Aufgrund ihres z-Werts nah genug beeinander liegen. Generell könnte man, anstatt alle Objekte mit beliebigen z-Werten in einer Liste zu halten, die Szene in 4 Ebenen aufteilen, die für ein solches Spiel auch locker reichen sollten, und nur die ersten Ebenen testen. Um das Kollisionsergebnis zu optimieren, könnte man weiterhin das Rechteck auf einen kleineren Bereich des Sprites einschränken oder anstelle von Rechtecken Ellipsoiden verwenden. Die Möglichkeiten sind da vielfältig.

Im nächsten Teil werden wir dann auf diesen Check mal die entsprechende Antwort implementieren. Hierzu wird in HandleCollision einfach ein switch eingefügt, der testet, mit was für einer Art von Objekt wir kollidiert sind. Kollidiert also bspw. der Gleiter mit einem (grossen) Schrottteil, nimmt der Gleiter Schaden. Umgekehrt wird der Schrott sich in seiner Kollisionsbehandlung bei Zusammenstoss mit dem Gleiter selbst zerstören und eine Explosion in der Szene platzieren. Ebenso verhält es sich mit Powerups. Kollidiert der Gleiter mit einem solchen, erhält er den entsprechenden Bonus. Umgekehrt wird das Powerup nach Kollision mit dem Gleiter zerstört.

Weiterführende Links

Absolut lesenswert ist die “Enginuity” Serie von Richard Fine auf gamedev.net. Hier findet ihr Informationen über den Aufbau einer soliden Game-Engine.

Download

2 Comments

Cancel

  1. Heyho matt,
    das war mal ein Tutorial von dem ich echt was gelernt hab. Hast du vor das Tutorial noch weiter zu schreiben, oder ist es an dieser Stelle einfach vorbei???

    Mfg androphinx

    PS: Antwort einfach hier rein, ich gucke demnächst wieder vorbei…

    PPS: Du solltest das Tutorial irgendwie mal veröffentlichen, ist echt das beste zu dem Thema was ich je gesehen habe.

  2. Das Tutorial habe ich vor fünf Jahren geschrieben, eine Fortsetzung wird es mangels Zeit leider eher nicht geben.