Advertisement
  1. Game Development
  2. Game Physics

Grundlegende 2D-Platformer-Physik, Teil 5: Objekt-/Objektkollisionserkennung

by
Difficulty:BeginnerLength:LongLanguages:
This post is part of a series called Basic 2D Platformer Physics .
Basic 2D Platformer Physics, Part 4
Basic 2D Platformer Physics, Part 6: Object vs. Object Collision Response

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

In diesem Teil der Serie werden wir darauf hinarbeiten, dass Objekte nicht nur physisch mit der Tilemap, sondern auch mit jedem anderen Objekt interagieren können, indem wir einen Kollisionserkennungsmechanismus zwischen den Spielobjekten implementieren.

Demo

Die Demo zeigt das Endergebnis dieses Tutorials. Verwenden Sie WASD, um den Charakter zu bewegen. Die mittlere Maustaste erzeugt eine Einwegplattform, die rechte Maustaste erzeugt eine feste Kachel und die Leertaste erzeugt einen Charakterklon. Die Schieberegler ändern die Größe des Charakters des Spielers. Die Objekte, die eine Kollision erkennen, werden halbtransparent gemacht.

Die Demo wurde unter Unity 5.4.0f3 veröffentlicht, und der Quellcode ist auch mit dieser Version von Unity kompatibel.

Kollisionserkennung

Bevor wir über irgendeine Art von Kollisionsreaktion sprechen, beispielsweise darüber, dass die Objekte sich nicht gegenseitig durchlaufen können, müssen wir zunächst wissen, ob sich diese bestimmten Objekte überlappen.

Dies kann eine sehr teure Operation sein, wenn wir einfach jedes Objekt mit jedem anderen Objekt im Spiel vergleichen, je nachdem, wie viele aktive Objekte das Spiel derzeit verarbeiten muss. Um den schlechten Prozessor unserer Spieler ein wenig zu lindern, verwenden wir ...

Räumliche Partitionierung!

Das teilt den Spielraum im Grunde genommen in kleinere Bereiche auf, wodurch wir die Kollisionen zwischen Objekten überprüfen können, die nur zu demselben Bereich gehören. Diese Optimierung wird in Spielen wie Terraria dringend benötigt, wo die Welt und die Anzahl der möglichen kollidierenden Objekte riesig sind und die Objekte spärlich platziert sind. In Einzelbildspielen, bei denen die Anzahl der Objekte stark durch die Größe des Bildschirms begrenzt ist, ist dies häufig nicht erforderlich, aber dennoch nützlich.

Die Methode

Die beliebteste räumliche Partitionierungsmethode für den 2D-Raum ist der Quad-Tree. Die Beschreibung finden Sie in diesem Tutorial. Für meine Spiele verwende ich eine flache Struktur, was im Grunde bedeutet, dass der Spielraum in Rechtecke einer bestimmten Größe aufgeteilt ist, und ich überprüfe auf Kollisionen mit Objekten, die sich im selben rechteckigen Raum befinden.

The Rectangular space for our objects

Das hat eine Nuance: Ein Objekt kann sich gleichzeitig in mehr als einem Unterraum befinden. Das ist völlig in Ordnung - es bedeutet nur, dass wir Objekte erkennen müssen, die zu einer der Partitionen gehören, mit denen sich unser früheres Objekt überschneidet.

An object residing in more than one sub-space

Daten für die Partitionierung

Die Basis ist einfach. Wir müssen wissen, wie groß jede Zelle sein sollte und ein zweidimensionales Array, von dem jedes Element eine Liste von Objekten ist, die sich in einem bestimmten Bereich befinden. Wir müssen diese Daten in die Map-Klasse einfügen.

In unserem Fall habe ich beschlossen, die Größe der Partition in Kacheln auszudrücken, sodass jede Partition 16 x 16 Kacheln groß ist.

Für unsere Objekte benötigen wir eine Liste der Bereiche, mit denen sich das Objekt derzeit überlappt, sowie den Index in jeder Partition. Fügen wir diese der MovingObject-Klasse hinzu.

Anstelle von zwei Listen könnten wir ein einziges Wörterbuch verwenden, aber leider lässt der Leistungsaufwand bei der Verwendung komplexer Container in der aktuellen Iteration von Unity zu wünschen übrig, sodass wir uns an die Listen für die Demo halten.

Partitionen initialisieren

Lassen Sie uns fortfahren, um zu berechnen, wie viele Partitionen wir benötigen, um den gesamten Bereich der Karte abzudecken. Hierbei wird davon ausgegangen, dass kein Objekt außerhalb der Kartengrenzen schweben kann.

Abhängig von der Kartengröße müssen die Partitionen natürlich nicht genau mit den Kartengrenzen übereinstimmen. Aus diesem Grund verwenden wir eine Obergrenze mit berechnetem Wert, um sicherzustellen, dass wir mindestens genug haben, um die gesamte Karte abzudecken.

Lassen Sie uns jetzt die Partitionen initiieren.

Hier passiert nichts Besonderes - wir stellen nur sicher, dass jede Zelle eine Liste von Objekten hat, an denen wir arbeiten können.

Weisen Sie die Partitionen des Objekts zu

Jetzt ist es Zeit, eine Funktion zu erstellen, die die Bereiche aktualisiert, in denen sich ein bestimmtes Objekt überlappt.

Zunächst müssen wir wissen, mit welchen Kartenkacheln sich das Objekt überlappt. Da wir nur AABBs verwenden, müssen wir nur überprüfen, auf welcher Kachel jede Ecke des AABB landet.

Um die Koordinate im partitionierten Raum zu erhalten, müssen wir nur die Kachelposition durch die Größe der Partition teilen. Wir müssen die Partition der unteren rechten Ecke jetzt nicht berechnen, da ihre x-Koordinate gleich der oberen rechten Ecke und ihre y-Koordinate gleich der unteren linken Ecke ist.

Das alles sollte unter der Annahme funktionieren, dass kein Objekt außerhalb der Kartengrenzen verschoben wird. Andernfalls müssten wir hier eine zusätzliche Überprüfung durchführen, um die Objekte zu ignorieren, die außerhalb der Grenzen liegen.

Jetzt ist es möglich, dass sich das Objekt vollständig in einer einzelnen Partition befindet, dass es sich in zwei Partitionen befindet oder dass es genau dort Platz einnimmt, wo sich vier Partitionen treffen. Das setzt voraus, dass kein Objekt größer als die Partitionsgröße ist. In diesem Fall könnte es die gesamte Karte und alle Partitionen belegen, wenn es groß genug wäre! Ich habe unter dieser Annahme gearbeitet, und so werden wir im Tutorial damit umgehen. Die Modifikationen zum Zulassen größerer Objekte sind jedoch recht trivial, daher werde ich sie auch erklären.

Beginnen wir damit, zu überprüfen, mit welchen Bereichen sich das Zeichen überschneidet. Wenn alle Partitionskoordinaten der Ecke gleich sind, belegt das Objekt nur einen einzigen Bereich.

The object occupying a single area

Wenn dies nicht der Fall ist und die Koordinaten auf der x-Achse gleich sind, überlappt sich das Objekt vertikal mit zwei verschiedenen Partitionen.

An object occupying two of the same partitions along the x-axis

Wenn wir Objekte unterstützen würden, die größer als Partitionen sind, würde es ausreichen, wenn wir einfach alle Partitionen von der oberen linken Ecke zur unteren linken Ecke mithilfe einer Schleife hinzufügen würden.

Die gleiche Logik gilt, wenn nur die vertikalen Koordinaten gleich sind.

An object occupying two of the same partitions along the y-axis

Wenn alle Koordinaten unterschiedlich sind, müssen wir alle vier Bereiche hinzufügen.

An object occupying four quadrants

Bevor wir mit dieser Funktion fortfahren, müssen wir in der Lage sein, das Objekt zu einer bestimmten Partition hinzuzufügen und daraus zu entfernen. Lassen Sie uns diese Funktionen erstellen, beginnend mit dem Hinzufügen.

Wie Sie sehen können, ist die Vorgehensweise sehr einfach: Wir fügen den Index des Bereichs zur Liste der überlappenden Bereiche des Objekts hinzu, fügen den entsprechenden Index zur ID-Liste des Objekts hinzu und fügen das Objekt schließlich der Partition hinzu.

Jetzt erstellen wir die Entfernungsfunktion.

Wie Sie sehen können, verwenden wir die Koordinaten des Bereichs, mit dem sich das Zeichen nicht mehr überlappt, seinen Index in der Objektliste in diesem Bereich und den Verweis auf das zu entfernende Objekt.

Um das Objekt zu entfernen, tauschen wir es gegen das letzte Objekt in der Liste aus. Dazu müssen wir auch sicherstellen, dass der Index des Objekts für diesen bestimmten Bereich auf den Index aktualisiert wird, den unser entferntes Objekt hatte. Wenn wir das Objekt nicht austauschen würden, müssten wir die Indizes aller Objekte aktualisieren, die nach dem zu entfernenden Objekt verlaufen. Stattdessen müssen wir nur den aktualisieren, mit dem wir getauscht haben.

Ein Wörterbuch hier zu haben, würde viel Aufwand sparen, aber das Entfernen des Objekts aus einem Bereich ist eine Operation, die weitaus seltener erforderlich ist als das Durchlaufen des Wörterbuchs. Dies muss in jedem Frame für jedes Objekt durchgeführt werden, wenn die Überlappung des Objekts aktualisiert wird Bereiche.

Jetzt müssen wir den betroffenen Bereich in der Bereichsliste des ausgetauschten Objekts finden und den Index in der IDs-Liste in den Index des entfernten Objekts ändern.

Schließlich können wir das letzte Objekt aus der Partition entfernen. Dies ist nun ein Verweis auf das Objekt, das wir entfernen mussten.

Die gesamte Funktion sollte folgendermaßen aussehen:

Kehren wir zur Funktion UpdateAreas zurück.

Wir wissen, in welchen Bereichen das Zeichen diesen Frame überlappt, aber im letzten Frame könnte das Objekt bereits demselben oder verschiedenen Bereichen zugewiesen worden sein. Lassen Sie uns zunächst die alten Bereiche durchlaufen. Wenn sich das Objekt nicht mehr mit ihnen überlappt, entfernen wir das Objekt aus diesen.

Lassen Sie uns nun die neuen Bereiche durchlaufen. Wenn ihnen das Objekt zuvor noch nicht zugewiesen wurde, fügen Sie sie jetzt hinzu.

Löschen Sie abschließend die Liste der überlappenden Bereiche, damit das nächste Objekt verarbeitet werden kann.

Das ist es! Die endgültige Funktion sollte folgendermaßen aussehen:

Kollision zwischen Objekten erkennen

Zunächst müssen wir sicherstellen, dass UpdateAreas für alle Spielobjekte aufgerufen wird. Wir können dies in der Hauptaktualisierungsschleife nach dem Aktualisierungsaufruf jedes einzelnen Objekts tun.

Bevor wir eine Funktion erstellen, in der wir alle Kollisionen überprüfen, erstellen wir eine Struktur, die die Daten der Kollision enthält.

Dies ist sehr nützlich, da wir die Daten so behalten können, wie sie zum Zeitpunkt der Kollision sind. Wenn wir jedoch nur den Verweis auf ein Objekt speichern, mit dem wir kollidiert haben, hätten wir nicht nur zu wenig zum Arbeiten. Aber auch die Position und andere Variablen könnten sich für dieses Objekt geändert haben, bevor wir tatsächlich die Kollision in der Aktualisierungsschleife des Objekts verarbeiten können.

Die Daten, die wir speichern, sind der Verweis auf das Objekt, mit dem wir kollidiert haben, die Überlappung, die Geschwindigkeit beider Objekte zum Zeitpunkt der Kollision, ihre Positionen und auch ihre Positionen kurz vor dem Zeitpunkt der Kollision.

Wechseln wir zur MovingObject-Klasse und erstellen einen Container für die frisch erstellten Kollisionsdaten, die wir erkennen müssen.

Kehren wir nun zur Map-Klasse zurück und erstellen eine CheckCollisions-Funktion. Dies wird unsere Hochleistungsfunktion sein, bei der wir die Kollisionen zwischen allen Spielobjekten erkennen.

Um die Kollisionen zu erkennen, werden wir alle Partitionen durchlaufen.

Für jede Partition durchlaufen wir jedes Objekt darin.

Für jedes Objekt überprüfen wir jedes andere Objekt, das sich weiter unten in der Liste in der Partition befindet. Auf diese Weise überprüfen wir jede Kollision nur einmal.

Jetzt können wir prüfen, ob sich die AABBs der Objekte überlappen.

Folgendes passiert in der OverlapsSigned-Funktion des AABB.

Wie Sie sehen können, kann eine AABB-Größe auf einer Achse, mit der sie Null ist, nicht kollidiert werden. Die andere Sache, die Sie bemerken könnten, ist, dass die Funktion selbst dann wahr zurückgibt, wenn die Überlappung gleich Null ist, da sie die Fälle zurückweist, in denen die Lücke zwischen den AABBs größer als Null ist. Das liegt hauptsächlich daran, dass wir, wenn sich die Objekte berühren und sich nicht überlappen, immer noch die Information haben möchten, dass dies der Fall ist, also brauchen wir dies, um durchzugehen.

Als letztes berechnen wir, sobald die Kollision erkannt wurde, wie stark sich der AABB mit dem anderen AABB überlappt. Die Überlappung ist signiert. Wenn sich in diesem Fall der überlappende AABB auf der rechten Seite dieses AABB befindet, ist die Überlappung auf der x-Achse negativ, und wenn sich der andere AABB auf der linken Seite dieses AABB befindet, ist die Überlappung auf der x-Achse positiv. Dies erleichtert später das Verlassen der überlappenden Position, da wir wissen, in welche Richtung sich das Objekt bewegen soll.

Zurück zu unserer CheckCollisions-Funktion: Wenn es keine Überlappung gab, können wir zum nächsten Objekt wechseln. Wenn jedoch eine Überlappung aufgetreten ist, müssen wir die Kollisionsdaten zu beiden Objekten hinzufügen.

Um es uns einfacher zu machen, nehmen wir an, dass sich die Einsen (speed1, pos1, oldPos1) in der CollisionData-Struktur immer auf den Eigentümer der Kollisionsdaten beziehen und die Zweien die Daten des anderen Objekts sind.

Die andere Sache ist, dass die Überlappung aus der Perspektive des Objekts berechnet wird. Die Überlappung von obj2 muss negiert werden. Wenn sich obj1 also nach links bewegen muss, um aus der Kollision herauszukommen, muss sich obj2 nach rechts bewegen, um aus derselben Kollision herauszukommen.

Es gibt noch eine kleine Sache, um die wir uns kümmern müssen: Da wir die Partitionen der Karte durchlaufen und ein Objekt sich in mehreren Partitionen gleichzeitig befinden kann, in unserem Fall bis zu vier, ist es möglich, dass wir eine Überlappung für dieselbe feststellen zwei Objekte bis zu viermal.

Um diese Möglichkeit auszuschließen, prüfen wir einfach, ob wir bereits eine Kollision zwischen zwei Objekten festgestellt haben. In diesem Fall überspringen wir die Iteration.

Die HasCollisionDataFor-Funktion wird wie folgt implementiert.

Es durchläuft einfach alle Kollisionsdatenstrukturen und prüft, ob bereits Objekte zu dem Objekt gehören, auf das die Kollision überprüft werden soll.

Dies sollte im allgemeinen Anwendungsfall in Ordnung sein, da wir nicht erwarten, dass ein Objekt mit vielen anderen Objekten kollidiert. Daher wird das Durchsuchen der Liste schnell gehen. In einem anderen Szenario ist es jedoch möglicherweise besser, die Liste der CollisionData durch ein Wörterbuch zu ersetzen. Anstatt zu iterieren, können wir sofort feststellen, ob ein Element bereits vorhanden ist oder nicht.

Die andere Sache ist, dass diese Prüfung uns davor bewahrt, mehrere Kopien derselben Kollision zur gleichen Liste hinzuzufügen. Wenn die Objekte jedoch nicht kollidieren, werden wir trotzdem mehrmals auf Überlappung prüfen, wenn beide Objekte zu denselben Partitionen gehören.

Das sollte kein großes Problem sein, da die Kollisionsprüfung billig ist und die Situation nicht so häufig ist. Wenn es sich jedoch um ein Problem handelt, könnte die Lösung darin bestehen, einfach eine Matrix überprüfter Kollisionen oder ein Zwei-Wege-Wörterbuch auszufüllen es wird angezeigt, wenn die Kollisionen überprüft werden, und es wird unmittelbar vor dem Aufrufen der CheckCollisions-Funktion zurückgesetzt.

Rufen wir nun die Funktion auf, die wir gerade in der Hauptspielschleife beendet haben.

Das ist es! Jetzt sollten alle unsere Objekte die Daten über die Kollisionen haben.

Um zu testen, ob alles richtig funktioniert, machen wir es so, dass das Sprite des Charakters halbtransparent wird, wenn ein Charakter mit einem Objekt kollidiert.

Reviewing Collisions via Animation

Wie Sie sehen können, scheint die Erkennung gut zu funktionieren!

Zusammenfassung

Das war's für einen weiteren Teil der einfachen 2D-Platformer-Physik-Reihe. Es ist uns gelungen, einen sehr einfachen räumlichen Partitionierungsmechanismus zu implementieren und die Kollisionen zwischen den einzelnen Objekten zu erkennen.

Wenn Sie eine Frage haben, einen Tipp, wie Sie etwas besser machen können, oder einfach eine Meinung zum Tutorial haben, können Sie mich im Kommentarbereich informieren!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.