41 replies to this topic

[papalazaru]

Yeah, I already got a few testing functionality in my network layer, such as latency and packet loss. I am missing functions for duplication and out of order though. I´ll make sure to implement that.

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.

Current state of the game: Client-Side Prediction and Interpolation seems to work quite well in my current implementation, but I am not reacting to lost, duplicated and out of order packages yet. That´s my next step :-P

I'm toying with sending inputs in a sort of reliable fashion. It's a queue of inputs, and I keep sending them until they are acknowledged. I also have a bandwidth throttle to keep the bandwidth usage in check. If I run out of buffer space (because the server hasn't aknowledged the 3, 4 times the latency or so, or the past second, the buffer with a limited capacity becomes full and I cannot push any more inputs, ect...), then the client would pause, keep resending, until it gets acknowledgements from the server.

It's slightly OTT in a way. Some games (Quake3 for example), naively duplicates inputs (it's a console command you can tweak) so that in case of mild packet loss, you can still reconstruct the stream accurately, with minimum delays. Then if the stream is hopelessly broken (packet loss sometimes happen in bursts, so duplication from one packet to another isn't gonna help you), the server just ignores the client since the break, and correct him to his best ability. It depends how dependent you are on the reliability on your input stream (for example, fully deterministic games like Starcraft 3 which requires fully reliable input streams to work), how much more bandwidth naive duplication would consume, versus how much you have available.

Edited by papalazaru, 24 September 2012 - 06:54 AM.

[papalazaru]

I'm alse experimenting with client side prediciton / server side correction as follow :


Packets would look like :

client_packet (num_inputs=10) : inputs(sqn=4) + inputs(sqn=5) + inputs(sqn=6) + .... inputs(sqn=13) + predicted_state(sqn=13).

The host checks the predicted_state(sqn=13) by applying client inputs up to sqn=13, and if there is significant discrepencies with the client prediciton, sends a correction.

server_packet : correction_state(sqn=13).

The client can then wind back his player state to (sqn=13), re-apply all the inputs in the queue after (sqn=13), and can carry on sending more prediction to the server, which will hopefully stop deviating after a while.

You could send each prediciton with each input sequence, but that would increase the client packet size significantly. I'm still unsure if you would get benefits from that.

[lawnjelly]

I'm toying with sending inputs in a sort of reliable fashion. It's a queue of inputs, and I keep sending them until they are acknowledged. I also have a bandwidth throttle to keep the bandwidth usage in check.

This is a fairly standard way of doing it, I've been doing it for a while, there's a gaffer on games article describing this I think:

http://gafferongames.com/

I think (without looking at the code) I send the server calculated position with the ack for the client input. In fact this may all be part of the regular update packet from server to client (with actor positions).

Then when the client gets the ack, it can compare the server calculated position with its own client side predicted, and if it's different, roll back and recalculate the client position based on the input history. And once it has the server ack up to tick 'blah' it only now needs to send input out from tick 'blah' onwards, etc etc.

Edited by lawnjelly, 24 September 2012 - 12:45 PM.

[papalazaru]

Then when the client gets the ack, it can compare the server calculated position with its own client side predicted, and if it's different, roll back and recalculate the client position based on the input history. And once it has the server ack up to tick 'blah' it only now needs to send input out from tick 'blah' onwards, etc etc.

True. Stamp the server update of that player with the latest input sqn received, send new player position to everyone as part of the regular server update, then the player can use that to check his prediction and correct accordingly. A bit more lightweight, meaning no need for server-side correction, only client-side corrections. Interestingly, it also means that plugging in client prediction into the naive implementation is more straight forward.

Edited by papalazaru, 24 September 2012 - 09:05 AM.

[Heg]

Sending redundant client input is a brilliant idea! I already implemented it. The client now sends input, which is still waiting for server correction, along with new input to the server. I also added some simulation routines to my network layer. A package loss of 10% isn´t even noticeable when looking at the movement of the client. However the opponents do jump occasionally, because of the missing movement information.

The next step would be to implement Lag Compenensation. After that I need some animation to hide the delay between the planting bombs command and the actual appearence of the bomb, and the delay between running over an item and the time when it´s actually collected. I really want to wait for the server response before drawing bombs or collecting items.

Edited by Heg, 24 September 2012 - 11:39 AM.

[hplus0603]

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.

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.

[Heg]

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:




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, 25 September 2012 - 06:18 AM.

[lawnjelly]

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...

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?).

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.

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.

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

[Heg]

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?).

I think you understood the problem quite well, so no video is needed 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.

[Heg]

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 ). 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

Edited by Heg, 26 September 2012 - 12:03 PM.

[Khatharr]

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, 26 September 2012 - 12:56 PM.

[hplus0603]

Even at 100ms you're talking 10 screen updates per second

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.

[Heg]

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.

I think I failed to explain my problem. In valves networking wiki, 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, 26 September 2012 - 03:52 PM.

[hplus0603]

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.

[Khatharr]

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, 26 September 2012 - 06:44 PM.

[Inferiarum]

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.

[Heg]

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.

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 player movement in the game update send by the server gets a starting time 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 renderTime = estimatedServerTime - Latency * 0.5 - 1.5 * UpdateInterval. All queued up movement data will be executed when renderTime >= starting time.

4. If an update arrives way too late, i.e. over 1.5 update intervals, the starting time of the movement will be way behind the current render time. If the movement still takes place during the current render time, 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

Edited by Heg, 27 September 2012 - 05:35 AM.

[Heg]

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?)

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.

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.

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 ;)

[papalazaru]

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).

[Inferiarum]

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.

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 player movement in the game update send by the server gets a starting time 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 renderTime = estimatedServerTime - Latency * 0.5 - 1.5 * UpdateInterval. All queued up movement data will be executed when renderTime >= starting time.

4. If an update arrives way too late, i.e. over 1.5 update intervals, the starting time of the movement will be way behind the current render time. If the movement still takes place during the current render time, 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

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.