Sign in to follow this  
Heg

Client-Side Prediction & Packet Loss

Recommended Posts

hplus0603    11347
[quote]While we are at it, how do you guys handle lost or out of order client input? I would say client input needs to be ordered, but that would also imply that you would have to wait for a resend of lost client packages, since it´s not ordered when you are missing one package.
Should I really wait for such packages, or should I just let the client input get lost? This would result in a correction of the movement on the client, since it predicted the movement wrong.[/quote]

Yes, that's the problem of TCP as well. That darn "in-order" just crimps the style of any good network engineer :-)

You can predict that the lost packet just continued whatever the client was previously doing. This will be right 90% of the time.
You can also encode multiple time steps in each input packet. Send the input for the last N steps, instead of just last 1. With RLE encoding, this may not take up much extra space at all.

Share this post


Link to post
Share on other sites
Heg    173
As I said I am currently working on the Lag Compensation and I would like to hear your opinion on one special case.. In Bomberman you only die when you get hit by an explosion. This means that other players can´t kill you actively, like shooting you in the face with a gun. Instead they can trap you by planting bombs at the right position, because you can´t move through bombs. An example is illustrated in the picture:

[sharedmedia=gallery:images:2830]

So first of all I am incorporating bomb explosions into lag compensation. You only die if you are standing in an explosion on your screen. This can result in players moving through flames on the other clients because of the latency.
But the trapping situation is giving me a headache.. It is an important part of the gameplay, but the latency makes it kinda complicated. Consider the example in the picture again. The trapping player can plant a bomb perfectly infront of his opponent to trap him, but on the opponents machine, the bomb won´t get planted right in front of him, since he already moved to a different position on his machine.

What do you guys think would be the smartest thing to do in those situations? When a player only gets trapped when the bomb is appearing on his screen, trapping players in close positions gets almost impossible, but otherwise you will get trapped even if you have already moved out of the dangerous position.

I hope the problem is understandable.. If it isn´t, please let me know. Edited by Heg

Share this post


Link to post
Share on other sites
lawnjelly    1247
A video would be quite useful if you have fraps? It's always going to be a difficult one though. Player interactions is where client side prediction breaks down...[img]http://public.gamedev.net//public/style_emoticons/default/mellow.png[/img]

As a caveat I haven't personally dealt with this type of scenario, but here's some guesses:

When it does break down I believe it is usually best to rely on the server being authoritative. If you 'see' on the client you've planted a bomb and trapper another player, but as far as the server is concerned, that player has already moved out of the way (their input is ahead of yours, for example), you have a choice, you either let the server be authoritative and you correct your client, or you wind back the server, and say 'hey this client made a hit' and replay everything from there and send the result to everyone.

I personally wouldn't want to wind back the server, it strikes me as a bit of a nightmare in terms of balancing, potential for cheating, etc .. (what happens if there's a stutter on the client, and the other player is not updated, and thus easier to trap?). [img]http://public.gamedev.net//public/style_emoticons/default/unsure.png[/img]

So with an authoritative server you are going to get situations where either the trapper or the trappee is corrected (or both), and it's going to look kind of annoying, like in a FPS when you get shot round a corner or snapped back. Whether this totally mucks up gameplay is a question - some games maybe are not suitable for this sort of multiplayer I guess. You'll just have to try it and see.[img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]

It maybe something that works as a splitscreen game (with zero lag), but totally falls down when playing with lag.

The other thing you could do if all else failed, easy solution - don't use client side prediction lol. Then the problem is solved. It just means you'd have to either play with fast connections, or lan games, or try and hide the delay somehow in the gameplay.[img]http://public.gamedev.net//public/style_emoticons/default/laugh.png[/img]

There may also be other possible solutions with client-client communication, but I don't know much about that.

Share this post


Link to post
Share on other sites
Heg    173
[quote name='lawnjelly' timestamp='1348577579' post='4983547']

When it does break down I believe it is usually best to rely on the server being authoritative. If you 'see' on the client you've planted a bomb and trapper another player, but as far as the server is concerned, that player has already moved out of the way (their input is ahead of yours, for example), you have a choice, you either let the server be authoritative and you correct your client, or you wind back the server, and say 'hey this client made a hit' and replay everything from there and send the result to everyone.

I personally wouldn't want to wind back the server, it strikes me as a bit of a nightmare in terms of balancing, potential for cheating, etc .. (what happens if there's a stutter on the client, and the other player is not updated, and thus easier to trap?). [img]http://public.gamedev.net//public/style_emoticons/default/unsure.png[/img]
[/quote]

I think you understood the problem quite well, so no video is needed :D These two choices you speak of (rewinding or not rewinding the server) are basically the once that are giving me trouble. Not in terms of implementing, but in deciding what would provide the better gameplay experience.

I´ve got a friend who always manages to punish players immediately for walking into a potentially trap situation.. You walk into it, and boom, he trapped you and you are doomed. On the one hand I consider this a high skill move, and therefore it should be rewarded with a kill. On the other hand this gets very frustrating for players with high latency. Maybe they moved into the trap knowing that the other player is too far away to trap them in time.. But little do they know that the guy is way more ahead on the server...

I don´t think there is a perfect solution to this, I think I have to decide what´s the lesser evil.

Share this post


Link to post
Share on other sites
Heg    173
Okay, I have yet another question:

I tested my interpolation a little bit more, and it doesn´t work well with variating latencies (unfortunately I forgot those in my testing [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img] ). Currently my game updates include movement data in a format like this: "At position x,y the player moved up for 30 ms." and so on. I did this, because you can turn instantly in the game. The client just needs to set the player to the given position and execute the same movement code as the server did to reproduce the movement.

I am sending out updates at a 100ms interval. So if the client gets an update, it views the movement of the update for the next 100 ms. If a new update arrives during that time, the action gets queued and displayed afterwards. So far, so good. But what happens when an update arrives to late? I could display the movement until the next update arrives and then jump directly to the next update.

But how do I realize what updates are too early and which are too late? Basically what my question is is, how does the time synchronizing work between server and client? Currently my idea is that when the client recieves the first update, he starts his internal "client time" and expects the next update 100ms later, since it should be send out 100ms later relative to the first update by the server. This whole idea falls flat when the first update arrives too fast. If for example a package needs 150 ms to arrive at the client, but the first one arrived after 50ms already, the client would render the first state for 100 ms and expect the new update, but that wouldn´t arrive for another 100 ms.

This gives me a real headache and I think I missunderstood something along the way. Please help me clear up my head [img]http://public.gamedev.net//public/style_emoticons/default/sad.png[/img] [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Edited by Heg

Share this post


Link to post
Share on other sites
Khatharr    8812
If the client is not getting updates as expected from the server then maybe you could pop up a notice in the corner of the screen or something and stop interpolating/predicting (only set player positions by server positions) until the problem is resolved. It looks tacky, but it will prevent adding confusion to the confusion already being presented by packet loss/lag.

If the server is not getting updates from a client then after missing 2 or 5 expected packets it could mark that client as being lagged out and notify the other clients?

Even at 100ms you're talking 10 screen updates per second, so if prediction fails for one or even two frames it's not the end of the world.

If you've got a player(s) continually lagging or dropping packets you could dynamically reduce the update frequency to some degree. You should be able to store the current update rate in a single byte included in each packet by just tacking on an extra byte. Edited by Khatharr

Share this post


Link to post
Share on other sites
hplus0603    11347
[quote]Even at 100ms you're talking 10 screen updates per second[/quote]

The screen can paint 60 times a second even if you run your physics at 20 Hz and your networking at 10 Hz. These are fully independent (but related) concepts.

Share this post


Link to post
Share on other sites
Heg    173
[quote name='Khatharr' timestamp='1348684432' post='4984058']
If the client is not getting updates as expected from the server then maybe you could pop up a notice in the corner of the screen or something and stop interpolating/predicting (only set player positions by server positions) until the problem is resolved. It looks tacky, but it will prevent adding confusion to the confusion already being presented by packet loss/lag.
[/quote]

I think I failed to explain my problem. In [url="https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking"]valves networking wiki[/url], under Entity Interpolation, they state that the actual render time is 100 ms behind the client time, so that basically all other players get displayed to the user 100ms in the past to allow smooth movement. I do understand the basic concept, but what I don´t understand is where the client time begins in the first place. When do they start the client time? On the first recieved update package from the server?

Also, to adapt this behavior I would have to shift my "rendering time" 200 ms into the past, since my update period is 100ms. This would just be too much for my taste. Is it viable to set my update interval to 50 ms and use valves technique? Or is there a better way for me to do this? Edited by Heg

Share this post


Link to post
Share on other sites
hplus0603    11347
In general, the client will attempt to estimate the clock of the server by using time stamps in packets. There are various ways to accomplish this, discussed extensively in other threads on this board.

The actual delay from "server" time when using "perfect" interpolation will be one-way transmission time plus (average) one and a half times your update rate. The reason for this is that you need the "next" point to interpolate towards, to start moving towards that point away from the previous point, and you want a little bit of receive buffer to account for jitter. In practice, the quantization of your game loop, and the game loop of the server, may add additional latency.

Additionally, your client will send data to the server at your one-way transmission time plus average one tick time ahead of time, for the data to be sure to be there when it's needed on the server.

Thus, the time that other players are behind the client input is going to be at least your round-trip-time, plus two ticks' worth of time (and usually, a little bit more than that.)

Yes, you can set your network tick time to 50 ms. Or 16 ms, if your graphics and simulation will keep up. This will reduce the "plus tick times" part of the equation, but not the "transmission time" part of the equation, which is generally the bigger part unless you have really good internet and live close to the server.

Share this post


Link to post
Share on other sites
Khatharr    8812
I didn't speak clearly. (sleep deprivation, lol) Yeah, I didn't mean screen updates. I meant updates of client positions, etc. Otherwise interpolation would not be possible.

There's no reason to render 2 ticks behind. (That's the opposite of what you're looking to do with prediction, isn't it?)

As far as timing the packets, if your server is sending its update frequency, or if the update frequency is fixed then you could reasonably expect the packet to arrive within 2x that amount of time from the previous packet. If you get a packet with a later sequence num or if the packet does not arrive in 2x the expected time then you may as well consider it lost. Whenever you get an update you animate the movement of the players between their current position and the indicated position. Run that animation such that it will complete when the next packet is expected. If the next packet has not arrived when that animation completes then run a tick's worth of prediction animation. If that completes and you still haven't received the next packet you can wait a tick or two for the next packet and then complain, with or without prediction animation during the wait. If a late packet finally arrives don't bother interpolating, but just drop the players into their current position and resume interpolation on the next frame. I guess what I was trying to say is that there's no reason to keep predicting if your timing is highly sporadic or has fallen several packets behind. You may as well just pop up a little lag notification and do your best to keep up with whatever scraps you're getting. Edited by Khatharr

Share this post


Link to post
Share on other sites
Inferiarum    739
concerning the problem with trapping players with bombs etc.
Did you try how your game feels without any form of client side prediction? That is, the player just has to live with the delay.
I guess that should work quite well for a bomberman clone. Afaik this is also how it is done for most Dota like games, e.g. League of Legends etc.

Share this post


Link to post
Share on other sites
Heg    173
[quote name='hplus0603' timestamp='1348704225' post='4984171']
In general, the client will attempt to estimate the clock of the server by using time stamps in packets. There are various ways to accomplish this, discussed extensively in other threads on this board.

The actual delay from "server" time when using "perfect" interpolation will be one-way transmission time plus (average) one and a half times your update rate. The reason for this is that you need the "next" point to interpolate towards, to start moving towards that point away from the previous point, and you want a little bit of receive buffer to account for jitter. In practice, the quantization of your game loop, and the game loop of the server, may add additional latency.

Additionally, your client will send data to the server at your one-way transmission time plus average one tick time ahead of time, for the data to be sure to be there when it's needed on the server.

Thus, the time that other players are behind the client input is going to be at least your round-trip-time, plus two ticks' worth of time (and usually, a little bit more than that.)

Yes, you can set your network tick time to 50 ms. Or 16 ms, if your graphics and simulation will keep up. This will reduce the "plus tick times" part of the equation, but not the "transmission time" part of the equation, which is generally the bigger part unless you have really good internet and live close to the server.
[/quote]

Okay, so what I would try to do now is the following (I am only talking about displaying the opponents, i.e. the remote players, in a smooth movement, not client-side predicition):

1. I estimate the current server time by using timestamps and package latency.

2. Each [i]player movement[/i] in the [i]game update[/i] send by the server gets a [i]starting time[/i] which indicates when the server started to process the movement.

3. To play the movement of the other players back, I set the current time on the client to [b]renderTime = estimatedServerTime - Latency * 0.5 - 1.5 * UpdateInterval[/b]. All queued up movement data will be executed when [b]renderTime >= starting time[/b].

4. If an update arrives way too late, i.e. over 1.5 update intervals, the [i]starting time[/i] of the movement will be way behind the current [b]render time[/b]. If the movement still takes place during the current [b]render time[/b], I will either speed up the action or cut it off, so the movement will jump to the next position.

Is this a sane approach, or did I miss something?

And before I forget: You guys are a big help, thanks alot [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img] Edited by Heg

Share this post


Link to post
Share on other sites
Heg    173
[quote name='Khatharr' timestamp='1348705778' post='4984174']
I didn't speak clearly. (sleep deprivation, lol) Yeah, I didn't mean screen updates. I meant updates of client positions, etc. Otherwise interpolation would not be possible.

There's no reason to render 2 ticks behind. (That's the opposite of what you're looking to do with prediction, isn't it?)

[/quote]

I am not talking about Client-Side Predicition anymore, i.e. the prediciton of my local player. We went a little bit offtopic, since my prediction is working fine at this point :)
If you are talking about predicting the movement of the remote players, I am not trying to do that. I just want to show 'old' movement data of the other players, so it will look smooth on the local machine.

[quote name='Inferiarum' timestamp='1348735063' post='4984279']
concerning the problem with trapping players with bombs etc.
Did you try how your game feels without any form of client side prediction? That is, the player just has to live with the delay.
I guess that should work quite well for a bomberman clone. Afaik this is also how it is done for most Dota like games, e.g. League of Legends etc.
[/quote]

I didn´t, because the lag compensation is not implemented for explosions. In the current version you will die when the server detects you in a fire, even though you didn´t stand in the fire on your local machine. That is horrible and will drive players insane, that is why I couldn´t make some real test runs. :)

I have to refine my entitiy interpolation and implement lag compensation for explosions first, then I can test how bomb planting feels. I´ve got my hopes up that it will feel okay as it is. We´ll see ;)

Share this post


Link to post
Share on other sites
oliii    2196
Generally, you need some 'a-team' style clock synchronisation.

Can be as simple as using timestamps to measure roundtrip latency (and half it) and convert local time to to a global shared time (maintained by the server).

I don't have an algorithm at hand, but it should be easy to work out. Being aware of drift, and especially if you base your clocks on timesteps (imo you'll be better served with using the cpu tick counter for that).

Share this post


Link to post
Share on other sites
Inferiarum    739
[quote name='Heg' timestamp='1348745640' post='4984316']
[quote name='hplus0603' timestamp='1348704225' post='4984171']
In general, the client will attempt to estimate the clock of the server by using time stamps in packets. There are various ways to accomplish this, discussed extensively in other threads on this board.

The actual delay from "server" time when using "perfect" interpolation will be one-way transmission time plus (average) one and a half times your update rate. The reason for this is that you need the "next" point to interpolate towards, to start moving towards that point away from the previous point, and you want a little bit of receive buffer to account for jitter. In practice, the quantization of your game loop, and the game loop of the server, may add additional latency.

Additionally, your client will send data to the server at your one-way transmission time plus average one tick time ahead of time, for the data to be sure to be there when it's needed on the server.

Thus, the time that other players are behind the client input is going to be at least your round-trip-time, plus two ticks' worth of time (and usually, a little bit more than that.)

Yes, you can set your network tick time to 50 ms. Or 16 ms, if your graphics and simulation will keep up. This will reduce the "plus tick times" part of the equation, but not the "transmission time" part of the equation, which is generally the bigger part unless you have really good internet and live close to the server.
[/quote]

Okay, so what I would try to do now is the following (I am only talking about displaying the opponents, i.e. the remote players, in a smooth movement, not client-side predicition):

1. I estimate the current server time by using timestamps and package latency.

2. Each [i]player movement[/i] in the [i]game update[/i] send by the server gets a [i]starting time[/i] which indicates when the server started to process the movement.

3. To play the movement of the other players back, I set the current time on the client to [b]renderTime = estimatedServerTime - Latency * 0.5 - 1.5 * UpdateInterval[/b]. All queued up movement data will be executed when [b]renderTime >= starting time[/b].

4. If an update arrives way too late, i.e. over 1.5 update intervals, the [i]starting time[/i] of the movement will be way behind the current [b]render time[/b]. If the movement still takes place during the current [b]render time[/b], I will either speed up the action or cut it off, so the movement will jump to the next position.

Is this a sane approach, or did I miss something?

And before I forget: You guys are a big help, thanks alot [img]http://public.gamedev.net//public/style_emoticons/default/smile.png[/img]
[/quote]

You can do your game state updates as soon as the packets from the server arrive. The entity positions at render time are then calculated as the interpolation between two game states. Thus it is maybe also better to go back 2.5*Updateinterval, so you can still interpolate the positions when one packet is lost.

For the game state updates from the server you could also use quake3 style delta packets so you never miss any information and you only have a problem if two packets in a row are lost.

Share this post


Link to post
Share on other sites
Inferiarum    739
[quote name='Heg' timestamp='1348746338' post='4984320']
I didn´t, because the lag compensation is not implemented for explosions. In the current version you will die when the server detects you in a fire, even though you didn´t stand in the fire on your local machine. That is horrible and will drive players insane, that is why I couldn´t make some real test runs.

I have to refine my entitiy interpolation and implement lag compensation for explosions first, then I can test how bomb planting feels. I´ve got my hopes up that it will feel okay as it is. We´ll see ;)
[/quote]

I do not really get that part. Lag compensation or not, you should always see exactly what happened on the server only with a delay. Lag compensation just makes it smoother. At least that is how I meant it. You just draw all entities at the same point in time and do not do any client prediction.

Share this post


Link to post
Share on other sites
Heg    173
[quote name='papalazaru' timestamp='1348754703' post='4984353']
Generally, you need some 'a-team' style clock synchronisation.

Can be as simple as using timestamps to measure roundtrip latency (and half it) and convert local time to to a global shared time (maintained by the server).

I don't have an algorithm at hand, but it should be easy to work out. Being aware of drift, and especially if you base your clocks on timesteps (imo you'll be better served with using the cpu tick counter for that).
[/quote]

I´ll use the stuff explained in [url="http://www.gamedev.net/topic/609269-synchronizing-server-and-client-time/page__st__20"]this topic[/url]. I hope that it will be sufficent.

[quote name='Inferiarum' timestamp='1348772788' post='4984458']

You can do your game state updates as soon as the packets from the server arrive. The entity positions at render time are then calculated as the interpolation between two game states. Thus it is maybe also better to go back 2.5*Updateinterval, so you can still interpolate the positions when one packet is lost.

For the game state updates from the server you could also use quake3 style delta packets so you never miss any information and you only have a problem if two packets in a row are lost.
[/quote]

I´ll have a look into delta compression. Thanks for the tip :)

[quote name='Inferiarum' timestamp='1348824812' post='4984670']
[quote name='Heg' timestamp='1348746338' post='4984320']
I didn´t, because the lag compensation is not implemented for explosions. In the current version you will die when the server detects you in a fire, even though you didn´t stand in the fire on your local machine. That is horrible and will drive players insane, that is why I couldn´t make some real test runs.

I have to refine my entitiy interpolation and implement lag compensation for explosions first, then I can test how bomb planting feels. I´ve got my hopes up that it will feel okay as it is. We´ll see ;)
[/quote]

I do not really get that part. Lag compensation or not, you should always see exactly what happened on the server only with a delay. Lag compensation just makes it smoother. At least that is how I meant it. You just draw all entities at the same point in time and do not do any client prediction.
[/quote]

Oh, sorry about that. What I was trying to say is that trapping other players is a matter of gameplay, therefore I have to test it with real players. I tested the current state against my A.I. players, and the delay is noticeable. The thing that automatically happens is that I am anticipating the delay and because of that I am still able to trap the players. This happens, because I am the programmer and know that the delay is there. I have to see how it affects other people, whether it is annyoing or not and how often it occurs in a series of matches. Only after that I can decide if some sort of lag compensation is needed or not.

If you suggested that I shouldn´t interpolate or predict the players at all and just show them at there last recieved position, I tested that as well. That works horrible over an internet connection, because the delays are very noticeable.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this