Einfache Kollisionsbehandlung (Collision-Response)

Kollisionen sind für Spiele extrem wichtig und werden praktisch in jedem Spiel benötigt. In einigen Spielen wird lediglich die Information benötigt, ob ein Schuß einen Gegner getroffen hat (z.B. in einem 2D Top-Down-Shooter), in anderen werden noch mehr Informationen benötigt. Immer dann, wenn eine Kollision dazu verwendet werden soll, daß Objekte nicht überlappen wird es ein wenig komplizierter, da einige Dinge beachtet werden müssen.

Dieser Artikel versucht nun etwas Licht ins Dunkel zu bringen und einen einfachen, wenn auch nicht physikalisch vollständig korrekten Ansatz aufzuzeigen. Dabei werden Rotationen, Reibung und ähnliche Dinge außer Acht gelassen, da diese häufig nicht benötigt werden.

Einsteiger machen oft den Fehler und unterschätzen die Kollisionsbehandlung, insbesondere, da die Kollisionsprüfung auf den ersten Blick sehr einfach ist. Mehrfachkollisionen und Kollisionslösungen, die zu neuen Kollisionen führen, sowie stapeln von Objekten führen schnell zu unüberwindbaren Hindernissen.

Erstmal möchte ich ein paar grundsätzliche Dinge anmerken. In diesem Artikel wird es keinen Code geben, sondern ich erkläre, wie man selbst eine Lösung erarbeiten kann. Dies ist extrem wichtig für das Verständnis. Aber auch wer nicht selbst Code erarbeiten möchte, der hat die Möglichkeit, das kostenlose Kollisionssystem der starLiGHT.Engine zu verwenden. Dieses hier beschriebene Konzept und noch viel mehr sind dort enthalten.

Fangen wir mit einer ganz einfachen Form der Kollisionsbehandlung an, wie sie oft von Einsteigern erdacht und durchgeführt wird. Wir prüfen mit Rectangle.Intersect ob zwei Rechtecke überlappen.

Rectangle.Intersect ohne Überlappung

Alle Objekte, hier zwei einfache, grüne Rechtecke werden regelmäßig (in der Update Methode) mittels Rectangle.Intersect auf Kollision überprüft. Im Bild rechts würde diese Methode false zurückliefern. Sobald die beiden Rechtecke überlappen, Rectangle.Intersect gibt also true zurück, wird die Bewegung einfach rückgängig gemacht oder das Rechteck wird einfach gestoppt. Wer dies testet wird schnell bemerken, daß dieser Ansatz in keinster Weise annehmbare Ergebnisse liefert. Die Objekte bleiben einfach bei einer Kollision stehen und können sich nicht mehr bewegen, da sonst eine neue Kollision auftritt, die wieder zu einem sofortigen Stop führen würde.

Kollisionslösung Rectangle.IntersectDer nächste Ansatz, der dann oft ausprobiert wird, und schon ein wenig besser ist, ist der im folgenden beschriebene Ansatz. Wir haben zwei Rechtecke, die kollidieren (rot). Rechteck A (das linke, obere) bewegt sich in Richtung des grünen Pfeils. Sobald Rectangle.Intersect true zurückliefert, bewegen wir das Rechteck so lange in kleinen Schritten rückwärts (gelber Pfeil), bis keine Kollision mehr erkannt wird. Dies ist sehr einfach in einer Schleife umzusetzen: Bewegungsvektor invertieren und durch Anzahl der Schritte teilen. Rechteck um diesen neuen Vektor zurück bewegen und auf Kollision prüfen. Liegt keine Kollision mehr vor, dann haben wir die Abbruchbedingung für die Schleife.

Dieser Ansatz ist schon deutlich besser und liefert auch annähernd korrekte Ergebnisse. Er hat aber auch ein paar Nachteile:

  1. Der Rechenzeitverbauch ist nicht zu unterschätzen, da einfach in kleinen Schritten versucht wird, eine Kollision aufzulösen.
  2. Wir erhalten kein exaktes Ergebnis, da die Penetrationstiefe nicht bekannt ist. Wir schieben das Rechteck einfach so lange zurück, bis keine Kollision mehr auftritt, dadurch entstehen Lücken, da die Schrittweite nicht 100% passen wird.
  3. Das Rechteck wird anfangen zu zittern. Nachdem die Kollision aufgelöst wurde, wird das Rechteck wieder minimal weiter bewegt (aufgrund der Lücke aus Punkt 2). Diese führt zu einer erneuten Kollision, die wieder aufgelöst wird. Dadurch entsteht eine Lücke in einer anderen Größe. Das Rechteck springt also zwischen mehreren Zuständen hin und her, was sich als Zittern äussert.
  4. Mehrfachkollisionen führen zu einer Endlosschleife. Wenn Rechteck A nicht so bewegt werden kann, daß die Kollision aufgelöst wird, ohne eine neue zu erzeugen, dann erhalten wir eine Endlosschleife.

Leider funktioniert dieser Ansatz auch nicht anständig. Wir benötigen also weitere Informationen um die Kollision korrekt aufzulösen. Wir benötigen, wie im vorherigen Abschnitt vielleicht schon klar geworden ist, die Penetrationstiefe. Dies ist die Überlappung, die die kollidierenden Rechtecke haben. Sehr gut geeignet ist der sogenannte MTV (Minimum Translation Vector). Dies ist der Vektor, der die kürzeste Strecke und Richtung angibt, die benötigt wird, um eine Kollision aufzulösen. Ich empfehle für den Einsteiger, diesen mittels des Separating Axis Theorems (SAT) zu ermitteln. Wie SAT genau funktioniert, lasse ich in diesem Artikel aus und verweise auf den verlinkten Artikel, da dies sonst den Umfang sprengen würde. Ich werde jedoch zu einem späteren Zeitpunkt sicherlich noch mal auf SAT zurück kommen und dieses genauer erklären und auch eine Lösung speziell für XNA präsentieren.

Wunderbar! Wir haben SAT implementiert, eine Kollision erkannt und können die Rechtecke jetzt dank des MTV exakt so weit auseinander schieben, wie es notwendig ist, um die Kollision aufzulösen. Dies funktioniert auch problemlos. Scheinbar, wie wir im folgenden feststellen werden. Wir sind nämlich noch nicht fertig und es gibt noch einige Stolpersteine.

Es macht Sinn den Objekten, die kollidieren können ein Flag mitzugeben, und zwar eines, daß beschreibt, ob das Objekt statisch ist oder nicht. Statische Objekte können sich nicht bewegen und stehen immer still an einer Stelle. Dies ist eine nette Optimierungsmöglichkeit: Zwei statische Objekte müssen selbstverständlich nicht auf Kollision geprüft werden, da diese sich nicht bewegen und somit auch nicht kollidieren können. Bei einem Breakout-Spiel zum Beispiel sind am oberen Bildschirmrand (oder je nach Spiel auch woanders) eine Menge Steine, die alle statisch sind. Diese sollen verschwinden, wenn der Ball sie trifft, aber können niemals untereinander kollidieren. Werden diese alle auf statisch gestellt, dann können wir uns durch diese Optimierung schnell einige hundert oder gar tausend Kollisionsprüfungen sparen.

Wir müssen also nur prüfen, wenn eines oder beide der Objekte nicht statisch ist. Fangen wir mit dem etwas einfacheren Fall an: Ein Objekt ist beweglich, daß andere ist statisch. Die beiden Objekte kollidieren. Die Auflösung der Kollision erfolgt exakt so, wie oben beschrieben.

Kollisionsauflösung mit MTVDer zweite Fall ist ein wenig komplizierter. Beide Objekte sind beweglich und kollidieren. Die Bewegungsrichtung wird durch die grünen Pfeile angezeigt. Der MTV ist die gelbe, kleine Linie, die – um einfacher rechnen zu können – eine Länge von 2 hat.

Der naive Ansatz wäre nun, in der Schleife die auf Kollision überprüft, das Rechteck, daß kollidiert einfach um den MTV zu verschieben und somit die Kollision aufzulösen, also genau so, wie es bei der Kollision eines beweglichen mit einem statischen Objekt gemacht wird. Dies führt zu der im mittleren Bild dargestellten Situation (grüne Rechtecke). Das linke Rechteck wurde um zwei Einheiten nach links verschoben. Dieses Ergebnis ist jedoch falsch. Da sich beide Objekte bewegen, treffen sich diese ja in der Mitte und um die Kollision aufzulösen müssten beide um die Hälfte, also jeweils um eine Einheit in entgegengesetzte Richtungen verschoben werden. Dies würde zu dem korrekten (bzw. korrekteren Ergebnis) in der unteren Darstellung führen.

Der letzte Punkt, den wir nun noch beachten müssen sind die sogenannten Mehrfachkollisionen. Diese können auf zwei Arten entstehen:

  1. Ein Rechteck trifft während eines Updates auf zwei oder mehr andere Rechtecke
  2. Bei der Auflösung einer Kollision entsteht eine neue Kollision

MehrfachkollisionEin guter Ansatz um dies zu lösen ist, die Kollisionen nicht isoliert zu betrachten, sondern alle Kollisionen gemeinsam. Den Ansatz, den ich dafür in der starLiGHT.Engine gewählt habe, sind sogenannte Kollisionspaare. Diese stellen gleichzeitig noch eine gute Optimierungsmöglichkeit dar: Normalerweise wird geprüft, ob Objekt A mit Objekt B kollidiert und später unter Umständen noch mal ob Objekt B mit Objekt A kollidiert. Durch die Kollisionspaare lassen sich solche Dinge leicht ausfiltern, wenn man dies bei der Gleicheitsprüfung berücksichtigt und eine entsprechende Liste verwendet.

Dies ist jedenfalls ein sehr einfaches, aber extrem effektives Konzept. In einem ersten Schritt werden alle Kollisionen in der Szene ermittelt und die beiden Objekte, die kollidieren werden als Paar in einer Liste abgelegt. In der starLiGHT.Engine übernimmt dies der PairManager, der im verlinkten Artikel etwas genauer beschrieben ist. Erst wenn alle Paare erkannt wurden, wird die Kollisionsauflösung durchgeführt. Dafür wird die Liste aller Paare abgearbeitet. In der rechten Abbildung wird eine mögliche Mehrfachkollision dargestellt. In diesem Fall würden drei Kollisionspaare gebildet, das rote Rechteck bildet jeweils mit einem grünen Rechteck ein Paar. Würden wir nun die drei dabei entstehenden MTV auf das rote Rechteck anwenden, dann wäre dieses zu weit verschoben. Das Problem ist hierbei die Kollision mit dem Rechteck rechts unten. Zur vollständigen Auflösung der Kollision wären die beiden anderen MTV vollkommen ausreichend. Die Herausforderung liegt jetzt also darin, dies zu ermitteln. Dies ist glücklicherweise nicht sonderlich schwierig. Wir betrachten einfach einfach alle Achsen des MTV separat und speichern den jeweils größten Wert. Erst nachdem wir dies für alle Kollisionspaare durchgeführt haben, wenden wir diese neu entstandenen MTV auf die zugehörigen Rechtecke an. Damit filtern wir effektiv und einfach den zuvor beschriebenen Fall aus.

Bleibt nur noch ein letzter Punkt, um die Kollision aufzulösen. Unter Umständen kann es passieren, daß durch die Auflösung einer Kollision eine neue Kollision entsteht. Dies führt zu unschönen und vor allem falschen Ergebnissen. Zum Glück ist auch dies relativ einfach zu lösen. Dazu zählen wir einfach die Anzahl der Kollisionen und packen alle zuvor beschriebenen Schritte in eine Schleife, die so lange ausgeführt wird, bis keine Kollision mehr gezählt wurde. Um Endlosschleifen zu verhindern, zählen wir noch die Anzahl der Schleifendurchläufe und legen ein Maximum fest. Sinnvoll sollte hier ein Wert von ca. 5-10 maximalen Durchläufen sein.

Wir haben in diesem Artikel gelernt, wie wir Kollisionen und Mehrfachkollisionen korrekt und einfach auflösen können. Die meisten Fallen, in die Anfänger oft tappen, wurden beschrieben und Lösungen aufgezeigt. Rotationskräfte und Reibung, sowie Masseverteilung und Impulsübertragungen wurden jedoch nicht berücksichtigt. Diese teils sehr fortgeschrittenen Themen würden dazu führen, daß die wichtigsten Teile einer Physik-Engine entwickelt werden müssten. Ich empfehle hier – da dies eine extrem aufwendige Aufgabe ist – die Verwendung einer fertigen Physik-Engine wie die in der starLiGHT.Engine.

Advertisements

Veröffentlicht am 27.01.2011, in Grundlagen, Kollision, Mini-Tutorial, XNA. Setze ein Lesezeichen auf den Permalink. 6 Kommentare.

  1. RaverGames

    Hi Glatzmann

    vorab erstmal richtig geiler Blog!

    Und jetzt mein richtiger Kommentar:

    richtig cooles Tutorail die Bilder sind einfach aber Perfekt!

    Ich hoffe das diese Blog lange bestehen bleibt
    PS:

    wird es hier auch 3d Tutorials geben?

    • Vielen Dank für die netten Worte… Ich höre natürlich gerne, wenn die Arbeit nicht umsonst ist, und jemand das wertschätzt und vor allem, wenn es jemandem hilft.

      Ja, es wird hier auch 3D-Tutorials geben. Wann und in welcher Form die kommen werden, kann ich allerdings noch nicht sagen, da ich mir darüber selber noch nicht im klaren bin…

  2. Hi 😉

    Netter Artikel, sehr informativ und gut geschrieben.

    Ich habe einen kleinen Satzbaufehler gefunden, ich weiß ich nerve schon mit den Kleinigkeiten :P. Du hast im vorletzten Absatz „alle zuvor beschriebenen Schritte ein eine Schleife“ geschrieben, das soll, glaube ich, „Schritte IN eine Schleife“ heißen.

  1. Pingback: Kollisionserkennung: Pair Manager « "Mit ohne Haare"

  2. Pingback: Breakout: Steinwand | Delphi400’s Weblog

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: