Genaue Kollisionen

[kddc.l3usch]

Hi

wie der titel schon verrät geht es um kollisionen! Es geht dabei um unsere eigene 2D Engine Edge2D.
einfach rechteckollisionen haben wir schon. Genauso geht es auch ganz exakt genau in eine einzelne richtung.
Das mache ich so...Ich überprüfe den Abstand von einem Objekt zum anderen. Es gibt einzel Abstände rechts, links, oben, unten und eine gesamtdistanz zum andern Objekt. wenn ein Objekt nun runter fällt, dann überprüfe ich also den abstand, und habe eine gegebene Geschwindigkeit. So lange der ABstand > distanz soll er ganuso schnell weiter machen. Wenn der abstand kleiner der Distanz ist, dann setzt er das Objekt um den Abstand weiter und somit liegt ein Objekt exakt auf dem andern auf...logisch denke ich.

Das Problem ist nur dass, das in mehrere Richtungen nicht mehr klappt, speziell im Bezug auf Maps wo ein Objekt mehrere hundert Objekte auf kollisionen an allen seiten überprüfen muss. Da wirken die sich alle irgendwie entgegen...es funktioniert zwar so weit, aber wenn ich diagonal auf eine wand treffe zum beispiel springt das objekt seltsam hin und her....

Also wie würdet ihr genau kollisionen machen? Habt ihr ne Idee? Ihc bin echt am Ende...ich geb echt nicht schnell auf, aber das war nciht meine erste idee sondern meine zehnte oder so und nichts hat so wirklich geklappt...
Also das habe ich IM MOMENT zu verfügung:

Normale Rechteckskollisionen (Überlappen)
Positionen von Objekten und Ecktpunkte
Die Bewegungsrichtung der Objekte (links, rechts, diagonal etc)
die distanz von einem Objekt zum Anderen ( linken, Abstand, rechten Abstand, nach oben, nach unten) gesamt Abstand

Habt ihr ne idee wie ich die Sachen so verknüpfen kann, dass ich in alle Richtungen genaue kollisionen habe?...hat jemand shconmal ähnliches gemacht?
Wenn irgendwelche werte oder eigenschaften fehlen, kann ich die auch noch irgendwie einbauen...das sollte nciht das Problem sein

Danke für eure Hilfe KddC

[Namenloser]

Ich hab sowas ähnliches in einer Billard-Umsetzung gemacht. Ich wollte unbedingt, dass die Kollisionen exakt sind, damit nicht bei großen Geschwindigkeiten Kugeln tunneln o.ä. Das ganze hat sich in der Tat als komplizierter herausgestellt, als ich zuerst dachte.

Ich habe es am Ende so gelöst, dass ich für alle Objekte den Zeitpunkt berechne, wann sie miteinander Kollidieren würden. Anschließend wird der früheste Zeitpunkt ermittelt, an dem zwei Objekte kollidieren würden. Wenn dieser Zeitpunkt nach dem Intervall des aktuellen Frames liegt, passiert gar nichts. Wenn der Zeitpunkt jedoch innerhalb des aktuellen Intervalls liegt, werden erst mal alle Bewegungen bis zu diesem Zeitpunkt simuliert. Dann wird die Kollision behandelt. Anschließend begintn die Kollisionsprüfung von vorne.

Das Problem dabei: Man bekommt es hier mit Grenzwertproblemen und Rechenungenauigkeiten zu tun, die imo derzeit nicht wirklich lösbar sind. Wenn du nämlich den Zeitpunkt berechnest, an dem die Kugeln kollidieren, anschließend die Bewegung bis zu diesem Zeitpunkt simulierst und die Kollision behandelst, ändern sich erst mal nur die Bewegungsrichtungen und Geschwindigkeiten der kollidierenden Objekte, aber nicht deren Position. D.h., wenn du anschließend erneut auf Kollisionen prüfst, wird die Kollision sofort (am Zeitpunkt 0, oder nahe 0 - Ungenauigkeiten) erneut erkannt und du befindest dich in einer Endlosschleife. Du kannst das nur umgehen, indem du ein minimales Zeitintervall für die Bewegung vorgibst oder anderweitig trickst, indem du z.B. bei jeder Kollision die Objekte ein kleines Stückchen auseinander schiebst. Nach etlichen Stunden Debuggen habe ich mich für eine Kombination aus beidem entschieden. Dadurch ist es nicht mehr 100%ig exakt, Kollisionen werden manchmal auch doppelt oder dreifach erkannt, aber es funktioniert halbwegs und fällt nicht auf.

So, wenn ich mir jetzt überlege, dass ich das ganze nur für Kugeln und Banden brauchte, während du beliebig geformte Objekte unterstützen willst, komme ich zu dem Schluss, dass der Aufwand sich wahrscheinlich nicht lohnt. Du kannst die Genauigkeit der Kollisionserkennung etwas erhöhen, indem du zuerst testest, ob die Bewegungslinien der Objekte, bzw. deren Boundingboxen, sich schneiden o.ä. Damit kannst du zumindest das Tunneling etwas reduzieren, wenn du etwas trickst.

Diese Präsntation über exakte Kollisionserkennung ist sehr interessant. Daran habe ich mich bei der Berechnung der Kollisionszeitpunkte etwas orientiert. Das ganze vollständig umzusetzen, dürfte aber erstens sehr aufwändig und zweitens sehr rechenintensiv sein.

[kddc.l3usch]

Ich hatte das auch echt unterschätzt:D .genau das Problem mit der Endlosschleide habe ich nämlich auch. Wenn sie dann einmal kollidieren kriege ich sie teilweise einfach nicht mehr auseinander. das mit dem auseinandersetzen werde ich nochmal probieren...hört sich ja ganz logisch an eigentlich...mal sehen ob ich das hinbekomme...

habs eben mal mit http://wiki.delphigl.com/index.php/T...g_Axis_Theorem probiert aber das hilft auch nciht weiter...da hat man natürlich dasselbe Problem mit der Ungenauigkeit.

Danke dir schonmal:)
Wenn noch jemand mal dieses Problem hatte und es iwi gelöst hat...immer her damit:D

[Khabarakh]

Zitat:

Zitat von NamenLozer

D.h., wenn du anschließend erneut auf Kollisionen prüfst, wird die Kollision sofort (am Zeitpunkt 0, oder nahe 0 - Ungenauigkeiten) erneut erkannt und du befindest dich in einer Endlosschleife.

Sollte (in deinem Fall) nicht ein Test genügen, ob sich die Kugeln überhaupt aufeinander zubewegen? Soll heißen, mit Position p und Bewegungsrichtung v muss (p2 - p1) . (v1 - v2) > 0 gelten.

Zitat:

Zitat von NamenLozer

So, wenn ich mir jetzt überlege, dass ich das ganze nur für Kugeln und Banden brauchte, während du beliebig geformte Objekte unterstützen willst, komme ich zu dem Schluss, dass der Aufwand sich wahrscheinlich nicht lohnt.

Mit Informationen über die genauen Anforderungen geht der Post ja leider etwas geizig um, aber wenn es wirklich um beliebige Objekte inkl. Rotation geht, hast du sicherlich recht :) .

[kddc.l3usch]

ich dachte das wäre rübergekommen.

Die Kollision soll mit nur einem Objekt stattfinden, das allerdings dank array an mehreren positionen gezeichnet ist. Also nicht, das die Dinger alle ne andere Form haben. Alle vierecking und gleich groß:P

[Khabarakh]

Also Rechtecke mit beliebigen Geschwindigkeitsvektoren ohne Rotation? Dann lässt sich das auf jeden Fall exakt lösen, entspricht ja ziemlich genau der Billard-Simulation :) . Meinen Tipp zur Erkennung doppelter Kollisionen solltest du ebenfalls einbauen können.

[kddc.l3usch]

am besten läasst sich das Problem wohl nachvollziehen wenn man einfach mal n bisschen source code sieht...

Das mit der Richtung hatte ich glaub ich zwischendurch auch mal gemacht...Und da kamen dann irgendwie soviele Abfragen, dass das einfach nur noch unelegant wirkte. Jetzt inzwischen ist das auch ne ziemliche Pipifax lösung denke ich weil das auf andere weisen eifach nicht hinhauen wollte. wenn ihr die exe ausführt, seht ihr dass das ding wunderbar kollidiert, aber dann bewegt euch mal diagonal auf ne wand zu....vor allem oben und unten....und ihr seht was mich noch stört. Und mir fällt einfach ncihts mehr ein wie ich das noch wegkriegen könnte.
Die Funktionen für die distance und kollisionen sind in der Edge unit ganz unten, falls jemand lust hat sich das mal anzusehen.

http://www.megafileupload.com/en/fil...tance-rar.html

danke für eure Hilfe=)

[mkinzler]

Du kannst den Code, wenn er nicht zu umfangreich ist, auch direkt hier im Forum an den Beitrag anhängen. Das hätte den Vorteil, dass er dann auch noch vorhanden ist, wenn er auf dem externen Server gelöscht wird.

[Namenloser]

Die Bewegunsgrichtung zu überprüfen, bzw. ist das auch noch implementiert, aber es reicht alleine nicht aus, weil es immer noch das Problem mit den Ungenauigkeiten gibt. Es kann in nämlich ungünstigen Fällen passieren, dass die eine Kugel durch Rechenungenauigkeiten etwas zu schnell ist, sodass sie gleich wieder mit der anderen Kugel kollidiert.

[Aphton]

Steinigt mich bitte nicht, weil ich hier uralte Threads ausgrabe..

Ich hab mir vor kurzem auch genauer Gedanken darüber gemacht, wie man den Kollisionszeitpunkt (relativ) genau berechnet.

Problembeschreibung (Beispiel)
Wenn sich zwei Objekte mit einer bestimmten Geschwindigkeit v1 und v2 zueinander bewegen, dann kann es passieren, dass
zwischen Zustand A und B, wobei A der Zustand vor dem Positionupdate (Position += Velocity) ist und B der Zustand danach, eine Kollision stattgefunden hat,
aber der einfache Kollisionscheck das nicht erkennt!

Code:

Objekte:
[X]--------->v1
v2<--[Y]

Zustand A:
[X]      [Y]

Zustand B:
   {Y]       [X]

Ich habe die Objekte als umschließende Kugeln betrachtet (Bounding Spheres), die aus Position, Velocity und Radius bestehen.
Anschließend habe ich als erstes den Zeitpunkt berechnet (approximiert), wo sie den kürzesten Abstand voneinander auf ihren Bahnen haben.
Wenn sie hier kollidieren (Abstand kleiner als Summe beider Radien), so habe ich den Zeitpunkt berechnet (approximiert), wann es gerade eben zu keiner Kollision kommt.
Ähnlicher Ansatz, wie ihn NamenLozer beschreibt.

Im Anhang befindet sich eine kleine Demo, die das ganze in 2d realisiert! Funktioniert aber genauso auch in 3d.
Kritsiert die Struktur nicht, darauf habe ich keinen Wert gelegt - habe es auf die schnelle entwickelt!

Bin für (algorithmische) Verbesserungsvorschläge offen, da das hier mein erster Lösungsansatz ist.
Gibt es bessere Methoden?

Als Optimierung benutzt man doch Quadtrees (2d) und Octrees (3d) und prüft nur Objekte im selben Node auf Kollision (um unnötigen Kollisionscheck zu vermeiden).
Diese Methode wirkt doch dem entgegen; es kann ja durchaus passieren, dass Objekt X in Node 1 mit Objekt Y in Node 2 kollidiert, da die Velocity sehr groß ist~.
Wie integriert man das?