I''m trying to understand interpolation of movement and its use in network games... What is movement interpolation? I thought of it as of moving slightly from one point to another... For example, if the first pair of 2d (top-view) coordinates is first_vec2 = { 1.0, 1.0 } and the second is second_vec2 = { 2.0, 2.0 }, then interpolation between these two points would look like a smooth movement along { 1.1, 1.1 }, { 1.2, 1.2 }, { 1.3, 1.3 }, etc... So, now that we know that, how can this help to compensate lag effect in network games? Let''s try and imagine a situation: We got a server and two clients A and B... There''s a 2d-plane (space) - the game world... Players can move in any direction on this plane. Let''s also assume that the server and clients are already connected and time-synced. Each game-cycle is a ''frame''. Client A is at the point 1.0:1.0 and begins to move towards 2.0:2.0. It takes one time-cycle for the packet to reach the server and at this moment client A is already at 2.0:2.0. The server should immediately resend the packet to client B, and after one more game-cycle the packet reaches client B. B now know that A has began moving towards 2.0:2.0 two cycles ago, and it can calculate, that after two cycles (the current time moment) client A is at 3.0:3.0 (B doesn''t know anything about the changes of A trajectory duting these two cycles, so it consideres that the trajectory is straight-forward). It draws A at 3.0:3.0 (this is the first jerky jump). So what happens next? B can only draw A in its past positions (real, two cycles ago), or in current (calculated, current moment, but probably wrong). How can interpolation help?

Interpolation can help a few ways, and note that it can be something higher order than linear too (e.g.splines). I am not an expert but here are a few ways interpolation can help:

1) most straightforward: when A moves around, its motion (position, velocity, maybe acceleration, etc) is echoed to B. All B knows is it was at point 1 some time ago, and now is at point 2. How will B animate the movement of A between these points? Good interpolation can make A (from B''s perspective) move smoothly and naturally (but not 100% accurately) from point to point.

2) related, and really needed to make (1) work is you run your simulation, say 100 ms, back in time. The clients act as if there is 100ms of latency between when you make a command and when it responds, and also what is rendered is 100ms in the past. Small local latency values (<150 ms or so) will still feel responsive.

This in effect lets the client already know the future for the next 100 ms. So rather than extrapolating to generate the current position of A (from B''s perspective), B can interpolate, if the latency is less than 100ms. If its greater than 100ms, things are still better off because B will have to extrapolate 100ms less than it would have otherwise.

E.g. if B has 200ms of latency, it will have to extrapolate 100ms into the future now, where without a time lagged simulation, it would have had to extrapolate 200ms into the future.

Some other things to help latency situations (which you probably know):
Extrapolate, which is to take the model of its current motion and predict where it will be in the future.

Vary update rates on game objects based on closeness to the client and priority to the client.

Hope some of this helps

The way I use interpolation to smooth movement is like this.

The server recieves velocity information from a client (e.g. Client is pressing move foward key).

The server calculates the position of the client over time and sends this information out to other clients so they can draw the player (actually, it sends out the velocity information to each client so they can calculate the proper position of each of the other players on their own).

Player 1 now stops pressing the move forward key. This gets transmitted to the server, but it takes a few hundred ms to get there. In the meantime, the server (and all the other clients) is happily calculating new positions for the player, unaware that the player has actually stopped (or changed direction).

When the velocity change gets to the server, the server will now realize it has the player in the wrong position. It can pop the player back to where it should be.

But what do we do about the other clients? It would look bad to pop the player back to the proper position. Instead we apply an interpolation factor to smoothly move them over the course of several frames into the proper position.

Hmmm... i still don''t get it... What do we interpolate? Positions? Positions of players at different time moments? What are those moments (or, to be correct, when those moments are?)?
Do we interpolate between the calculated current position and predicted position in future? Or what?

Oh, forgot to add, that we can know for sure only previous positions of other players in past... Current position is unknown and the next position is also unknown... We need to know current position and next position to make the animation run smoothly until next packet arrives... But we only know about situation in past, so how can we make it smooth for present?

[edited by - dgtalx on December 4, 2003 3:55:30 PM]

red_mage:
>>> 1) most straightforward: when A moves around, its motion (position, velocity, maybe acceleration, etc) is echoed to B. All B knows is it was at point 1 some time ago, and now is at point 2. How will B animate the movement of A between these points? Good interpolation can make A (from B's perspective) move smoothly and naturally (but not 100% accurately) from point to point.

hmm... so, while we interpolate from previous point 1 to current point 2, time changes and present becomes past, so, when we finish interpolating and animating, A is rendered at its position in past again... its current position is still unknown... So how can a game be responsive and interactive, if the situation the player is seeing on his display is always in past?


[edited by - dgtalx on December 4, 2003 3:55:04 PM]

I would be glad if anybody posts a step-by-step algorithm of actions which a client and a server perform to make the game run smoothly...

Usually within a network game you extrapalate from the recived state ( which is old ) to the predicted current state ( which should be wihtin a limited error range of the current server state). Using this predicted current state you then interperlate from the current local state (state on the client currently) to the predicted state. This is done over time and the predicted current state could be time dependent as well( in the case of motion). Anyways the end result is as time passes the local state converges to the correct predicted current state ( as good as your extrapaltion algorithms are able to predict anways ).

This way you avoid unsightly jerkyness and get the best responsiveness.

Hope this makes sense.

Good Luck!

-ddn

quote:

---

Original post by DGtalx
hmm... so, while we interpolate from previous point 1 to current point 2, time changes and present becomes past, so, when we finish interpolating and animating, A is rendered at its position in past again... its current position is still unknown... So how can a game be responsive and interactive, if the situation the player is seeing on his display is always in past?

---

In my game, I don''t interpolate the controlling player''s avatar position. This position is based on keyboard input, just like in a single player game (the only difference is that the player movement actions are subject to server verification). So the game is perfectly responsive in respect to moving yourself.

The only interpolation I do is for other player''s avatars in your display. In this case, the avatars position is based on velocity and time. Now, when you get a velocity update packet, what you will find is that you have that player in the wrong position by some amount based on where you thought they were at the time the packet was sent. You still need to calculate their new position over time based on the last velocity gotten, so they continue to move, but you also add in a "fudge factor" in order to correct them to the proper place that they should have been when you got the packet, but you divide this over time so they don''t "pop". What this means is that the path you see another player take isn''t *exactly* the same as the path they actually took, though it ought to be pretty close.

The packets you get from the server about other player''s positions look something like this (in my game):

"At server time T, Player 1 was at position X, Y, Z, Rotation A, B, C forward speed = FS, Rotational speed = RS, Sidestep speed = SS"

From this, you can figure out where they were, where they were facing, and how fast they were moving in any direction at time T (based on the last packet time T'' you can determine the amount of time that passed since then) and compare that against where you calculated they were, get a difference, and apply the interpolation to smoothly correct to where they should be "now" (all the while they are still moving along the path as determined by their last given FS, RS, and SS).

You will never know another player''s "current position" at 100% accuracy, unless they have stopped long enough for your update to catch up to their last movement command (and then only if it''s a stop command). But generally, you can be pretty sure they are reasonably close to where you think they are (unless you are badly dropping packets from the server).

Hmmm... I think the further it goes, the harder it becomes to understand something... please correct the following statements, if they are wrong...
Client B receives a packet from a server, which contains something like "at time moment T1 in past A was moving along vector V_movement, the view direction vector is V_view, speed is S_forward, S_side", right? So client B can calculate the current time T2 position of A (not 100% accurate) and predict the position of A in future time T3 (even less accurate than at T2). Then B pops A to its calculated position at T2 and starts moving A towards its predicted position at T3 until the next packet arrives? or what? Please write what B should do with the avatar of client A:
1. at T1,
2. between T1 and T2,
3. at T2,
4. between T2 and T3
5. and finally at T3

[edited by - dgtalx on December 5, 2003 6:13:28 PM]