Frame-rate independance and Mario-style jumping
Author
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.
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)
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.
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.
Author
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]
[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]
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 loopvoid 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)}
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...
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...
Author
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.
Thanks everyone, especially to Mo6eB, whose suggestion I so hastily dismissed in the first place.
This is a common problem caused by using code like this:
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.
v += a * t d += v * t v = v0 + at d = d0 + v0t + ½at2 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.
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.
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.
position += velocity * deltaTime + acceleration * (deltaTime*deltaTime)/2.0f;
velocity += acceleration * deltaTime;
That should do it for ya.
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
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
