next »

[cmspice]

So now that I'm actually working on a game, things like framerate dependence have suddenly become relevant to me. I originally thought framerate dependence (FRD) (i.e. when update cycles are fixed -> 30 fps = 30 updates a second) was kinda stupid but after working on a framerate independent (FRI) engine (i.e. engine updates as many times as it can in a second) I realized  that an FRI engine has no uniformity in the updates. A set of inputs that work a certain way the first time might not work the same way the second time, especially when framerates start to drop. This destroys the precision that can be achieved in a lot of 2d games. Moreover, this would be inappropriate for something like a fighting game where the difference between comboing or not can be as small as one frame.

So I'm asking for people's experience and opinions on FRI and FRD and maybe how you go about implementing them. Is there a way to achieve the precision of FRD in something that's FRI. What do you do when an FRD game when it updates slower than it can render (frameskipping?).

[moi]

Either you use FRD if you don't want to be bothered with the technicalities.
Otherwise, with FRI, it's pretty obvious. You have to include a variable to hold the elapsed time since last update, then scale all movements and time based processes according to this.
It can be very tricky if you didn't build the engine around that from the start.
Also try to ignore elapsed time values that are to small (or negative) or too big (too much time between updates). I just set the elapsed time to 0 so nothing happens (prevents stuff like player jumping through obstacles).
Also you should include a few wait cycles to prevent your engine from abusing the CPU from the rear area.

If I had to start again I'd probably Use FRD (fixed cycles).

[mildmojo]

I've only built FRI engines because it's the easiest way for me to ensure consistent gameplay with variable framerates across a variety of hardware (and I'm new to game programming)...  Measure the time since the last update, feed that into the update routines for all game objects.  Time becomes your unit of measure for everything.

I guess if your framerate dropped too low, you might not be able to properly execute combos in a fighting game if the button timing is tight.

I'm interested to hear about dealing with an FRD system when an update cycle takes too long, too.

[Farbs]

I usually use FRI, but that's mostly out of habit. I love the way a game feels at 100fps, and in FRD systems that's generally not viable.

Fighting games are an area where I'd go FRD though. Anything that needs consistent animation playback over as few as 1-2 frames really shouldn't be FRI.

[ஒழுக்கின்மை (Paul Eres)]

I've only used set frame rates, although I did make a game where the player could choose between 30 fps and 60 fps (I simply doubled the speed of everything depending on which was chosen).

I suspect having a set frame rate is much easier, especially for simple games that don't tax hardware that much. Most computers nowadays can get 60 fps for most 2D games, so I suspect variable frame rate is more useful for 3D games.

I believe some of cactus's games even use a 120 fps fixed rate, but I think that's kind of risky because you can't really be as sure that someone's computer will be able to run even simple Game Maker games at 120 fps as you can be with 60 fps or 30 fps.

[cpets]

I don't think it's necessary to go all the way to either extreme. You can run game logic at a fixed rate to get all the benefits of simplicity and predictability while still running display logic at whatever rate the hardware can support. To make this useful, interpolate between two logic states when the display rate exceeds the logic rate. For things like movement, a simple linear interpolation gives great results.

[deadeye]

I've only built FRI engines because it's the easiest way for me to ensure consistent gameplay with variable framerates across a variety of hardware (and I'm new to game programming)...  Measure the time since the last update, feed that into the update routines for all game objects.  Time becomes your unit of measure for everything.

I guess if your framerate dropped too low, you might not be able to properly execute combos in a fighting game if the button timing is tight.

Yeah, if the framerate drops unexpectedly there can be problems with things like collision.

Say if you had two small objects on a collision course, each moving 200px/s * timedelta.  At a framerate of 60fps you get a .0166 timedelta which means 3.32px per frame, but if the framerate crashes unexpectedly for whatever reason, say to 20fps, then suddenly they're moving 10px/frame and if the objects are too small they might just pass each other over.

You can work around it but it's something you have to watch for.

[Zaphos]

I've only built FRI engines because it's the easiest way for me to ensure consistent gameplay with variable framerates across a variety of hardware (and I'm new to game programming)...  Measure the time since the last update, feed that into the update routines for all game objects.  Time becomes your unit of measure for everything.

This is harder to keep consistent if you have movement with acceleration, especially non-constant acceleration.  A classic problem is a platformer with hard jumps that become impossible on either slower or faster computers, because they use basic euler integration to apply the acceleration and use the velocity from one end of the time step instead of the middle (ie: pos += v*t; v += g*t).  If you have varying acceleration (for example to model a spring) this problem is even more obnoxious.

If you use a fixed time step, it doesn't matter so much what integration you use -- it'll be consistent because all computers run the exact same logic code.

Also, the fixed update is not much more complex to implement ... here's some hopefully convincing pseudocode:

Code:

while (timeElapsedSinceLastUpdate() > fixedTimeForAFrame)
{
   DoLogicWithTimeStep(fixedTimeForAFrame);
   SubtractFromTimeElapsed(fixedTimeForAFrame);
}

instead of:

Code:

DoLogicWithTimeStep(timeElapsedSinceLastUpdate());

I'm interested to hear about dealing with an FRD system when an update cycle takes too long, too.

You just don't render some frames in this case (ie "frameskip") while still doing the logic.  People also often limit the number of renders they can skip, which is equivalent to limiting the size of a time step in FRI.

I don't think it's necessary to go all the way to either extreme. You can run game logic at a fixed rate to get all the benefits of simplicity and predictability while still running display logic at whatever rate the hardware can support. To make this useful, interpolate between two logic states when the display rate exceeds the logic rate. For things like movement, a simple linear interpolation gives great results.

This can be good, although then your logic must 'lag' one frame behind in some sense, so that you're interpolating between two known values.

Edit: Also, I should mention that in terms of visual fidelity, FRI can match the refresh rate of the monitor, which is nice.
And if you want something to be as precise as FRD in an FRI system, you can try implementing it as a mini version of the loop I've listed above -- within your update code, instead of scaling the movement by the real timestep t normally, take a fixed timestep f and apply the movement for that fixed timestep floor(t/f) times, making a note of the leftovers so you can make up for them on the next update.

[mildmojo]

within your update code, instead of scaling the movement by the real timestep t normally, take a fixed timestep f and apply the movement for that fixed timestep floor(t/f) times, making a note of the leftovers so you can make up for them on the next update.

I realized after I posted that this is sort of what I'm doing.  I've been using a third-party physics engine that's stepped X times per frame at a fixed time step, and that X is scaled up toward a fixed limit as the framerate goes down.  I'm using time mainly for effects and HUD animations.  So I was mistaken.  I'm using a FRD/FRI hybrid.

[muku]

This is harder to keep consistent if you have movement with acceleration, especially non-constant acceleration.  A classic problem is a platformer with hard jumps that become impossible on either slower or faster computers, because they use basic euler integration to apply the acceleration and use the velocity from one end of the time step instead of the middle (ie: pos += v*t; v += g*t).

One should mention that there is an integration formula for constant acceleration which is exact for any stepsize; see here. I would suppose that that is good enough for platformers. But you are of course right that once you start doing "real" physics, the issues get more complex. (Although in that case you can't use an Euler integrator anyway and have to use Runge-Kutta integration.)

Also, the fixed update is not much more complex to implement ... here's some hopefully convincing pseudocode:

Code:

while (timeElapsedSinceLastUpdate() > fixedTimeForAFrame)
{
   DoLogicWithTimeStep(fixedTimeForAFrame);
   SubtractFromTimeElapsed(fixedTimeForAFrame);
}

The problem I could see here is that if your actual framerate is e.g. just a bit higher than your update framerate, you would get unsightly jumps every few frames (whenever the leftover time accumulates to more than one update frame). But I don't know whether this is an issue in reality; perhaps it can be avoided by having the fixed frame time sufficiently small, though then you need more CPU because you have to run more logic cycles per frame...

Do you have practical experience with this model and can comment on these worries?

I personally usually go FRI (though limiting the maximum update timestep to avoid issues with very large update times). Though another thing I also do is limiting the maximum framerate by judiciously placed sleep() calls, because everything above 100fps or so is just useless burning of CPU cycles.

[Hajo]

At a framerate of 60fps you get a .0166 timedelta which means 3.32px per frame, but if the framerate crashes unexpectedly for whatever reason, say to 20fps, then suddenly they're moving 10px/frame and if the objects are too small they might just pass each other over.

You can work around it but it's something you have to watch for.

I loved the way one could warp through planets in Elite II by suddenly switching to time lapse factor 10000 just before crashing on the surface.

Seriously, games should do collision detection on a finer time scale than screen updates if movement vectors get too large.

[Zaphos]

One should mention that there is an integration formula for constant acceleration which is exact for any stepsize; see here. I would suppose that that is good enough for platformers. But you are of course right that once you start doing "real" physics, the issues get more complex. (Although in that case you can't use an Euler integrator anyway and have to use Runge-Kutta integration.)

In that post I also mentioned taking the velocity at the midpoint instead of an endpoint, which is also exact for constant acceleration.  But I assume people figure out the basic Euler thing first, simply because that's the first thing I learned as a young kid implementing a basic platformer.
You don't have to use runge-kutta for many instance of game physics which are more complex than constant acceleration; for example see http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml
(And Euler integration gets used a lot in practice I think ... also, backwards Euler ... also horrible hackish things that probably don't even have names)

Of course you also must worry a lot about "non constant acceleration" in the form of collisions ... if the timesteps aren't aligned to let you do collision detection at the apex of your jump, and you need to reach that to make a jump, then for a lot of collision handling methods this will also make the player miss the jump and be sad.  This sort of issue is especially frustrating to debug because it will tend to not appear on a computer that is fast enough and has vsync working, so it might show up in feedback as just a few people complaining about an issue that you can't reproduce.

The problem I could see here is that if your actual framerate is e.g. just a bit higher than your update framerate, you would get unsightly jumps every few frames (whenever the leftover time accumulates to more than one update frame). But I don't know whether this is an issue in reality; perhaps it can be avoided by having the fixed frame time sufficiently small, though then you need more CPU because you have to run more logic cycles per frame...

Do you have practical experience with this model and can comment on these worries?

Ah, that reminds me that I forgot a detail -- if you get to that logic update call and you don't have to do a logic update yet, you should yield to the OS or something until it's time to do the logic update.  So if your framerate is slightly faster than the fixed rate, then you just a bit of spare time to yield to the OS.
Unless the frame rate doesn't divide into the refresh rate and you properly vsync; then you have some regular glitch like you mentioned.  You also see this if your actual framerate is just a bit lower than your fixed framerate.  The alternatives are running the game at the wrong rate or using a FRI scheme.  So yes, it is problematic.  But it's the same for all FRD schemes, so ...

As far as practical experience -- I typically use a similar system for my games, though I implement it in allegro with a logic time ticking up automatically so the code is slightly different ( see http://alleg.sourceforge.net/faq.html#How_can_I_make_my_game_run_at_the_same_speed_on_any_computer_ ).  I don't really notice / mind the issues, but then I'm not very sensitive about this sort of thing.

This also reminds me, Shawn Hargreaves had a post about how XNA does it:
http://blogs.msdn.com/shawnhar/archive/2007/07/25/understanding-gametime.aspx

[muku]

One should mention that there is an integration formula for constant acceleration which is exact for any stepsize; see here. I would suppose that that is good enough for platformers. But you are of course right that once you start doing "real" physics, the issues get more complex. (Although in that case you can't use an Euler integrator anyway and have to use Runge-Kutta integration.)

In that post I also mentioned taking the velocity at the midpoint instead of an endpoint, which is also exact for constant acceleration.

Yes, that's exactly what I was talking about. I sort of missed that remark in your post.

You don't have to use runge-kutta for many instance of game physics which are more complex than constant acceleration; for example see http://www.gamasutra.com/resource_guide/20030121/jacobson_01.shtml

Ah yes, Verlet integration. It's fun to play around with and good for individual effects, but I have my doubts whether it would work as the basis of a general physics engine for a game.

(And Euler integration gets used a lot in practice I think ... also, backwards Euler ... also horrible hackish things that probably don't even have names)

You really can't use forward Euler once you start doing nontrivial physics. Things will blow up in the most horrible ways, besides requiring ridiculously small timesteps. Backward Euler is stable, yes, but it isn't all that accurate, and the biggest problem is that it is an implicit method, meaning you have to solve an equation system at every step which tends to be sort of annoying. So, seeing as classical RK4 is pretty easy to implement compared to backward Euler and it's much more accurate, I'd say it's usually a good choice.

Of course you also must worry a lot about "non constant acceleration" in the form of collisions ... if the timesteps aren't aligned to let you do collision detection at the apex of your jump, and you need to reach that to make a jump, then for a lot of collision handling methods this will also make the player miss the jump and be sad.  This sort of issue is especially frustrating to debug because it will tend to not appear on a computer that is fast enough and has vsync working, so it might show up in feedback as just a few people complaining about an issue that you can't reproduce.

Good point. That definitely favors fixed logic timesteps.

[Kekskiller]

I mix FRI and FRD frequently. This can by done using threads:
Thread A: Update objects every timestep, fill on-screen object list.
Thread B: Render as frequently as possible the object list, wait a bit if render time was shorter than the timedelta for rendering.

Otherwise, I like FRD games, because its possible to cheat a bit on slower PCs...

[mildmojo]

Thread A: Update objects every timestep, fill on-screen object list.
Thread B: Render as frequently as possible the object list, wait a bit if render time was shorter than the timedelta for rendering.

Is this just a matter of having each thread lock the shared game state while it's reading/writing?  Does the update thread operate on a copy of the game state until it's finished with a timestep to make the game state more available to the render thread?  I'm imagining a case where the render thread has to wait for the update thread to finish a timestep before it can draw a frame.

[Decipher]

Ah beautiful, time-based movement!

In Demoscene instead of taking the delta of the time between the two consecutive frames we rather feed the time itself to our functions. This way it becomes more like: "We want this to happen in 2 seconds no matter how many frames it skips", as the visuals must be in sync with the music. This approach can be quite useful aswell if someone would like to make a game where synchronization with certain realtime based events (such as a music playing) is required.

[Zaphos]

Ah yes, Verlet integration. It's fun to play around with and good for individual effects, but I have my doubts whether it would work as the basis of a general physics engine for a game.

I don't know what you mean by a general physics engine, really, but the article I linked was describing its use in multiple parts of hitman, which is a real game sort of.  I've only used it on trivial examples though.

You really can't use forward Euler once you start doing nontrivial physics. Things will blow up in the most horrible ways, besides requiring ridiculously small timesteps. Backward Euler is stable, yes, but it isn't all that accurate, and the biggest problem is that it is an implicit method, meaning you have to solve an equation system at every step which tends to be sort of annoying. So, seeing as classical RK4 is pretty easy to implement compared to backward Euler and it's much more accurate, I'd say it's usually a good choice.

Edit: er, yeah, I think I was confused about some things 
But if you're more concerned about stability than accuracy, and have a fixed time budget to compute physics, backwards euler makes some sense?  And I was told at some point that forwards is actually used in some games for cloth that's just a visual effect and not done very well -- like those sports games where the cloth floats magically like a foot above where the character's actual shoulders are.

I mix FRI and FRD frequently. This can by done using threads:
Thread A: Update objects every timestep, fill on-screen object list.
Thread B: Render as frequently as possible the object list, wait a bit if render time was shorter than the timedelta for rendering.

Otherwise, I like FRD games, because its possible to cheat a bit on slower PCs...

This sounds like what I've just been calling FRD -- a locked update rate with optional frame skipping?  I don't really see the need to introduce threads for it, but if you want them anyway then this makes sense.

[Kekskiller]

Yeah, thats a little problem. Thread A has the game object list and Thread B has a list with sprite objects to render. So the sprite list is locked by Thread A for a very short time and gets interrupted very rarely, while the real game objects can be calculated. Thread A calculates the sprite list update if neccessary, only. And even this little interrupt can be skipped by waiting until the sprite isn't locked anymore or timedelta/2 has been reached.

It works quite good, maybe it's not very stable with a massive number of objects. It would work with 2D only (obvious).

[muku]

Ah yes, Verlet integration. It's fun to play around with and good for individual effects, but I have my doubts whether it would work as the basis of a general physics engine for a game.

I don't know what you mean by a general physics engine, really, but the article I linked was describing its use in multiple parts of hitman, which is a real game sort of.  I've only used it on trivial examples though.

Yeah, me too, so I'm really in no position to comment on this, but... what I meant is that it seems they used this stuff mainly for ragdoll physics. That's fine because that's an isolated effect, you have some static geometry and you have these couple of ragdoll particles which collide with them. Simple. As soon as you try simulating the physics of your entire game world with Verlet, you get a lot of interlocking constraints, and you have to solve for them all with some Gauss-Seidel relaxation or whatever, and I can see that getting messy. But, as I said, I don't really know, I'm just theorizing here.

Yeah, thats a little problem. Thread A has the game object list and Thread B has a list with sprite objects to render. So the sprite list is locked by Thread A for a very short time and gets interrupted very rarely, while the real game objects can be calculated. Thread A calculates the sprite list update if neccessary, only. And even this little interrupt can be skipped by waiting until the sprite isn't locked anymore or timedelta/2 has been reached.

Personally I'm doubtful about the advantages of using threads here too. Certainly you don't want to render the same sprite list more than once, so you'll have to put the rendering thread to sleep anyway while waiting for the new list, and then you get all these synchronization headaches, and blargh. The only advantage I see is utilizing multicore CPUs.

That said, couldn't you use something akin to double buffering, where the update thread modifies one copy of the sprite list while the rendering thread renders the other one, and only when the update thread is done does it lock the global sprite list pointer and redirect it to its new version?

It would work with 2D only (obvious).

Why? It's not obvious to me.

[Zaphos]

Yeah, me too, so I'm really in no position to comment on this, but... what I meant is that it seems they used this stuff mainly for ragdoll physics. That's fine because that's an isolated effect, you have some static geometry and you have these couple of ragdoll particles which collide with them. Simple. As soon as you try simulating the physics of your entire game world with Verlet, you get a lot of interlocking constraints, and you have to solve for them all with some Gauss-Seidel relaxation or whatever, and I can see that getting messy. But, as I said, I don't really know, I'm just theorizing here.

I see ... yeah, I think you're correct, although it's probably not too large a problem for most games because they don't simulate their entire world in a consistent way in the first place.