Wenn Welten kollidieren Simulation von Kreis-Kreis-Kollisionen

Die meiste Kollisionserkennung in Computerspielen wird mit der AABB-Technik durchgeführt: Ganz einfach: Wenn sich zwei Rechtecke schneiden, ist eine Kollision aufgetreten. Es ist schnell, effizient und unglaublich effektiv - für rechteckige Objekte. Was aber, wenn wir Kreise zusammenschlagen wollten? Wie berechnen wir den Kollisionspunkt und wohin gehen die Objekte? Es ist nicht so schwer wie du vielleicht denkst…

Hinweis: Obwohl dieses Tutorial mit AS3 und Flash geschrieben wurde, sollten Sie in der Lage sein, in fast jeder Spieleentwicklungsumgebung dieselben Techniken und Konzepte anzuwenden.

Vorschaubild aus diesem klassischen Psdtuts + Tutorial.


Schritt 1: Erstellen Sie einige Bälle

Ich werde diesen Schritt überdenken, denn wenn Sie keine grundlegenden Sprites erstellen können, wird der Rest des Tutorials ein wenig über Ihnen liegen.

Es genügt zu sagen, wir haben einen Ausgangspunkt. Nachfolgend finden Sie eine sehr rudimentäre Simulation von Bällen, die um einen Bildschirm springen. Berühren sie den Bildschirmrand, springen sie zurück.

Es ist jedoch eine wichtige Sache zu beachten: Wenn Sie Sprites erstellen, wird der obere linke Teil häufig auf den Ursprung gesetzt (0, 0) und unten rechts ist (Breite Höhe). Hier sind die Kreise, die wir erstellt haben, auf dem Sprite zentriert.

Dies erleichtert die Arbeit erheblich, denn wenn die Kreise nicht zentriert sind, müssen wir sie bei jeder Berechnung um den Radius verschieben, die Berechnung durchführen und dann zurücksetzen.

Den Code finden Sie bis zu diesem Punkt im v1 Ordner des Quelldownloads.


Schritt 2: Suchen Sie nach Überlappungen

Als erstes wollen wir prüfen, ob sich unsere Bälle in der Nähe befinden. Es gibt einige Möglichkeiten, dies zu tun, aber da wir gute kleine Programmierer sein wollen, beginnen wir mit einem AABB-Check.

AABB steht für achsausgerichtete Begrenzungsbox und bezieht sich auf ein Rechteck, das so gezeichnet ist, dass es fest um ein Objekt passt und dessen Seiten parallel zu den Achsen ausgerichtet sind.

Eine AABB-Kollisionsprüfung funktioniert nicht Prüfen Sie, ob die Kreise einander überlappen, aber es zeigt uns an, ob dies der Fall ist nahe gegenseitig. Da in unserem Spiel nur vier Objekte verwendet werden, ist dies nicht erforderlich. Wenn Sie jedoch eine Simulation mit 10.000 Objekten ausführen, sparen wir durch diese kleine Optimierung viele CPU-Zyklen.

Auf geht's:

 if (firstBall.x + firstBall.radius + secondBall.radius> secondBall.x && ersterBall.x < secondBall.x + firstBall.radius + secondBall.radius && firstBall.y + firstBall.radius + secondBall.radius > secondBall.y && firstBall.y < seconBall.y + firstBall.radius + secondBall.radius)  //AABBs are overlapping 

Dies sollte ziemlich einfach sein: Wir stellen Begrenzungsboxen mit der Größe des Quadrates jedes Balls her.

Hier ist eine „Kollision“ aufgetreten - oder besser, die beiden AABBs überlappen sich, was bedeutet, dass die Kreise nahe beieinander liegen und möglicherweise kollidieren.

Sobald wir wissen, dass sich die Kugeln in der Nähe befinden, können wir etwas komplexer werden. Mit Hilfe der Trigonometrie können wir den Abstand zwischen den beiden Punkten bestimmen:

 distance = Math.sqrt ((((firstBall.x - secondBall.x) * (firstBall.x - secondBall.x)) + ((firstBall.y - secondBall.y) * (firstBall.y - secondBall.y))) ; wenn (Entfernung) < firstBall.radius + secondBall.radius)  //balls have collided 

Hier verwenden wir den Satz von Pythagoras, a ^ 2 + b ^ 2 = c ^ 2, um den Abstand zwischen den Mittelpunkten der beiden Kreise zu ermitteln.

Wir kennen die Längen nicht sofort ein und b, Aber wir kennen die Koordinaten jedes Balls. Es ist also trivial zu erarbeiten:

 a = firstBall.x - secondBall.x; b = erster Ball.y - zweiter Ball.y;

Wir lösen dann nach c mit etwas algebraischer Umlagerung: c = Math.sqrt (a ^ 2 + b ^ 2) - daher dieser Teil des Codes:

 distance = Math.sqrt ((((firstBall.x - secondBall.x) * (firstBall.x - secondBall.x)) + ((firstBall.y - secondBall.y) * (firstBall.y - secondBall.y))) ;

Wir prüfen diesen Wert dann anhand der Summe der Radien der beiden Kreise:

 wenn (Entfernung) < firstBall.radius + secondBall.radius)  //balls have collided 

Warum prüfen wir gegen die kombinierten Radien der Kreise? Wenn wir uns das Bild unten ansehen, können wir das sehen - egal in welchem ​​Winkel sich die Kreise berühren - wenn sie dann die Linie berühren c entspricht r1 + r2.

Also - wenn c ist gleich oder kleiner als r1 + r2, dann müssen sich die Kreise berühren. Einfach!

Beachten Sie außerdem, dass Sie zur korrekten Berechnung von Kollisionen wahrscheinlich zuerst alle Objekte verschieben und dann eine Kollisionserkennung durchführen müssen. Andernfalls haben Sie möglicherweise eine Situation, in der Ball1 Updates, prüft auf Kollisionen, kollidiert dann Ball2 Updates, ist nicht mehr im selben Bereich wie Ball1, und meldet keine Kollision. Oder als Code:

 für (n = 0; n 

ist viel besser als

 für (n = 0; n   

Den Code finden Sie bis zu diesem Punkt im v2 Ordner des Quelldownloads.


Schritt 3: Kollisionspunkte berechnen

Für Ballkollisionen ist dieser Teil nicht unbedingt erforderlich, aber er ist ziemlich cool, also werfe ich ihn rein. Wenn Sie nur alles herumspringen möchten, können Sie mit dem nächsten Schritt fortfahren.

Es kann manchmal praktisch sein, den Punkt herauszufinden, an dem zwei Kugeln zusammengestoßen sind. Wenn Sie beispielsweise einen Partikeleffekt hinzufügen möchten (möglicherweise eine kleine Explosion) oder eine Art Richtlinie für ein Snooker-Spiel erstellen, kann es hilfreich sein, den Kollisionspunkt zu kennen.

Es gibt zwei Möglichkeiten, dies herauszufinden: den richtigen Weg und den falschen Weg.

Der falsche Weg, den viele Tutorials verwenden, besteht darin, die beiden Punkte zu mitteln:

 collisionPointX = (firstBall.x + secondBall.x) / 2 collisionPointY = (firstBall.y + secondBall.y) / 2

Dies funktioniert aber nur, wenn die Bälle gleich groß sind.

Die Formel, die wir verwenden möchten, ist etwas komplizierter, funktioniert aber für Bälle aller Größen:

 collisionPointX = ((firstBall.x * secondBall.radius) + (secondBall.x * firstBall.radius)) / (firstBall.radius + secondBall.radius); collisionPointY = ((firstBall.y * secondBall.radius) + (secondBall.y * firstBall.radius)) / (firstBall.radius + zweiter Ball.radius);

Dies verwendet die Radien der Kugeln, um uns die wahren x- und y-Koordinaten des Kollisionspunkts zu geben, dargestellt durch den blauen Punkt in der Demo unten.

Den Code finden Sie bis zu diesem Punkt im v3 Ordner des Quelldownloads.


Schritt 4: Zusammenprallen

Nun wissen wir, wann unsere Objekte ineinander stoßen, und wir kennen ihre Geschwindigkeit und ihre x- und y-Position. Wie können wir herausfinden, wohin sie als nächstes reisen??

Wir können etwas namens elastische Kollision.

Der Versuch, in Worten zu erklären, wie eine elastische Kollision funktioniert, kann kompliziert sein - das folgende animierte Bild sollte die Dinge klarer machen.


Bild von http://en.wikipedia.org/wiki/Elastic_collision

Wir verwenden einfach mehr Dreiecke.

Jetzt können wir die Richtung herausfinden, die jeder Ball einnimmt, aber es können andere Faktoren am Werk sein. Spin, Reibung, das Material, aus dem die Kugeln bestehen, Masse und unzählige andere Faktoren können verwendet werden, um die „perfekte“ Kollision zu erreichen. Wir werden uns nur um eines davon kümmern: Masse.

In unserem Beispiel nehmen wir an, dass der Radius der Kugeln, die wir verwenden, auch deren Masse ist. Wenn wir nach Realismus streben, wäre dies ungenau, da die Masse der Kugeln - vorausgesetzt, dass alle Kugeln aus demselben Material bestehen - entweder ihrer Fläche oder ihrem Volumen proportional ist, je nachdem, ob Sie sie berücksichtigen möchten oder nicht Scheiben oder Kugeln. Da dies jedoch ein einfaches Spiel ist, genügt die Verwendung der Radien.

Wir können die folgende Formel verwenden, um die Änderung der x-Geschwindigkeit der ersten Kugel zu berechnen:

 newVelX = (firstBall.speed.x * (firstBall.mass - secondBall.mass) + (2 * secondBall.mass * secondBall.speed.x)) / (firstBall.mass + secondBall.mass);

Also, lasst uns das einfach noch einmal durchgehen:

  • Angenommen, beide Kugeln haben die gleiche Masse (wir sagen 10).
  • Der erste Ball bewegt sich mit 5 Einheiten / Update (nach rechts). Die zweite Kugel bewegt sich -1 Einheiten / Update (nach links).
 NewVelX = (5 * (10-10) + (2 * 10 * -1)) / (10 + 10) = (5 * 0) + (-20) / 20 = -20/20 = -1

In diesem Fall beginnt der erste Ball bei einer Frontalkollision mit -1 Einheit / Aktualisierung. (Nach links). Da die Massen der Kugeln gleich sind, die Kollision direkt ist und keine Energie verloren gegangen ist, haben die Kugeln Geschwindigkeiten "gehandelt". Wenn Sie einen dieser Faktoren ändern, wird sich das Ergebnis offensichtlich ändern.

(Wenn Sie dieselbe Berechnung verwenden, um die neue Geschwindigkeit des zweiten Balls herauszufinden, bewegen Sie sich mit 5 Einheiten / Update nach rechts)..

Wir können dieselbe Formel verwenden, um die x / y-Geschwindigkeiten beider Kugeln nach der Kollision zu berechnen:

 newVelX1 = (firstBall.speed.x * (firstBall.mass - secondBall.mass) + (2 * secondBall.mass * secondBall.speed.x)) / (firstBall.mass + secondBall.mass); newVelY1 = (firstBall.speed.y * (firstBall.mass - secondBall.mass) + (2 * secondBall.mass * secondBall.speed.y)) / (firstBall.mass + secondBall.mass); newVelX2 = (secondBall.speed.x * (secondBall.mass - firstBall.mass) + (2 * firstBall.mass * firstBall.speed.x)) / (firstBall.mass + secondBall.mass); newVelY2 = (secondBall.speed.y * (secondBall.mass - firstBall.mass) + (2 * firstBall.mass * firstBall.speed.y)) / (firstBall.mass + secondBall.mass);

Hoffentlich ist es offensichtlich, dass jede Berechnung gleich ist, indem Sie einfach die Werte entsprechend ersetzen.

Sobald dies geschehen ist, haben wir die neuen Geschwindigkeiten für jeden Ball. Also sind wir fertig Nicht ganz.

Zuvor haben wir sichergestellt, dass alle unsere Positionsaktualisierungen gleichzeitig durchgeführt werden dann Auf Kollisionen prüfen. Das heißt, wenn wir auf kollidierende Bälle prüfen, ist es sehr wahrscheinlich, dass eine Kugel in einer anderen ist. Wenn also die Kollisionserkennung aufgerufen wird, registrieren sowohl die erste als auch die zweite Kugel diese Kollision, was bedeutet, dass unsere Objekte geraten können zusammenkleben.

(Wenn die Bälle zusammen fahren, kehrt die erste Kollision ihre Richtung um - also bewegen sie sich auseinander - und die zweite Kollision kehrt ihre Richtung um, wodurch sie sich zusammen bewegen.).

Hierfür gibt es mehrere Möglichkeiten, beispielsweise die Implementierung eines Boolean, der prüft, ob die Bälle diesen Rahmen bereits kollidiert haben. Am einfachsten ist es jedoch, jeden Ball einfach mit der neuen Geschwindigkeit zu bewegen. Dies bedeutet im Prinzip, dass sich die Kugeln mit der gleichen Geschwindigkeit bewegen sollten, in der sie sich bewegt haben. Sie sollten einen Abstand voneinander haben, der dem Rahmen entspricht, bevor sie kollidieren.

 firstBall.x = firstBall.x + newVelX1; firstBall.y = firstBall.y + newVelY1; secondBall.x = secondBall.x + newVelX2; secondBall.y = secondBall.y + newVelY2;

Und das ist es!

Sie können das Endprodukt hier sehen:

Quellcode bis zu diesem Teil ist in der v4 Ordner des Quelldownloads.

Danke fürs Lesen! Wenn Sie selbst mehr über Kollisionserkennungsmethoden erfahren möchten, lesen Sie diese Sitzung. Möglicherweise interessieren Sie sich auch für dieses Tutorial zu Quadtrees und dieses Tutorial zum Separating Axis Test.