Moin an alle
Ich experimentiere im Moment mit C und SDL. Dabei bin ich auf ein Problem gestossen, das wohl eher logisch-rechnerischer Art ist.
Bei der Simulation von sich beeinflussenden Massen (z.B. Planeten, Satelliten) kommt es immer wieder vor, dass eine Masse plötzlich unglaublich Beschleinigt wird, wenn sie auf eine andere "stösst" (b.z.w ohne Kollisionsroutine durch sie "hindurchfliegt").
Das rührt daher, dass ich die Kräfte, welche auf die Massen wirken mit Vektoren berechne. Aus den Vektoren ergeben sich dann die neuen Geschwindigkeiten der Massen für den nächsten Frame.
Ist dieser gezeichnet, werden die neuen Positionen analysiert und wiederum die verschiedenen Kräfte berechnet.
Das Problem ist nun folgendes:
Die Gravitationskraft berechnet sich aus F_g = M_1 * M_2 / r^2. Befindet sich nun eine Masse extrem nah an einer anderen (r ist also sehr klein) wird die Kraft die auf die Massen wirken dementsprechend hoch. Demnach wird auch die Geschwindigkeit für diesen Frame für die Massen dementsprechend hoch. Da die Geschwindigkeit aber so hoch ist, sind die Massen beim nächsten Frame so weit voneinander entfernt, dass die neu wirkende Kraft in keinem Verhältnis zur herrschenden Geschwindigkeit steht. Die Masse wird einfach von der Bildfläche katapultiert.
Die Positionen werden also Schrittweise berechnet, Bild für Bild, Frame für Frame. "Hüpft" nun eine Masse nah an eine Andere ist die Geschwindigkeit so hoch, dass sie mit dem nächsten Frame praktisch aus dem Wirkungsberech der anderen Masse herauspringt und somit die eigentliche Abbremsung nie erfahren wird.
Wenn ich nun also zwei gleich schwere Massen mit einem Abstand von 200 Pixeln definiere, "fallen" sie aufeinander zu, wegen der Fehlenden Kollisionsroutine, fallen sie durcheinander, und werden dann so sehr beschleunigt, dass sie einen Abstand weit über 200 Pixeln haben, wenn sie zum Stillstand kommen.

Die selbe Art von Problem habe ich, wenn ich ein Pong programmiere. Die Kugel hat dann z.B. eine Geschwindigkeit von 10 Pixeln pro Frame. Wenn die Kugel nun an den Rand des Fensters kommt, und gerade bei Pixel 2 ist, ist sie beim nächsten Frame bei Pixel -8 und wird erst dann umgelenkt.

Es geht also im Prinzip darum, wie ich die Kräfte bz.w. die Zustände zwischen zwei Frames korrekt rechne. Ich habe einwenig nachgedacht und mir ist keine Gescheite Lösung für dieses wohl allgemeine Problem eingefallen...

Irgendwelche Ideen?

simple lösung: die zeit des frames verkürzen. auf das pong-problem bezogen würde ich einfach pixel für pixel berechnen. du musst ja nicht für jeden frame den du berechnest auch gezwungenermassen einen frame zeichnen.
bei den planeten könntest z.b. umgekehrt berechnen, wie lange es dauert, bis der planet x pixel weiter geflogen ist. sobalt die summe der berechneten zeiten einen schwellwert überschreitet, zeichnest du einen neuen frame und nimmst den übertrag mit in den nächsten.

zum Pong: wieso das? bewegt sich die kugel in zehner schritten ? wenn ja, ist sie schon bei 2 pixel abstand an den rand angestoßen... d.h. du musst schauen, ob die nächste bewegung zur kollision führt und nicht ob die aktuelle position eine kollision ist.

[quote=Taulmarill,09.02.2006, 14:40][/quote]

Quote

simple lösung: die zeit des frames verkürzen.

Das ändert ja nichts, an der eigentlichen Ungenauigkeit der Simulation die ich eigentlich beheben will (sorry, wenn das nicht so korrekt rüberkam)

Quote

auf das pong-problem bezogen würde ich einfach pixel für pixel berechnen.

Jo das habe ich mir auch überlegt und da funktionierts auch...

Quote

bei den planeten könntest z.b. umgekehrt berechnen, wie lange es dauert, bis der planet x pixel weiter geflogen ist.

Jo, das geht bei einem Planeten - doch wird recht mühsam, wenn es sich um 10 Planeten handelt die sich unterschiedlich schnell bewegen...
Und ob es so rum dann genauer ist?

Quote

zum Pong: wieso das? bewegt sich die kugel in zehner schritten ? wenn ja, ist sie schon bei 2 pixel abstand an den rand angestoßen... d.h. du musst schauen, ob die nächste bewegung zur kollision führt und nicht ob die aktuelle position eine kollision ist.

Ja, sie bewegt sich, mit einer Geschwindigkeit von 10Pixeln/Frame in Zehnerschritten. Je nachdem wie schnell eine Kugel ist, ist es nicht möglich bei einer Bewegung jeden Pixel davon in einem Frame darzustellen ohne, dass die Animation dann hinkt...

ich habe ja auch nie gesagt, dass du bei jeder pixelbewegung den frame neu zeichnen sollst, aber wenn du genauer rechnen willst, musst du gezwungenermassen mehr zwischenwerte berechnen.

ich bin nicht der grosse mathecrack, aber ich glaube nicht, dass es die eine formel gibt, in die du alle variablen einträgst, die dir dann die genauen positionen nach einer gewissen zeit ausgibt. da sich alle massen gegenseitig beeinflussen, kann man sich da nur annähern, indem man die berechneten zeiträume kleiner macht.

folgende idee:
nimm den momentan schnellsten körper, den du in deinem system hast und berechne, wie lange es dauert, bis er eine gewisse strecke zurückgelegt hat. der betrag dieser strecke ist gewissermaßen die genauigkeit deiner berechnung. jetzt lass sich alle körper entlang ihres momentanen bewegungsvektors diese entsprechende zeit lang bewegen (hier müsste man jetzt auch noch eine kollisionsabfrage implementieren). nachdem sich alle körper bewegt haben, addierst du zum bewegungsvektor jedes körpers die entsprechenden beschleunigungen die sich aus der masse der umliegenden körper für die verstrichene zeit ergeben. danach fängst du mit dem spass wieder von vorne an. erst wenn die zeit eines frames verstrichen ist (z.b. 1/60 sec), zeichnest du einen neuen frame.
das könnte man jetzt noch dadurch verfeinern, dass die zu berechnende zeit niemals die zeit bis zum nächsten frame überschreiten darf (damit deine framerate erhalten bleibt, auch wenn sich alles besonders langsam bewegt).

das "echtzeitproblem" ist unter spieleprogrammierern weit verbreitet. evtl. solltest du dich mal duch entsprechende websites (z.b. http://www.gamedev.net/)wühlen.\n\n

<!--EDIT|Taulmarill|1139502130-->

Jo das ist eine gute Idee...
Das Problem was ich sonnst noch so hab ist halt, dass die Simulation genau sein soll - und mich würde es interessieren, wie professionelle wissenschaftliche Simulationen mit solchen Problemen umgehen.
Wenn du mal die zwei Massen nimmst, die sich anziehen, durch einander durchfliegen und sich wieder entfernen müsste der Endpunkt immer derselbe sein. Das kannst du in einer Simulation aber nur garanieren, wenn du genau rechnest...
Hmmm. Ich werd deinen Vorschlag auf jedenfall mal umsetzen.

und genau bei'm "genau rechnen" ist das problem. selbst wenn die methode theoretisch 100% genau währe und du alle variablen kennen würdest, kann der computer bei gleitkomma-operationen immer nur eine begrenzt genaues ergebnis liefern.

BigNum erlaubt die Verwendung höherer Genauigkeit bei entsprechenden Operationen. Natürlich zu Lasten der Geschwindigkeit. Es gibt in einigen Sprachen Bibliotheken zum Rechnen mit beliebiger Genauigkeit (vor allem in der Finanzwelt z.B. COBOL).

Man kann mit gmp oder ähnlichen Bibliotheken zwar mit beliebiger, jedoch immer nur mit endlicher Genauigkeit rechnen.

Außerdem ist bei dem Problem, das diesem Thread zugrundeliegt eine adaptive Schrittweitensteuerung, wie sie schon vorgeschlagen wurde, wesentlich mehr angebracht als ein Erhöhen der Genauigkeit der Fließkommaoperationen.

(edit: Typo)\n\n

<!--EDIT|murphy|1139520580-->

Es gibt zwei Möglichkeiten, solche Berechnungen wie für eine Gravitationsfeld durchzuführen: In Form einer analytischen Lösung (d.h. als geschlossene Formel, die das System zu jedem Zeitpunkt beschreib) oder als numerische Näherung. Für Mehrkörperprobleme gibt es schnell keine geschlossenen Lösungen mehr (bei n > 3, wenn ich mich recht erinnere), daher sind dort numerische Verfahren die Regel.

Wie Taulmarill direkt schon bemerkte, ist eine entscheidende Frage der zeitliche Abstand, in dem du die einzelnen Schritte berechnest. Dein Körper ist permanent beschleunigenden (oder bremsenden) Kräften ausgesetzt, du berechnest aber nur die Kräfte zu diskreten Zeitpunkten. Theoretisch bräuchtest du zur Berechnung der Wirkung das Integral F(t) von t_n bis t_{n+1}, du hast aber nur F(t_n) und F(t_{n+1}). Natürlich kann man nicht infinitesimal kleine Zeitschritte zwischen den Berechnungen nehmen, aber es gibt Methoden, die Ungenauigkeiten der diskreten Berechnung etwas auszugleichen.
Im ersten Schritt kann man linear zwischen den diskreten Werten F(t_n) und F(t_{n+1}) interpolieren (man erhält sozusagen die Fläche des Trapezes zwischen t_n, F(t_n), F(t_{n+1}) und t_{n+1}), in einem zweiten Schritt kann man eine bessere Interpolation mit mehr Zwischenwerten vornehmen, was z.B. ganz elegant mit dem Runge-Kutta-Verfahren geht. Das Verfahren hat natürlich seine Grenzen bei nicht-stetigen Funktionen, was bei Gravitationsfeldern aber wenig ins Gewicht fällt, solange die Körper eine endliche Größe haben (keine Polstelle bei Abstand Null) oder sicher gestellt ist, dass sie nicht direkt aufeinander stoßen.
Möglicherweise nimmt man heute bessere und/oder schnellere Verfahren, mein Stand ist von vor über 15 Jahren. ;)