Delayed linear interpolation for networking

I'm trying to implement the delayed snapshot interpolation presented at Valve's article and also Gambetta's.

My current implementation is almost identical as described in the 'Multiplayer object interpolation' question posted here (can't link due to rep limit). I have an authoritative server that is sending snapshots to the clients about every other client. Those clients store each snapshot in a queue. I calculate a x millisecond delay (currently using twice my send rate) before starting to interpolate. This delay is calculated against peeking the first received timestamp in the queue and the current time.

What my code does is the following: Enqueue every entry from the server. The entry has a stamp from when the movement was captured, a position and a received time (client).

The client then keeps checking against the beggining of the queue if a set delay has passed since the most recent movement (currently 80ms). If it has, the client then sets the 'currentTime' (iterpolation begin time or T0) to the first entry stamp minus the interpolation delay. Then we know where we are:

  * The time is:
*
* T0           T0+dt <- currentTime
* |-------------|========
*
* where T0 is the oldest entry in the queue.
* Now we need to find the current two entries
* that we need to interpolate to.
* This is done by finding the first entry where
* T0+dt is smaller the the timestamp.
*
* Entry(n-1)        T0+dt      Entry(n)
* |-----------------=|=--------|-----------
*
* Then we just need to interpolate pos to from E(n-1) to E(n).


I handle the case where the current pos is less than E(n-1) and greater than E(n).

Since setting up unity is hard, building takes time and testing on the actual game code is heavy, I wrote a simulator in processing to test interpolation code. It is freely avaliable here and already contains an almost exact copy of my original Unity3D code.

The problem I'm facing is that interpolation is not working propperly. It is relatively jittery. It is probably a problem in the way I handle time but I can't figure it out how. The queue is never empty during movement. The edge cases also seem to be all handled. It can be something with the logic of the code itself.

I have a clip that shows the interpolation queue (the green line) and the previous interpolation movement (gray line): Can't post more than 2 links (link in the comments). In the clip, even though the queue seems to be 'full' and the movement almost presents no gaps, there is a noticeable stutter in the character movement. It seems like the character stops every x seconds and then starts again.

The current code I use is this:

public class PiecewiseLinearIntepolation {
public static float interpolationDelay = 0.07f;
private Queue<InterpEntry> interpolationQueue = new Queue<InterpEntry>();
private float currentTime = -1f;
private Vector3 latestPosition;
private Quaternion latestRotation;

private float latestStamp;

public void Enqueue(float timestamp, Vector3 pos, Quaternion rot) {
interpolationQueue.Enqueue(new InterpEntry(timestamp, Time.time, pos, rot));
latestPosition = pos;
latestRotation = rot;
latestStamp = timestamp;
}

public void Interp(float dt, Transform target) {
//Store oldest
if (interpolationQueue.Count > 0) {
}
//Delay the interpolation here, return oldest pos.
if (Time.time - oldestReceivedTime < interpolationDelay) {
//Reset current time
currentTime = -1f;
return;
}

//If we have elements, we need to start the interpolation
if (interpolationQueue.Count > 0) {
//This is E(n-1)
InterpEntry prev = null;
//If we don't have a time set, set the time to the oldest interp entry
//The oldest entry is the first in the queue.
if (currentTime < 0f) {
prev = interpolationQueue.Peek();
currentTime = prev.timestamp - interpolationDelay;
} else {
//If we had time, we need to move forward by adding the delta time
//From the last frame.
currentTime += dt;
}

//Boundaries More than last
if (currentTime > latestStamp) {
//Set to latest position
target.position = Vector3.LerpUnclamped(target.position, latestPosition, currentTime / latestStamp);
target.rotation = Quaternion.LerpUnclamped(target.rotation, latestRotation, currentTime / latestStamp);
//Dump queue and clear time
currentTime = -1;
interpolationQueue.Clear();
return;
}
//Current position is towards the first element of the queue
//This means, since the first frame, the interpolation is still towards the first entry
if (prev != null && currentTime < prev.timestamp) {
target.position = Vector3.Lerp(target.position, prev.position, currentTime / prev.timestamp);
target.rotation = Quaternion.Lerp(target.rotation, prev.rotation, currentTime / prev.timestamp);
return;
}
//This is E(n)
InterpEntry next = interpolationQueue.Dequeue();

//Find the first entry where the current time doesn't pass it.
while (currentTime > next.timestamp && interpolationQueue.Count > 0) {
prev = next;
next = interpolationQueue.Dequeue();
}

//Current position is towards the first element of the queue
//This means, since the first frame, the interpolation is still towards the first entry
//This is probably impossible
if (prev == null) {
target.position = Vector3.Lerp(target.position, next.position, currentTime / next.timestamp);
target.rotation = Quaternion.Lerp(target.rotation, next.rotation, currentTime / next.timestamp);
return;
}

//Calculate the time between points
float timeBetween = next.timestamp - prev.timestamp;
//Calculate T0+dt since prev instead of since begining
float timeSincePrev = currentTime - prev.timestamp;

//If there is no time, return next
//This is probably impossible
if (timeBetween == 0) {
target.position = Vector3.LerpUnclamped(target.position, next.position, currentTime / next.timestamp);
target.rotation = Quaternion.LerpUnclamped(target.rotation, next.rotation, currentTime / next.timestamp);
currentTime = -1;
return;
}
//Return the interpolation of T0+dt in this piece
target.position = Vector3.LerpUnclamped(prev.position, next.position, (timeSincePrev / timeBetween));
target.rotation = Quaternion.Lerp(prev.rotation, next.rotation, (timeSincePrev / timeBetween));
} else {
//We reach here each time we are within the oldest stamp delay but we cleared the list
//Reset current time
currentTime = -1f;
}
}

private class InterpEntry {
public float timestamp;
public Vector3 position;
public Quaternion rotation;
public InterpEntry(float timestamp, float timeReceived, Vector3 pos, Quaternion rot) {
this.timestamp = timestamp;
position = pos;
rotation = rot;
}
}
}


To replicate the problem, in Unity, just need to create an object, add a character controller, or any other controller to it. Then add a custom NWBehaviour and in it have an instance of this script. As server the object will call in FixedUpdate an RPC to send its position and rotation update along with a Time.time stamp. In this RPC (in the client), just call Enqueue with the data. In the Update, call Interp and pass in the Time.deltaTime and the object's transform.

• I'll explain better what is happening. Sorry if it seemed I want you guys to debug for me. I'm debugging for 2 weeks already, just didn't understand what you meant for "minimal and verifiable example". I'll edit now. – Lucas Montenegro Carvalhaes Jun 13 '17 at 23:16
• Link to the clip: my.mixtape.moe/ldedrc.mp4 – Lucas Montenegro Carvalhaes Jun 13 '17 at 23:30
• Is this better? I have managed to get the single class miss behaving, describe the expected and current results... – Lucas Montenegro Carvalhaes Jun 14 '17 at 0:24
• As far as I can see, much better :) I can not comment on others opinions, but I will retract my close vote. – Gnemlock Jun 14 '17 at 0:28

I have solved the problem. There were two main issues (along with smaller issues) with the code logic.

The main issue was that the delay was beeing applied to all inputs. The delay code was counting on each input arriving equally spaced and this was a wrong assumption. The new delay code just waits for inputs to arrive, saves the first time an input is stored and uses this time to apply delay only to the current input 'session'. When inputs cease to come, the queue is empty and this time variable is reset to -1.

Then I disabled the delay and focused on the interpolation. Testing each step of the code repeatedly, I discovered that although the way of thinking was correct, the logic was not behaving as I imagined it to. The interpolation should indeed search the element to interpolate where the current time would be smaller than the element time but I thought this is were the code would spend most of the time. This actually happens only in one frame. After this frame the next interpolation is actually a interpolation to the first element of the queue (since in the prev frame the queue was cleared until the next element). Sounds confusing because it was a LOT of development... so resuming it all: The new logic (fixed and adjusted in account to what I have said) is:

• Wait for input.
• When input arrives, delay from the first input.
• When the delay is over, set currentTime to (first interp message timestamp) - (delay).
• Interpolate to the first element in the queue.
• [Next frames] Update current time.
• If the interpolation is greater than one find the next element to interpolate where the next interpolation will be less than one. Remove all elements before it. Interpolate to the point between the point found and its previous. Set prev element so that the next frame it will consider the next point as the first in the queue.
• Repeat until queue is empty.

And for those that like reading code:

[Serializable]
public class PiecewiseLinearIntepolation : Interpolator {

//[...] class attributes removed for space

public override void Receive(float timestamp, Vector3 pos, Quaternion rot) {
interpolationQueue.Enqueue(new InterpEntry(timestamp, Time.time, pos, rot));
latestPosition = pos;
latestRotation = rot;
latestStamp = timestamp;

}

public override void Interp(float dt, Transform target) {

//Delay the interpolation here, return oldest pos.
if (ShouldDelay()) {
//Reset current time
currentTime = -1f;
return;
}

//Update time
if (currentTime >= 0f) {
//If we had time, we need to move forward by adding the delta time
//From the last frame.
currentTime += dt;
}

//If we have elements, we need to start the interpolation
if (interpolationQueue.Count > 0) {
//This is E(n-1)
prev = interpolationQueue.Peek();

//If we don't have a time set, set the time to the oldest interp entry
//The oldest entry is the first in the queue.
if (currentTime < 0f) {
currentTime = Math.Max(prev.timestamp - interpolationDelay, 0f);

//Set the time this interpolation piece has started from
startedTime = currentTime;

//Set starting points to interpolate from
startingPosition = target.position;
startingRotation = target.rotation;
}

//Current position is towards the first element of the queue
//This means, since the first frame, the interpolation is still towards the first entry
if (currentTime < prev.timestamp) {
timeBetween = prev.timestamp - startedTime;
timeSincePrev = currentTime - startedTime;

target.position = Vector3.LerpUnclamped(startingPosition, prev.position, timeSincePrev / timeBetween);
target.rotation = Quaternion.LerpUnclamped(startingRotation, prev.rotation, timeSincePrev / timeBetween);
return;
}

//This is E(n)
InterpEntry next = prev;

//Find the first entry where the current time doesn't pass it.
while (currentTime > next.timestamp && interpolationQueue.Count > 0) {
if (interpolationQueue.Count == 1) {
next = interpolationQueue.Dequeue();
prev = next;
} else {
prev = interpolationQueue.Dequeue();
next = interpolationQueue.Peek();
}
}

//Calculate the time between points
timeBetween = next.timestamp - prev.timestamp;
//Calculate T0+dt since prev instead of since begining
timeSincePrev = currentTime - prev.timestamp;

if (timeBetween == 0) {
timeBetween = 1;
timeSincePrev = 1;
}

//Return the interpolation of T0+dt in this piece
target.position = Vector3.LerpUnclamped(prev.position, next.position, (timeSincePrev / timeBetween));
target.rotation = Quaternion.Lerp(prev.rotation, next.rotation, (timeSincePrev / timeBetween));

startedTime = currentTime;
startingPosition = prev.position;
startingRotation = prev.rotation;
}
}

private bool ShouldDelay() {
//If the list is empty, delay and reset the current piece start.
if (interpolationQueue.Count == 0) {
pieceStartTime = -1;
return true;
}

//If the piece start time is reset and there are entries in the list,
//set the piece to the oldest entry and delay until interpolationDelay has
//passed since the oldest (stored in pieceStartTime).
if (pieceStartTime < 0) {

• Hey Zumbi! Did you finish this one? Is the gist a final version? – Jacob Jul 9 '17 at 17:43