7 days of WordPress plugins, themes & templates - for free!* Unlimited asset downloads! Start 7-Day Free Trial
Advertisement
  1. Code
  2. ActionScript

Vorhersage von Kollisionspunkten mit Mathematik in AS3

Read Time: 13 mins
This post is part of a series called Collision Detection and Reaction.
Pixel-Level Collision Detection
Pixel-Level Collision Detection Based on Pixel Colors

German (Deutsch) translation by Valentina (you can also view the original English article)

In meinem vorherigen Tutorial zur Kollisionserkennung zwischen einem Kreis und einer Linie habe ich die Projektion auf eine Linie mit dem Punktprodukt eines Vektors behandelt. In diesem Tutorial werden wir uns das senkrechte Punktprodukt ansehen und es verwenden, um den Schnittpunkt für zwei Linien vorherzusagen.


Endergebnis Vorschau

Werfen wir einen Blick auf das Endergebnis, auf das wir hinarbeiten werden. Verwenden Sie die linke und rechte Pfeiltaste, um das Schiff zu steuern(Dreieck), und drücken Sie nach oben, um die Geschwindigkeit vorübergehend zu erhöhen. Befindet sich der projizierte zukünftige Kollisionspunkt an der Wand (der Linie), wird ein roter Punkt darauf gemalt. Bei einer Kollision, die "bereits" aufgetreten ist (d. h. In der Vergangenheit aufgetreten wäre, basierend auf der aktuellen Richtung), wird weiterhin ein roter Punkt gezeichnet, der jedoch leicht transparent ist.

Sie können auch mit der Maus klicken und die schwarzen Punkte ziehen, um die Wand zu verschieben. Beachten Sie, dass wir nicht nur den Ort der Kollision, sondern auch die Zeit vorhersagen.


Schritt 1: Überarbeitung

Bevor wir zum Thema kommen, lassen Sie uns einige Überarbeitungen vornehmen. Hier ist die Punktproduktgleichung (zuvor hier behandelt):

dot product formuladot product formuladot product formula

Und hier ist die senkrechte Punktproduktdefinition, wie sie aus Wolfram extrahiert wurde:

perp dot product formulaperp dot product formulaperp dot product formula

Schritt 2: Senkrechtes Punktprodukt

Um uns ein Bild zu machen, habe ich das folgende Bild vorbereitet. Ich bin zuversichtlich, dass Sie an dieser Stelle die vertikalen und horizontalen Komponenten eines Vektors ableiten können, sodass die Komponenten mit Sinus und Cosinus keine Herausforderung darstellen sollten.

a mental picture for two formulaa mental picture for two formulaa mental picture for two formula

Ersetzen wir beide Komponenten durch ihre Entsprechung. Ich habe A mit einem Hut verwendet, um den Einheitsvektor von A darzustellen (d.h. einen Vektor, der in die gleiche Richtung wie A zeigt, aber eine Größe von genau 1 hat). Ein weiteres Detail ist, dass die Senkrechte von B tatsächlich die richtige Normalen von B ist - mehr zu den Normalen im nächsten Schritt.

second mental picture for two formulasecond mental picture for two formulasecond mental picture for two formula

Aus dem obigen Diagramm können wir sehen, dass die Projektion von B auf A |B|*cos (theta) erzeugt. Aber warum sollte die Projektion von B's Normal |B|*sin (theta) erzeugen?

Um dies besser zu verstehen, habe ich unten eine Flash-Demo eingefügt. Klicken und ziehen Sie die schwarze Pfeilspitze. Wenn Sie es vorsichtig bewegen, werden Sie feststellen, dass auch seine senkrechte Achse folgt. Während sie sich drehen, werden auch die fetten roten Linien animiert. Beachten Sie, dass diese beiden Längen gleich sind - daher die Gleichung des senkrechten Punktprodukts.


Schritt 3: Normalen

Normalen liegen per Definition auf einer senkrechten Linie, die Ihre interessierende Linie schneidet. Versuchen wir uns diese Linien auf einer geometrischen Ebene vorzustellen.

normals of a vectornormals of a vectornormals of a vector

Das kartesische Koordinatensystem wird im obigen Diagramm verwendet. B ist die linke Normalität und C ist die rechte Normalität. Wir sehen, dass die x-Komponente von B negativ ist (weil sie nach links zeigt) und die y-Komponente von C negativ ist (weil sie nach unten zeigt).

Überprüfen Sie jedoch die Ähnlichkeiten zwischen B und C. Ihre x- und y-Komponenten sind die gleichen wie die von A, außer dass sie durcheinander gebracht wurden. Der Unterschied ist nur die Position des Zeichens. Wir kommen also zu einer Schlussfolgerung aus dem Bild unten.

second mental picture for two formulasecond mental picture for two formulasecond mental picture for two formula

Beachten Sie, dass wir uns in diesem Beispiel speziell auf das kartesische Koordinatensystem beziehen. Die y-Achse des Flash-Koordinatenraums spiegelt die kartesische Achse wider, was zu einem Wechsel zwischen der linken und der rechten Normalen führt.


Schritt 4: Projizieren des Kollisionspunktes

Um den Kollisionspunkt des Vektors k auf Ebene A herauszufinden, verbinden wir zuerst den Schwanz von k mit einem beliebigen Punkt auf Ebene A. Für den folgenden Fall ist der Vektor j der Verknüpfungsvektor; dann erhalten wir die senkrechte Projektion von k und j auf Ebene A.

using perp dot product of vectorsusing perp dot product of vectorsusing perp dot product of vectors

Der rote Punkt auf dem Bild unten ist der Kollisionspunkt. Und ich hoffe, Sie können das ähnliche Dreieck im folgenden Diagramm sehen.

similar trianglessimilar trianglessimilar triangles
  • |k|, Größe des Vektors k
  • Länge von j senkrecht zur Ebene A.
  • Länge von k senkrecht zur Ebene A.

Angesichts der drei oben genannten Komponenten können wir das Konzept des Verhältnisses verwenden, um die Länge zwischen dem roten und dem blauen Punkt abzuleiten. Schließlich setzen wir die Größe des Vektors k auf diese Länge und haben unseren Kollisionspunkt!


Schritt 5: ActionScript-Implementierung

Hier kommt also die ActionScript-Implementierung. Ich habe unten eine Demo beigefügt. Versuchen Sie, die Pfeilspitzen so zu bewegen, dass sich beide Linien schneiden. Ein kleiner schwarzer Punkt markiert den Schnittpunkt der Linien. Beachten Sie, dass sich diese Segmente nicht unbedingt schneiden, sondern die unendlichen Linien, die sie darstellen.

Hier ist das Skript, das die Berechnungen durchführt. Unter Basic.as im Quelldownload finden Sie das vollständige Skript.


Schritt 6: Liniengleichungen

Daher hoffe ich, dass der erste Ansatz, den ich vorgestellt habe, leicht verständlich war. Ich verstehe, dass die Leistung beim Ermitteln des Schnittpunkts wichtig ist. Daher werde ich als Nächstes alternative Ansätze bereitstellen, obwohl dies einige mathematische Überarbeitungen erfordert. Tragen Sie mit mir!

Lassen Sie uns zunächst über Liniengleichungen sprechen. Es gibt verschiedene Formen der Liniengleichung, aber wir werden in diesem Tutorial nur zwei davon berühren:

  • Generelle Form
  • Parametrische Form

Ich habe das Bild unten eingefügt, damit Sie sich besser erinnern können. Interessenten können sich auf diesen Eintrag auf Wikipedia beziehen.

different forms of line equationdifferent forms of line equationdifferent forms of line equation

Schritt 7: Ableiten des Standardformulars

Bevor wir Manipulationen an zwei Liniengleichungen durchführen, müssen wir diese Liniengleichungen zuerst ableiten. Betrachten wir das Szenario, in dem wir Koordinaten von zwei Punkten p1 (a, b) erhalten. und p2 (c, d). Wir können eine Liniengleichung bilden, die diese beiden Punkte aus den Verläufen verbindet:

derive constantsderive constantsderive constants

Dann können wir unter Verwendung dieser Gleichung die Konstanten A, B und C für die Standardform ableiten:

derive constantsderive constantsderive constants

Als nächstes können wir mit dem Lösen simultaner Liniengleichungen fortfahren.


Schritt 8: Simultangleichungen lösen

Nachdem wir nun Liniengleichungen bilden können, nehmen wir zwei Liniengleichungen und lösen sie gleichzeitig. Angesichts dieser beiden Liniengleichungen:

  • Ex + Fy = G.
  • Px + Qy = R.

Ich werde diese Koeffizienten gemäß der allgemeinen Form Ax + By = C tabellieren.

A B. C.
E. F. G
P. Q. R.

Um den Wert von y zu erhalten, gehen wir wie folgt vor:

  1. Multiplizieren Sie die reziproken Koeffizienten von x für die gesamte Gleichung.
  2. Führen Sie für beide Gleichungen eine Subtraktionsoperation (von oben) durch.
  3. Ordne die erhaltene Gleichung in y um.
A B. C. Multipliziert mit
E. F. G P.
P. Q. R. E.

Und wir kommen zu der folgenden Tabelle.

A B. C.
EP FP GP
SPORT QE RE

Nachdem wir zwei Gleichungen herausgezogen haben, kommen wir zu:

  • y (FP - QE) = (GP - RE), das sich neu ordnet zu:
  • y = (GP - RE) / (FP - QE)

Fahren Sie fort, um x zu erhalten:

A B. C. Multipliziert mit
E. F. G Q.
P. Q. R. F.

Wir kommen zu der folgenden Tabelle

A B. C.
EQ FQ GQ
PF QF RF

Nachdem wir die beiden Gleichungen herausgezogen haben, kommen wir zu:

  • x (EQ - PF) = (GQ - RF), das sich neu ordnet zu:
  • x = (GQ - RF) / (EQ - PF)

Lassen Sie uns y weiter neu ordnen.

  • y = (GP - RE) / (FP - QE)
  • y = (GP - RE) / - (QE - FP)
  • y = (RE - GP) / (QE - FP)

Wir kommen also zum Schnittpunkt von x und y. Wir stellen fest, dass sie denselben Nenner haben.

  • x = (GQ - RF) / (EQ - PF)
  • y = (RE - GP) / (QE - FP)

Nachdem wir die mathematischen Operationen ausgearbeitet und das Ergebnis erhalten haben, pflücken Sie einfach die Werte ein und wir haben den Schnittpunkt.


Schritt 9: Anwenden auf Actionscript

Hier ist die Actionscript-Implementierung. Daher werden alle Vektoroperationen auf einfache Arithmetik reduziert, es sind jedoch zunächst einige Algebraarbeiten erforderlich.

Natürlich ist es das gleiche Ergebnis wie in der vorherigen Demo, nur mit weniger Mathematik und ohne Verwendung der Vector2D-Klasse.


Schritt 10: Matrix Alternative

Eine andere Alternative zur Lösung dieses Problems ist die Verwendung von Matrixmathematik. Ich lade wieder interessierte Leser ein, in Prof. Wildbergers Vortrag über Liniengleichungen einzutauchen. Hier werden wir das Konzept schnell durchgehen.

Laut Prof. Wildberger gibt es zwei Rahmenbedingungen, die wir übernehmen können:

  • Der kartesische Rahmen
  • Das parametrisierte Vektor-Framework

Lassen Sie uns zuerst die kartesische durchgehen. Schauen Sie sich das Bild unten an.

Cartesian matrix operationCartesian matrix operationCartesian matrix operation

Beachten Sie, dass die Matrix T und S konstante Werte enthalten. Was unbekannt bleibt, ist A. Wenn wir also die Matrixgleichung in Bezug auf A neu anordnen, erhalten wir das Ergebnis. Wir müssen jedoch die inverse Matrix von T erhalten.


Schritt 11: Implementierung mit AS3

Hier ist die Implementierung des oben genannten mit ActionScript:


Schritt 12: Parametrische Form

Schließlich gibt es die parametrische Form der Liniengleichung, und wir werden versuchen, sie erneut durch Matrixmathematik zu lösen.

deriving matrix from parametric equationsderiving matrix from parametric equationsderiving matrix from parametric equations

Wir möchten den Schnittpunkt erhalten. Angesichts aller Informationen außer u und v, die wir zu finden versuchen, werden wir beide Gleichungen in Matrixform umschreiben und lösen.


Schritt 13: Matrixmanipulation

Also führen wir erneut Matrixmanipulationen durch, um zu unserem Ergebnis zu gelangen.

arriving at resultarriving at resultarriving at result

Schritt 14: Implementierung mit AS3

Hier ist die Implementierung der Matrixform:


Schritt 15: Leistung

Wir haben vier Ansätze zur Lösung dieses kleinen Problems behandelt. Was ist also mit der Leistung? Nun, ich denke, ich überlasse dieses Thema nur den Lesern, obwohl ich glaube, dass der Unterschied vernachlässigbar ist. Nutzen Sie diesen Kabelbaum für Leistungstests von Grant Skinner.

Nun, da wir dieses Verständnis haben, was kommt als nächstes? Wende es an!


Schritt 16: Vorhersage der Kollisionszeit

Angenommen, ein Partikel bewegt sich auf einem Pfad, der mit einer Wand kollidieren soll. Wir können die Zeit bis zum Aufprall anhand der einfachen Gleichung berechnen:

Geschwindigkeit = Verschiebung / Zeit

concept of tunnelingconcept of tunnelingconcept of tunneling

Stellen Sie sich vor, Sie befinden sich in diesem orangefarbenen runden Partikel und für jeden vorbeiziehenden Frame und jede Ankündigung erfolgt die Zeit, um mit der Wand zu kollidieren. Sie werden hören:

"Zeit bis zum Aufprall: 1.5 Frames" - Frame 1

"Zeit bis zum Aufprall: 0.5 Bilder" - Bild 2

"Zeit bis zum Aufprall: -0.5 Frames" - Frame 3

Wenn wir Bild 3 erreichen, ist bereits eine Kollision mit der Linie aufgetreten (wie durch das negative Vorzeichen angezeigt). Sie müssen die Zeit zurückspulen, um den Kollisionspunkt zu erreichen. Offensichtlich sollte eine Kollision zwischen den Bildern 2 und 3 auftreten, aber Flash bewegt sich in Einzelbildschritten. Wenn also eine Kollision auf halbem Weg zwischen den Frames aufgetreten ist, zeigt ein Umdrehen des Vorzeichens auf negativ an, dass die Kollision bereits aufgetreten ist.


Schritt 17: Negative Zeit

getting negative displacementgetting negative displacementgetting negative displacement

Um eine negative Zeit zu erhalten, verwenden wir das Vektorpunktprodukt. Wir wissen, dass wenn wir zwei Vektoren haben und die Richtung von einem nicht innerhalb von 90 Grad auf beiden Seiten des anderen liegt, sie ein negatives Punktprodukt erzeugen. Das Punktprodukt ist auch ein Maß dafür, wie parallel zwei Vektoren sind. Wenn also bereits eine Kollision stattgefunden hat, sind Geschwindigkeit und Richtung eines Vektors zu einem Punkt an der Wand negativ - und umgekehrt.


Schritt 18: ActionScript-Implementierung

Hier ist das Skript (in CollisionTime.as enthalten). Ich habe hier auch die Kollisionserkennung innerhalb des Liniensegments hinzugefügt. Für diejenigen, die es nicht kennen, lesen Sie mein Tutorial zur Kollisionserkennung zwischen einem Kreis und einem Liniensegment, Schritt 6. Und für die Hilfe beim Steuern von Schiffen, hier eine weitere Referenz.


Schritt 19: Endergebnis

Hier ist eine Demo von dem, was Sie erreichen werden. Verwenden Sie die linke und rechte Pfeiltaste, um das Schiff zu steuern (Dreieck), und drücken Sie Nach oben, um die Geschwindigkeit vorübergehend zu erhöhen. Befindet sich der vorhergesagte zukünftige Kollisionspunkt an der Wand (der Linie), wird ein roter Punkt darauf gemalt. Bei einer Kollision, die "bereits" stattgefunden hat, wird weiterhin ein roter Punkt gemalt, der jedoch leicht transparent ist. Sie können auch die schwarzen Punkte auf beiden Seiten der Wand ziehen, um sie zu verschieben.

Abschluss

Ich hoffe, dieses Tutorial war informativ. Teilen Sie mit, wenn Sie diese Idee tatsächlich an einer anderen Stelle als der von mir erwähnten angewendet haben. Ich plane eine kurze Beschreibung der Anwendung zum Malen von Laserzielen - was denkst du? Vielen Dank fürs Lesen und lassen Sie mich wissen, wenn es Fehler gibt.

Advertisement
Did you find this post useful?
Want a weekly email summary?
Subscribe below and we’ll send you a weekly email summary of all new Code tutorials. Never miss out on learning about the next big thing.
Advertisement
Scroll to top
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.