In the process of working on Aurora, my Node.js game engine, I found myself in need of an accurate game loop which wouldn’t slowly get more and more off over time, while still remaining predictable and deterministic. Eventually I abandoned it because I realized it was unnecessary (even with a perfectly accurate game loop, there would be latency between the server and clients), so instead the code will be immortalized here.

There is lot of good literature on the Internet about game loops (I’ll include some of the articles I found particularly useful at the end of the post) but nothing that I found quite fit my requirements.

The solution I eventually came to allows for the scheduling of a loop to a tolerance of about 3 ms or less, which appears to be about as good as it gets in JavaScript.

Requirements

Because this loop would be used by my server to compute simulation ticks, and not do any rendering, every update should be regular and deterministic. This means it will always update the game world in increments of 100 ms, meaning the actual time between updates is not used in the updates, but must remain regular so that the server doesn’t get behind schedule over hours or days of running.

This also means that I could not rely on methods using requestAnimationFrame() since there is no browser window or DOM attached to the server.

And finally, I did not want to rely on systems like a blocking while() loop or high speed checks every 5 or 10 ms, with an accumulator. While the latter could work, it’s a waste when your server doesn’t need to render 60 frames per second, and can better spend its time listening for user input. It also felt at odds with “good JavaScript practices.”

The First Attempt

To get an initial benchmark, I first tried the simplest implementation:

// NOTE: Present() is like performance.now() without the browser.
class Engine {
  start() {
    this._lastFrameTime = Present();
    this._running = true;
    setInterval( this._update().bind(this), this._step );
  }

  stop() {
    this._running = false;
  }

  _update() {
    if ( this._running ) {
      const now = Present();
      const delta = now - this._lastFrameTime;
      this._lastFrameTime = now;
      console.log( delta );
      this._systems.forEach( ( system ) => {
        system.update( this._step );
      });
    }
  }
}

This worked surprisingly well. It was regular and deterministic, executing at a regular interval. The problem? That interval was always about 5 ms more than the intended step size. 5 ms is hardly noticeable, but if the server was left to run for extended periods of time, with the simulation updating by a flat 100 ms every 104.8 ms, the lag would add up. After 1 second the server would be about 50 ms behind, and after 1 minute it would be a full 3 seconds behind schedule.

Of course, setting the interval timer to 95 ms pretty much fixed this, but that’s only because the execution time of the logic happened to be about 5 ms. In practice it would likely vary depending on simulation load and so hard coding the interval to be this._step - 5 was not ideal.

The Second Attempt

After doing some research, I decided to replace setInterval() with setTimeout() (because dynamic intervals are not supported with setInterval()) and set each timeout to be the ideal step minus whatever lag has occurred. In code that looked like:

// NOTE: Present() is like performance.now() without the browser.
class Engine {
  start() {
    this._lastFrameTime = Present();
    this._running = true;
    function tick() {
      // Update the logic:
      this._update();
      
      // Update the timing:
      const now = Present();
      const delta = now - this._lastFrameTime;
      console.log( delta );
      const drift = delta - this._step;
      this._lastFrameTime = now;
      setTimeout( tick.bind( this ), this._step - drift );
    }
    // See note below about why the first run uses setTimeout().
    setTimeout( tick.bind( this ), this._step );
  }

  stop() {
    this._running = false;
  }

  _update() {
    if ( this._running ) {            
      this._systems.forEach( ( system ) => {
        system.update( this._step );
      });
    }
  }
}

This approach did work, once I figured out an infuriating bug caused by first running tick() without a timeout. Doing so caused the first delta to be about 2 ms, meaning the drift was -98 ms, meaning the next loop ran 198 ms later.

The results of the code above ensure that after the first step tick completes with a delta of about 105 ms, the next tick completes with a delta of about 95 seconds to compensate.

At this point, the system was working perfectly well-enough to use for the application I wanted. However, it still bothered me that rather than simply scheduling the tick every 100 ms, every tick was off the target, but alternating by the same amount. Missing the target by the same distance to the left and right is not a bullseye, so I tried to improve one more time.

The Final Attempt & Success

To avoid over compensating and instead reach a "stable" tick time, I decided to use a floating average of deltas over the last 5 (initially 10 but 5 worked) ticks. The resulting code is:

// NOTE: Present() is like performance.now() without the browser.
class Engine {
  start() {
    this._lastFrameTime = Present();
    this._running = true;
    function tick() {
      // Update the logic:
      this._update();
      
      // Update the timing:
      const now = Present();
      const delta = now - this._lastFrameTime;
      this._lastFrameTime = now;
      if ( this._deltas.length >= 5 ) {
        this._deltas.shift();
      }
      this._deltas.push( delta );
      const average = this._deltas.reduce( ( sum, a ) => {
        return sum + a;
      }, 0 ) / ( this._deltas.length || 1 );
      const drift = average * 1.05 - this._step;
      
      setTimeout( tick.bind( this ), this._step - drift );
    }
    // See note below about why the first run uses setTimeout().
    setTimeout( tick.bind( this ), this._step );
  }

  stop() {
    this._running = false;
  }

  _update() {
    if ( this._running ) {            
      this._systems.forEach( ( system ) => {
        system.update( this._step );
      });
    }
  }
}

This version looks almost like the second attempt, except that we use a floating average from the last 5 updates to compensate for timing inaccuracies.

Calculating the Floating Average

First, we remove the first delta from the array of past deltas if there are at least 5, then add the newest delta to the end. You could use a different number, but I got very good results using only 5 and adding more only increases boilerplate computation time when the engine could be handling user intput or doing simulation. Next, we average all the deltas in the array, and then remove the base step size to figure out how much to compensate by.

You’ll also notice a random looking 1.05 in there. Surprise! Despite my best efforts, there’s still one magic hard-coded constant in the mix. It dramatically improves results though.

Results

Throughout the process I had been looking high resolution time stamps for each tick to ensure they were happening every 100 ms. This is the output of the code above, without the magic 1.05 constant:

[16:21:55.431] Delta: 103 ms
[16:21:55.533] Delta: 102 ms
[16:21:55.634] Delta: 101 ms
[16:21:55.737] Delta: 103 ms
[16:21:55.840] Delta: 103 ms
[16:21:55.941] Delta: 101 ms
[16:21:56.042] Delta: 102 ms
[16:21:56.144] Delta: 102 ms
[16:21:56.245] Delta: 101 ms
[16:21:56.347] Delta: 102 ms
[16:21:56.448] Delta: 101 ms

This is not bad at all. Over one second, the total drift has been reduced from 50 ms (when using setInterval()) to 17 ms, so a more than 60% reduction.

Using the little constant though, this can be improved to ±3 ms:

[16:40:09.252] Delta:  99 ms
[16:40:09.350] Delta:  98 ms
[16:40:09.449] Delta:  99 ms
[16:40:09.550] Delta: 102 ms
[16:40:09.649] Delta:  99 ms
[16:40:09.750] Delta: 101 ms
[16:40:09.849] Delta: 100 ms
[16:40:09.950] Delta: 101 ms
[16:40:10.050] Delta: 100 ms
[16:40:10.150] Delta: 100 ms
[16:40:10.249] Delta:  99 ms

The above works out to an average of 99.8 ms. Of course, this may eventually get off over long durations, but it would seem that this is really as good as it gets in JavaScript.

So, why would you need this over simply using setInterval()? I’m not sure. It turns out I didn’t really either, but it’s a useful exercise in JavaScript watch-building. Also, while there is some useful information in the references section below, most information on JavaScript gameloops which is available on the Internet focuses on using requestAnimationFrame(). The approach above could be a good solution if you need to build a timer or gameloop that runs at a regular interval without having access to build-in methods like requestAnimationFrame().


References