How to achieve smooth movement with a fixed timestep

Question

Previously in the update method of my game I was using a variable time step which provided very smooth movement of a player sprite except when the frame rate would drop, even slightly. At that point I would end up with the sprite making a noticeable lunge forward. I tried averaging the delta to make it less noticeable but wasn't satisfied.

So I've been trying to implement a fixed time step using the code provided in the article http://gafferongames.com/game-physics/fix-your-timestep/ as an example.

double t = 0.0;
const double dt = 0.01;

double currentTime = hires_time_in_seconds();
double accumulator = 0.0;

State previous;
State current;

while ( !quit )
{
     double newTime = time();
     double frameTime = newTime - currentTime;
     if ( frameTime > 0.25 )
          frameTime = 0.25;  
     currentTime = newTime;

     accumulator += frameTime;

     // ***** Is this where I should add acceleration to the current state velocity? *****
     // current.v += Player::MoveAcceleration * frameTime;

     while ( accumulator >= dt )
     {
          previousState = currentState;
          integrate( currentState, t, dt );
          t += dt;
          accumulator -= dt;
     }

     const double alpha = accumulator / dt;

     State state = currentState*alpha + previousState * ( 1.0 - alpha );

     render( state );
}

In this example where would I add to the velocity? As I noted in the code comment, I am currently adding it prior to the integration loop, but the sprite movement is now consistently lunging forward each frame and is not smooth at all. Even when lowering the acceleration it is still there, and is not a solution anyway as I want the player to be able to walk or run.

I hope this makes sense. I have read so many articles over the last couple weeks and tried many combinations but nothing is working smoothly. I figure someone here must have a solid routine to achieve a fixed time step in a game with smooth sprite movement/animation.

Thanks

Answer 1

You are probably updating the velocity twice, since this is usually done in the integration step itself. I expect you implemented the RK4 integration from http://gafferongames.com/game-physics/integration-basics/.

The author defines Derivative.dv as the acceleration (derivative of velocity) and State.v as as the velocity

In the evaluate function you can then see that the following line updates the velocity using the acceleration d.dv:

state.v = initial.v + d.dv*dt;

and that this line updates the acceleration (calculated by acceleration)

output.dv = acceleration(state, t+dt)

So if you want to change the acceleration, you should change the acceleration function to return the acceleration you want (e.g. constant 9.81f for gravity). The velocity is then changed by the existing code, there is no need to add your own line.

Keep in mind that all of this is one-dimensional (position, velocity etc. are given as a single float) so you can only move in a straight line.

Answer 2

Gordonk was absolutely spot on. It now appears that I have silky smooth movement at 60fps. If I cap the frame rate at anything less than 60 I start to see serious stuttering, but I guess that's a separate issue to explore.

So here is the code I am using right now. It hasn't been optimized in any way, it was just to implement a fixed time step. I'm using the cocos2d-x framework. CCPoint is a simple class that contains two floats, x and y.

struct State
{
    CCPoint statePosition; // position
    CCPoint stateVelocity; // velocity
};

struct Derivative
{
    CCPoint derivativePosition; // derivative of position: velocity
    CCPoint derivativeVelocity; // derivative of velocity: acceleration
};

double getCurrentTimeInSeconds()
{
   struct cc_timeval currentTime;
   CCTime::gettimeofdayCocos2d(&currentTime, NULL);
   return (currentTime.tv_sec) + (currentTime.tv_usec / 1000000.0);
}

void update(float dt) 
{
    if (GetAsyncKeyState(VK_LEFT) & 0x8000) {
        pPlayer->movement = -1;
        pPlayerSprite->setScaleX(1);
    }

    if (GetAsyncKeyState(VK_RIGHT) & 0x8000) {
        pPlayerSprite->setScaleX(-1);   
        pPlayer->movement = 1;
    }

    applyPhysics(dt);

    pPlayer->movement = 0;
}

void applyPhysics(float gameTime) {
    const float newTime = getCurrentTimeInSeconds();
    float deltaTime = newTime - currentTime;
    currentTime = newTime;

    if (deltaTime>0.25f)
        deltaTime = 0.25f;

    accumulator += deltaTime;

    int loopCount = 0;
    while (accumulator>=dt)
    {
        accumulator -= dt;
        previous = current;
        integrate(current, t, dt);
        t += dt;
        loopCount++;
    }

    State state = interpolate(previous, current, accumulator/dt);

    pPlayerSprite->setPosition(state.statePosition);
}

State interpolate(const State &previous, const State &current, float alpha)
{
    State state;
    state.statePosition.x = current.statePosition.x*alpha + previous.statePosition.x*(1-alpha);
    state.statePosition.y = current.statePosition.y*alpha + previous.statePosition.y*(1-alpha);

    state.stateVelocity.x = current.stateVelocity.x*alpha + previous.stateVelocity.x*(1-alpha);
    state.stateVelocity.y = current.stateVelocity.y*alpha + previous.stateVelocity.y*(1-alpha);

    return state;
}

CCPoint acceleration(const State &state, float t)
{
    CCPoint tempPoint = CCPointZero;

    tempPoint.x = pPlayer->movement * Player::MoveAcceleration;

    if (pPlayer->isOnGround) {
        tempPoint.x *= Player::GroundDragFactor;
    }
    else {
        tempPoint.x *=  Player::AirDragFactor;
    }

    tempPoint.x = MathHelper::Clamp(tempPoint.x, -Player::MaxMoveSpeed, Player::MaxMoveSpeed);

    return tempPoint;
}

Derivative evaluate(const State &initial, float t)
{
    Derivative output;
    output.derivativePosition.x = initial.stateVelocity.x;
    output.derivativePosition.y = initial.stateVelocity.y;

    CCPoint tempPoint = acceleration(initial, t);
    output.derivativeVelocity.x = tempPoint.x;
    output.derivativeVelocity.y = tempPoint.y;

    return output;
}

Derivative evaluate(const State &initial, float t, float dt, const Derivative &d)
{
    State state;
    state.statePosition.x  = initial.statePosition.x + d.derivativePosition.x*dt;
    state.statePosition.y  = initial.statePosition.y + d.derivativePosition.y*dt;

    state.stateVelocity.x  = initial.stateVelocity.x + d.derivativeVelocity.x*dt;
    state.stateVelocity.y  = initial.stateVelocity.y + d.derivativeVelocity.y*dt;

    Derivative output;
    output.derivativePosition.x = state.stateVelocity.x;
    output.derivativePosition.y = state.stateVelocity.y;

    CCPoint tempPoint = acceleration(state, t+dt);

    output.derivativeVelocity.x = tempPoint.x;
    output.derivativeVelocity.y = tempPoint.y;

    return output;
}

void integrate(State &state, float t, float dt)
{
    Derivative a = evaluate(state, t);
    Derivative b = evaluate(state, t, dt*0.5f, a);
    Derivative c = evaluate(state, t, dt*0.5f, b);
    Derivative d = evaluate(state, t, dt, c);

    const float dxxdt = 1.0f/6.0f * (a.derivativePosition.x + 2.0f*(b.derivativePosition.x + c.derivativePosition.x) + d.derivativePosition.x);
    const float dxydt = 1.0f/6.0f * (a.derivativePosition.y + 2.0f*(b.derivativePosition.y + c.derivativePosition.y) + d.derivativePosition.y);

    const float dvxdt = 1.0f/6.0f * (a.derivativeVelocity.x + 2.0f*(b.derivativeVelocity.x + c.derivativeVelocity.x) + d.derivativeVelocity.x);
    const float dvydt = 1.0f/6.0f * (a.derivativeVelocity.y + 2.0f*(b.derivativeVelocity.y + c.derivativeVelocity.y) + d.derivativeVelocity.y);

    state.statePosition.x  = state.statePosition.x + dxxdt*dt;
    state.statePosition.y  = state.statePosition.y + dxydt*dt;

    state.stateVelocity.x  = state.stateVelocity.x + dvxdt*dt;
    state.stateVelocity.y  = state.stateVelocity.y + dvydt*dt;
}

I haven't tried applying any vertical force yet but hopefully it will work the same way.

Thanks again for helping me understand the acceleration method.