Issue with multiplayer interpolation

(Posted earlier on a StackExchange site, but it was probably too unity-specific)

In a fast-paced multiplayer game I'm working on, there is an issue with the interpolation algorithm. This interpolation is for a moving object not controlled by the local computer.

The server sends packets with the object's position at a fixed rate. (red markers) The interpolation algorithm is attempting (and failing) to create a smooth path between the red markers.

The results of this interpolation are shown by green and black markers. Green is the local position at the exact time a packet is received, and black is the local position at every frame.

Green: Local position when a packet is received (edited for clarity)

Red: Position received from packet (goal)

Blue: Line from local position to goal when packet is received

Black: Local position every frame

On a network with a realistic amount of lag and packet loss, this is the result:



The local position (green&black lines) seems to oscillate around the goals (red lines) instead of moving between them smoothly.

This is how it looks on a perfect network with the object moving right to left. (0 ping, 0 packet loss, etc.)



The code works like this:

1. Every x ms, receive a packet with a Vector3 position
2. Set the `goal` to that position
3. Set the `positionAtLastPacket` to the current local position
4. Every frame, lerp from `positionAtLastPacket` to `goal`, attempting to reach the goal approximately when the next packet should arrive.
5. If the next packet takes longer than expected, interpolation continues past the goal and becomes extrapolation.

I believe what is happening is the extrapolation overshoots a bit to far. Over several packets, this issue compounds, causing the oscillation.

Code (CSharp):

1. // local transform position when the last packet arrived. Will lerp from here to the goal
2. private Vector3 positionAtLastPacket;
3.  
4. // location received from last packet
5. private Vector3 goal;
6.  
7. // time since the last packet arrived
8. private float currentTime;
9.  
10. // estimated time to reach goal (also the expected time of the next packet)
11. private float timeToReachGoal;
12.  
13. private void PacketReceived(Vector3 position, float timeBetweenPackets)
14. {
15.     positionAtLastPacket = transform.position;
16.     goal = position;
17.    
18.     timeToReachGoal = timeBetweenPackets;
19.     currentTime = 0;
20.    
21.     Debug.DrawRay(transform.position, Vector3.up, Color.cyan, 5); // current local position
22.     Debug.DrawLine(transform.position, goal, Color.blue, 5); // path to goal
23.     Debug.DrawRay(goal, Vector3.up, Color.red, 5); // received goal position
24. }
25.  
26. private void Update()
27. {
28.     currentTime += Time.deltaTime;
29.    
30.     float delta = currentTime/timeToReachGoal;
31.     transform.position = FreeLerp(positionAtLastPacket, goal, delta);
32.    
33.     // current local position
34.     Debug.DrawRay(transform.position, Vector3.up * 0.5f, Color.black, 5);
35. }
36.  
37. /// <summary>
38. /// Lerp without being locked to 0-1
39. /// </summary>
40. Vector3 FreeLerp(Vector3 from, Vector3 to, float t)
41. {
42.     return from + (to - from) * t;
43. }

Any idea about what's going on?