Sichere Kollisionsbehandlung für 2D Rennspiel

[Sliver21]

Hallo Jungs,
ich bin gerade dabei, für unser Spiel eine Kollisionsbehandlung zu machen. Oder eher: ich habe sie schon längst fertig, aber leider läuft sie fehlerhaft (zwar selten, kommt aber in ungünstigen Situationen vor). Zum Spiel: Es ist ein 2D Rennspiel a la Micro Machines mit rechteckigen Fahrzeugen. Wenn zwei Fahrzeuge kollidieren, so stoßen sie sich voneinander ab, als seien sie Kugeln. Der Algorithmus zur Berechnung der Geschwindigkeiten nach dem Stoß funktioniert einwandfrei. Der Algorithmus zur Kollisionskontrolle funktioniert auch einwandfrei.
Bei uns ist es so, dass bei jedem Frame zuerst die Translation aller Fahrzeuge berechnet wird und dann, nachdem diese abgeschlossen ist, die Translation durchgeführt wird.
Nun zu unserem Problem: Eine Kollision findet statt, wenn zwei Fahrzeuge überlappen. Wie muss die Kollisionsbehandlung nun logisch richtig strukturiert werden, damit es zu keinen 'Inkonsistenzen' im Spiel kommt. Zur Zeit prallen die Fahrzeuge sehr gut aneinander ab, wenn bei der Kollision 2 Fahrzeuge beteiligt sind. Sind aber gleichzeitig mehrere Fahrzeuge darin verwickelt und die Kollisionen finden am Rand der Karte statt, wo die Fahrzeuze noch von der Wand abstoßen, so kommt es manchmal dazu, dass sich die Fahrzeuge ineinander 'verbeißen'. Sie überlappen, prallen ab, bleiben im nächsten Frame aber immer noch überlappend und kollidieren erneut usw. Es sieht auf jeden Fall ganz wild aus.
Nun zur eigentlichen Frage: Wie muss eine Kollisionsbehandlung aufgebaut sein, damit es zu keinem unerwarteten Verhalten der Fahrzeuge kommt. Mit Google konnte ich bisher nichts sinnvolles finden, was uns helfen könnte. Ich hoffe, ihr versteht, was ich meine und habt auch eine Idee, wie man das Lösen kann.
Falls noch etwas fehlt, dann sagt bescheid.

[micki]

das problem ist einfach dass du zuwenig zeitschritte hast. nehmen wir mal an du hast so standard werte von 60 oder 100 zeitintervalen. bei soeiner kleinen frequenz kann es sehr leicht passieren dass sich zwei fahrzeuge knapp verpassen obwohl sie eigentlich einander schneiden oder wie bei der massenkarambolage, dass sie schon ineinander stecken und keine richtung die richtige ist.

du brauchst also zwei wichtige schritte.
1. beim feststellen von kollisionen musst du zwischeniterationen einbauen, manche physic/collision libs haben 1000 unterstufungen einer sekunde (oft durch binaersuche der kollision)

2. (dazu ist 1. die grundlage) musst du die objekte an der kollisionsstelle schon von der richtung her aendern, nicht wenn sie schon gnadenlos ueberlappen. dazu kannst du in einfachen faellen einfach ausrechnen wie die jetzige entfernung der kugeln ist und wie sie im frame davor waren und dann die kollisionsposition ausrechnen, in komplexen systemen geht das eben durch iterieren und (WICHTIG) waehrend der iteration musst du weiter bis zum ende der zeiteinheit simulieren

quasi

SubMove = (NewPosition-OldPosition)/1000;
SubPosition = OldPosition;
if(Collision(NewPosition)
{
for(a=0;a<1000;a++)
if(Collision(SubPosition +SubMove)
Respond(SubPosition ,SubMove); //
NewPosition = SubPosition;
}


das ist uebrigens mit ein grund weshalb physicengines bei vielen interaktionen so einbrechen waehrend sie bei simplen rumfliegenden dingen (ganz zu schweigen von statischen dingen ;) ) kaum rechenzeit ziehen.

[Sliver21]

Danke. Das klingt sehr vernünftig, was du gesagt hast. Scheinbar ist dieses Thema um einiges komplexer, als ich dachte. Wenn ich wieder Zeit habe, werde ich versuchen, deine Vorschläge einzubauen.

[grandmasterw]

Du kannst auch den Abstand aus dem vorigen Frame hernehmen, und den Abstand des jetzigen Frames (der ja negativ ist). Dann kannst du dir ausrechnen, zu welchem Zeitpunkt die Berührung eingetreten ist.

Also du hast 2 Bewegungsvektoren (normalisiert), und 2 Geschwindigkeiten.
Wenn der Abstand vorher 5 war, und jetzt -3, dann weißt du, dass nach 5/8 des Bewegungsvektors die Berührung stattgefunden hat. d.h. du addierst mal 5/8 des Bewegungsvektors zu beiden Objekten, berechnest die neuen Bewegungsvektoren und Geschwindigkeiten aus, und addierst dann 3/8*geschw*vektor zu jedem Objekt. Damit entfernen sich die Objekte wieder ein wenig.

Sollte flotter gehn, als mit iterationen.

[micki]

...

Sollte flotter gehn, als mit iterationen.das hatte ich ebenfalls geschrieben und auch dass es bei komplexen interaktionen nicht mehr funktioniert, denn dann hast du viele objekte die interagieren und nach dem ersten durchlauf und reflektionsberechnung kann es sein dass sofort wieder kollisionen/ueberlappungen auftreten. falls du es wirklich richtig berechnen wollen wuerdest, muesstest du die objekte um eine dimension erweitern und dann in abhaengigkeit von zeit (und zudem auch noch der auftretenden kollisionen) formen und gegeneinander kollidieren... sehr sehr komplex selbst bei 2d-kreisen. deswegen iterieren wohl die meisten.

[Sliver21]

Micki, hast du sowas ähnliches schon mal geschrieben? Du hast schon recht, dass man da sehr vorsichtig vorzugehen hat, denn sonst verfängt man sich wieder in irgendwelchen Fehlern, wo viele Objekte beteiligt sind.

[micki]

Micki, hast du sowas ähnliches schon mal geschrieben?
jap,hunderte male :), gerade letzte woche erst wieder fuer meine psp-engine :), ist heutzutage auch relativ einfach fuer jeden zu machen, dank schneller CPUs bei float. frueher musste man das mit int (fixpoint) rechnen, das hatte sehr oft genauigkeitsprobleme (und es war scheisse langsam :) )

[MuLuNGuS]

und das hier:

http://chrishecker.com/Rigid_Body_Dynamics
®