next »

[raigan]

I'm in the process of converting a simulation that was written for a hard-coded 40hz update frequency so that it works at 60hz (or really, whatever new frequency is required).

Unfortunately, lots of slightly-weird math was used in the movement code, so that converting movement parameters between these two simulation rates is proving to be somewhat confusing: there are several different flavours of velocity- and acceleration-like values which are used to evolve the positions forward through time, and I'm hoping someone will have some suggestions on how to approach this.

The goal is to have the positions of objects change at a constant rate regardless of simulation rate.

Here are the different types of variables, and how they're used:

velocity
vel = v1
pos += vel

acceleration
acc = a1
vel += acc
pos += vel         

velocity damping
damp = vd1
vel *= damp
pos += vel   

acceleration damping
damp = ad1
acc *= damp
vel += acc
pos += vel

impulse
imp = i1
vel += imp
pos += vel


And here are my current best guesses at how to calculate the new 60hz values:

velocity: v2 = v1 * (40/60)   

acceleration: a2 = a1 * (40/60)^2
(from http://www.gamedev.net/topic/570306-uniform-gravity-at-different-framerates/page__view__findpost__p__4643832 )

velocity damping: vd2 = vd1^(40/60)
(from http://www.gamedev.net/topic/573407-consistant-damping-at-different-frame-rates/page__view__findpost__p__4659503 )

acceleration damping: ad2 = ad1^((40/60)^2)... maybe? (this is a pure guess)

impulse: i1 = the same as acceleration, maybe? (again, grasping at straws)


Are these correct? If anyone could point me in the right direction, I'd really appreciate it... I'm feeling pretty stupid getting stuck on this


For bonus points, I have the following code which terrifies me:

Code:

acceleration *= accel_rate;
speed += acceleration;

tangent_amt = dir.Perp().Dot(target_pos - current_pos);
tangent_vec = tangent_amt * dir.Perp();
dir += turn_rate * tangent_vec;
dir.Normalize();

current_pos += speed * dir;

accel_rate is a "damping of acceleration" type; turn_rate on the other hand seems pretty awkward because of that normalize() -- I really don't understand how to formalize discrete time-stepped systems like that.

Any advice, links, or other help would be really appreciated.

[ham and brie]

acceleration damping: ad2 = ad1^((40/60)^2)... maybe? (this is a pure guess)

If acc(n,t) is the value for acc after time t seconds when running at nHz, then:
acc(60,t) = acc(40,t) * (40/60)^2
acc(40,0) = acc(40,1) * ad1^(40)
acc(60,0) = acc(60,1) * ad2^(60)

Which gives:
acc(40,0) * (40/60)^2 = acc(40,1) * (40/60)^2 * ad2^(60)
acc(40,0) = acc(40,1) * ad2^(60)
acc(40,1) * ad1^(40) = acc(40,1) * ad2^(60)
ad1^(40) = ad2^(60)
ad2 = ad1^(40/60)

impulse: i1 = the same as acceleration, maybe? (again, grasping at straws)

It would be i2 = i1 * (40/60).

I think you're making it hard for yourself by calling values things like vel, acc or imp when they are not a velocity/acceleration/impulse, since you've multiplied the duration of the time step into them.

The "vel" you're using is actually velocity * time step
"acc" is acceleration * time step * time step
"imp" is impulse * time step / mass

If you used real world names for the quantities, things would probably be clearer.



Bear in mind that, because of the approximations made, different simulation rates will almost certainly lead to divergent results. For instance, even in a very simple case: if something is accelerating from 0m/s at 1 m/s/s over 1s, you'd want it to have moved 0.5m. Instead, at nHz you'd get (n^2+n)/(2(n^2)) (i.e. at 40Hz you get 0.5125m and at 60Hz you get 0.5083m; higher rates get a better approximation). The difference will mount up, potentially enough to make a significant difference to the player.

[raigan]

Thanks for the reply... I've got a few questions.

If acc(n,t) is the value for acc after time t seconds when running at nHz, then:
(...)
ad2 = ad1^(40/60)

This is identical to the formula for velocity damping: is that correct?!

It seems to me that since velocity and acceleration affect the evolution of position over time in different ways (and are adjusted to the new simulation rate using different formulas), damping velocity vs damping acceleration should likewise affect the evolution of position differently as well, which implies that each requires a different formula.

I think you're making it hard for yourself by calling values things like vel, acc or imp when they are not a velocity/acceleration/impulse, since you've multiplied the duration of the time step into them.

Yeah, this is regrettably very true.

The "vel" you're using is actually velocity * time step
"acc" is acceleration * time step * time step
"imp" is impulse * time step / mass

Is this necessarily true? Specifically, if I'm using Newton-Stormer-Verlet/semi-explicit Euler, then I'm doing this:

v += a*dt
x += v*dt

rather than v += a*dt*dt.

But... since my "a" value has the timestep baked in, how can I tell which formula I was actually using?!

Bear in mind that, because of the approximations made, different simulation rates will almost certainly lead to divergent results. For instance, even in a very simple case: if something is accelerating from 0m/s at 1 m/s/s over 1s, you'd want it to have moved 0.5m. Instead, at nHz you'd get (n^2+n)/(2(n^2)) (i.e. at 40Hz you get 0.5125m and at 60Hz you get 0.5083m; higher rates get a better approximation). The difference will mount up, potentially enough to make a significant difference to the player.

My (possibly wrong) understanding was that position moved along a curve, which is approximated piecewise linearly as we step forward in time. By changing the size of the time steps, the positions of the sample points will change, so the actual position may be different at a particular point in time, but it should always be following the same ideal curve. But your example also makes perfect sense...

Man... I feel like I'm in way over my head here

[ham and brie]

This is identical to the formula for velocity damping: is that correct?!

The reasoning is almost the same for converting vd1. The (40/60)^2 terms would be (40/60) instead, but those cancel out, because the damping is applied by multiplication.

Is this necessarily true? Specifically, if I'm using Newton-Stormer-Verlet/semi-explicit Euler, then I'm doing this:

v += a*dt
x += v*dt

rather than v += a*dt*dt.

But... since my "a" value has the timestep baked in, how can I tell which formula I was actually using?!

If you substitute acc with a*dt*dt and vel with v*dt, then
vel += acc
is equivalent to
v += a*dt
(a dt on each side cancelled out)

My (possibly wrong) understanding was that position moved along a curve, which is approximated piecewise linearly as we step forward in time. By changing the size of the time steps, the positions of the sample points will change, so the actual position may be different at a particular point in time, but it should always be following the same ideal curve.

Unfortunately not. The approximations will diverge, the higher rate simulation being closer to the ideal. The problem is in sampling values that are varying over time and applying them in calculations as though they were constant. And then further approximations are calculated from those approximations.

[randomnine]

Whoa. Your physics is a bit strange. If you'll have to work with this for a while in future, I seriously recommend picking up a few books on calculus and learning integration (the science of "approximating piecewise linearly as we step forward in time") so you can get this stuff right. Then you'll have to work out formulae for framerate-independent physics which are compatible with how it was acting before, which will be fun.

Anyway, here's an example of basic integration for ya:

x = x + v*dt + 0.5*a*dt*dt;
v = v + a*dt;

I don't care how many timesteps you use or how big or small they are, in the case of "0m/s at 1 m/s/s over 1s" you will always get x = 0.5m and v = 1m/s after a second by repeatedly applying those two lines in that order.

Of course, maybe you just need to get this rendering in a framerate independent way and don't really want to go into overhauling the physics to achieve that. If so, here is what you need to do:

- Simulate at 40Hz. Every time you cross another 25ms boundary, simulate another frame. However, keep the positions of all objects from the last frame.
- When rendering, interpolate linearly between the old position and the new position.

Something like this:

Code:

timestep = 1/60;
simulation_timestep = 1/40;

while (1)
{
    time += timestep;

    if ( time > latestSimulationFrameTime )
    {
        previousSimulationFrameTime = latestSimulationFrameTime;

        simulateNextFrame(); // Run the old simulation code.

        latestSimulationFrameTime += simulationTimestep;
    }

    // How far are we between simulation frames?
    frameInterpolation = (time - previousSimulationFrameTime) / simulationTimestep;

    for ( each object in scene )
    {
        latest_pos = object.pos;
        previous_pos = object.previousPos;
       
        interpolatedPos = frameInterpolation * object.pos + (1 - frameInterpolation) * object.previousPos;

        object.renderAt( interpolatedPos );
    }
}

[raigan]

@ham and brie: I've started making the changes and stuff seems to be working more or less properly! It *is* slightly off but I think it's close enough, thanks so much for your help. Of course, I haven't yet reached the super-ugly code that I pasted at the bottom, so far it's just been relatively straightforward stuff.

I'm not sure I understand what you're saying about dt*dt terms for forces/acceleration; frankly I was just copying Box2d which does:
gravity = (0,-10)
velocity += h * gravity
position += h * velocity

Which to me looks like they're not using a dt*dt term (i.e gravity is -10, not -10*stepsize), only dt for acceleration.


@randomnine: I admit that I don't really understand the mathematical underpinnings of how NSV works, but I just copied it from Box2d:

v += a
p += v

AFAIK the 0.5*a*dt*dt isn't commonly used -- I think there was a thread about this on the Bullet forums a year or two ago, the consensus was that unless you're simulating a dropped ball no one will notice the difference that dropping the 0.5 makes, but NSV has some properties (symplectic-ness AFAICR) that make it desirable.

About sticking with 40hz and interpolating, sadly the reason I'm switching to 60hz is that it's not responsive enough at 40hz. Basically, old versions of the flashplayer would actually run at 120hz, so I would have the flashplayer running at 120fps and then internally step forward at 40hz (i.e the flashplayer would feed time to my main loop in 8ms increments, and I would step my sim forward whenever 25ms elapsed).

These days, flashplayer seems to be locked to no more than 60hz, which makes my above approach feel terrible (I'm assuming due to the coarser granularity of 16ms per time-slice). Rather than implementing interpolation (or I should say in addition to), I'm going to try to just let the flashplayer run my main loop (i.e don't handle the stepping myself, just step once per frame of the flashplayer). AFAIK this is how e.g Flixel works, and that tends to produce nice smooth games. I still sort of don't trust the flashplayer though, I'm very sensitive to framerate fluctuations and especially when running in-browser it does seem to suffer from a not-perfectly-constant framerate.

[ham and brie]

Of course, I haven't yet reached the super-ugly code that I pasted at the bottom, so far it's just been relatively straightforward stuff.

I guess that's code for a homing missile. It's sort of using the small angle approximation to rotate dir through roughly turn_rate * tangent_amt radians, so dealing with turn_rate might be as simple as scaling it by (40/60).

[raigan]

Yeah, it's a homing rocket -- it's not the small-angle approximation as much as a very hacky way of avoiding trig

I came to the same conclusion, it's a constant change of rate so similar to velocity. Thanks again... so far things are working, there are small differences (e.g damped springs are sadly not exactly identical in movement). Tomorrow I tackle the really ugly stuff

[BorisTheBrave]

It's quite a lot of work to change the framerate of a fixed step function, as you are seeing. And it is impossible to make it 100% accurate.

As a hacky alternative, have you considered running the simulation at 40hz, but the screen updates at 60hz. If you run the simulation ahead of the screen, and then interpolate all positions from the last two frames, this can look moderately smooth (though it only improves the graphics - it keeps the same latencies in the gameplay).

Something like the following will work to adapt to an arbitrary time step:

Code:

float gameTime = 0;
float lastGameTime = 0;
while(true)
{
  float actualTime = getActualTime();
  while(gameTime < actualTime)
  {
    lastGameTime = gameTime;
    doFixed40hzStep();
    gameTime += 1/40.0f;
  }
  float interpolation = (actualTime - lastGameTime) / (gameTime - lastGameTime);
  drawGame(interpolation);
}

where drawGame will draw each object interpolating from it's position and previous position.

[raigan]

(hmm, I guess the internet ate my first reply)

As I mentioned to randomnine, sadly the problem is that 40hz just isn't as responsive as 60hz, which feels a lot better. Once things are running at 60hz I do plan on adding an interpolated display step like you describe, just to see if it makes a difference.