Methoden zur Lösung von 2D-Starrkörperkollisionen

Lösung von 2D-Starrkörperkollisionen

Problemdefinition

• Vom Moment, in dem Mario auf eine Wolke springt, bis zum Zusammenstoß zweier Autos in einem Rennspiel ist der Umgang mit Kollisionen ein äußerst wichtiger Bestandteil der meisten Videospiele.
• In dieser Blogserie geht es um die tatsächliche Mathematik und Physik hinter der Physiksimulation.
• Videospiele sind eine gute Möglichkeit, diese Konzepte in einen Kontext zu setzen und sie weniger abstrakt zu machen.

Ein Wort zur Mathematik

• In diesem Artikel kommt viel Mathematik vor, aber man sollte sich davon nicht abschrecken lassen.
• Die mathematische Notation kann kompliziert wirken, aber das meiste davon ist einfache Arithmetik.
• Hab keine Angst vor Mathematik und probiere es aus.

Bevor wir anfangen

Starrkörper

• Starrkörperphysik ist eine Physiksimulation, die sich mit Objekten befasst, die sich nicht verformen.
• In der Realität verformen sich alle Objekte auf molekularer Ebene, aber in der Simulation wird dies vereinfacht und als Starrkörper behandelt.

Kollisionserkennung und Kollisionsauflösung

• Kollisionserkennung ist der Prozess, bei dem geprüft wird, welche Objekte in einer Szene kollidieren.
• Kollisionsauflösung ist der Prozess, bei dem entschieden wird, wie sich kollidierte Objekte bewegen sollen.
• In dieser Blogserie liegt der Fokus auf der Phase der Kollisionsauflösung.

Was wollen wir erreichen?

• Die meisten Spiele laufen in einer großen Schleife.
• Bei jeder Wiederholung der Spielschleife wird die Position eines Objekts entsprechend seiner aktuellen Geschwindigkeit aktualisiert.
• Geschwindigkeit ist ein Vektor mit Betrag und Richtung.

Geschwindigkeit

• Geschwindigkeit beschreibt die Positionsänderung eines Objekts über eine bestimmte Zeit.
• Die neue Position eines Objekts wird berechnet, indem man die Verschiebung addiert, die sich aus der Multiplikation der aktuellen Geschwindigkeit mit dem Zeitintervall ergibt.

Kollisionsauflösung

• Das Ziel der Kollisionsauflösung ist es, nach einer Kollision die Geschwindigkeit der Objekte so zu ändern, dass sie sich nicht länger gegenseitig durchdringen.
• Die Geschwindigkeit nach der Kollision lässt sich als Summe der Geschwindigkeit vor der Kollision und der durch die Kollision verursachten Geschwindigkeitsänderung ausdrücken.

Was ist eine Kollision?

• Damit zwei Objekte als kollidierend gelten, müssen zwei Bedingungen erfüllt sein:
  1. Die geometrischen Formen der Objekte müssen sich berühren oder überlappen.
  2. Die Objekte müssen sich weiterhin auf die Kollision zubewegen.

Flächennormale

• Um ein Objekt möglichst weit von einer Oberfläche wegzubewegen, muss es in eine Richtung bewegt werden, die senkrecht zur Oberfläche steht.
• Diese Richtung wird Normalenrichtung genannt und steht senkrecht auf der Oberfläche.

Skalarprodukt

• Um zu berechnen, wie stark zwei Vektoren in dieselbe Richtung zeigen, verwendet man das Skalarprodukt.
• Das Skalarprodukt ist definiert als die Summe der Produkte der entsprechenden Komponenten zweier Vektoren.
• Am Vorzeichen des Skalarprodukts lässt sich erkennen, ob zwei Vektoren in die gleiche oder in entgegengesetzte Richtung zeigen.

Fazit

• Eine Kollision tritt auf, wenn ein Punkt eines Objekts einen Punkt eines anderen Objekts berührt und die relative Normalgeschwindigkeit negativ ist.
• Im nächsten Artikel geht es um die eigentliche Physik von Kollisionen.

Meinung von GN⁺

• Die Bedeutung der Physiksimulation: In der Spieleentwicklung ist Physiksimulation ein wichtiger Faktor, um den Realismus zu erhöhen.
• Die Rolle der Mathematik: Mathematik ist der Kern der Physiksimulation, und wer sie versteht, kann bessere Simulationen erstellen.
• Die Komplexität der Kollisionsauflösung: Kollisionsauflösung ist ein komplexerer Prozess, als einfach nur die Position von Objekten zu aktualisieren.
• Pädagogischer Wert: Dieser Artikel hilft sehr dabei, die Grundlagen der Physiksimulation zu verstehen.
• Weiterführendes Lernen: Es ist auch eine gute Lernmethode, eine Physics Engine selbst zu implementieren. Als Referenz können Open-Source-Physics-Engines wie Box2D oder Chipmunk dienen.

[GN⁺]

Hacker-News-Meinungen

Zusammenfassung der Hacker-News-Kommentare

• Hey everyone, author here!

  • Dies ist der erste Beitrag einer Blogserie und richtet sich an Menschen, die keine Spieleentwickler sind oder nur wenig mathematischen Hintergrund haben.
  • Deshalb werden die Konzepte ausführlich erklärt.
  • Fragen sind jederzeit willkommen.

• Oh! Look, a well-researched, deeply-explained, and interactive post.

  • Wegen des Domainnamens und der TLD ".ski" dachte ich zuerst, es sei der Autor eines anderen großartigen Artikels, aber es war jemand anderes.
  • Die Qualität des Beitrags ist ähnlich hervorragend.
  • Ich frage mich, was das Geheimnis der ".ski"-TLD ist.

• One side project I am working on right now is a 2d space shooter I am developing with my son.

  • Ich entwickle gerade zusammen mit meinem Sohn einen 2D-Weltraum-Shooter.
  • Ich wollte es ohne Game Engine selbst implementieren, hatte aber Schwierigkeiten bei der Kollisionserkennung.
  • Am Ende habe ich mich entschieden, Box2D zu verwenden.
  • Trotz mehr als 20 Jahren Entwicklungserfahrung und mathematischem Hintergrund wurde mir klar, dass ich das Problem unterschätzt hatte.

• I always enjoyed the explanation from the N game: N game tutorial

  • Ich mochte die Erklärung aus dem N-Spiel immer gern, damals als Flash populär war.

• I had fun building a TypeScript demo about this topic, involving balls that can bounce and collide. I learned a lot.

  • Ich hatte Spaß daran, eine TypeScript-Demo zu diesem Thema zu bauen, in der Bälle springen und kollidieren können, und habe dabei viel gelernt.
  • Code
  • Ergebnis/Demo

• This is great. This reminds me of Chris Hecker's Rigid Body Dynamics series from GDMag/Gamasutra that I read (checks watch) almost 30 years ago!

  • Das erinnert mich an Chris Heckers Serie zu Rigid Body Dynamics.
  • Chris Heckers Rigid Body Dynamics

• Collisions are violations of the pairwise non-intersection constraint between bodies.

  • Kollisionen sind Verletzungen der paarweisen Nicht-Überschneidungsbedingung zwischen Körpern.
  • Kollisionskräfte sind die Lagrange-Multiplikatoren dieser Zwangsbedingungen.
  • Die Kollisionsnormale ist die partielle Ableitung der Zwangsfunktion.

• If you want to go further and go for rigid body dynamics and constraint, I found that series of blog post very useful: Toptal blog post

  • Wenn man tiefer in Rigid Body Dynamics und Zwangsbedingungen einsteigen möchte, ist diese Blogserie sehr nützlich.

• To dredge up a related oldie-but-goodie memory of blog posts: Gaffer on Games

  • Das ruft die Erinnerung an einen thematisch verwandten alten, aber guten Blog hervor.
  • Gaffer on Games

• Guess this is a Shameless plug but I wrote an interesting program over 12 years ago using even then very old three Js which is not quite the metal but much less abstract than today's tools.

  • Das ist wohl schamlose Eigenwerbung, aber ich habe vor über 12 Jahren ein interessantes Programm geschrieben, mit einem schon damals sehr alten three Js, das nicht ganz so nah an der Hardware ist, aber deutlich weniger abstrakt als die heutigen Tools.
  • Busy Boxes