Advanced Games Physics
Inhaltsverzeichnis zum
Inhalt

Kollisionserkennung

Kollisionerkennung an Objekten, die als Image vorliegen

Kollisionserkennung an photorealistischen Objekten

So richtig schön wird ein Spiel erst dann, wenn die Akteure und die Objekte fotorealistisch sind! Deshalb soll am Beispiel der Kollision eines künstlichen Himmelskörpers mit einem Kometen (hier Vektorbasierte Verfahren für Polygone) gezeigt werden, wie eine Kollisionerkennung an Objekten, die als Image vorliegen, zu lösen ist.

Die Herausforderung besteht darin, dass jedes fotorealistisch dargestellte Objekt einen Doppelgänger in Form einer Polygonkontur benötigt. Das Image ist zum Anschauen da, die Kontur, um Kollisionen berechnen zu können. Dazu muss das Objekt, dessen Image als .bmp- oder .png-Datei vorliegt, digitalisiert werden. Und zwar so, dass Kontur und Image deckungsgleich und maßstäblich zur Anwendung passend sind.

Kontur-Erfassung eines Images

Wegen der erforderlichen hohen Präzission beim Erfassen einer Kontur verbietet sich das Arbeiten mit Geräten geringer Display-Auflösung. Eine Möglichkeit zur Digitalsierung einer Kontur auf der Grundlage eines Images wird in der Desktop-Version dieser Seite vorgestellt.

Für die Verwendung einer digitalisierten Kontur genügt es, diese als file verfügbar zu haben. zeigt die Datenstruktur des files contour.txt. Dieses wird in einen Folder namens data des aufrufenden Programms geladen.

Mit größter Sicherheit gibt es im Internet unzählige Programme, mit deren Hilfe Images digitalisiert werden können. Dennoch habe ich mich dazu entschieden, ein weiteres Programm zu schreiben. Dieses Programm liefert deckungs­gleiche und maß­stäbliche Kontur-Daten. Darüber hinaus werden für spätere Anwendungen die normierte Fläche der Kontur A', die Koordinaten des Flächen­schwerpunktes S(x0', y0') und das normierte Flächen­trägheits­moment J' bereit gestellt. Alle Daten sind so auf­bereitet, dass sie zwischen allen hier vor­gestell­ten Beispiel­programmen die auch zwischen meinen Programmen aus­getauscht werden können.

download processing
download p5.js
run program

Wegen der erforderlichen Präzission beim Erfassen einer Kontur, ist das Arbeiten mit der Maus zu empfehlen. Deshalb sind die folgenden Anweisungen für die Mausbenutzung verfasst!


So ist das Erfassungsprogramm zu handhaben:
  • Vorbereitung

    1. Lade das zu erfassende Image in den Ordner "data" des Erfassungsprogramms. Sinnvoller Weise liegt das Image als .png-File vor und ist so orientiert, dass seine größte Abmessung entweder in x- oder y-Richtung zeigt! Images, die anders orientiert vorliegen, sind mit Hilfe eines Grafikprogramms so zu drehen, dass die größte Abmessung der oben aufgestellten Forderung entspricht.

    2. Benenne das Image-File in "image.png" um.

    3. Starte das Erfassungsprogramm Grund_0050_digitize_Objects.pde (processing) oder pGrund_0050_digitize_Objects.js (p5.js).

      Für einfache Anwendungen, d.h. das Objekt ist fixiert, werden die Werte für Fläche, Trägheitsmoment und Schwerpunkt nicht benötigt. Darum kann das Erfassungs­programm in einer vereinfachten Form gestartet werden. Standardmäßig ist das Erfassungsprogramm auf die einfache Erfassung eingestellt. Andernfalls (z.B. wenn nichtzentrale Stöße an einem beweglichen Objekt dargestellt werden sollen) ist in Zeile 12 des Programmcodes in der p5.js-Version die Variable imageCenter statt mit "center" mit "gravity" zu laden.




    Abb. Laden und Einrichten eines Image zur Konturerfassung


  • Programmausführung

    1. Suche die größte Abmessung. Fasse mit der Maus den grünen Knopf links oberhalb des rot gezeichneten Quadrats und verschiebe das Quadrat so, dass entweder die linke Seite des Quadrats an die äußerste linke Abmessung des Images (größte Abmessung ist parallel zur x-Achse) oder die obere Seite an den obersten Punkt des Images (größte Abmessung ist parallel zur y-Achse).

    2. Fasse nunmehr den rechten unteren grünen Knopf mit der Maus und passe das Quadrat so an, dass entweder der rechte Rand des Quadrates die äußerste rechte Abmessung des Images (größte Abmessung ist parallel zur x-Achse) oder der untere Rand die tiefste Abmessung (größte Abmessung ist parallel zur y-Achse) berührt. Diese Maßnahmen führen dazu, dass die erfasste Kontur auf den Wert 1 normiert wird. D.h. die Ausdehnung der größten Abmessung erscheint in der erfassten Kontur mit dem Wert 1.

    3. Verschiebe das Quadrat so, dass das Fadenkreuz mit dem Mittelpunkt des Images übereinstimmt. Auf diese Weise wird sicher gestellt, dass bei einer späteren Anwendung Image und Kontur wirklich deckungsgleich sind.

    4. Jetzt kann mit der Konturerfassung begonnen werden. Klicke mit der Maus charakteristische Konturpunkte des Images an. Dieser Punkt wird rot gekennzeichnet auf dem Image zu sehen sein. Erfasse so weitere Punkte. Aus ökonomischen Gründen sollte die Anzahl von Konturpunkten möglichst klein bleiben!

    5. Korrekturen, Löschungen oder Erweiterungen der Kontur sind immer möglich: Anfassen eines vorhandenen Punktes und verschieben ändert die Koordinaten dieses Punktes, Klicken auf eine Verbindungsline erzeugt an dieser Stelle einen neuen Konturpunkt. Anklicken mit der rechten Maustaste (processing) oder linke Maustaste + Shift (p5.js) löscht diesen Konturpunkt. Betätigen des Buttons "new" löscht die gesamte erfasste Kontur und eine komplette Neueingabe ist möglich!

    6. Mit dem Button "close" wird die Kontur geschlossen, wenn das Objekt ein Körper ist. In der Regel ist dies der Fall, dann wird der letzte Konturpunkt mit den Werten des ersten Konturpunktes geladen.

    7. Mit dem Kommado "close" werden die Koordinaten des Schwerpunktes S (blaus Kreuz), die Fläche A und das Flächen­trägheits­moment J berechnet.

    8. Zuletzt werden mit dem Button "save" die normierten Kontur­koordinaten P'i und die weiteren normierten Kenngrößen A', J' und die Orientierung "x" oder "y" der größten Abmessung im File "data/contour.txt" abgespeichert ().


Aufbau des Files contour.txt

Abb. Aufbau des Files contour.txt


Kollisionserkennung und -behandlung

Für die Kollisionserkennung und -behandlung selbst ist es unwichtig, wo der Mittelpunkt der Kontur positioniert ist. Für die Anwendung aber schon! Denn, erfolgt ein Stoß auf das Objekt, das durch das Image repräsentiert wird, so ist es entscheidend für die Bewegung nach dem Stoß, ob dieser zentral oder dezentral erfolgte. Über die Konsequenzen kannst Du näheres unter Behandlung des dezentralen, elastischen Stoßes bzw. Wechselwirkung von Stoß und Drehimpuls erfahren.
In diesem Kapitel ist diese Thematik noch nicht relevant. Darum wurde das Kontur­erfassungs­programm so eingestellt, dass auf Trägheitsmoment und Schwerpunkt verzichtet wird. Vielmehr betrachten wir das Objekt als fixiert, was bedeutet, dass uns der Imagemittelpunkt als Bezug genügt. Damit wird garantiert, dass Image und Kontur einen gemeinsamen Mittelpunkt haben. Damit beide auch noch deckungsgleich sind wird sowohl das Image mittels resize(polygonWidth, 0) auf die gewünschte Breite gebracht, aber auch die Kontur mit eben diesem Wert polygonWidth entnormiert ().



Abb. Laden einer Kontur aus einem file und Entnormierung



Hier ist ein Beispiel für eine Kontur, die von einem Objekt abgenommen wurde. Das Image und damit auch die Kontur werden als unbeweglich betrachtet. Stöße der Kugel an das Objekt führen daher nur zur Reflexion der Kugel.
In der Darstellung ist die Deckungsgleichheit zu erkennen. Mit dem Button show/hide kann die Kontur zum Image sichtbar/unsichtbar geschaltet werden.
download p5.js
run program

Kollision an Multi-Polygonen - Flipper

Das oben beschriebene Verfahren der vektoriellen Kollisionserkennung eignet sich besonders gut für die Implementierung der Kollision an Multi-Polygonen als class (processing) oder object (p5.js). Dadurch wird es möglich, komplexe Anordnungen von vielen Hindernissen zu modellieren. Ein klassisches Beispiel hierfür ist das Spiel FLIPPER. Für jedes Hindernis wird eine Instanz eröffnet. Für jedes Hindernis wird auf Kollision geprüft und für jedes Hindernis wird eine nachträgliche Korrektur des Stoßortes vorgenommen.
So weit so gut. Die Herausforderung für die Implementierung besteht beim FLIPPER aber darin, die verschiedenen Geometrien des Spieles geeignet zu erfassen und gleichzeitig einen ökonomischen, d.h. Rechenzeit optimierten, Ablauf zu ermöglichen.

Berücksichtigen der Geometrien bedeutet, unterschiedliche Bewegungsabläufe zu berücksichtigen:
  1. Startkanal: Fall unter Berück­sichtigung der Strömungs­reibung
  2. Oberer Halbkreis: Fadenpendel
  3. Spielfeld mit Hindernissen: Schräger Wurf unter Reibungs­einfluss und Kollisions­erkennung Kollisionserkennung mit nach­träglicher Korrektur des Stoß­ortes
  4. Reflexionsfreie Bewegung auf Hindernissen: Schiefe Ebene und
  5. Rücklaufkanal: Schiefe Ebene

Insbesondere der Übergang von 3. zu 4. ist nicht unproblematisch. Einziges Unterscheidungsmerkmal ist die Abfolge von Kollisionen: Solange die Kugel noch springt, liegt der Zustand nach 3. vor. Zwischen jeder Kollision gibt es kollisionsfreie Phasen. Im Gegensatz dazu finden im Zustand 4. stets Kollisionen ohne Pause statt. Dies machen wir uns als Kriterium für das Weiterschalten von 3. auf 4. zu nutze. Das setzt aber eine sehr zuverlässig funktionierende Ortskorrektur während der Kollision voraus!
Um die CPU-Last klein zu halten, wird das Spielfeld segmentiert. D.h. je nach Aufenthaltsort der Kugel werden bestimmte Segmente zur Kollisionserkennung aktiv geschaltet, während in den nichtaktiven Segmenten keine Kollisionserkennung durchgeführt wird.

Der hier implementierte Flipper hat eine sehr überschaubare Struktur und nur eine Bedienungsmöglichkeit, nämlich den Zug-Griff rechts unten am Spielfeld. Wird der Zug-Griff nach unten gezogen und dann losgelassen, wird die Kugel losgeschnippt. Je weiter Du nach unten ziehst, desto stärker die Kraft (zu erkennen an der Geschwindigkeitsanzeige rechts neben dem Spielfeld).
Mit dem Button "visible" können die Hindernisse und die Segmentierung des Spielfeldes sichtbar gemacht werden. Ebenso werden die Vektoren für die Kollisionserkennung angezeigt. Viel Spaß!

download processing
download p5.js
run program

Ergebnisdiskussion: Der Programmierer wird immer wieder vor besondere Herausforderungen gestellt. Hier ist es die unvollständige Approximation einer gleichmäßigen Rundung durch ein Polygon, z.B. am oberen Halbbogen oder an den Hindernissen. So approximierte Objekte haben keinen konstanten Radius! Das führt bei Kollisionsentscheidungen, die sich auf einen konstanten Radius beziehen (z.B. zum Verlassen des oberen Halbbogens), zu Fehlern. Diese Fehler zu vermeiden, müssen diesen Entscheidungen gewisse Toleranzen eingeräumt werden, die wiederum zu anderen Fehlentscheidungen führen können. Hier ist also durch sorgfältiges Ausprobieren ein Optimum zu finden.