Spielephysik (game physics): Numerische Integration

Physikalische Simulationen mit sich schnell ändernden Kräften (z. B. ein Masse-Feder-System) tendieren mit der Zeit dazu, instabil zu werden. Da sich keine Aussagen darüber treffen lassen, wie sich die Kräfteverhältnisse und damit verbunden die Geschwindigkeiten zwischen zwei Zeitschritten verändern, vergrößern sich mit jedem Rechenschritt die Abweichungen vom realen Verhalten. Irgendwann sind die Berechnungsfehler so groß, dass die Bewegungsenergie der simulierten Körper über die Maßen ansteigt und die Simulation regelrecht explodiert.
Besonders problematisch ist die Situation bei Wechselwirkungskräften (z. B. Federkräfte), denn dann wirken sich die Berechnungsfehler zusätzlich auf alle miteinander wechselwirkenden Körper aus. Nachfolgend wird nun ein Integrationsverfahren vorgestellt, mit dessen Hilfe sich die Berechnungsfehler minimieren lassen.

Für naturwissenschaftliche Berechnungen ist dieses Verfahren nicht geeignet, denn es verletzt den Energieerhaltungssatz. Durch die sogenannte numerische Dämpfung wird bei jedem Simulationsschritt etwas Bewegungsenergie aus dem System abgeführt, wodurch Berechnungsfehler, die zu einer Erhöhung der Energie führen, zumindest teilweise kompensiert werden. Die numerische Dämpfung trägt somit zur Stabilität der Simulation bei und macht das Verfahren interessant für die Spieleprogrammierung. Hier die einzelnen Integrationsschritte:

Berechnung der momentanen Beschleunigung:

a(t) = F(t)/m

Berechnung der neuen Geschwindigkeit:

v(t+dt) = a(t)*dt + v(t)

Neuberechnung der alten Geschwindigkeit:

v'(t) = v(t+dt) - a(t-dt)*dt

Mitteln der Geschwindigkeiten minimiert den numerischen Fehler (numerische Dämpfung):

vm(t) = 0.5*( v(t) + v'(t) )

Berechnen der neuen Geschwindigkeit mithilfe der gemittelten Geschwindigkeit:

v(t+dt) = a(t)*dt + vm(t)

Berechnung der neuen Position wie gehabt:

s(t+dt) = v(t+dt)*dt + s(t)

Nachfolgend ist die Berechnung von zwei Simulationsschritten pro Frame skizziert:

D3DXVECTOR3 Acceleration, AccelerationLastSimulationStep,
            Velocity, Velocity2, VelocityNew, Position;

long
NumSimulationStepsPerFrame = 2;

float SimulationTime = FrameTime/NumSimulationStepsPerFrame;

for(long i = 0; i < NumSimulationStepsPerFrame; i++)
{
    // hier die aktuelle Beschleunigung ermitteln:
    ...

    // neue Geschwindigkeit berechnen:
    VelocityNew = Velocity + Acceleration*SimulationTime;

    // alte Geschwindigkeit neu berechnen:
   
Velocity2 = VelocityNew -
    AccelerationLastSimulationStep*SimulationTime;

    // alte Geschwindigkeiten mitteln:
   
Velocity = 0.5f*(Velocity+Velocity2)

    // neue Geschwindigkeit neu berechnen:
   
Velocity += Acceleration*SimulationTime;

    // neue Position berechnen:
    Position += Velocity*SimulationTime;

   
// aktuelle Beschleunigung für den nächsten Simulationsschritt
    // zwischenspeichern:

    AccelerationLastSimulationStep = Acceleration;
}