Festlegen, ob zwei sich schnell bewegende Objekte für eine Kollisionsprüfung eingereicht werden sollen

8

Ich habe eine grundlegende 2D-Physik-Engine. Es ist so ziemlich eine Partikelmaschine, verwendet nur Grundformen wie AABBs und Kreise, so dass keine Drehung möglich ist. Ich habe CCD implementiert, das genaue TOI für zwei sich schnell bewegende Objekte liefern kann, und alles funktioniert reibungslos.

Mein Problem ist jetzt, dass ich nicht herausfinden kann, wie ich feststellen kann, ob zwei sich schnell bewegende Objekte überhaupt gegeneinander geprüft werden sollten. Ich verwende einen Quad-Baum für die räumliche Partitionierung und für jedes sich schnell bewegende Objekt überprüfe ich ihn mit Objekten in jeder Zelle, die es passiert. Dies funktioniert gut zur Bestimmung der Kollision mit der statischen Geometrie, bedeutet jedoch, dass jedes andere sich schnell bewegende Objekt, das damit kollidieren könnte, sich jedoch nicht in einer der überprüften Zellen befindet, niemals berücksichtigt wird.

Die einzige Lösung dafür kann ich mir vorstellen, entweder die Zellen groß genug zu haben und die Daumen zu drücken, dass dies ausreicht, oder eine Art Brute-Force-Algorithmus zu implementieren. Gibt es eine richtige Möglichkeit, damit umzugehen? Vielleicht hat jemand dieses Problem auf effiziente Weise gelöst. Oder gibt es eine bessere Möglichkeit, Speicherplatz zu partitionieren, die dies berücksichtigt?

Hier ist ein Diagramm:

Geben Sie hier die Bildbeschreibung ein

Die "Wirkungsbereiche" von Objekt A und B kreuzen sich, sie sollten gegeneinander geprüft werden. Aber mit der Art und Weise, wie ich derzeit nach Kollisionen suche, ist dies nicht berücksichtigt. Auch hier kann ich mir ein paar Lösungen vorstellen, wie tatsächlich zu überprüfen, ob sich die Pfade von Objekten kreuzen, sobald ihre Geschwindigkeit höher als x ist, oder so, aber das fühlt sich wie ein Hack an und es ist ein Chaos, es zu versuchen und zu implementieren.

collision-detection physics Dreta
quelle
Können Sie ein Beispielszenario nennen, in dem Ihre Methode fehlschlägt?
Anko
1
Ich denke, es würde so aussehen: Objekt A und B befinden sich in dieser Konfiguration: [A] [] [B]. A geht nach rechts und B nach links. Sie gehen schnell. Die Kollisionsprüfung lautet wie folgt: Ist die nächste Zelle für A leer? Ja, da ist nichts in der mittleren Zelle. Ist die nächste Zelle für B leer? Ja. Also keine Kollision. Aber echte Physik würde zeigen, dass A und B wahrscheinlich kollidieren (besonders in diesem eindimensionalen Spiel, das ich beschreibe;)
Cystack
@Cystack Ich habe CCD implementiert. Die von Ihnen beschriebene Situation ist kein Problem. Die beiden Objekte gehen direkt aufeinander zu, die von mir beschriebene Implementierung wird das aufgreifen und lösen.
Dreta
Die Physik der Situation ist klar. Angenommen, Sie können ein Objekt im Voraus als "sich schnell bewegend" identifizieren. Wenn Sie dann eine Kollisionsprüfung durchführen, müssen Sie nicht nur die Zelle überprüfen, in der sich das Objekt gerade befindet, sondern alle Zellen, die es im letzten Zeitschritt durchlaufen hat. Jedes sich schnell bewegende Objekt hat also tatsächlich mehrere Positionen, wie der gesamte grüne Streifen, den Sie im obigen Bild gezeichnet haben.
TheJollySin
@theJollySin Ich habe bereits die Lösung beschrieben, die Sie geben. Es ist ein Hack, ein Sonderfall. Ich suche nach einer allgemeinen Lösung, wenn es eine gibt.
Dreta

Antworten:

5

Das Problem, über das Sie sprechen, wird oft als "Breitphasen-Kollisionserkennung" bezeichnet. Ihre Lösung ist ein "überstrichenes Volumen", nicht wirklich ein Hack, nur wie es gemacht wird (nehmen Sie einfach den AABB des Objekts, einschließlich Start und Ende der Bewegung und Verwenden Sie dies für Kollisionen - obwohl es bei Rotationen etwas schwierig wird).

Dann wird der Algorithmus zur Erkennung von Breitphasen-Kollisionen, der dies schnell macht, als "Sweep and Prune" bezeichnet.

Jeff Gates
quelle
Ich habe SAP verworfen, bevor dieses Problem auftrat. Ich mache dies in JavaScript, wodurch der Overhead für Listen spürbar wird. Auch Arrays können in Bezug auf die Leistung unzuverlässig werden. Ich denke, ich muss die Dinge überdenken. Danke, der Algorithmus löst tatsächlich das Problem.
Dreta