Game Loop: Fixed timestep, Variable rendering

[d13]

Hello!

 

I'm trying to implement a game loop with a fixed time step and variable rendering, based on ideas from these two articles:

 

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

http://gameprogrammingpatterns.com/game-loop.html

 

I've got a prototype here that *seems* to work:

 

http://jsbin.com/ditad/7/edit?js,output

 

Can anyone out there tell me if it's actually correct, or is it doing some really bad or wrong that I've missed?

 

Here's the game loop:

    //Set the frame ratevar fps = 60,    //Get the start time    start = Date.now(),    //Set the frame duration in milliseconds    frameDuration = 1000 / fps,    //Initialize the lag offset    lag = 0;//Start the game loopgameLoop();function gameLoop() {  requestAnimationFrame(gameLoop, canvas);    //Calcuate the time that has elapsed since the last frame  var current = Date.now();  var elapsed = current - start;  start = current;  //Add the elapsed time to the lag counter  lag += elapsed;    //Update the frame if the lag counter is greater than or  //equal to the frame duration  while (lag >= frameDuration){      //Update the logic    update();    //Reduce the lag counter by the frame duration    lag -= frameDuration;  }  //Calculate the lag offset and use it to render the sprites  var lagOffset = lag / frameDuration;  render(lagOffset);}

The last line above calls the `render` function and sends it the `lagOffset` amount.

The `render ` function loops through all the sprites and calls each sprite's own `render` method.

 

function render(lagOffset) {  ctx.clearRect(0, 0, canvas.width, canvas.height);  sprites.forEach(function(sprite){    ctx.save();    //Call the sprite's `render` method and feed it the    //canvas context and lagOffset    sprite.render(ctx, lagOffset);    ctx.restore();  });}

The sprites  `render` method uses the `lagOffset` amount to interpolate the correct screen position.

This is is the part that I'm least sure about, so I'd really appreciate it if anyone can tell me whether I'm calculating the interpolation correctly

o.render = function(ctx, lagOffset) {  //Use the `lagOffset` and the sprite's previous x/y positions to  //calculate the new interpolated x/y positions  o.renderX = (o.x - o.oldX) * lagOffset + o.oldX;  o.renderY = (o.y - o.oldY) * lagOffset + o.oldY;      //Render the sprite  ctx.strokeStyle = o.strokeStyle;  ctx.lineWidth = o.lineWidth;  ctx.fillStyle = o.fillStyle;  //Use the new interpolated `renderX` and `renderY` values to position the sprite on screen  ctx.translate(    o.renderX + (o.width / 2),    o.renderY + (o.height / 2)  );  ctx.beginPath();  ctx.rect(-o.width / 2, -o.height / 2, o.width, o.height);  ctx.stroke();  ctx.fill();      //Capture the sprite's current positions to use as   //the previous position on the next frame  o.oldX = o.x;  o.oldY = o.y;};

Any feedback welcome

[alex_h]

For comparison here's my implementation of the locked timestep update loop, based on the same article. Mine runs off setInterval, I have separate render loop running of RAF which simply calls draw on the PIXI stage.

utils.RunLoop = function(){	this.boundGameLoop = null;	this.gameLoopId = -1;//interval id	this.interval = 1000/30;//30 fps	this.accumulator = 0;        this.currentTime = 0;//Date.now()	//	this.gameLoop = function(){        var newTime = Date.now();        var elapsed = newTime - this.currentTime;        this.currentTime = newTime;        this.accumulator += elapsed;	    //use that accumulator system for processing time!	    var chunk = this.interval;	    while(this.accumulator > chunk){	        this.accumulator -= chunk;	        this.updateGame(chunk);	    }	};	this.boundGameLoop = this.gameLoop.bind(this);	this.start = function(){		clearInterval(this.gameLoopId);		this.currentTime = Date.now();		this.gameLoopId = setInterval(this.boundGameLoop, this.interval);	};	this.stop = function(){		clearInterval(this.gameLoopId);	};	//override this probably	this.updateGame = function(p_time){            // loop through all objects and call update on them, passing through the time value	}};

You shouldn't need to consider any 'lagOffset' anywhere else in your code if you use this approach, the whole point is that the time step is always constant. Therefore you should keep the rendering out of this loop and restrict it to dealing with game logic. Have a separate requestAnimationFrame loop that just deals with drawing to canvas.

[Deban]

Interesting.

 

d13:

For what I have read, your interpolation isn't correct. I may be wrong, but I think what you are supposed to interpolate is the position where it should theoretically be if it continue it's current trajectory. Of course it will be a guess and as you don't actually know if it stop or even collide with something.

 

With your code it will be:

    o.renderX = o.x + o.vx * lagOffset;    o.renderY = o.y + o.vy * lagOffset;    //o.renderX = (o.x - o.oldX) * lagOffset + o.oldX;    //o.renderY = (o.y - o.oldY) * lagOffset + o.oldY;

Here is the clone of your prototype. To me the output look exactly the same (but to be honest, even without the offset it looks the same to me).

 

Your loop looks perfect to me.

 

 

alex_h:

The problem with set interval is that it's fixed and that it doesn't care if you are doing something at that time, it will stack the new call.

Also the time step is not constant, the call to the function is constant but in reality it changes according to different delays.

 

Let's say you game couldn't run at 30 fps, it run at 28 which is not that of a big deal.

At 33 milliseconds the first function is called, it takes 36 ms to finish running.

The next update should be at 66 ms, but because your update took more time, it's run at 69. Set interval will try to call the update again at 99 and not 33 ms after the last one finished. And repeat again and again. 

 

    0             33             66   69          99        105

|Start|          |      update      ||     update         |

 

 

Eventually you will end with a lot of callbacks that you aren't able to process because you didn't finish the last one. This will empty batteries, fill the memory and slow down your code even more.

 

One possible solution would be to use setTimeout with the difference of the remaining times, or if there isn't any, at least don't stack the calls. Pixi uses setTimeout as a fall back if RAF doesn't exist.

But it's far from optimal, for example the times aren't usually respected.

 

And a last thing, you are rendering in vain. If your don't offset anything, you are rendering 2 times the same frame (if your RAF is 60 FPS and your update 30 FPS as it seams in the example).

The idea of rendering more than updating is that rendering contains a little bit of logic, just enough to make another frame and make it look smooth. Like for example extrapolating positions, or advancing bone animations.

 

 

 

 

EDIT: OH! btw d13, when you change your tab the RAF isn't call and that mean you can accumulate a LOT of lag that isn't really lag. I recommend doing something like Phaser, a maximum possible lag:

  if (elapsed > 1000) elapsed = frameDuration;

I used 1 second because RAF has a minimum call of 1 FPS.

Here is the full code.

[alex_h]

Fair enough, I'm just using setInterval because I want to keep the update loop independent of the render loop so can't tie it into the RAF. I've no idea why I put 30fps for the interval, I think that must have been a mistake! It should have been 60. Thanks for drawing my attention to the implications of using setInterval, I'll consider using setTimeout in future.

[Deban]

Remember that setTimeout has a minimum time of 4ms in HTML5 and in some browsers before 2010 it's 10 ms (source).

 

And good luck.

[d13]

    o.renderX = o.x + o.vx * lagOffset;    o.renderY = o.y + o.vy * lagOffset;    //o.renderX = (o.x - o.oldX) * lagOffset + o.oldX;    //o.renderY = (o.y - o.oldY) * lagOffset + o.oldY;

Thanks so much Deban for your extremely detailed and thoughtful answer!

 

I have one outstanding question about the interpolation (in the above quote) that I have been unable to find an answer for:

 

Should the current position of the sprite be used for interpolation, or its previous position?

My understanding is that using the current position is extrapolation (moving the sprite forward in time) and that using the previous position is interpolation (moving the sprite back in time.) I learnt that from this article, but I don't know how correct it is:

 

http://gamedev.stackexchange.com/questions/75474/interpolation-using-a-sprites-previous-frame-and-current-frame

 

Antriel suggests the previous positions should be used in this thread:

http://www.html5gamedevs.com/topic/7735-myths-and-realities-of-canvas-javascript-performance/

[d13]

Hi everyone,

 

I finally managed to "solve" this problem.

Here's the latest version:

 

http://jsbin.com/janibo/1/edit

 

It uses interpolation (the sprite's previous position plus its calculated velocity) to work out the rendered position.

Extrapolation (the sprite's current position plus its velocity) was giving me off-by-one errors when a sprite's position was changed due to collisions.

 

Using interpolation is smooth and accurate at any framerate.

The trick to making it work is that you need to capture the sprite's previous position in the logic `update` function *before* you calculate its new position in the current frame.

function update () {  sprite.previousX = sprite.x;  sprite.previousY = sprite.y;  //... then calculate the sprite's new position for this current frame...}

Then in the `render` function you interpolate the sprite's rendered position using this formula:

o.renderX = (o.x - o.previousX) * lagOffset + o.previousX;o.renderY = (o.y - o.previousY) * lagOffset + o.previousY;

That's an old trick from Verlet Integration where you dynamically calculate the sprite's velocity based on the difference between its previous and current position.

That was the key to getting interpolation properly working (thanks Antriel!!)

 

Here's how it's implemented in the sprite's `render` function in the working example linked above :

if (o.previousX) {  o.renderX = (o.x - o.previousX) * lagOffset + o.previousX;} else {  o.renderX = o.x;}if (o.previousY) {  o.renderY = (o.y - o.previousY) * lagOffset + o.previousY;} else {  o.renderY = o.y;}//Render the spritectx.translate(  o.renderX + (o.width / 2),  o.renderY + (o.height / 2))

If you have lots of sprites, you can capture all their previousX and previousY positions in a function that runs each frame *just before the `update` function*:

function capturePreviousPositions(sprites) {  sprites.forEach(function(sprite) {    sprite.previousX = sprite.x;    sprite.previousY = sprite.y;  });}

Here's the final game loop that implements this:

function gameLoop(timestamp) {  requestAnimationFrame(gameLoop);  //Calcuate the time that has elapsed since the last frame  if (!timestamp) timestamp = 0;  var elapsed = timestamp - previous;  //Optionally correct any unexpected huge gaps in the elapsed time  if (elapsed > 1000) elapsed = frameDuration;  //Add the elapsed time to the lag counter  lag += elapsed;    //Update the frame if the lag counter is greater than or  //equal to the frame duration  while (lag >= frameDuration) {      //Capture the sprites' previous positions    capturePreviousPositions(sprites);    //Update the logic    update();    //Reduce the lag counter by the frame duration    lag -= frameDuration;  }  //Calculate the lag offset. This tells us how far  //we are into the next frame  var lagOffset = lag / frameDuration;  //Render the sprites using the `lagOffset` to  //extrapolate the sprites' positions  render(lagOffset);  //Capture the current time to be used as the previous  //time in the next frame  previous = timestamp;}

A huge thanks to Deban and Antriel, I couldn't have figured this out without your help!