Sign in to follow this  
Aardvajk

Frame-rate independance and Mario-style jumping

Recommended Posts

Bit of a general question this but I'm just hoping for some inspiration. I'm now getting started on a Mario-style 2D side scroller and have come across a bit of a problem. Obviously I want frame-rate-independant motion and am using the normal approach of multiplying a velocity by a time delta each frame to move the character. This worked fine with my last spaceship based game since pixel precision was not really an issue. However, I've just been running some tests with a block jumping up and down on the screen via a vertical velocity balanced against a force of gravity. The test program is recording the highest Y position the block reaches during its jump. The problem is that when I put a random Sleep() call into the main loop to simulate different frame rates, it has a significant effect on the highest point the block jumps to. With a Sleep() of 30, the block actually makes 3 pixels lower than running at full pelt (60 fps on my hardware). Clearly this means that on a slower computer, the character would not jump as high under a given velocity and on a 80 fps set-up, say, the character would actually jump higher. This is no good for a jumping-based platformer as I need the character to attain exactly the same height, and cover exactly the same horizontal distance during a jump regardless of the frame-rate. Has anyone else come across this problem and have any suggestions for a different way to handle it? The only other option seems to be to throttle the frame rate, but that sucks. Any advice, ideas or suggestions would be appreciated.

Share this post


Link to post
Share on other sites
Lock the update rate. Meaning
Let's say, that you want to update every 30ms, then for every frame do the following (all time variables are in ms)


int timePassed = 0;
void drawFrame (int timeDelta, <other params>) {
if ( timePassed < 30 )
timePassed += timeDelta;
if ( timePassed >= 30 ) {
timePassed -= 30;
updatePhysics ();
}
}


The purpose of the first if is to prevent the counter from increasing indefinitely on machines that are too slow to draw a frame every 30ms. Without it, timePassed would actually loop around, when it reaches the maximum value for an int and become a very negative number indeed, which would make your game appear locked. With it, on slow machines, your game would run rather slowly, but it won't freeze.

Share this post


Link to post
Share on other sites
I appreciate the response, but I'm pretty sure that locking the physics to a fixed rate based on time elapsed since last frame will be subject to the same inaccuracies as the current method. I may be wrong.

[EDIT] Actually, thinking about it, it may well be the solution. Sorry about my hasty dismissal above. Fixing the physics updates but continuing to have the fastest possible render rate may well be a fantastic solution.
[END EDIT]

I've just been reading up and it appears that my problem method is called Euler Integration. I've just been trying to get my head round RK4 intergration as an alterative but

a) It seems very complicated for a Mario side scroller
b) I'm far to stupid to understand it anyway

I reckon I'm going to need to fudge a simpler solution.

[Edited by - EasilyConfused on November 27, 2006 1:59:05 PM]

Share this post


Link to post
Share on other sites
What you really need is to update all of the game physics in a frame rate independent way. Something like this I think.


// called from the master update loop
void PhysicsUpdate(float delta)
{
const float maxStep = 0.0166667f; // 60hz max step time

do
{
float step = maxStep < delta ? maxStep : delta;
delta = delta - step;
// update game physics with a max time step
UpdateGamePhysics(step)

}while (delta > 0.0f)
}

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
It's a combo of both problems actually
your current approach attemps to compensate for variable time by using the delta time in the motion equations, however, Euler will behave differently based on the size of the time multiplier used (timestep)
basically each timestep with Euler is like a small linear approximation of the real 'curved' physics motion, thus changing the timestep lands you in slightly different paths...

If you do Mo6eb's suggestion of locking the physics time interval to be multiplies of 30, Euler will remain Consistent
Alternatly RK4/5 is purely more accurate to begin with and more tolerant of variations in the timing, but this only reduces the error, it won't enforce determinism

personally I'd got with locking the time to fixed intervals, its a lot easier and should be good enough
So you'll have a physics update, which is quantized and runs as few or as many times as needed to fill up time between the graphics refresh
and of course, it will generally be out of synch
to handle syncrhonization and 'beat frequency' issues with motions looking jerky, you actually simulate physics 1 step into the future then linearly interpolate the graphics between the two physics stages that bracket it...

Share this post


Link to post
Share on other sites
I've just implemented locking the physics update rate and it seems to work perfectly. I won't fully understand the implications of this for a while but this seems to be the direction to go in.

Thanks everyone, especially to Mo6eB, whose suggestion I so hastily dismissed in the first place.

Share this post


Link to post
Share on other sites
This is a common problem caused by using code like this:
    v += a * t
d += v * t
It is not correct. "d += v * t" is only correct when v is constant and in this case it is not. Here are the correct formulas for motion with constant acceleration.
    v = v0 + at
d = d0 + v0t + ½at2
d0 and v0 are the starting location and velocity. t is the time since the start. The starting point can be any time in the past (e.g. the previous frame or the start of the jump) as long as d0, v0 and a are constant since the start of the motion.

Mo6eB suggests locking the physics update interval. That is not really a solution. It will make the motion consistent, but it will still not be accurate (though it may be sufficiently accurate for your purposes). Also, keep in mind that if you set up your levels to work at a particular update rate, they may not work at a different update rate.

Finally, the incorrect code above turns out be an approximation called "Euler integration". Most people using that code don't intend for it to be an approximation and that's why I call it "incorrect". There are other methods of approximation (or "integration"), such as Runga-Kutta ("RK4/5" as the AP mentioned above). For motion with constant acceleration, these approximation methods are not necessary -- just use the real formulas.

Share this post


Link to post
Share on other sites
Even if those are the formulas being used, a constant physics timestep can still be useful in cases where the acceleration is not constant. A non-passive entity in a sidescrolling game might decide to change its acceleration, velocity, and/or position at every timestep. If the timestep changes, the resulting motion will also change. A deterministically chosen timestep allows for consistency no matter how the entity is designed.

Share this post


Link to post
Share on other sites
As John Bolton suggests, a modified Euler implementation will fix all of your problems (it's what I used in my platformer as well):

position += velocity * deltaTime + acceleration * (deltaTime*deltaTime)/2.0f;
velocity += acceleration * deltaTime;

That should do it for ya.

Share this post


Link to post
Share on other sites
Quote:
Original post by Roof Top Pew Wee
As John Bolton suggests, a modified Euler implementation will fix all of your problems (it's what I used in my platformer as well)


Depending on what the OP means by "consistent" that's true only with a constant timestep. you can really never guarantee that a frame will be calculated at the exact peak of a jump. it's much more likely that the peak will occur between frames since it's time-based movement. The root of the problem is that with digital physics you're quantizing the movement. There is no workaround to get consistent results other than time-restricing the physics processing or doing some pre-calculation to determine the exact location of the high-point of the jump (i.e. current frame notes that the high-point happened between curFrame and lastFrame, so triggers a hit at the highpoint location).

the best solution is to not require per-pixel accuracy in your platformer. give your toon a little fudge with collision so if you're off the peak by a couple milliseconds it's not a big deal.

AFAIK mario could always jump higher than the things he needed to hit on his jumps. this would also fix your problem because you don't need an exact peak of the jump to trigger the hit.

-me

Share this post


Link to post
Share on other sites
Quote:
Original post by Roof Top Pew Wee
As John Bolton suggests, a modified Euler implementation will fix all of your problems (it's what I used in my platformer as well):

position += velocity * deltaTime + acceleration * (deltaTime*deltaTime)/2.0f;
velocity += acceleration * deltaTime;

That should do it for ya.


This can also be rendered as:


float old_velocity = velocity;
velocity += acceleration * deltaTime;
position += deltaTime * (velocity + old_velocity) / 2.0f;

Share this post


Link to post
Share on other sites
Hello everyone, and thanks! I was just toying around with the new XNA framework and was irritated how bad my motions where.. Reading this one, I've solved all of the problems (except the one that my notebook is quite slow when it comes to rendering, thus resulting in those big motion problems) with the help of this thread, really cool.

I'm somehow ashamed that I didn't got the idea myself.. i mean, we've learned that equation in school, didn't we?

But it's all so long ago...

Share this post


Link to post
Share on other sites
Good grief. Fair few responses here since I looked last. Thanks very much to every body. I'll try out some of those formulas tonight and see what results I get in my test application.

I agree with the poster who suggested levels shouldn't be so accurate and should have a fudge factor. I was just finding a difference of 3 pixels over just +/- 10 fps with the basic Euler, which seemed quite high.

I'll test out John Bolton and Roof Top Pew Wee's improved formulas and see if they give better accuracy.

Thanks again.

Share this post


Link to post
Share on other sites
Just wanted to point out that any solution that supports a variable frame rate is going to feel more sloppy to control than a fixed time step, and control is critical to platformers to the point where a good player will know exactly what frame to jump at. Once that is lost, the game controls will suffer, even if the problem is very slight. Slowdown is even worse when the timestep is variable, the tiniest lag-warp will kill and frustrate your player.

The best solution is the one that it sounds like you have already implemented: keep your gameplay updates consistent at 30/60 fps.

Share this post


Link to post
Share on other sites
Quote:
Original post by JBourrie
Just wanted to point out that any solution that supports a variable frame rate is going to feel more sloppy to control than a fixed time step, and control is critical to platformers to the point where a good player will know exactly what frame to jump at. Once that is lost, the game controls will suffer, even if the problem is very slight. Slowdown is even worse when the timestep is variable, the tiniest lag-warp will kill and frustrate your player.

The best solution is the one that it sounds like you have already implemented: keep your gameplay updates consistent at 30/60 fps.


Yep. I'm becoming inclined to agree. It would also vastly simplify the majority of the rest of the game, since motion and animation timings would no longer need to be modulated by the time delta.

The article mattdev posted looks like exactly the answer. Thanks to everyone for yet another informative and interesting set of responses.

[EDIT]

Based on that article, fixed timestep seems to work like a charm, as per the figures below. The first figure is the highest pixel attained and the second is the proportion of a second (in actual time) the entire jump took to execute. The lines represent the loop running with no Sleep() then with Sleep()s of 10, 20, 30, 40 and 50:


305, 0.664
305, 0.662
305, 0.656
305, 0.666
305, 0.681
305, 0.664


Then the result with no Sleep(), but the time each frame divided by two (to simulate a 120 fps set up):


305, 0.664


Fantastic results and exactly what I wanted.

[Edited by - EasilyConfused on November 28, 2006 1:28:28 PM]

Share this post


Link to post
Share on other sites
An hybrid solution that hasn't been mentioned yet and addresses JBourrie's concern with animation timing is updating the model at a fixed rate and drawing two kinds of frames: the important ones, one per model update, in which everything moves, and extra frames in which the sprites and other critical graphics remain still (to allow the player to count frames) while only elements whose movement is unimportant, like subtly animated textures or status text and icons, are animated and look as smooth as possible.

Share this post


Link to post
Share on other sites
I really recommend that you use fixed timestep game logic. This will make your game deterministic.

Of course the frame rate may vary, therefore to achieve optimum smoothness, you should interpolate between the frames.

You can interpolate an animation variable by doing the weighted average of its current value and its previous timestep value, weighted by the amount of time which has passed since the last timestep.

Effectively, the animation state will always be exactly 1 tick behind the "real" physics. This is not a problem as the player probably won't notice this (set physics ticks to 1/20 s or faster).

I've implemented this and it really is the nicest way of doing it.

The trouble with variable-timestep is that you have to take it into account for all your timers etc, in the game as well as movement, rotation, animation etc, and it gets a little bit error prone, particularly when using floating point.

Mark

Share this post


Link to post
Share on other sites
Got a new problem now though.

I've implemented fixed rate physics with independant rate rendering. Just a block bouncing round the screen.

It jitters. It jitters real bad.

markr - could you give me a bit more detail on this stuff about interpolating based on an average? I'm not sure what you mean exactly.

Does tihs mean calculating the actual position when I do the physics, then working out an interpolated position to actually draw an object when I render?

Wouldn't this mean that every object has to effectively carry two states around with it - its previous and its current?

[EDIT]
My test app is here.

My main loop code looks like this:


CResult CEngine::Cycle()
{
static float Accumulator=0;

Accumulator+=Timer.Get(); // returns time since last called as proportion of second from 0.0f to 1.0f

while(Accumulator>=PhysicsDelta)
{
CResult R=CurrentMode()->Physics(); if(R!=rsOk) return R;
Accumulator-=PhysicsDelta;
}

Dev.BeginScene();

CResult R=CurrentMode()->Render(Dev,Qu); if(R!=rsOk) return R;

Dev.EndScene();
Dev.Present();

return rsOk;
}






If anyone has time to download the exe, you notice every two or three seconds the block jitters really badly. I reckon that would look awful if it was a whole screen of a moving map and various objects.

Any ideas would be appreciated.

[EDIT]

I've just tried storing the old X and Y of the Block in the physics function before update, then passing the remainder of the accumulator into the Render function and doing:


CResult CGameMode::Render(float Time,CDevice &Dev,CQuadBuffer &Qu)
{
float Alpha=Time/PhysicsDelta;

float x=X*Alpha+Ox*(1.0f-Alpha);
float y=Y*Alpha+Oy*(1.0f-Alpha);

Dev.Clear(Col);

Qu.Begin();
Qu.Add(x,y,40,40,D3DFLOATRECT(),D3DCOLOR_ARGB(255,128,0,0));
Qu.End();

Dev.Draw(Qu);

return rsOk;
}




That does actually make it a hell of a lot smoother, although I have no idea how this would apply to velocity varibles. Would I actually need to perform any alpha blending of velocities, or would it just literally be the positions like above?

Blimey. Surely you can write a Mario style platformer on a modern PC without all this complication?

[EDIT]

It would appear that velocity calculations do not need to be affected, just purely the position you render at each frame. Makes sense I guess.

So I guess I need to come up with a way of wrapping all this horrible maths into an object that all moving objects can contain. Might work.

[Edited by - EasilyConfused on November 29, 2006 2:42:58 PM]

Share this post


Link to post
Share on other sites
You could even consider not interpolating between physics timesteps at all. For a simple sidescroller using sprites, not interpolating should work fine. The interpolation step is used with 3d engines to try to get smoother, more realistic movement out of the 3d models.

Share this post


Link to post
Share on other sites
Quote:
Original post by Vorpy
You could even consider not interpolating between physics timesteps at all. For a simple sidescroller using sprites, not interpolating should work fine. The interpolation step is used with 3d engines to try to get smoother, more realistic movement out of the 3d models.


Well, I was doing that in the first place but that was causing a really bad jitter. I think interpolation is the way forward. I just need to find a way of doing it that will scale up to lots of objects well.

Thanks again for everybody's input.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yup,
the 'jitter' is a Beat Frequency that occurs when every few renders the physics cycle gets an extra step (or loses one) over the render cycles.

Your options include:
-totally disable VSynch for the rendering
-store 2 physics states for every object and calculate an interpolated position that matches up with the exact render time

The first option is easiest, but can lead to ugly 'screen tearing' artifacts


The interpolation option means storing the previous Position of each object, and calculating physics cycles to be 1 cycle ahead of render
so for example:
past physics cycle was at 2000ms, current render is at 2005ms, future physics is at 2030ms
so you have to:
2030-2000=30ms
2005-2000=5ms

inter_ratio =5/30

player_render_position= player_past_pos + inter_ratio*( player_future_pos - player_past_pos )

where player position data is Vectors...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
P.S.

oh, looks like you already figured out that interpolation math.
well, in clarification, Yes you only need to worry about position for the most part
past velocity doesnt matter for the interpolation (you cant exactly 'render' velocity now can you?)
only things that will be rendered matter
ie- position, rotation, character animation(if they're complicated, stuff like blinking probably wont be noticed)

Share this post


Link to post
Share on other sites
Quote:
Original post by Anonymous Poster
P.S.

oh, looks like you already figured out that interpolation math.
well, in clarification, Yes you only need to worry about position for the most part
past velocity doesnt matter for the interpolation (you cant exactly 'render' velocity now can you?)
only things that will be rendered matter
ie- position, rotation, character animation(if they're complicated, stuff like blinking probably wont be noticed)


Cheers for the clarification.

Can't claim to have "figured out" so much as "copied" the interpolation math [smile]. Seems to work though.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this