Jump to content

  • Log In with Google      Sign In   
  • Create Account





Game loops

Posted by Norman Barrows, 08 September 2013 · 628 views

Game loops

render everything, process input, and update everything. that's what games do. this leads to a basic loop like:

while ! quitgame
process_input
update_all
render_all

the order of the calls:
there are only two possible orders for a game loop:
1. input - update - render
2. input - render - update
all other orderings are simply out of phase versions of these two, that start the loop in a different place in the order. IE input-update-render is functionally equivalent to update-render-input once the loop is up and running. its only in the first iteration that there is any difference.

so there are two possible orders, and for each order, three possible places to start the loop, for a total of 6 possible layouts.

so which one is best? well, the difference in where you start the loop is negligible. it only affects the very first frame of the entire game, so who cares?

And it turns out that input, render, and update are all pretty order independent of each other. You just have to call each one every time through the loop (more on that later).

so, it doesn't seem to really matter. and of the six possible orders are fine.

i personally was taught: draw the screen, process input, move everything, which is: render - input - update

so, it looks like you can use any of the six possible orders:

input before update:
render - input - update
input - update - render
update - render - input

input after update:
render - update - input
update - input - render
input - render - update


now, what about de-coupling, IE variable timesteps and all that jazz?

Well it just so happens that my life is full of poorly coupled game loops. not my games - games i play.

You see, i have a passion for submarine simulators. And unfortunately, sub sims tend to have poorly coupled main loops that can interfere with gameplay at the worst possible moment.

ok, lets say we have a "game" that moves a square from the left side of the screen to the right side of the screen over 1 second.
this will be our test case for performing Gedankenexperimenten (thought experiments) about de-coupling game loops.

http://en.wikipedia.org/wiki/Thought_experiment

we'll start with a baseline case:

vsync on. 60Hz refresh rate. update moves the square by (screen_width / 60) pixels each update. fixed timestep, no de-coupling.

First - why decouple?

well, if your frame rate is jittery, de-coupling render and update will smooth things out. so you update based on frame ET.

accelerated time is another reason to decouple - in fact it pretty much requires de-coupling.

making the game run at the same speed on different PCs is the third reason, but that's not the only way to get the same speed on all PCs, and perhaps is not the best way either.

the problem with totally de-coupling render from update occurs when frame times go way high - unplayably high - like > 66 ms per frame (slower than 15 fps). Over the years, i've determined that 15 fps is the slowest a game can go and still be sufficiently responsive to play.
when frame times go high, the amount of update per frame increases drastically. to the user, this gives the perception of the game speeding up in relation to the graphics, just when the graphics are slowing down. worst of both worlds.

to fix this, you have to have an upper limit on how much update you'll do per frame.

lets apply this to the test case.

we modify out test program so update takes a frame ET as a parameter.

in the baseline case, we're at 60 fps, so update gets passed 16ms as its update ET.

in the worst case, we want to lower limit fps to say 15fps (or 20 or 30 or whatever). for 15fps, we're looking at a fame ET of 66ms max.

so we do something like:

if (ET > 66) update(66) else update(ET)

this forces a screen update after 66ms of simulation time, to provide the user with sufficient feedback to continue playing.

in general it appears that the following statements must be true for de-coupling to not have a negative impact on gameplay:

1. render speed >= update speed
2. render speed >= input speed

this gets a little tricky with variable timestep. with variable timestep, render speed must be >= update speed for the minimum playable frametime. so if you decide that 33ms is the slowest playable frametime, then render must run at least once every 33 ms of game time.


now, what about playing with vsync?

well, the video controller only copies data from vidram to the monitor at the refresh rate. So updating vidram more often gets you nothing. if you update vidram at twice the refresh rate, your first update gets overwritten by your second update, then your second update gets copied to the monitor. so turning off vsync and running faster than refresh rate doesn't do much.

now, what about input?

well, you have two issues:
1. missed input
2. unprocessed input.

missed input:
if you use polling for input, its possible to miss an input event that starts and ends between pollings. The answer to this is to use an input event queue. polling is done at a very high frequency so events are not missed. events are added to the event queue. input() processes the event queue. for windows pc development, it just so happens that windows already implements polling and an even queue for you - the windows message queue.

unprocessed input:
when using an event queue, not all games process the entire queue each frame. This is fundamentally wrong. Everything in the queue is user commands that have been issued up to that point in time, so they should all be executed in turn, immediately. leaving commands in the queue is like temporarily ignoring the player's input!


so, looks like our simple loop actually has a lot of considerations:
1. run at the same speed on all pcs
2. smooth animation with jerky framerate
3. render at least once every 66ms (or 33ms, etc) of game game.
4. not miss any input
5. don't leave input unprocessed.

for running at the same speed, there are two basic approaches:
1. variable timestep
2. framerate limiter

variable timestep:
update takes ET as a parameter, and updates the simulation for ET worth of time. unless you set an upper limit for ET of no more than about 66ms, this loop design comes unglued when ET goes high. this loop design, with no ET limit is what most sub sims use. thus, they have a tendancy to come unglued and become unplayable at the worst possible moment. You get a radar contact of a convoy ahead. you charge straight at them at flank speed on the surface in broad daylight. You close to visual range, the escort destroyers spot you and come sharing in for the attack. You order crash dive, and take her down to about 150 feet, and sail right under those destroyers! then you bring it back up to periscope depth. When you up scope, you're in the middle of the convoy, surrounded by big fat freighters and tankers! Tonnage as far as the eye can see! And the destroyers are still back where you submerged, clueless as to your whereabouts. So you start capping off torpedoes. Before you know it, you've got thousands of explosion particles going on. frametimes therefore become unstable. no problem - we have variable timestep! (yeah - right!). So now the simulation is now running faster with respect to update due to high frame ET. that means that all of a sudden those destroyers are moving much more each frame - and they're moving towards you! Then things get really busy and frame ET goes beyond playable. All of a sudden, you're dead! What happened? The destroyers made a depth charge run on you between screen updates! Obviously, killing the player between infrequent screen updates with no chance to react is undesirable at best.

so it looks like variable timestep with no upper limit on ET is a bad thing. if variable ET is used to make the game run at the same speed on different PCs, an upper limit on frame ET seems to be required for playability when the frametime goes high. But its not always bad. In console games, its not uncommon for a publisher to dictate a minimum framerate below which the game can never drop. To meet this challenge the developers must limit on-screen content. As a result ET is pretty much guaranteed to never go way high. So in these cases the upper limit on ET is unnecessary, and therefore usually omitted. but often times its also omitted in PC games where the play is not as staged, is more random, and the developers don't / can't easily control the amount of on-screen content, and the publisher doesn't dictate a minimum framerate. in these cases, the omission is a major design flaw that leads to the game loop coming unglued. with the simulation racing so far ahead of the graphics as to make the game un-playable.

framerate limiter:
this sort of takes the opposite approach from variable timestep. variable timestep speeds up the simulation in relation to render on slower PCs.
by contrast, a framerate limiter works by slowing down the entire simulation on faster PCs. depending on the target framerate, vsync can make a handy built-in framerate limiter. you just turn vsync on, and use a fixed timestep. the game is guaranteed to run at 60 fps (assuming a 60Hz refresh rate) , and to degrade gracefully under load. for slower target framrates such as 30fps, you do something like:

start timer
render
input
update
while (get_ET() < 33) { } // do nothing until ET = 33ms

this gets you everything except smooth animation with a jerky framerate.

but the framerate only gets jerky when the frame time becomes unstable and starts going high. so its only the point between when things start to slow down, and when they become unplayably slow that a variable timestep for smooth animation comes into play.

if your game tends to run at a playable by unsteady framerate, then variable timestep with an upper limit on ET should smooth out the animations some by eliminating temporal aliasing. The upper limit on ET guarantees you render often enough to provide sufficient feedback for the user. of course, even with a limit on ET, render can still slow things down so much as to make the game unplayable.

if your game can run steady at a given framerate, variable timestep is unnecessary. your ET each frame is the same, so your animation each frame is the same, and therefore automatically smooth.

i use this fact to my advantage. i purposely choose a steady framerate i can run, such as 60, 30, 25, 24, 20,or 15 fps (movies run at 24 fps).
then i use a framerate limiter and fixed time step.

this gets me everything with the least amount of hassle, and i'm not trying to make the game run faster than the PC is really capable of doing on a long term steady state basis.

1. runs at the same speed on all pcs -> framerate limiter keeps it from running too fast. slower PCs degrade gracefully.
2. smooth animation with jerky framerate -> no jerky framerate, so no jerky animation.
3. render at least once every 66ms (or 33ms, etc) of game time. -> automatic with fixed timestep of 66ms, 33ms, 16ms, etc.
4. not miss any input -> i typically poll at 15Hz with no problems with missed input. missed input doesn't seem to be a big issue.
5. don't leave input unprocessed.-> since polling works fine, an event queue is unnecessary. no queue = no unprocessed input in the queue.
so overall, it looks like the best approach is to use a framerate limiter, such as vsync, or a timer based limiter if you need a lower limit.

then - if your framerate is unsteady but playable, you can either lower your max fps to a steady framerate (such as from 60fps down to 50, 40, or 30 fps), or add variable timestep with upper limit on ET. variable timestep will let you run faster (and hence smoother) when possible. the upper limit on ET defines the framerate at which render and update couple and de-couple. if you set ET limit to 33ms, render and update are coupled at 30fps and below, and de-coupled above 30fps. When using semi-fixed timestep, and no minimum framerate is mandated, coupling render and update at low frame rates is ABSOLUTELY VITAL to playability when the game slows down. If you use semi-fixed timestep and no minimum framerate, YOUR GAME LOOP WILL COME UNGLUED unless you limit overall ET to ~66ms or less!

all this culminates in one of two basic loop designs (fixed timestep for games with steady framerates, and variable timestep for games with unsteady framerates):

steady framerate, fixed timestep, 60 fps vsync:

render
input
update

or with a timer controlled framerate limiter:

start timer
render
input
update
do
get ET
while ET < minimum_frametime


unsteady framerate, variable timestep, 60fps vsync. 33ms ET limit (couples and de-couples at 30 fps):
start timer
render
input
get ET
if (ET < 33) update(ET) else update (33)

note that i added input into the frame time. input overhead will probably be steady and low, but better safe than sorry! after all it is part of the time that the game spends not updating. to paraphrase a famous quote:

"everything except update generates ET, and update consumes ET."


now, what about de-coupling input?

well input has the same sort of de-coupling issues that update has. in both cases, you're relying on render to tell the user whats happening. this means you have to render at least every 66ms or so (15 fps) to be playable.

i make a lot of simulator and war games. in both types of games, accelerated time is a common game feature. accelerating time requires decoupling the main loop, or reducing render time. reducing render time usually isn't an option. that leaves de-coupling. so, you can go about it two ways: render less often -or- update more often or by a greater amount per update.

well, if you render less often, say every 10th frame, things should run faster, but now you have to wait 10 times a long to get feedback from input (such as scrolling the screen in a RTS title). and when you do get feedback, its for 10 turns worth of input. this breaks the rule of render speed must be >= input speed. input is running at 10x the speed of render, so the user doesn't get feedback on input each frame. a bad thing.
the result is you go to scroll, and it scrolls up to 10 times before you see a change. this makes it unresponsive, and easy to scroll too far.

so having input run faster than render is bad. this means you cant just draw every 10th frame. instead you must update 10 times. this is ok, 'cause you're in accelerated time. lots of stuff is SUPPOSED to happen between screen updates.

so putting it all together:

steady framerate:
start timer
render
input
update
do
get ET
while ET < max ET

steady framerate, accelerated time:
start timer
render
input
update(time_mulitplier)
do
get ET
while ET < max ET

note that time_multiplier works like ET and affects turn rate, movement rate, etc, in update.


unsteady framerate:
start timer
render
input
get ET
if (ET > max ET) update(max ET) else update (ET)



unsteady framerate, w/ accelerated time:
start timer
render
input
get ET
if (ET > max ET) update(max ET* time_multiplier) else update (ET* time_multiplier)

not sure about that last line there, you may be able to get away with something simpler like... well, uh.... maybe you can't ! <g>


so there you have it. the basics of game loops.

i'm both pleased and displeased with the outcome of this investigation.

i'm pleased that variable timestep without accelerated time was one of the possible outcomes. many games use this method. and if it didn't turn up in the final analysis, then it would tend to indicate a flaw in the analysis.

i'm also pleased that an upper limit on ET for variable timestep was part of the results. This seems to be the bit missing from most variable timestep games that causes them to come unglued and blow up when ET goes way high.

even the infamous article "fix your timestep" mentions the fact that ET must never be an unreasonably large value, but for a different reason. There, they are using ET in a physics model which only works for a limited range of input values. They work around large ETs by defining a physics timestep, then consuming ET in physics timestep sized chunks. any remainder is stored until the next update, and is used for tweening graphics. but they do not set an upper limit on overall ET, so while their physics model may still work with high ET values, their game loop itself still comes unglued when ET goes high. this is probably due to the fact that its demonstration code meant to explain how to handle variable timestep in the physics engine only. their game loop doesn't even have input! at any rate, they're not PRIMARILY addressing the issue of degrading gracefully under high ETs. However, they do touch on this point with the topic the "spiral of death" - IE when you don't limit ET, and it takes longer than ET to simulate ET worth of time. This case may be only theoretical. if a game is supposed to run at 60 fps, and has lets say, a 8ms ET for render and input. that leaves 8ms to do 8ms worth of update. i'm not so sure how often (if at all) a REAL game will ever have an update that can't keep up with itself. sure, you may have a 15ms ET, leaving 1ms to do 15ms worth of update, but different ET values just change the multiplication factor, they don't change the algo. so update runs at the same speed irregardless of ET. That means you'd only get the spiral of death if the execution time of update was inherently longer than that of render and update combined. not bloody likely in a real game.


the one thing that displeases me about the outcome of this little analysis is that the conclusion that "all input should be processed in turn and immediately", at first glance, seems to go contrary to "ET based input" as proposed by L Spiro. I'm going to have to think about that one some more. I've noticed that L Spiro tends to know what she's talking about, so i may have missed something there, or perhaps the two concepts are not incompatible upon closer examination.

so , whats the different way to do it?
keep it simple:
fixed timestep. framerate limiter. keep your scene complexity within your max framerate. if things do slow down a bit, you'll degrade gracefully and won't ruin the gameplay experience for your user.

an interesting article i read on game loops pointed out the fact that in a game loop, if the framerate is too low, render is the only part that can give. IE reducing render time by reducing LOD, detail, effects, and clip range is the ONLY way to speed things up (assuming all optimizations have already been done). So if your framerate drops, reducing graphics detail is the only real solution.

recently i've had good luck with automatically adjusting scene complexity based on ET (using it to adjust clip ranges on the fly). This lets me run a pretty rock solid fps under all but the absolute worst conditions.

Important new concepts to come away with:

1. when a minimum framerate is not dictated, and variable/semi-variable timestep is used, an upper limit MUST be placed on overall ET to force screen updates frequently enough to maintain playability. This upper limit is probably no more that 66ms (15 fps) - your tastes may vary - adjust according to your tastes. With today's faster graphics, i'm moving towards a standard of 60 fps steady state and 30 fps minimum. compare that to my original standard from the late 80's of 15 fps steady state and 10 fps minimum for a complex simulation.

2. polling at speeds as low as 15fps is sufficient to avoid missed input.

3. variable/semi-fixed timestep is only required when your game runs at an unsteady but playable framerate.

4. All input available at the time of processing input should be processed.
back to sub sims as an example. Silent Hunter 4 uses an input queue. It also does not process all input available every frame. it appears to consume input at the somewhat unbelievable rate of one command per second. IE the game runs at lets say 30 fps, and the input queue is processed at 1 fps. And commands that counteract each other are not filtered out. so a left followed immediately by a right doesn't result in a right turn, it results in one second of turning left, followed by a right turn. I was taking on a convoy (same battle described earlier). when you empty your forward tubes, you turn the scope around, order all back emergency, and start driving the boat backwards at targets, and use your stern tubes. steering is the tricky part. while still moving forwards, left is still left and right is still right, but once the boat stops and starts to move backwards, the steering reverses. So you're looking at the compass heading and the TBD indicator (torpedo angle on target), trying to figure out if you should turn left or right. And once you figure out which way to turn, is port left, or is starboard now left? As a result you can easily issue commands to turn in the wrong direction. It takes the boat a few seconds to respond, meanwhile your angle on target is getting worse and worse because your not tuning the right way! Straight isn't good enough, you must turn WITH the target to get a firing solution. So in the heat of battle, you start issuing turn orders: Left! No! Right! No! Left! OK, Straight!, No! LEFT! LEFT! LEFT! LEFT damn it! , and they start queuing up. and then they start executing at ONE FPS! by the time the game once again responds to commands in realtime, you've lost your target and must start a new approach. by processing the entire queue this is avoided, as only the last valid commands issued take effect. older commands are automatically overridden by new commands . to do this one would have to use the queue to set some variable to left, right, or straight (for example) with each input, then only process the final result. last command was straight, we go straight! by polling at a reasonable speed (>= 15 fps) and processing input as it occurs, this problem is avoided entirely. no queue is needed. no queue is used. so there's no queue to leave unprocessed events in!

5. 2 and 4 above imply that an input queue is unnecessary in a game!


i think that next time i'll be taking a step back and discussing compiler settings. after all, you need to setup your compiler correctly before you can code. and that's when things start to get VERY different! Posted Image

until then,

Happy coding! Posted Image


LINKS:

fix your timestep:
if you're game runs at an unsteady but playable framerate, you can use the semi-fixed timestep technique as described in this article to eliminate temporal aliasing and smooth out your animations. but you'll need to either mandate a minimum framerate and reduce scene complexity to match, or place a limit on oveall ET of no more than ~66ms (above and beyond the physics stepsize limit of 1/60 in the article), or your game loop will come unglued when ET goes over ~66ms. Note that the examples in the article do not limit overall ET - only the physics step size. So they WILL come unglued when ET goes high!

http://gafferongames.com/game-physics/fix-your-timestep/



ET based input:
L Spiro has proposed a method of ET based input similar to ET based update. Unfortunately i am unable to find the exact link. However i did find the link to the L Spiro engine, if anyone knows the link to L Spiro's ET based input, please add it to the comments!

http://lspiroengine.com/




PARTNERS