Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Kollisionserkennung

Kollisionsbehandlung mit Ortskorrektur

Kollisionsbehandlung

In den meisten Anwendungsfällen dient die Kollisionserkennung der Ausführung von Stößen. Dabei stoßen bewegte Objekte, die sich mit typischen Geschwindigkeiten vObject bewegen, aufeinander. Würden die Objektbewegungen, d.h. die Änderungen der Objekt-Orte je Zeiteinheit, kontinuierlich sein, bräuchten wir überhaupt nicht über dieses Thema sprechen. Nun ist aber in der digitalen Welt die Zeit nicht analog, sondern diskretisiert. Sinnvoller Weise verwenden wir den Kehrwert der Bildwechsel­frequenz als Zeitquant ().
Wird nun ein Objekt mit der Geschwindigkeit v bewegt, kann er infolge der diskretisierten Zeit nicht mehr jeden beliebigen Ort einnehmen, sondern nur solche Orte, die der diskretisierten Zeit entsprechen:
()
Formel
Das hat u.a. zur Folge, dass der Kollisionsort nur mit der Unschärfe
()
Formel
bestimmt werden kann.

Warum müssen wir über die Behandlung der Kollision überhaupt nachdenken? Ist doch klar, dass bei einer Kollision die Objektgeschwindigkeiten vor und nach der Kollision den Stoßgesetzen folgend umgerechnet werden müssen. Aber ist das wirklich so einfach? Betrachten wir doch mal den Fall, der in dargestellt ist.
Eine Kugel nähert sich unter einem sehr flachen Winkel einer Ebene. Zum Zeitpunkt ti-1 berührt die Kugel die Ebene noch nicht. Aber bereits zum Zeitpunkt ti, der um einen Bildwechsel später liegt, ist die Kugel so weit fortgeschritten, dass die Kollisionsbedingung entsprechend erfüllt ist und eine Berührung der Ebene signalisiert.
Dieser Augenblick sollte nun als die Kollision registriert und die Kugelgeschwindigkeit gemäß der geltenden Stoßgesetze umgerechnet werden.
Fehlerhafte Reflexion infolge

Abb. Fehlerhafte Reflexion infolge "Eindringens"

Aber schauen wir genauer hin, stellen wir fest, dass die Kugel die Ebene nicht nur berührt, sondern in diese sogar "eindringt". Das passiert natürlich in der Realität nicht, aber bei uns schon! Das liegt an der Diskretisierung der Zeitachse. Nur bei Bildwechseln werden die Standorte neu berechnet. Und da sich unsere Zeitachse in Sprüngen von dt = 1/frmRate vorwärts bewegt, wird der wahre Kollisions­zeitpunkt gar nicht wahrgenommen und die Kugel fliegt in die Ebene hinein. In liegt der Zeitpunkt ti relativ weit hinter dem wahren Kollisionszeitpunkt, so "dringt" die Kugel relativ weit in die Ebene hinein.
Da eine Kollision registriert wurde, wird die Kugel jetzt an der Ebene reflektiert. Unglücklicher Weise findet diese Kollision in einer spitzen Ecke eines Polygons statt. So kann es dazu kommen, dass bereits beim nächsten Bildwechsel wieder eine Kollision erfolgt, die aber nicht als neues Ereignis registriert wird, sondern noch der ersten Kollision zugerechnet wird. Die Folge ist, dass die nächste Ortsberechnung zur Zeit ti+1 einen neuen Ort erfolgt, bei dem die Kugel noch immer in der Ebene "steckt". Damit sind die Bedingungen für die Erkennung einer Kollision wieder gegeben und eine erneute Reflexion wird berechnet. Diese geht aber wieder in die Richtung, die die Kugel zum Zeitpunkt ti-1 hatte. So beginnt das Spiel von vorn und die Kugel kann die Ebene nie verlassen (es sei denn, die Ebene ist begrenzt). Eine solche Konstellation tritt nicht sehr häufig auf, aber sie tritt auf. Ursachen hierfür können Rundungsfehler oder eine gewollte Dämpfung beim Stoß sein.
Die Folgen dieses Effektes können sein, dass, wenn mehrere Kugeln im Spiel sind, diese nach einer Kollision "verklumpen" oder statt an einer Ebene reflektiert zu werden, parallel an dieser entlang "rutschen". So ist also klar, dass hier Gegenmaß­nahmen erforderlich sind, um dieses "Eindringen" zu verhindern.
Im folgenden Programmbeispiel kannst Du den letztgenannten Effekt beobachten. Drücke einfach den START-Button und lass die Kugel laufen. Nach einer kurzen Zeit (nach ca. 35 Kollisionen) siehst Du die Kugel in die Wand eindringen, danach kann sie sich nicht mehr davon lösen! Erst am nächsten Segment ist dies wieder möglich.

Bitte einen Augenblick Geduld
während das Programm geladen wird!
Abb. Kollisionserkennung ohne Korrekturmaßnahmen

Die Erkennung einer Kollision erst nach der Berührung oder gar dem Eindringen des bewegten Objektes hat Nachteile bei großen Objektgeschwindigkeiten, die zu einem Eindringen oder im Extremfall Überspringen der stoßenden Körper führen können. zeigt den prinzipiellen Programmablauf der Stoßerkennung, -behandlung und -ausführung. Dieses Verfahren gewährleistet nicht, dass der berechnete Stoßort mit dem tatsächlichen Stoßort zusammen fällt. Das führt in einigen Fällen zu unerwartetem Verhalten nach der Kollision.
Gesucht wird also ein Verfahren zur Kollisionserkennung, dass diese Nachteile vermeidet, zu mindest aber minimiert. Im folgenden sollen zwei Verfahren einer Ortskorrektur besprochen werden.

Kollisionsbehandlung ohne Orts-Korrektur

Abb. Kollisionsbehandlung ohne Orts-Korrektur


Kollisionserkennung mit vorausschauender Prognose des Stoßortes

Betrachten wir die folgende Standardsituation: zwei Kugeln bewegen sich aufeinander zu und kollidieren. Besitzen beide Kugeln die gleichen Massen m, bewegen sie sich nach dem Zusammenstoß gemäß der Stoßgesetze mit jeweils der Geschwindigkeit der anderen Kugel von einander fort.
Was Du beim Experimentieren in der beschriebenen Kollisions­situation, insbesondere bei großen Objekt­geschwindig­keiten, beobachten kannst, ist das gegenseitige "Eindringen" beim Stoß des einen Objektes in das andere, weil der Zusammenstoß zweier Objekte in der Regel erst dann bemerkt wird, wenn der Stoßort bereits überschritten ist. Den Beobachter stört das nicht, weil das Auge viel zu träge reagiert, um dieses Malheur während des einen Frames zu bemerken. Aber unter ungünstigen Bedingungen kann dieses Verhalten Folgen haben. Z.B. "verkleben" Objekte nach einem Stoß oder registrieren überhaupt keine Kollision, weil die Orte, die beim nächsten Bildwechsel errechnet werden, bereits jenseits der beiden Kugeln liegen. Zur Behebung dieses Problems werden wir jetzt nicht nur die aktuellen Objektorte, sondern auch noch die aktuellen Objektgeschwindigkeiten zur Ermittlung des Kollisionsortes heranziehen.

Ausgangspunkt ist die Überlegung, dass der Stoßort auch im Voraus berechnet werden kann. Das ist möglich, weil - zumindest für die Dauer eines frames - alle Objekt­geschwindig­keiten bekannt und unveränderlich sind. Also sind alle Bewegungen zwischen zwei frames gleichförmig. Daher berechnen wir anstelle der Distanzen zwischen den Objekten, den Zeitpunkt, zu dem sich beide Wege der auf Kollisionskurs befindlichen Objekte so weit angenähert haben, dass sie sich berühren.
Zur Verdeutlichung dieser Idee schauen wir uns den einfachsten Fall, nämlich den zentralen Stoß an (). Im oberen Teilbild wird die einfache Kollisionserkennung gezeigt. Im unteren Teilbild die Kollisionserkennung mit Prognose des Stoßortes.
Gehen wir davon aus, dass zum Zeitpunkt tn - oben wie unten - beide Objekte kurz vor der Kollision stehen.
  • oberes Teilbild: Infolge der Geschwindigkeiten beider Objekte haben sich die Objekte im folgenden frame so weit bewegt, dass die Orte x1(tn+1) bzw. x2(tn+1) einnehmen. Unglücklicher Weise sind diese Orte aber so weit fortgeschritten, dass sich beide Objekte teilweise überlappen. Zur Erinnerung: der Zeitpunkt des neuen frames ergibt sich aus dem vorangegangen Zeitpunkt zu tn+1 = tn + dt!

  • unteres Teilbild: Hier wird gar nicht erst die Berechnung des neuen frames abgewartet, sondern noch im jeweils aktuellen frame eine Prognose des künftigen Ortes berechnet, die dann ein verkürztes Intervall dt' liefert. Damit kann nun der exakte Stoßort berechnet werden. Mit t' bzw. dt' werden hier korrigierte Zeitgrößen bezeichnet!
Kollisionserkennung mit und ohne Prognose des Stoßortes

Abb. Kollisionserkennung mit und ohne Prognose des Stoßortes



Die Prognose des richtigen Stoßortes wird auf eine Zeitprognose zurück geführt. Es wird nämlich gefragt, ob die verbleibende Zeit t' bis zum Stoß größer oder gleich/kleiner der regulären Framedauer dt ist. Dazu werden für beide Objekte lineare Gleichungen aufgestellt (), die mathematisch die Orte beider Objekte auf der Basis der aktuellen Orte und der aktuellen Geschwindigkeiten berechnen:

()
Formel

Nun kann die Summe beider Objektradien mit der Differenz der beiden Objektorte (die ja eine Funktion der Zeit t' sind) verglichen werden ():

()
Formel

Da es sich hier um eine lineare Funktion von der Zeit handelt, weiterhin die Geschwindigkeiten als konstant (da gleichförmige Bewegung vorliegt) angesehen werden kann, ist es ein Leichtes, die Zeit t' bis zum Stoß zu berechnen ():

()
Formel

Für die spätere Anwendung ist es zweckmäßig, den Betrag der Zeit t' zu verwenden. Denn sie kann auch negative Werte annehmen, nämlich dann, wenn sich beide Körper nach dem Stoß wieder von einander entfernen!

Somit liegt ein Stoß vor, wenn t' ≤ dt wird. Ja, und wie erfolgt nun die Ortsberechnung? Ganz einfach. Das bis dahin geltende Zeitincrement dt wird bei erkanntem Stoß einmalig durch t' ersetzt. Dadurch sind die Objektorte genau um die Summe der Objektradien von einander entfernt.

Dem muss nun im Programmablauf der Ortsberechnung Rechnung getragen werden (). Jetzt müssen die Prognose des Stoßortes, d.h. die Kollisionserkennung, und die Kollisionsbehandlung voneinander getrennt werden, muss doch die Ortsberechnung im Fall des zu erwartenden Stoßes mit einem anderen Zeitincrement berechnet werden.

Kollisionserkennung mit und ohne Prognose des Stoßortes

Abb. Kollisionserkennung mit Prognose des Stoßortes


Im Beispielprogramm sind im direkten Vergleich eine Standard-Kollisionserkennung (oben) und die Kollisionserkennung mit Ortsprognose zu sehen. Im Gegensatz zu einer normalen Anwendung wird hier der Programmablauf nach jedem Bildwechsel (frame) gestoppt. So kannst Du beobachten, wie sie die Kugel aufeinander zu bewegen. Betätigen des Buttons next aktiviert das Programm bis zum Ablauf des nächsten frames. Mit dem Schieberegler v2 kann die Geschwindigkeit der zweiten Kugel verändert werden.

download processing
download p5.js
run program
Ergebnisdiskussion: Bei geringen Relativ­geschwindig­keiten ist im oberen Experiment das gegenseitige Eindringen der Kugeln gut zu beobachten, während im unteren Experiment dank der Ortsprognose ein exaktes Berühren ohne Eindringen zu sehen ist.
Im oberen Experiment kann die fehlerhafte Kollisions­erkennung so weit getrieben werden, dass eine Kollision überhaupt nicht mehr registriert werden kann, weil die diskreten Orte eine Kollision unmöglich machen. Wähle dazu eine Geschwindigkeit v2 ≈ -30 m/s.

Geistesblitz
on/off

Etwas unübersichtlicher sieht die Prognoseerstellung beim dezentralen Stoß aus. Prinzipiell werden aber die gleichen Überlegungen wie oben angestellt. Die Vorhersage des Stoßortes führt auf eine interpretations­bedürftige Gleichung ():

()
Formel

worin
Formel
bedeuten.

Interpretationsbedürftig, weil eine Quadratwurzel stets zwei Lösungen hat. Schauen wir uns dazu an. Daraus ist zu ersehen, dass sowohl vor, als auch nach dem Stoßort Kugelabstände, die genau unserer Bedingung 2r entsprechen, auftreten können (der Zustand nach dem Stoß ist dabei natürlich nur fiktiv, da ja nach dem Stoß die Bewegungen in andere Richtugen fortgesetzt werden). Die uns interessierende Zeit bis zum Stoß t' ist auf jeden Fall kleiner als die Zeit bis nach dem Stoß. Darum kommt nur die negative Wurzel für unsere weitere Verwendung in Frage. Um zu vermeiden, dass das Wurzelargument negativ wird - das kann bei großen Abständen auftreten - sollte auch dieser Zustand bei der Implementierung abgetestet werden.
 Ortsberechnung mit Prognose des Stoßortes

Abb. Ortsberechnung mit Prognose des Stoßortes


Das Beispielprogramm erlaubt den Vergleich zwischen einer Kollisionserkennung mit und ohne Ortsprognose. Im Stoßmoment stoppt die Programmabarbeitung zum Zwecke einer optischen Kontrolle der Stoßsituation. Mit Betätigung des Buttons next wird das Programm fortgesetzt.
Du hast außerdem die Möglichkeit, vor Betätigung des START-Buttons per drag'n drop Ort und Startgeschwindigkeit beider Objekte zu verändern.
download processing
download p5.js
run program


Ergebnisdiskussion: Die Wirkung der Ortsprognose für die Kollisionserkennung ist gut zu beobachten. Was besonders auffällt, sind deutlich unterschiedliche Bewegungen nach dem Stoß zwischen Standard-Kollisionserkennung und Erkennung mit Ortsprognose!