Algorithmus: Grundsatzfrage Kollisionserkennung

[TheLordix]

Hallo!

Ich hoffe das ist überhaupt ein passendes Forum für meine Frage, aber ich beschäftige mich seit kurzen wieder mit Spieleprogrammierung in Java (Hobby) und bin da auf ein Problem gestoßen.

Quasi jedes Spiel braucht eine Routine zur Berechnung von Kollisionen. In den meisten Tutorials im Netz werden Algorithmen zur Überschneidung von Polygonen oder Kreisen gezeigt. Das geht jedoch meiner Meinung nach an der Kernfrage vorbei, wie man den Beginn der Kollision und den exakten Zeitpunkt (exakter als pro Frame) berechnen kann.

Siehe hierzu folgendes Beispiel:



Wie berechnet man ideal eine Kollision von sehr schnellen Objekten? Analytisch durch Berechnung der Bewegungsgleichungen oder als Näherung durch möglichst kleine deltaT Schritte (kleiner als 1 Frame)? Was ist aus Design und Performancesicht besser?

Würde mich über eine ergiebige Diskussion freuen!

Lg, TheLordix

 

[NullPointer]

Meine Vermutung ist, dass, falls die Objekte sich gleichförmig bewegen, eine analytische Lösung effizienter ist, weil sie nur einmal berechnet werden muss. Wenn sich der Bewegungsvektor aber unterwegs ändern kann, dann ist evtl. die Näherungsmethode besser geeignet, weil jede einzelne Berechnung weniger aufwendig ist.

 

[Demon0no]

[...]oder als Näherung durch möglichst kleine deltaT Schritte[...]

So würd' ich es machen, liegt aber eher daran, dass ich kacke in Mathe bin
Ich glaube aber ehrlich gesagt nicht, dass es einen spürbaren Unterschied macht.

 

[Nai]

Ich würde sagen es kommt drauf an. Einfachere Sachen (Schuss trifft Menschen) würde ich analytisch die Schnittpunkte berechnen. Komplexere Sachen wie Partikelsimulation (zum Beispiel https://www.youtube.com/watch?v=RqduA7myZok) numerisch. Dazwischen gibt es m.E. relativ viel.

Problematisch ist vor allem bei der numerischen Berechnung, dass du unbedingt eine CFL-Condition brauchst:
Zeitschrittweite << Auflösung /maximale Geschwindigkeit in der Simulation
Oder in deinem Beispiel:
Zeitschrittweite << Kugelradius /maximale Geschwindigkeit in der Simulation
Denn sonst könnten sich in deinem Beispiel die Kugeln einfach durcheinander hindurchbewegen. Dadurch skaliert die numerische Berechnung extrem scheiße, je höher die Geschwindigkeiten oder je feiner deine Auflösung sind. Ist aber ein Problem, an welchem man relativ wenig machen kann.

 

[TheLordix]

Danke für die Ideen!

Momentan hätte ich geplant, dass die Bewegungen beschleunigt sind und Reibungseffekte berücksichtigen, was eine lineare Lösung ausschließt (zumindest im allgemeinen Fall). Die Anzahl der Objekte sind noch nicht ganz klar (das Spielprinzip ist noch im Entstehungsprozess), deshalb werde ich einmal beide Varianten testen und Performancevergleiche aufstellen. Aber an eueren Ideen sehe ich auf jeden Fall, dass es keine "Standardlösung" gibt und das Projektbezogen entschieden werden muss.

 

[Nai]

Problematisch ist ja, dass dir die Beschleunigungen und Reibungsterme eine reine analytische Lösung relativ schwer machen werden, wenn nicht sogar unmöglich. Allerdings werden beide die Geschwindigkeit innerhalb eines Zeitschritts kaum ändern. Deshalb würde ich wohl in diesem Fall so vorgehen:
-Position zu Beginn des Zeitschritts merken
-Geschwindigkeit zu Beginn des Zeitschritts merken
-Position und Geschwindigkeit zum Ende des Zeitschritts berechnen
Dann zwischen Position am Anfang und Position am Ende mit dem Betrag die Bewegung innerhalb des Zeitschritts linear interpolieren, um auf der Strecke Kollisionen zu finden.

 

[benneq]

Du könntest natürlich auch einfach eine Physik Engine einbinden, die dir das abnimmt. Z.B. sowas: http://www.jbox2d.org/
Da werden sich schon Leute genug Gedanken um Kollisionserkennung gemacht haben.

Grundsätzlich hast du die Probleme aber ja schon erkannt:
- Wenn man pro Frame die Kollision bestimmen will, kann es passieren, dass man mit einem Auto problemlos durch eine Wand fahren kann, weil man bei Frame (n-1) noch vor der Wand war und bei Frame (n) schon komplett hinter der Wand ist.

Ich bezweifle, dass es wirklich gut ist, diese Methode zu "verbessern" indem man noch mehr Zwischenschritte einbaut. Das Problem besteht ja weiterhin, nur dass man nun noch schnellere Objekte braucht, um den Fehler auszulösen.
Alternativ könnte man sich natürlich auch an der echten Physik bedienen und die Lichtgewindigkeit als max. Geschwindigkeit heranziehen und so dem Ganzen einen Riegel vorzuschieben. Vermutlich braucht es dann aber Stunden um einen einzigen Frame zu berechnen

Im Klartext heißt das: Man braucht eine Methode, die kontinuierlich die Kollisionen bestimmt.
Bestes Beispiel: Ein Raytracer!
Fragt sich nur, ob man das auch auf richtige Objekte im Raum anwenden kann.

 

[Nai]

Du könntest natürlich auch einfach eine Physik Engine einbinden, die dir das abnimmt. Z.B. sowas: http://www.jbox2d.org/
Da werden sich schon Leute genug Gedanken um Kollisionserkennung gemacht haben.

Grundsätzlich hast du die Probleme aber ja schon erkannt:
- Wenn man pro Frame die Kollision bestimmen will, kann es passieren, dass man mit einem Auto problemlos durch eine Wand fahren kann, weil man bei Frame (n-1) noch vor der Wand war und bei Frame (n) schon komplett hinter der Wand ist.

Da die analytische Lösung wie bei einem Raytracer bei komplexeren Fällen unmöglich ist, funktionieren die Physikengines intern ebenfalls dadurch , dass sie viele kleine Zeitschritte berechnen und bei jedem Zeitschritt die Kollisionen überprüfen. Deshalb verlangen sie entweder im Vorneherein, dass die Objekte in der Simulation für die numerische Stabilität eine maximale Geschwindigkeit nicht übertreten dürfen, oder alternativ passen sie intern ihre Schrittweite gemäß einer CFL-Condition an. Denn dadurch kann das Problem mit durch die Wand fahren nicht auftreten.

 

[benneq]

Hmm... aber man könnte doch ein raytrace-ähnliches Verfahren auf Framebasis verwenden.


Frame (n-1): Objekt ist vor der Wand (und bewegt sich schnell auf die Wand zu)

Frame (n) wird berechnet. Bestimmung der neuen Objekt Position unter Berücksichtigung seiner Geschwindigkeit. Das Objekt wäre nun eigentlich hinter der Wand.

Bevor das Bild dargestellt wird, kommt das "raytracing" zum Einsatz: Man schickt Strahlen von der alten Objekt Position zur neu berechneten und berücksichtigt dabei (wie auch beim Raytracing) alle anderen Objekte dazwischen. Dabei fällt dann auf, dass zwischen alter und neuer Position eine Wand ist.
Also kann man nun berechnen wann (zwischen Frame (n-1) und (n)) das Objekt auf die Wand trifft und lässt es dann abprallen oder einfach stillstehen oder die Wand explodiert - je nach dem was für ein Objekt es war.

Klingt zwar gerade unheimlich umständlich, aber das Ergebnis sollte äußerst präzise sein. Richtig fies wird es aber, wenn das mit mehreren Objekten gleichzeitig passiert und diese dann auch noch miteinander interagieren müssen. Dann sollte man wohl doch mit Zeitslots arbeiten.


EDIT: Wieder was gelernt. Das nennt sich scheinbar Continuous Collision Detection: http://en.wikipedia.org/wiki/Collis...8discrete.29_versus_a_priori_.28continuous.29

 

[CapFuture]

Auch eine interesante Seite zum Thema Spielemechanik: http://gamemechanicexplorer.com

Ist zwar alles in Javascript, aber die Prinzipien kann man ja 1:1 übernehmen

 

[Nai]

EDIT: Wieder was gelernt. Das nennt sich scheinbar Continuous Collision Detection: http://en.wikipedia.org/wiki/Collisi...8continuous.29

Ah kewl, danke, auch nicht gewusst dass das so heißt