Implement hermite interpolation - multiplayer game

Question

I am trying to make a client-server architecture. I am stuck at the interpolation part. Right now, I have a very naive implementation of the interpolation algorithm. I have every player given a position history and whenever I receive a position data for other player from the server I push the position in to that array. Every client frame I use the oldest position history to interpolate to a new position with a constant speed.

// when new position for other player recieved 
p.stateHistory.push(data)

// Every client frame
if(p.stateHistory.length < 1)
            return false

    let deltaPosition = p.stateHistory[0].position.clone().sub(p.clientPosition)
    let direction = Math.atan2(deltaPosition.y, deltaPosition.x)
    let velocity = new Vector2(Math.cos(direction), Math.sin(direction)).scale(30/100)

    let threshold = 10
    if(deltaPosition.magnitude() < threshold) {
        p.clientPosition.x = p.stateHistory[0].position.x
        p.clientPosition.y = p.stateHistory[0].position.y
        p.stateHistory.shift()
    } else {
        p.clientPosition.add(velocity.clone().scale(deltaTime))
    }

I couldn't find way other to interpolate with a constant speed. I came to know about hermite interpolation from gafferongames. But it's sad that the article didn't have anything about its math and its implementation. I tried to go through the wikipedia article on hermite interpolation, but it didn't help. I know nothing about the math behind it. A pseudo code would be appreciated.

What I have been able to do so far: http://client-side-prediction-attempt.herokuapp.com/

Are the update that infrequent that you need interpolation? Are you aware that the client will lag a bit behind the server? — Nico Schertler, Mar 22 '19 at 15:24
the server tick is set to 100ms, so I think it is necessary. Yes, I am aware that the client will lag behind the server due to interpolation. Right now, I only want everything to appear smooth. — user278077, Mar 22 '19 at 17:04
Do you know anything about the velocity of the new point that you get from the server? If not, how do you want it to behave? Do you have some knowledge about the underlying movement (e.g. the the velocity is constant and only direction changes)? — Nico Schertler, Mar 23 '19 at 03:49
I don't think hermite's interpolation would require me to send the velocities. I do send them though. The magnitude of the velocities change too. — user278077, Mar 23 '19 at 10:25

Nico Schertler · Accepted Answer · 2020-05-27T15:43:46.123

4

Let's say say that your client receives a new position-velocity update at time currentTime. Then, you need to save the current position/velocity, the target position/velocity, the current time, and the time when you expect the next update:

function updateFromServer(position, velocity) {
    startP = currentPosition; //the current position of the player
    startV = currentVelocity;
    endP   = position;
    endV   = velocity;
    startT = currentTime; //the current time of the game
    endT   = startT + 0.1; //expect the next update in 100 ms
}

Once you have stored this data, you can do your frame update using interpolation. If you are outside of the [startT, endT] interval, you might just want to continue a uniform motion:

function frameUpdate(deltaT) {
    if(currentTime > endT)
        //uniform motion
        currentPosition += deltaT * currentVelocity;
    else {
        //cubic Hermite interpolation
        var t = (currentTime - startT) / (endT - startT); //interpolation parameter
        var t2 = t * t;
        var t3 = t2 * t;
        currentPosition = 
            (2 * t3 - 3 * t2 + 1) * startP + 
            (t3 - 2 * t2 + t)     * (endT - startT) * startV + 
            (-2 * t3 + 3 * t2)    * endP   + 
            (t3 - t2)             * (endT - startT) * endV;
        currentVelocity = 1 / (endT - startT) * (
            (6 * t2 - 6 * t)     * startP + 
            (3 * t2 - 4 * t + 1) * (endT - startT) * startV +
            (-6 * t2 + 6 * t)    * endP   +
            (3 * t2 - 2 * t)     * (endT - startT) * endV);
    }
}

Note that the formulas in this snippet are not valid JavaScript code. They must be translated to whatever library you use.

edited May 27 '20 at 15:43

answered Mar 23 '19 at 16:33

Nico Schertler

32,049
4
39
70

Is 'e' euler's number in your snippet? Where did you get the functions? I need more explanation to the algorithm. – user278077 Mar 23 '19 at 18:31
The `e` was a typo. The formulas are those of a [cubic Hermite spline](https://en.wikipedia.org/wiki/Cubic_Hermite_spline). – Nico Schertler Mar 23 '19 at 22:17
why do you use different functions for the velocity? I don't think they are on the wikipedia page. – user278077 Mar 24 '19 at 04:44
I tried changing the code to this but it doesn't appear like what I expected. It's still jerky, I guess. Other players also keep bouncing when they collide with the game border. – user278077 Mar 24 '19 at 11:22
The function for velocity is the derivative of the position function. Are you measuring time in seconds? If you have a different unit, you need to change the `0.1`. What does jerky mean? Could you try to increase the update time to 1 second to see if the interpolation itself works as expected? – Nico Schertler Mar 24 '19 at 16:28
Setting the interpolation time to 1s is giving false positions. They are not appearing where they actually are. By jerky I meant position jumps. – user278077 Mar 25 '19 at 02:22
What does *wrong* mean in this context? You only have a couple of positions and don't know anything for the positions in between. Hence, there is not really right or wrong. The formulas are guaranteed to reconstruct the start and end positions. Could you check if the right branches are chosen during runtime and that `t` is a number between 0 and 1? – Nico Schertler Mar 25 '19 at 15:37
t is being less than 1. I have updated the code on the app. You can see how simple interpolation is giving smoother path. – user278077 Mar 25 '19 at 17:52
Actually, both versions seem to be quite smooth for me. I assume the ghost is the position you get from the server? – Nico Schertler Mar 25 '19 at 21:05
I assume the endP and endV variables in the frameUpdate method are meant to be targetP and targetV? – Matt Clegg May 27 '20 at 08:13

Implement hermite interpolation - multiplayer game

1 Answers1