We just had an interesting technical conversation (and lecture from me, so doubly interesting :-)) about Dead Reckoning on irc. Why it is needed; what matters about it and what doesn't matter. Someone suggested I post it here and so I have. Slightly edited for on-topic-ness.
[17:03:24] <Serpentus> Well, the server treats mobs the same as characters, so what you really want is time synch between players, no?
[17:03:40] <Gothi[c]> right
[17:04:27] <Serpentus> One problem is that latency is never constant.
[17:04:39] <+Lanarel> also, iif clients would keep an estimate of their lag, the server could correct for what it receives, and the client could correct for what it gets from the server.
[17:04:42] <Serpentus> Another problem is that I type poorly.
[17:04:59] <Gothi[c]> Serpentus: right, that's why it would be better to have all clients+server agree on a common clock time
[17:05:24] <Serpentus> So you want us to host an atomic clock?
[17:05:40] * Serpentus grins.
[17:05:44] <Gothi[c]> well, that's something that i want to avoid
[17:05:51] <Serpentus> Vengeance: that's in the budget, right?
[17:06:01] <Gothi[c]> it's not for PS, don't worry
[17:06:05] <+weltall> ahhahaah
[17:06:09] <+Lanarel> Serpentus: that only works if everyone has such a clock
[17:07:06] <Serpentus> Gothi[c]: The simple fact is that it doesn't matter who is keeping time, you will always need to ask the clock what time it is. Even chipsets do not measure seconds accurately.
[17:07:28] <Gothi[c]> i guess i could implement something like Object->Translate(matrix,time,algorithm) where time is the time an object should change it's position/rotation in, and algorithm could be linear/logarithmic/whatever
[17:07:39] <Serpentus> If I leave my computer on for a month and do not sync it with a time server, I will inevetably lose a minute or two.
[17:08:01] <Gothi[c]> and then only send updates when needed, and pass them to that function
[17:08:27] <+Lanarel> I have been looking at pc time recently. I could see a jump in clock speed when it got a bit warmer, resulting in about 40 seconds difference a day
[17:08:52] <Serpentus> We can't really treat time as a variable.
[17:09:35] <Serpentus> I mean, we can use it in functions as an argument, but to have a "time server" that synchronizes data execution across disjoint groups of machines is a bit out of our reach technologically.
[17:09:59] <Serpentus> Unless you want to host an atomic clock.
[17:10:05] <Serpentus> Which I am all for.
[17:11:16] <Serpentus> And with that said, step 1 in the paper you pasted is inherently flawed.
[17:12:37] <Gothi[c]> heh
[17:12:49] <Vengeance> ok here
[17:13:27] <Vengeance> Gothi[c]: What kind of game are you making?
[17:13:47] <Gothi[c]> a couple
[17:13:55] <Gothi[c]> that's why i'm trying to keep things generic
[17:14:05] <Gothi[c]> right now it's just an engine
[17:14:31] <Vengeance> The issue is that different games require different levels of accuracy.
[17:15:07] <Gothi[c]> ok
[17:15:09] <Vengeance> FPS is a good example of needing a lot of accuracy.
[17:15:21] <Gothi[c]> well it wont' be for FPS games
[17:15:22] <Vengeance> Bullets and lasers go fast, and 1/2 second latency is a lot
[17:15:41] <Vengeance> if the enemy's mesh is off by 2 pixels, that might mean the diff between a hit and a miss
[17:15:43] <Gothi[c]> one idea was a space shooter mmo and the other was more something like PS
[17:15:54] <Gothi[c]> i guess the space shooter would have to be more accurate
[17:16:24] <Vengeance> In PS, we handled it the way every fantasy MMO handles it, which is to ignore it completely.
[17:16:30] <Gothi[c]> right now i have a working server and client. clients can login and move around and see eachother. i'm just trying to implement a generic algorithm to smoothen the movements between net updates
[17:16:32] <@Khaki> in PS time sync is not needed
[17:16:37] <Vengeance> None of our spells or targeting or rules require pixel perfect accuracy
[17:16:45] <Vengeance> in fact, none depend on physical location at all
[17:17:18] <Vengeance> So if client A moves at 0 msec
[17:17:21] <Gothi[c]> well, i'm not even worrying about shooting and stuff yet
[17:17:32] <Gothi[c]> right now i just want my mobile objects to move smoothly between net updates
[17:17:33] <Vengeance> and client B and C are both 200 msec ping time with the server
[17:17:48] <Gothi[c]> and not jump as server sends a new position to the client
[17:17:55] <Vengeance> smooth movement is a different issue from world consistency between A, B and C
[17:18:06] <Gothi[c]> that's true
[17:18:12] <Vengeance> Smooth movement is what dead reckoning is for
[17:18:37] <Vengeance> you send vel updates, and ang vel
[17:18:51] <Vengeance> but you don't send them every frame, of course
[17:18:55] * Serpentus wants Vengeance to do a podcast on DR.
[17:19:04] <Vengeance> Serpentus: yeah I should. we get lots of questions about it
[17:19:15] <Vengeance> Let's say you want to update from the network once a second
[17:19:22] <Vengeance> brb
[17:19:26] <Gothi[c]> ok
[17:20:37] <@Khaki> I don't see what's so hard about it
[17:21:32] <Serpentus> Khaki: Hard about what?
[17:22:18] <@Khaki> DR
[17:22:19] <+Lanarel> You need a smooth way of correcting wrong positions. PS just 'teleports' you. You could correct from current (wrong) position towards the correct one to keep it smoother
[17:23:07] <Serpentus> DR isn't hard, but it has pros and cons and knowing how PS implements it and for what functionality is no trivial matter.
[17:23:20] <@Khaki> Lanarel: for someone that is continuously running with varying lag and angular velocity, the errors will eventually build up to the point where the client is forced to teleport
[17:23:34] <+Lanarel> yes, there are limits
[17:24:37] <@Khaki> pixel perfect collisions in a fps still have to be done client side, that's why getting rid of cheating in a fps is so hard
[17:24:50] <@Khaki> maybe that's why there are so few open source FPSes
[17:25:15] <Gothi[c]> yeah
[17:25:21] <+Lanarel> hehe. I suggested that cheating was the reason it was done this way
[17:25:24] <Vengeance> b
[17:25:53] <Gothi[c]> a way to solve that is to do pixel perfect collision on the client, and on the server just check if the action is within the realm of possibility
[17:25:53] <Vengeance> Yes, so the issue is that for smooth movement you need updates every frame
[17:26:11] <Vengeance> The only way to do that is to extrapolate the movement from the last position and the last velocity
[17:26:31] <Vengeance> So now you do 200 updates in 200 frames in 1 second
[17:26:57] <Gothi[c]> yeah, but you're not always going to get 200 updates in a second
[17:27:06] <Gothi[c]> there may be a 1 second hickup
[17:27:09] <Vengeance> Gothi[c]: I'm saying 0 updates
[17:27:23] <Vengeance> Net update. 200 frames. Net update
[17:27:33] <Gothi[c]> oh ok
[17:27:35] <Vengeance> So now what are the possible errors here
[17:27:48] <Vengeance> If the person is going in a straight line at a constant speed, there is no error
[17:27:53] <Vengeance> the extrapolation is correct
[17:28:17] <Vengeance> If the person turns 1 frame after the first net update, you could be way off though
[17:28:33] <Vengeance> So you solve that by braeking your 1 net update/sec rule
[17:28:44] <Vengeance> and if the vel or ang vel changes, send the net update immediately
[17:29:27] <Vengeance> So now you are worried about the time lag between client A and B in that scenario
[17:29:33] <Gothi[c]> yes
[17:29:35] <Vengeance> But the time lag is invisible to both sides
[17:29:47] <Vengeance> Client A moves and controls his avatar directly so he has no lag
[17:30:00] <Vengeance> ok let me slow down
[17:30:05] <Vengeance> Let's say we have this sequence:
[17:30:14] <Vengeance> 0 msec: A starts moving
[17:30:27] <Vengeance> 500 msec: A stops moving.
[17:30:44] <Vengeance> Now with 200 msec of lag, here is what client B sees:
[17:30:51] <Vengeance> 0 msec: stationary
[17:30:59] <Vengeance> 200 msec: A starts moving
[17:31:07] <Vengeance> 700 msec: A stops moving
[17:31:20] <Vengeance> So it all happens late, but it happens consistently
[17:31:33] <Vengeance> and 200 msec isn't much unless you're shooting lasers
[17:31:50] <Vengeance> The hard part in all this isn't lag, but variable lag
[17:32:02] <Vengeance> Imagine if B sees this sequence:
[17:32:07] <Vengeance> 0 msec stationary
[17:32:13] <Vengeance> 200 msec: A starts moving
[17:32:32] <Vengeance> 800 msec: A stops moving and is now in the "700 msec" position
[17:32:51] <Vengeance> He was extrapolated for 600 msec but only actually moved for 500 msec
[17:33:02] <Vengeance> so when you "fix" his position, you have 100 msec of error
[17:33:15] <Vengeance> for a walking character at 2m/s, that's 200cm or 8 inches
[17:33:31] <Vengeance> Not enough to affect gameplay much, but enough to look jittery
[17:33:56] <Vengeance> In PS, we don't just instantly update the "fix" position though, and teleport him 8cm
[17:34:16] <Vengeance> we note the new "correct" position, and factor that into the next DR set
[17:34:24] <+Lanarel> ah, did not know that
[17:34:27] <Vengeance> so he slides gradually to the right spot over a second or so
[17:34:52] <Serpentus> crafty
[17:34:55] <Vengeance> This is harder than it sounds, because the stationary case is easy but the "running and turning plus error" case is trickier.
[17:35:10] <Gothi[c]> right
[17:35:33] <Vengeance> You end up having to extrapolate A's current position on client B, plus extrapolate A's "correct" position on client B, and interpolate beetween those at the same time
[17:36:05] <Vengeance> So this is what we do
[17:36:17] <Vengeance> Yes it was a PITA to build
[17:36:35] <@kougaro> which explains why you sometimes see people jumping in a pit, and then "teleporting" back at the border
[17:36:40] <Vengeance> The error interpolation may have been disabled or changed since the iteration I'm talking about
[17:36:55] <Vengeance> so I would need to check it to be 100% sure, but this is how it is supposed to work.
[17:37:13] <+Lanarel> the jumps are only after server updates have not been received for a bit, kougaro
[17:37:19] <Vengeance> kougaro: Now factor in non-guaranteed UDP packet delivery and out of order delivery.
[17:37:36] <@kougaro> Vengeance : no thanks, I will leave that to you
[17:37:46] <Serpentus> kougaro: I claim your scenario occurs because Klyros have wings.
[17:37:52] <@kougaro>
[17:38:03] <@kougaro> klyros are the cause of all evil, for sure
[17:38:09] <Gothi[c]> i need to digest this
[17:38:27] * Serpentus hides his wings.
[17:38:40] <Vengeance> Gothi[c]: If you run two PS clients at the same time and look at each other, you can see that the lag doesn't matter much quite easily.
[17:41:20] <Vengeance> Ok someone read all that out loud and record it and we'll call it a devcast.