Wie 2D-Kollisionen starrer Körper aufgelöst werden

 (sassnow.ski)
3 Punkte von GN⁺ 2024-05-25 | 1 Kommentare | Auf WhatsApp teilen
  • Die Auflösung von Kollisionen starrer Körper in der 2D-Spielphysik ist das Problem, die Geschwindigkeitsänderungen so zu berechnen, dass sich bereits berührende oder überlappende Objekte im nächsten Frame nicht gegenseitig durchdringen
  • Da die Spielschleife in jedem Frame die Position anhand von Geschwindigkeit und Δt aktualisiert, durchdringen sich Objekte ohne zusätzliche Behandlung gegenseitig, wenn sich ihre Geometrie an der neuen Position überlappt
  • Eine Kollision ist nicht nur die bloße Berührung, sondern man muss auch berücksichtigen, ob sich die berührenden Objekte mit ihren aktuellen Geschwindigkeiten weiterhin aufeinander zu bewegen
  • Ob sich ein Objekt von einer Oberfläche entfernt, lässt sich am Vorzeichen des Skalarprodukts aus Normale (normal) und Geschwindigkeit erkennen: Bei einem positiven Wert gibt es eine Komponente in gleicher Richtung, bei einem negativen Wert eine Komponente in entgegengesetzter Richtung
  • Bei zwei Objekten sind nicht die einzelnen Geschwindigkeiten, sondern die Relativgeschwindigkeit und die Kollisionsnormale entscheidend; befindet sich ein Kontaktzustand bei negativer relativer Normalgeschwindigkeit, kann man ihn als Kollision ansehen

Bereich der Starrkörperphysik und Kollisionsauflösung

  • Behandelt wird Starrkörperphysik (rigid body physics), also Objekte, die sich auch unter Krafteinwirkung nicht verformen
    • In der Realität verformen sich alle Objekte auf molekularer Ebene, daher existieren keine vollkommen starren Körper
    • In den meisten Physiksimulationen ist es sehr schwierig oder teuer, auch solche Detailverformungen zu berechnen
    • Wenn Objekte ausreichend realistisch wirken, ist die Vereinfachung als starrer Körper in der Praxis sinnvoll
  • Die Kollisionsbehandlung in Game-Engines ist meist in zwei Schritte unterteilt
    • Kollisionserkennung (collision detection): Es wird bestimmt, welche Objekte in der Szene kollidieren
    • Kollisionsauflösung (collision resolution): Auf Basis von Bewegungsrichtung, Geschwindigkeit, Material usw. der kollidierenden Objekte wird der Folgezustand bestimmt
  • Der Fokus hier liegt nicht auf dem Finden geometrischer Überschneidungen, sondern auf der Kollisionsauflösung, also der Bestimmung der Bewegung nach der Kollision

Wie Kollisionen in der Spielschleife entstehen

  • Die meisten Spiele berechnen in einer großen Schleife die Positionen der Objekte in der Szene immer wieder neu
  • In jeder Wiederholung wird die Position eines Objekts auf Grundlage seiner aktuellen Geschwindigkeit (velocity) aktualisiert
    • Geschwindigkeit ist eine Vektorgröße mit Betrag und Richtung
    • Die Länge des Pfeils steht für die Schnelligkeit, die Pfeilrichtung für die Bewegungsrichtung
  • Die Positionsänderung über ein Zeitintervall Δt wird als Verschiebung (displacement) dargestellt
    • Auch die Verschiebung ist eine Vektorgröße mit Betrag und Richtung
    • Läuft die Spielschleife 60-mal pro Sekunde, dann ist Δt gleich 1/60 Sekunde
  • Die neue Position ergibt sich, indem man die aus der aktuellen Geschwindigkeit berechnete Verschiebung zur bisherigen Position addiert
  • Falls die neuen Positionen zweier Objekte ihre Geometrie überlappen lassen, dringen die Objekte ohne gesonderte Behandlung ineinander ein und passieren einander

Welche Größe die Kollisionsauflösung sucht

  • Ziel der Kollisionsauflösung ist es, die Geschwindigkeitsänderung jedes Objekts so festzulegen, dass die Objekte im weiteren Verlauf der Simulation nicht mehr ineinander eindringen
  • Die Geschwindigkeit vor und nach der Kollision wird mit folgenden Symbolen dargestellt
    • v_a,i, v_b,i: Geschwindigkeiten der Objekte a und b vor der Kollision
    • v_a,f, v_b,f: Geschwindigkeiten der Objekte a und b nach der Kollision
    • Δv_a, Δv_b: Die durch die Kollision verursachten Geschwindigkeitsänderungen der jeweiligen Objekte
  • Letztlich ist Kollisionsauflösung also das Problem, die Werte Δv_a und Δv_b zu finden
  • Damit eine Kollision realistisch wirkt, müssen die gewählten Geschwindigkeitsänderungen die relevanten physikalischen Gesetze erfüllen

Aus Kontakt allein lässt sich keine Kollision erkennen

  • Dass zwei Objekte einander berühren, bedeutet nicht immer, dass gerade eine Kollision vorliegt
  • Eine Kollision ist eine Situation, in der die Objekte sich bei weiterer Bewegung mit ihren aktuellen Geschwindigkeiten gegenseitig durchdringen würden
  • Dieselbe Kontaktszene kann je nach Geschwindigkeitsrichtung der beiden Objekte eine Kollision sein oder nicht
  • Daher braucht die Kollisionsbedingung zwei Dinge zugleich
    • Die Geometrie der Objekte muss sich berühren oder überlappen
    • Die Objekte müssen sich weiterhin in Kollisionsrichtung bewegen

Oberflächennormale und Richtung des Entfernens

  • Ob sich ein Objekt von einer Oberfläche entfernt, lässt sich über die Normalenrichtung (normal direction) der Oberfläche bestimmen
  • Die Normalenrichtung steht senkrecht auf der Oberfläche und zeigt direkt von ihr weg
    • Bei einer flachen Oberfläche ist die Normalenrichtung an jedem Punkt gleich
    • Bei einer gekrümmten Oberfläche ist die Normale an jedem Punkt anders
    • Auf dem Umfang eines Kreises ist die Richtung vom Mittelpunkt zum jeweiligen Punkt auf dem Umfang die Normalenrichtung
  • Die Normalenrichtung wird als normalisierter Vektor der Länge 1 dargestellt
    • Ein Vektor der Länge 1 wird auch Einheitsvektor (unit vector) genannt
    • Um anzuzeigen, dass ein Vektor normalisiert ist, kann über der Variablen ein ^ stehen
  • Die Normalenrichtung an einem Punkt steht senkrecht auf der Tangente (tangent) der Oberfläche an diesem Punkt

Richtungsanteile mit dem Skalarprodukt bestimmen

  • Um zu berechnen, wie stark ein Vektor in dieselbe Richtung wie ein anderer zeigt, kann man das Skalarprodukt (dot product) verwenden
  • Bei 2D-Vektoren ist das Skalarprodukt die Summe der Produkte der entsprechenden Komponenten; das Ergebnis ist kein Vektor, sondern ein Skalar
  • Geometrisch kann man das Skalarprodukt als Produkt aus der skalaren Projektion eines Vektors auf die Richtung des anderen und der Länge des projizierten Vektors auffassen
  • Das Vorzeichen des Skalarprodukts zeigt die Richtungsbeziehung zweier Vektoren an
    • Ist der Winkel zwischen zwei Vektoren kleiner als 90°, ist das Skalarprodukt positiv und sie zeigen grob in dieselbe Richtung
    • Ist der Winkel größer als 90°, ist das Skalarprodukt negativ und sie zeigen grob in entgegengesetzte Richtungen
    • Beträgt der Winkel genau 90°, ist das Skalarprodukt 0
  • Ist das Skalarprodukt aus Geschwindigkeitsvektor eines Objekts und Oberflächennormale positiv, entfernt sich das Objekt von dieser Oberfläche

Anwendung auf die Kollision zweier Objekte

  • Gibt es zwei Objekte wie etwa zwei Boxen, dann hat jedes Objekt seinen eigenen Geschwindigkeitsvektor
  • In diesem Fall verwendet man statt der einzelnen Geschwindigkeiten die Relativgeschwindigkeit (relative velocity) der beiden Objekte
    • Die Relativgeschwindigkeit ist die Differenz der Geschwindigkeiten beider Objekte
    • Geometrisch ist sie der Vektor vom Ende von v_b zum Ende von v_a
    • Zwei Autos, die mit jeweils 50 km/h frontal zusammenstoßen, entsprechen unter gleichen Bedingungen einem Auto, das mit 100 km/h auf ein stehendes Auto auffährt
  • Die zur Oberfläche gehörende Richtung wird durch die Kollisionsnormale (collision normal) dargestellt
    • Wie die Kollisionsnormale berechnet wird, hängt von Form oder Geometrie der kollidierenden Objekte ab
    • Das Beispiel hier ist eine vertex-edge collision, bei der ein Punkt oder Eckpunkt eines Objekts mit der Kante eines anderen Objekts kollidiert
    • Bei einer vertex-edge collision steht die Kollisionsnormale senkrecht auf der betreffenden Kante
  • Konventionsgemäß werden die Objekte mit a und b bezeichnet, und die Kollisionsnormale zeigt auf Objekt a
    • Welches Objekt als a oder b bezeichnet wird, ist egal, solange dies in der gesamten Berechnung konsistent bleibt

Kollision über die relative Normalgeschwindigkeit definieren

  • Berechnet man das Skalarprodukt aus der Relativgeschwindigkeit v_ab und der Kollisionsnormalen n^, kann man feststellen, ob sich die beiden Objekte in Kollisionsrichtung bewegen
  • Dieser Wert heißt relative Normalgeschwindigkeit (relative normal velocity)
    • Sie ist die Komponente der Relativgeschwindigkeit in Richtung der Kollisionsnormalen
    • Hier ist vor allem das Vorzeichen wichtig, aber sie spielt später auch bei der Berechnung der während der Kollision wirkenden Kräfte eine wichtige Rolle
  • Das Vorzeichen der relativen Normalgeschwindigkeit unterscheidet die Kollisionssituation
    • Ist der Wert positiv, entfernen sich die beiden Objekte bereits voneinander
    • Ist der Wert negativ, bewegen sie sich noch aufeinander zu
  • Letztlich liegt eine Kollision dann vor, wenn ein Punkt eines Objekts ein anderes Objekt berührt und die relative Normalgeschwindigkeit negativ ist

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-05-25
Meinungen auf Hacker News
  • Hallo, ich bin der Autor! Als etwas Hintergrund: Dieser Beitrag ist nur Teil 1 einer Blogserie über Rigid-Body-Physik, die ich schreiben möchte
    Der Beitrag richtet sich an Leute, die wie ich keine Spieleentwickler sind und keinen starken mathematischen Hintergrund haben. Deshalb habe ich auch Konzepte ziemlich ausführlich erklärt, die für Erfahrene in diesem Bereich fast selbstverständlich wirken dürften. Wenn es Fragen gibt, beantworte ich sie gern
    • Als Feedback: Das Beispiel in der Einleitung mit „Mario springt auf einem Goomba ab …“ könnte etwas missverständlich sein. Die meisten klassischen Super-Mario-artigen Spiele auf NES und SNES brauchten den Großteil solcher Berechnungen nicht und verwendeten sie auch nicht
      Einsteiger in die Spieleentwicklung glauben oft fälschlicherweise, dass man für Collision Handling Rigid-Body-Kollisionsberechnungen oder eine 2D-Physik-Engine wie Box2D braucht. Wenn man ein Billardspiel oder ein Spiel wie Angry Birds bauen will, in dem Kisten einstürzen, stimmt das. Für einen 2D-Plattformer reicht es aber, Kollisionen durch den Vergleich achsenausgerichteter Rechtecke zu erkennen und dann die X-/Y-Koordinaten der Figur so zu ändern, dass Überlappungen zurückgesetzt werden, oder nach Sprung/Landung die Y-Geschwindigkeit zu setzen. So lässt sich auch das Spielgefühl der Figur feiner abstimmen; Trägheit kann enthalten sein, ist aber normalerweise keine physikalisch realistische Trägheit. Wenn Anfänger realistische Physik verwenden wollen, fühlt sich die Bewegung leicht schwebend und unbefriedigend an
      Ein Tutorial-Beispiel, mit dem man mit diesem einfachen Ansatz ohne Physik-Engine anfangen kann: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
    • Sehr gut. Der Abschnitt „A word about math“ ist wirklich wichtig. Ich bin selbst nicht besonders gut in Mathe, habe aber früher einmal mathematische Konzepte extrem vereinfacht, um eine sehr grundlegende Physiksimulation zu bauen
      Ich habe Bausteine wie Punkte und Linien immer wieder aufeinander aufgesetzt, und mit vielen kleinen Schritten und visuellen Debug-Linien war das Ergebnis sehr hakelig und langsam, funktionierte aber immerhin bis zu einem gewissen Grad
    • Der Beitrag ist ausgezeichnet und hat Spaß gemacht zu lesen. Da ich ebenfalls keinen starken mathematischen Hintergrund habe, danke ich für die Erklärung solcher „selbstverständlichen“ Konzepte :)
      Hast du vor, künftig auch XPBD (Extended Position Based Dynamics – http://mmacklin.com/xpbd.pdf) zu lesen und zu erklären? Dieses Konzept scheint zunehmend Aufmerksamkeit zu bekommen, und ich habe es in Bevy über https://github.com/Jondolf/bevy_xpbd ziemlich erfolgreich eingesetzt. Es wirkt stabiler als der übliche Ansatz
    • Ich habe den Beitrag wirklich gern gelesen :) Auch aus der Perspektive von jemandem, der sich in der Schule mit ähnlichen Inhalten schwergetan hat, war er gut verständlich
      Es wäre wirklich schön, wenn du einen RSS-Feed hinzufügen würdest, damit man weiter folgen kann
    • Die Erklärung ist wirklich gut!
      Aus Neugier: Welche Tools hast du zum Erstellen der Seite verwendet?
  • Oh! Gut recherchiert, tief erklärt und sogar interaktiv
    Ehrlich gesagt dachte ich anfangs, als ich den Domainnamen sah und bemerkte, dass die Top-Level-Domain „.ski“ ist, es sei die Seite der Person, die Mechanical Watch [1] und andere großartige Beiträge geschrieben hat. Es stellte sich heraus, dass es eine ganz andere Person ist, aber die Qualität ist ähnlich. Was ist nur die Geheimzutat dieser „.ski“-Top-Level-Domain? :)
    1. https://news.ycombinator.com/item?id=31261533
    • Der Grund ist sehr einfach. „ski“ ist das häufigste Suffix bei polnischen Nachnamen, das bekannteste Beispiel ist Kowalski. Es gibt ziemlich viele Menschen, die Polen sind oder polnische Wurzeln haben
      Der Autor von https://ciechanow.ski, den wir hier mögen, ist ebenfalls ein polnischer Programmierer, der bei Apple arbeitet
  • Ich baue gerade zusammen mit meinem Sohn als Nebenprojekt einen 2D-Weltraum-Shooter. Die Ansicht ist von oben, und die Idee ist, dass jeder Spieler ein Raumschiff steuert, in einem geschlossenen Bereich voller Weltraumschrott herumfliegt und auf den Gegner schießt
    Ein wichtiger Bestandteil des Spiels ist, dass man den Weltraumschrott in der Arena bewegen und kreativ nutzen kann, um den Gegner einzusperren oder ihn daran zu hindern, Ziele zu erreichen. Als Teil des Projekts wollten wir eine Game Engine komplett überspringen. Ich wollte meinem Sohn etwas mehr über Anwendungsarchitektur beibringen, und selbst wenn wir später eine fertige Game Engine verwenden, wollte ich zumindest einmal den Prozess durchlaufen, alles selbst zu implementieren. Bis wir zur Kollisionserkennung und -behandlung kamen, lief es gut. Ab da ging es schnell bergab. Obwohl ich einen theoretisch-mathematischen Hintergrund habe, war ich von der enormen Zahl an Grenzfällen schnell überwältigt und habe schließlich aufgegeben und mich für Box2D entschieden. Ich bin kein professioneller Spieleentwickler, habe aber über 20 Jahre Entwicklungserfahrung und einen mathematischen Hintergrund, und trotzdem habe ich den Fehler gemacht, dieses Problem zu unterschätzen. In Worten klingt es einfach, aber je tiefer man in die Details geht, desto mehr scheint die Komplexität exponentiell zu wachsen
    • Brauchte dieses Spiel wirklich realistische physikalische Kollisionen? Wenn nicht, könnte das unnötige Komplexität sein. Vor 2000 nutzten fast alle 2D-Shooter, und auch danach nur sehr wenige Spiele, so einen Ansatz
      Eine übliche Methode, einen Shooter mit sehr einfachen Rechteckvergleichen zu bauen, findet sich hier: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
      Wenn die Weltraumschrott-Objekte allerdings realistisch kollidieren und sich zusammenballen sollen und du möchtest, dass es für das Spielerschiff schwierig ist, eine Gruppe schwerer Objekte wegzuschieben, ist der Einsatz einer Physikbibliothek sinnvoll
    • Hast du dir Verlet-Integration [1] angesehen? Für viele Anwendungsfälle ist sie ziemlich überzeugend und praktisch, und in der Praxis recht einfach. Ich war selbst überrascht, dass ich nach diesem hervorragenden Tutorial [2] in ein paar Stunden ein grundlegendes Physiksystem bauen konnte
      [1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...

[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...

  • Trotzdem dürfte das eine gute Lektion für seinen Sohn sein. Denn es lohnt sich nicht immer, dem Traum zu folgen, in jedem Teil eines Projekts alles wirklich selbst von Grund auf zu bauen.
  • Wenn nicht jetzt, dann wird es später eine nützliche Referenz sein. http://www.jeffreythompson.org/collision-detection/table_of_... behandelt Kollisionserkennung zwischen Punkten, Kreisen, Rechtecken, Linien, Polygonen und Dreiecken.
  • Ich mochte die Erklärung von N Game schon immer: https://www.metanetsoftware.com/technique/tutorialA.html
    Das war noch die Zeit, als Flash überall war.
  • Ich hatte Spaß daran, zu diesem Thema eine TypeScript-Demo mit springenden und kollidierenden Bällen zu bauen. Ich habe viel gelernt.
    Code: https://github.com/vandrieu/canvas-bouncing-ball
    Die Kollisionslogik befindet sich in src/collision.ts.
    Ergebnis/Demo: https://vandrieu.github.io/canvas-bouncing-ball/
    • Eine wirklich gute Demo, gut gemacht! Wenn es für dich in Ordnung ist, würde ich das gern in ein kleines Multiplayer-Spiel verwandeln.
      Könntest du, wenn möglich, eine Lizenz hinzufügen?
  • Wenn man bei Starrkörperdynamik und Constraints tiefer einsteigen möchte, war diese Blogpost-Serie sehr hilfreich: https://www.toptal.com/game/video-game-physics-part-i-an-int...
  • Eine Kollision ist die Verletzung einer paarweisen Nichtdurchdringungs-Constraint zwischen Objekten. Die Kollisionskraft ist der Lagrange-Multiplikator dieser Constraint. Die Kollisionsnormale ist die normalisierte partielle Ableitung der Constraint-Funktion nach der Konfiguration eines Objekts.
    • Dieser Ansatz dürfte gut passen, wenn man die Physik mit 1 kHz oder mehr berechnet und numerisch stabile Integrationsalgorithmen verwendet, die die Energieerhaltung respektieren.
      In Spielen werden Physik-Updates aber oft bis auf 30 Hz abgesenkt und mit einem willkürlichen Euler-Cromer-Verfahren umgesetzt, daher braucht man einen ziemlich anderen Ansatz.
    • Interessant! Gibt es Material, das diese Sichtweise näher erklärt?
  • Wirklich großartig! Mir gefielen die Erklärung, die Interaktion und besonders der freundliche Ton des Artikels. Ich freue mich auf die nächsten Beiträge.
  • Eine 2D-Starrkörper-Physik-Engine zu bauen, ist ein wirklich spaßiges Projekt. Ich habe eine in JavaScript gebaut, bevor ich lineare Algebra gelernt hatte, und mich tief in die Mathematik eingearbeitet, damit sie funktioniert.
    Ich habe Monate damit verbracht, aber damit nur knapp an der Oberfläche gekratzt, auf einem Niveau, das etwas über die allgemein bekannten Grundlagen hinausging. Eine stabile Engine zu bauen, bei der Objekte nicht ineinander gedrückt werden oder zittern, ist ein bodenloser Kaninchenbau, und selbst die mathematiklastigen Artikel, die ich finden konnte, behandelten das kaum. Ich habe die Mathematik über Christ Heckers alte Artikelserie verstanden.
    http://www.chrishecker.com/Rigid_Body_Dynamics
    • Genau! „Part 3: Collision Response“ ist im Grunde das, was in diesen Artikeln als Referenzmaterial verwendet wird.
  • Ich habe mit canvas angefangen, um JavaScript zu lernen, und ohne Erfahrung in der Spieleentwicklung ein paar niedliche kleine Browsergames gebaut. Eines davon ist ein Galaga-Klon, der im Großen und Ganzen gut funktioniert.
    Der schwierige Teil sind Projektilkollisionen. Ich hätte die aktuelle Position der Kugel und ihre Position im nächsten Zeitschritt nehmen und dasselbe für die Hitbox des Gegners machen müssen, um dann auf Überschneidungen zu prüfen. Ich habe aber nur den aktuellen Zeitschritt geprüft. Dadurch können Kugeln wie durch Zauberhand am Gegner vorbeifliegen! Dumm gelaufen. Vielleicht gehe ich irgendwann zurück und behebe es.