Multiplayer Platformer Log #5 – Entity Interpolation

June 30, 2017

In the third log we made the server authoritative and implemented client-side prediction. Now is the time to add other players and properly implement entity interpolation.

Entity Interpolation In General

The principle is pretty simple. Server sends updates containing positions of all entities (other players). Client waits a few updates before moving the entity while interpolating between the individual updates.

As an example, if server sends updates every 100 ms, client can wait until it receives 3rd update (i.e. 200 ms since the first) and then starts moving the entity, while interpolating between the states. Code for interpolation is very simple:

function interpolateEntity(currentTime) {
	//assuming currentTime is synced with server time
	//calculate time at which we want to render the entity
	var time = currentTime - 0.2;//200 ms in the past
	
	//find points that surround our time
	var i = 0;
	while(updates[i].time < time) i++;
	var before = updates[i-1];
	var after = updates[i];
	
	//calculate progress towards 'after'
	var alpha = (time - before.time) / (after.time - before.time);
	
	//interpolate
	entity.x = before.x + (after.x - before.x) * alpha;
	entity.y = before.y + (after.y - before.y) * alpha;
}

The code here is simplified to make a nice example. In practice we need to be careful when searching for the before and the after updates, and handle situations like not having enough updates yet.

In case this still isn’t very clear, I can recommend some other resources that I already mentioned in the third developer log:

Fast-Paced Multiplayer (Part III): Entity Interpolation by Gabriel Gambetta
Real Time Multiplayer in HTML5 by Sven Bergström.

Synchronization

First thing to solve is calculating the currentTime. The simple approach might be to simply start counting time after the server sends its first update. That seems to work well enough, but consider these scenarios:

Client lags (packet loss, unstable Wi-Fi, etc.) when receiving the first update.
Latency change when the route, that packets travel between the server and the client, changes.
Clock precision difference between the client and the server. After certain time the error will accumulate.

Eventually, the time difference would get bigger and start causing issues. If the client’s clock is faster, then it will run too far in to the future and won’t have the data to interpolate from. Or its clock will run slower and it will show entities way further in the past than needed.

With this in mind, it’s obvious we can’t just start counting time from the first update, but we need to perform some kind of synchronization. There’s many ways to handle this, but ultimately it comes down to two approaches:

Synchronizing the time

We could use SNTP or some different protocol to find the time difference. We would still need to either repeat this occasionally or handle clock precision difference somehow.

Once we know the time is synced, we could timestamp all the inputs and server updates, knowing precisely what the currentTime is. We would also know what the travel time for every update/input was, which might be useful in case we need to implement latency compensation.

This solution seemed quite complicated to me and isn’t without its issues. Also, we don’t really need to synchronize the time. All we actually need is to make sure that the time progression is in sync.

Synchronizing the clock

With time synchronization if we say something happened at time x, we know exactly when that is. With clock synchronization we just know that the same amount of ticks happened on both the server and the client. This approach won’t give us the actual latency (though we can use the synchronized clock to find it out if needed).

Basically, we know that that server sends updates at regular intervals (100 ms), we can use that to synchronize the clock. I came up with multiple ways of doing this, but ultimately, great books about Development and Deployment of Multiplayer Online Games pointed me towards phase-locked loop.

As complicated as the wikipedia article seems, the principle is straightforward:

We predict the time of the next incoming server update, based off our local time and the knowledge of server’s step time.
When the next update comes, we calculate the difference of current time from the predicted time – this is the phase detector part of PPL, as described in the wikipedia article.
Now for the tricky part – we use this difference to adjust our clock to stay in sync. We can’t just apply it directly otherwise our time would jump around like crazy with jitter and every packet drop. To handle that we need to implement the filter part of PPL.
- The logic here is to take the difference over multiple updates and calculate which way we should shift our clock. That’s basically an Integrator.
- We feed it the differences, it gives us back adjustment that needs to be made. Goal here is to smooth out the jitter and packet loss causing too abrupt changes that would be visible to the player.
Last part is the oscillator, which gives us the predicted time of the next update. That’s as simple as taking the previous predicted time plus the server step time and adjusting it by what the integrator gives us.

That’s it. The code will probably make it even easier to understand:

class TimeSyncer {
	
	public static inline var SERVER_STEP_MS:Float = 100;
	
	var expectedTime:Float;
	
	var integrator:Float = 0;
	var totalDrift:Float = 0;

	public function new() {
		expectedTime = getNow() + SERVER_STEP_MS;
	}
	
	public function onServerUpdate() {
		var timeDifference = expectedTime - getNow();
		integrator = integrator * 0.9 + timeDifference;
		var adjustment = Math.clamp(integrator * 0.01, -0.1, 0.1);
		totalDrift += adjustment;
		expectedTime += SERVER_STEP_MS;
	}
	
	public function getNow() {
		return untyped __js__("Date.now()") + totalDrift;
	}
	
}

Usage and explanations

We create an instance of TimeSyncer when the first server update is received.
Each subsequent server update, we call onServerUpdate.
At any time, timeSyncer.getNow() will give us time that’s synced to server updates.
- That means we can use it for interpolating the entities based on received data (i.e. as the currentTime mentioned before).

The integrator = integrator * 0.9 + timeDifference is our filter. Basically we want to accumulate the error in such a way that it gives us the indicative value of how we should shift our time, and this value shouldn’t jump around too much. The parameter (0.9) is something to be tweaked. It must be a number lower than 1, but close to it. Basically it causes our integrator to slowly descend to 0 if there’s no time difference.

The adjustment calculation, Math.clamp(integrator * 0.01, -0.1, 0.1), is the final part of our filter. We take the accumulated error and modify it to give us some small value, that we use to shift our clock. The multiplication coefficient (0.01 here) and the clamping, again needs to be customized to fit the needs. We don’t want big changes, so we clamp it at 0.1 ms, while making sure it grows and descends optimally.

Server Update Loop

As far as I gathered there are two approaches to server update loop:

Tick at regular rate (e.g. 30 Hz). This means that clients can send only changes of their inputs (i.e. “I pressed right”, “I stopped pressing up”), and the server will simply update as the time goes using whatever inputs the players have active at the time.
- This has some benefits, but lag and jitter will cause the client-side prediction to cease being perfect.
- With this kind of update loop, our TimeSyncer would give us everything we need.
Other option is to have no game update loop at all. Instead it will apply the inputs (which are sent every client’s game loop tick), as they come, moving each player forward in time individually. We talked about that in the third log and we also mentioned the issues related to that.

In our case, we apply the inputs as they come. My main reason for that, which is something I didn’t mention in the third log, is to achieve perfect platformer movement. Basically, I want the movement to feel good and be predictable/learnable.

This approach has some additional requirements related to time synchronization and entity interpolation.

Synchronizing Client Update Loop

Client update loop needs to be synced too. That just means that the update rate can’t be determined by the framework’s (Phaser or whatever you use) inner game loop. We can modify the TimeSyncer to achieve that (previous code omitted):

class TimeSyncer {

	public static inline var STEP_MS:Float = 33;
	
	var simulationTime:Float;
	
	public function new(){
		simulationTime = getNow();
		//previous code omitted
	}
	
	public function moveSimulation():Bool {
		if (getNow() - simulationTime > STEP_MS){
			simulationTime += STEP_MS;
			return true;//did step
		}
		return false;//did not step
	}
}

Now in our render loop, we can do something like:

while (timeSyncer.moveSimulation()) { 
	stepWorld(); 
}

Synchronizing The Entity Interpolation

Earlier in the general approach to entity interpolation code, we needed two things to make it work – currentTime and update.time. We aren’t really synchronizing the time, so server doesn’t send it to us. All it sends are the updates containing position information. That is all we need though.

Server update data

Before we get to interpolation implementation for this kind of server update loop, we need realize another detail related to it (or lack of it).

If the server would simply send the positions the entities have, at the time of the network loop tick, the interpolation would look bad. That’s because the client’s actual simulation time is based on the amount of inputs it sent, not on the server current time (as it would be if the server simulated clients in its own update loop all at once).

We can solve that by making the server include relative time of the client, to the network tick time. That means the data will go something like this: “Entity id=1, had position x=100, y=200, delta=30 ms ago”. The server can calculate this delta by keeping the current time of every client, based off the server’s machine local time (which is what the clients sync their clock to), starting at the time the client sends its first input. And incrementing this client’s current time by STEP_MS for every applied input.

This also allows the server to prevent possible cheater sending inputs faster to move faster, by postponing the simulation of the client (applying its inputs) so that its current time never grows higher than the next network tick time. In which case the server buffers the inputs and applies them on the next network update tick.

Client synchronization – calculating the time

Let’s make a few modifications to TimeSyncer again (previous code omitted):

class TimeSyncer {

	var serverTicks:Int = 0;
	var startTime:Float;
	
	public function new(){
		startTime = getNow();
		//previous code omitted
	}
	
	public function onServerUpdate() {
		serverTicks++;
		//previous code omitted
	}
	
	public function serverDelta(delta:Float) {
		return serverTicks * SERVER_STEP_MS - delta;
	}
	
	public inline function timeSinceStart() {
		return getNow() - startTime;
	}

}

Now we can easily get the currentTime and the update.time needed for interpolation:

The currentTime is timeSyncer.timeSinceStart(), which is our client’s current time clock-synchronized to the server.
And after calling timeSyncer.onServerUpdate() when receiving one, we can take the position information and use the delta part (mentioned above) to calculate update.time for this update by using timeSyncer.serverDelta(delta).

Entity Interpolation Implementation (finally)

We now have everything we need to properly interpolate. The basic interpolation code explained at the beginning of the article mentioned that we need to be careful when we don’t yet have enough data to interpolate. And also we probably don’t want to keep all the old updates, which would gradually take more and more memory.

The best way to handle both these issues nicely is to implement a circular buffer. As a bonus I share my own implementation:

class PositionCircularBuffer {
	
	public static inline var INTERPOLATION_TIME:Float = 200;
	var buffer:Array<PointAtTime>;
	var size:Int;
	var nextIndex:Int = 0;
	var startIndex:Int = 0;
	
	var tempPoint:PointAtTime;

	public function new() {
		//maximum amount of points needed for interpolation
		//assuming they have at least TimeSyncer.STEP_MS time difference
		size = Math.ceil(INTERPOLATION_TIME / TimeSyncer.STEP_MS) + 1;
		buffer = [for (i in 0...size) new PointAtTime()];
		tempPoint = new PointAtTime();
	}
	
	public function push(x:Float, y:Float, time:Float):Void {
		buffer[nextIndex].x = x;
		buffer[nextIndex].y = y;
		buffer[nextIndex].time = time;
		
		nextIndex = increment(nextIndex);
		if (nextIndex == startIndex){
			startIndex = increment(startIndex);
		}
	}
	
	public function interpolateAtTime(time:Float):PointAtTime {
		time -= INTERPOLATION_TIME;
		clearOlderThan(time);
		var secondIndex = increment(startIndex);
		var first = buffer[startIndex];
		if (first.time >= time || secondIndex == nextIndex) {
			//not enough data for interpolation yet, wait
			tempPoint.x = first.x;
			tempPoint.y = first.y;
		} else {
			var second = buffer[secondIndex];
			var alpha = (time - first.time) / (second.time - first.time);
			tempPoint.x = first.x + (second.x - first.x) * alpha;
			tempPoint.y = first.y + (second.y - first.y) * alpha;
		}
		return tempPoint;
	}
	
	public function clearOlderThan(time:Float):Void {
		if (startIndex == nextIndex) return;//empty
		var secondIndex = increment(startIndex);
		while (buffer[secondIndex].time < time && secondIndex != nextIndex) {
			//second is smaller => first is useless
			//we can move the reader ahead unless we reached end
			startIndex = secondIndex;
			secondIndex = increment(secondIndex);
		}
	}
	
	private inline function increment(i:Int):Int {
		return (i + 1) % size;
	}
	
}

Now the usage is super simple. After receiving an update from the server and calling timeSyncer.onServerUpdate(), we can store the entity data easily by calling entity.positions.push(x, y, timeSyncer.serverDelta(delta)), where the entity.positions is an instance of the PositionCircularBuffer.

Then in the render loop we can simply call entity.positions.interpolateAtTime(timeSyncer.timeSinceStart()), to get the point at which we should render the entity.

And this is the end result – two clients running on my computer, connected to a real server on the other side of the globe (~200ms ping):