Wie funktioniert eine Kollisionsmaschine?

Wie genau funktioniert ein Kollisionsmotor ?

Dies ist eine äußerst weit gefasste Frage. Welcher Code lässt die Dinge gegeneinander springen, welcher Code lässt den Spieler gegen eine Wand laufen, anstatt durch die Wand zu laufen? Wie aktualisiert der Code ständig die Position des Spielers und die Position der Objekte, damit die Schwerkraft und die Kollision so bleiben, wie sie sollten?

Wenn Sie nicht wissen, was eine Kollisionsmaschine ist, wird sie im Allgemeinen in Plattformspielen verwendet , um den Spieler dazu zu bringen, Wände und Ähnliches akut zu treffen. Es gibt den 2D-Typ und den 3D-Typ, aber alle erreichen dasselbe: Kollision.

Also, was tickt eine Kollisionsmaschine?

Es gibt einen großen Unterschied zwischen einer Kollisionsmaschine und einer Physikmaschine. Sie tun nicht dasselbe, obwohl die Physik-Engine im Allgemeinen auf einer Kollisions-Engine basiert.

Die Kollisionsmaschine wird dann in zwei Teile aufgeteilt: Kollisionserkennung und Kollisionsreaktion. Letzteres ist in der Regel Teil der Physik-Engine. Aus diesem Grund werden Kollisions- und Physik-Engines normalerweise in derselben Bibliothek zusammengefasst.

Die Kollisionserkennung erfolgt in zwei Formen, diskret und kontinuierlich. Fortgeschrittene Engines unterstützen beide, da sie unterschiedliche Eigenschaften haben. Im Allgemeinen ist die kontinuierliche Kollisionserkennung sehr teuer und wird nur dort eingesetzt, wo sie wirklich benötigt wird. Der Großteil der Kollision und Physik wird mit diskreten Methoden behandelt. Bei diskreten Methoden dringen Objekte ineinander ein und die Physik-Engine arbeitet dann daran, sie auseinander zu drücken. Die Engine verhindert also nicht, dass ein Spieler teilweise durch eine Wand oder den Boden läuft, sondern repariert ihn nur, nachdem festgestellt wurde, dass sich der Spieler teilweise in der Wand / im Boden befindet. Ich werde mich hier auf die diskrete Kollisionserkennung konzentrieren, da ich die meiste Erfahrung darin habe, diese von Grund auf neu zu implementieren.

Kollisionserkennung

Die Kollisionserkennung ist relativ einfach. Jedes Objekt hat eine Transformation und eine Form (möglicherweise mehrere Formen). Bei naiven Ansätzen würde die Kollisionsmaschine eine O (n ^ 2) -Schleife durch alle Objektpaare durchführen und prüfen, ob es eine Überlappung zwischen den Paaren gibt. Bei intelligenteren Ansätzen gibt es mehrere räumliche Datenstrukturen (z. B. für statische und dynamische Objekte), eine Begrenzungsform für jedes Objekt und mehrteilige konvexe Unterformen für jedes Objekt.

Die räumlichen Datenstrukturen umfassen Dinge wie KD-Bäume, dynamische AABB-Bäume, Octrees / Quadtrees, Binary Space Partitioning-Bäume und so weiter. Jede hat ihre Vor- und Nachteile, weshalb manche High-End-Motoren mehr als eine verwenden. Dynamische AABB-Bäume zum Beispiel sind wirklich sehr schnell und eignen sich für die Bearbeitung vieler sich bewegender Objekte, während ein KD-Baum für die statische Ebenengeometrie, mit der Objekte kollidieren, besser geeignet ist. Es gibt auch andere Möglichkeiten.

Die breite Phase verwendet die räumlichen Datenstrukturen und ein abstraktes Begrenzungsvolumen für jedes Objekt. Ein Begrenzungsvolumen ist eine einfache Form, die das gesamte Objekt einschließt, im Allgemeinen mit dem Ziel, es so "dicht" wie möglich einzuschließen, während es billig bleibt, mit Kollisionstests durchzuführen. Die gebräuchlichsten Begrenzungsformen sind achsenausgerichtete Begrenzungsrahmen, objektausgerichtete Begrenzungsrahmen, Kugeln und Kapseln. AABBs werden im Allgemeinen als die schnellsten und einfachsten angesehen (Kugeln sind in einigen Fällen einfacher und schneller, aber viele dieser räumlichen Datenstrukturen erfordern ohnehin die Umwandlung der Kugel in eine AABB), aber sie passen auch in der Regel zu vielen Objekten eher schlecht. Kapseln sind in 3D-Engines zur Behandlung von Kollisionen auf Zeichenebene beliebt. Einige Motoren verwenden zwei Begrenzungsformen:

Die letzte Phase der Kollisionserkennung besteht darin, genau zu erkennen, wo sich die Geometrie schneidet. Dies impliziert normalerweise die Verwendung eines Netzes (oder eines Polygons in 2D), jedoch nicht immer. Der Zweck dieser Phase besteht darin, herauszufinden, ob die Objekte wirklich wirklich kollidieren, ob eine genaue Detailgenauigkeit erforderlich ist (z. B. eine Kugelkollision in einem Schützen, bei der Sie Schüsse ignorieren möchten, die gerade noch fehlen), und um herauszufinden, wo genau die Objekte kollidieren, was sich auf das Verhalten der Objekte auswirkt. Wenn beispielsweise eine Box am Rand eines Tisches sitzt, muss der Motor wissen, an welchen Punkten der Tisch gegen die Box drückt. Je nachdem, wie weit die Box hängt, kann die Box kippen und herunterfallen.

Kontakt Verteilergeneration

Zu den hier verwendeten Algorithmen gehören die bekannten Algorithmen GJK und Minkowski Portal Refinement sowie der Separating Axis-Test. Da die gängigen Algorithmen in der Regel nur für konvexe Formen funktionieren, müssen viele komplexe Objekte in konvexe Unterobjekte aufgeteilt und für jedes Objekt einzeln Kollisionstests durchgeführt werden. Dies ist einer der Gründe, warum vereinfachte Netze häufig für Kollisionen verwendet werden, und auch, weil weniger Dreiecke benötigt werden, um die Verarbeitungszeit zu verkürzen.

Einige dieser Algorithmen sagen Ihnen nicht nur, dass die Objekte sicher kollidiert sind, sondern auch, wo sie kollidiert sind - wie weit sie sich gegenseitig durchdringen und welche "Kontaktpunkte" sie haben. Einige der Algorithmen erfordern zusätzliche Schritte, z. B. das Abschneiden von Polygonen, um diese Informationen abzurufen.

Körperliche Reaktion

Zu diesem Zeitpunkt wurde ein Kontakt entdeckt, und die Physik-Engine verfügt über genügend Informationen, um den Kontakt zu verarbeiten. Die Handhabung der Physik kann sehr komplex werden. Bei einigen Spielen funktionieren einfachere Algorithmen, aber selbst etwas, das so einfach zu sein scheint wie ein stabiler Stapel von Kisten, erweist sich als recht schwierig und erfordert viel Arbeit und nicht offensichtliche Hacks.

Auf der einfachsten Ebene macht die Physik-Engine so etwas: Sie nimmt die kollidierenden Objekte und deren Kontaktverteiler und berechnet die neuen Positionen, die zum Trennen der kollidierten Objekte erforderlich sind. Die Objekte werden an diese neuen Positionen verschoben. Es berechnet auch die Geschwindigkeitsänderung, die aus diesem Stoß resultiert, kombiniert mit Rückgabe- (Bounciness-) und Reibungswerten. Die Physik-Engine wendet auch alle anderen auf die Objekte einwirkenden Kräfte an, z. B. die Schwerkraft, um die neuen Geschwindigkeiten der Objekte und dann (im nächsten Frame) ihre neuen Positionen zu berechnen.

Fortgeschrittenere Physikreaktionen werden schnell kompliziert. Der oben beschriebene Ansatz funktioniert in vielen Situationen nicht, einschließlich eines Objekts, das über zwei anderen Objekten sitzt. Der Umgang mit jedem Paar für sich verursacht "Jitter" und die Objekte werden viel herumspringen. Die grundlegendste Technik besteht darin, eine Reihe von Iterationen zur Geschwindigkeitskorrektur über die Paare von kollidierenden Objekten durchzuführen. Wenn beispielsweise eine Box "A" über zwei anderen Boxen "B" und "C" liegt, wird die Kollision AB zuerst behandelt, wodurch sich die Box A weiter in die Box C hinein neigt. Dann wird die AC-Kollision abends behandelt Ziehen Sie die Kästchen etwas heraus, aber ziehen Sie A nach unten und nach B hinein. Dann wird eine weitere Iteration durchgeführt, sodass der durch die Wechselstromkorrektur verursachte AB-Fehler leicht behoben wird, was zu einem etwas größeren Fehler in der Wechselstromantwort führt. Was behandelt wird, wenn AC erneut verarbeitet wird. Die Anzahl der durchgeführten Iterationen ist nicht festgelegt, und es gibt keinen Punkt, an dem sie "perfekt" wird, sondern nur eine beliebige Anzahl von Iterationen, die keine aussagekräftigen Ergebnisse liefert. 10 Iterationen sind ein typischer erster Versuch, aber es ist eine Feinabstimmung erforderlich, um die beste Zahl für eine bestimmte Engine und die Anforderungen eines bestimmten Spiels zu ermitteln.

Kontakt Zwischenspeichern

Es gibt andere Tricks, die sich als sehr praktisch herausstellen (mehr oder weniger notwendig), wenn es um viele Arten von Spielen geht. Kontakt-Caching ist eine der nützlicheren. Mit einem Kontakt-Cache wird jeder Satz kollidierender Objekte in einer Nachschlagetabelle gespeichert. Wenn in jedem Frame eine Kollision erkannt wird, wird dieser Cache abgefragt, um festzustellen, ob sich die Objekte zuvor in Kontakt befanden. Wenn die Objekte zuvor nicht in Kontakt waren, kann ein Ereignis "Neue Kollision" generiert werden. Wenn die Objekte zuvor in Kontakt waren, können die Informationen verwendet werden, um eine stabilere Reaktion zu erzielen. Alle Einträge im Kontakt-Cache, die nicht in einem Frame aktualisiert wurden, geben zwei Objekte an, die getrennt wurden, und ein Ereignis "Objekt trennen" kann generiert werden. Die Spielelogik hat häufig Verwendungen für diese Ereignisse.

Es ist auch möglich, dass die Spiellogik auf neue Kollisionsereignisse reagiert und sie als ignoriert markiert. Dies ist sehr hilfreich für die Implementierung einiger Funktionen, die auf Plattformen üblich sind, z. B. Plattformen, durch die Sie springen können, auf denen Sie jedoch stehen. Naive Implementierungen können Kollisionen ignorieren, die eine normale Plattform-> Charakterkollision nach unten aufweisen (was anzeigt, dass der Kopf des Spielers den unteren Rand der Plattform berührt). Ohne Kontakt-Caching wird dies jedoch unterbrochen, wenn der Kopf des Spielers über die Plattform stößt und er dann beginnt fallen. Zu diesem Zeitpunkt kann der Kontakt normal nach oben zeigen, was dazu führt, dass der Spieler über die Plattform springt, wenn er dies nicht sollte. Mit Contact Caching kann die Engine die anfängliche Kollisionsnormalität zuverlässig erkennen und alle weiteren Kontaktereignisse ignorieren, bis Plattform und Spieler wieder getrennt werden.

Schlafen

Eine andere sehr nützliche Technik besteht darin, Objekte als "schlafend" zu markieren, wenn sie nicht mit ihnen interagieren. Schlafende Objekte werden nicht aktualisiert, kollidieren nicht mit anderen schlafenden Objekten und sitzen im Grunde genommen nur so lange dort, bis ein anderes nicht schlafendes Objekt mit ihnen kollidiert.

Die Auswirkung ist, dass alle Paare von kollidierenden Objekten, die nur dort sitzen und nichts tun, keine Verarbeitungszeit in Anspruch nehmen. Da es keine konstante Anzahl kleiner physikalischer Korrekturen gibt, sind die Stapel stabil.

Ein Objekt ist ein Kandidat für den Schlaf, wenn es länger als ein Einzelbild eine Geschwindigkeit nahe Null hatte. Beachten Sie, dass das Epsilon, das Sie zum Testen dieser Geschwindigkeit nahe Null verwenden, wahrscheinlich etwas höher sein wird als das übliche Gleitkommavergleich-Epsilon, da Sie mit etwas Jitter bei gestapelten Objekten rechnen müssen und Sie möchten, dass ganze Stapel von Objekten einschlafen, wenn sie Sie bleiben "nah genug", um stabil zu bleiben. Die Schwelle erfordert natürlich Optimierungen und Experimente.

Einschränkungen

Das letzte wichtige Element vieler Physik-Engines ist der Constraint Solver. Der Zweck eines solchen Systems ist es, die Implementierung von Dingen wie Federn, Motoren, Radachsen, simulierten Weichkörpern, Stoffen, Seilen und Ketten und manchmal sogar Flüssigkeiten zu erleichtern (obwohl Flüssigkeiten oft als ein völlig anderes System implementiert werden).

Sogar die Grundlagen des Auflösens von Abhängigkeiten können sehr mathematisch intensiv werden und gehen über mein Fachwissen in diesem Bereich hinaus. Ich empfehle Randy Gallis exzellente Artikelserie über Physik zu lesen, um eine genauere Erklärung des Themas zu erhalten.

Das allgemeine Problem: Bestimmen Sie, welche der möglichen Objektkombinationen ein Schnittvolumen ungleich Null hat.

Der naive, allgemeine Ansatz ist einfach: Berechnen Sie für jedes mögliche Paar von Objekten das Schnittvolumen. Dies ist normalerweise nicht praktikabel, da es O (n ^ 2) relativ teure Schnittoperationen erfordert.

Daher sind praktische Implementierungen häufig spezialisiert, wobei bestimmte Annahmen getroffen werden, um die Vermeidung von Schnittmengenprüfungen oder die Reduzierung ihrer Kosten zu ermöglichen. Die räumliche Partitionierung macht sich die Tatsache zunutze, dass Objekte im Verhältnis zum Gesamtvolumen normalerweise klein sind und die Anzahl der Vergleiche mit O (n log n) normalerweise verringert. Mit Achsen ausgerichtete Begrenzungsrahmen und Begrenzungskugeln bieten kostengünstige Grobschnittprüfungen, sofern Objekte bestimmten Kompaktheitsannahmen entsprechen. Und so weiter.

Eine "Kollisionsmaschine", die ich verwendet habe, fühlte sich extrem leicht zu erfassen an.

Grundsätzlich hat API eine Art von Objekten mit Methode bereitgestellt collidesWith, so dass

1. Seine Parameter waren verschiedene Arten von Objekten, die für eine Kollision "in Frage kamen"
2. es gab wahr oder falsch zurück, abhängig davon, ob eine Kollision stattgefunden hat oder nicht
3. Es gab eine Option, mit der ausgewählt werden konnte, ob alle Begrenzungsrechtecke für die Objekte ein Kollisionsereignis auslösen oder nur undurchsichtige Pixel innerhalb dieser Rechtecke (Erkennung auf Pixelebene).

In meiner Anwendung habe ich nur in regelmäßigen Abständen aufgerufen collidesWith, um herauszufinden, ob eine Kollision stattgefunden hat oder nicht.

Ziemlich einfach, nicht wahr?

Vielleicht war das Einzige, was ein wenig Vorstellungskraft erforderte, wenn einfach begrenzte Rechtecke nicht ausreichten, um die Geometrie kollidierender Objekte zu simulieren. In diesem Fall müsste man einfach mehrere kollidierbare Objekte anstelle eines verwenden.

Wenn Sie herausfinden, dass ein einzelnes Kollisionsrechteck nicht das tut, was Sie benötigen, erfinden Sie eine Möglichkeit, Dinge in rechteckigere Unterelemente zu zerlegen, sodass diese Elemente in Kombination das gewünschte Verhalten simulieren / approximieren.

• Endbenutzer interessieren sich einfach nicht dafür, wie viele Objekte sich hinter den Kulissen befinden. Sie sind glücklich, solange sich das Endergebnis so anfühlt, wie sie es erwarten, z. B. wie ein Haus mit einem Hinterhofzaun:

  

Ich denke, Sie sind ein wenig verwirrt über das, worüber Sie sprechen, und sprechen über ein paar verschiedene Dinge.

Die Fähigkeit zu sagen, dass dieser Gegenstand von Position X zu Position Y bewegt wird, basiert auf der Physik (dies greift auch an, wie sie sich bewegen und warum sie sich bewegen).

Welche Methode zur Kollisionserkennung verwendet wird, hängt von der Struktur Ihres Spiels ab. Wenn es sich bei Ihrem Spiel um eine große offene Welt handelt, sollten Sie die Raumpartitionierung (Quad-Tree [Oct-Tree für 3D], BSP, ein traditionelles Grid oder den altmodischen Test-Alles-Ansatz) in Betracht ziehen.

Der beste Weg, ein Kollisionserkennungssystem zu implementieren, besteht darin, dies schrittweise durchzuführen.

1. Platzieren Sie alle Objekte in einem generischen Begrenzungsvolumen / einer generischen Begrenzungsform und testen Sie diese anschließend

2. Wenn 1 bestanden wurde, wiederholen Sie dies mit einer komplexeren Volumen- / Formwiederholung, bis Sie bereit sind, die absolute Geometrie zu testen

3. Absolute Geometrie testen Wie oft Sie Schritt 2 wiederholen, hängt von der Komplexität Ihrer Formen ab und davon, wie genau diese Formen sind.

Sie sollten jeden dieser Schritte als frühzeitig betrachten, um Kollisionen auf Ihrem Weg zu eliminieren, und nur dann als wahr in Schritt 3, wenn sie sich tatsächlich berühren.

Dann ist für den letzten Teil die Kollisionsauflösung. Dies bestimmt, was passiert, nachdem Sie eine Kollision gefunden und bewiesen haben, dass es sich tatsächlich um eine Kollision handelt, und was dagegen zu tun ist. Dies wird normalerweise von der Physik erledigt.

Die traditionelle Schleife sieht folgendermaßen aus:

receive input
update physics
collision detection
collision resolution
render
repeat

Auf der Grafikkartenebene (wo es sich normalerweise um Dreiecke handelt) besteht die allgemeine Idee darin, die Szene auf eine bestimmte Weise zu unterteilen, damit nicht alle N Dreiecke überprüft werden müssen (dies kann als Vorverarbeitungsschritt erfolgen) ), und finden Sie dann heraus, wo Sie sich in der Szene befinden, und überprüfen Sie nur die 10-50 Dreiecke in dieser Partition.

Weitere Informationen finden Sie unter BSP- und Kd-Bäume. Es gibt auch andere Partitionierungsansätze.

Erstens denke ich, dass die wichtigste Aufgabe einer Kollisionsmaschine darin besteht, zu bestimmen, was in einer bestimmten Situation nicht Frame für Frame auf Kollision überprüft werden muss, und diese Objekte bei weiteren Überprüfungen auszusortieren.

Zweitens, aber auch wichtig, überprüfen Sie die verbleibenden Objekte, die in diesem ersten Schritt nicht ausgesondert wurden, genauer.

Verwenden Sie drittens die effizientesten / geeignetsten Methoden, um die Überprüfungen durchzuführen.