The KISS rule, in practice

Date: March 12, 2016 Posted by: Chris St. John In: Uncategorized

I’ve gotten rid of the whole client-side prediction thing. There was a fundamental oversight in my strategy. My goal was two-fold: 1) make it so that when you press a move key, you moved immediately (responsive), and 2) make it not look stupid.

The strategy was like this. Every time an update from the server side comes in, update the client side stuff as though it had actually happened a few moments ago. This means replaying a couple of physics cycles to try to get things back to where they currently appear to be.

For example, let’s say I’m a box. I can move left and right by pressing and holding the left and right keys. My game runs at 60 fps, server updates will be sent out at 10Hz, the current time is 15 000 (ms) and my position is currently +36. I start holding down the right key, and immediately alert the server to this fact.

The time is now 15 050. 3 frames have gone by and my position on the client is +39. A server update comes in, telling me that my position should be +36. The server update also has a timestamp on it (15 000), so on the client side, this state is corrected to account for the time that has since gone by, and the inputs I’ve kept around on the client. Looking that up, I can see that “right” was held between 15 000 and 15 050, so we apply 3 right ticks, and we land where we were before. Yay!

Now the time is 15 150. 9 frames have gone by and the client position is now +45. A server update comes in, timestamped at 15 100, saying the position should be +40. No problem, says the client, let’s just apply 3 more ticks on top of that (15 150 – 15 100), and the position is now +43.

What happened? The server should report a position of +42 at time 15 100, surely?

The problem is that the server did not receive my “right” press at exactly 15 000 – it received it a short time later. And herein lies the problem: the strategy is correcting server updates at the client as though the server and client received the inputs at the same time. They didn’t. Hence, every 100ms, our character jumps a small amount if we’re moving around actively: jitter. Note that if you move in a straight line, the effect isn’t as apparent.

To correctly complete this idea, the server needs to apply inputs it receives as though they arrived in the past. So in the example above, at time 15 025, when the server hears that I’m moving “right”, it should look up the timestamp on the move (15 000), and replay some frames starting from that point. Then it would transmit the correct coordinates when it comes time to broadcast the next world positions at time 15 100.

This would work great, except in the following circumstances:

  1. More than one player involved: As soon as we allow for the possibility of the server doing “time travel”, we expose ourselves to jitter effects of a different kind: the server could (would) be doing constant corrections to account for players’ late inputs, and players could actually jump/warp in the server simulation as a result. This effect would be worse the more latency is involved in the players’ connections.
  2. Consequential game events already broadcast: Red shoots, blue doesn’t move, red scores! No wait, blue moved a second ago, simulate it again. Uh oh, this time, blue got in the way and red didn’t score. But we’ve already published the news of a goal … awk-waaard …

It’s too much headache.

Now, I’m contenting myself with a simpler approach. When a person presses the right button, guess how long it will take to reach the server. Don’t start moving on the client until then. (Note: this is still sooner than waiting for a complete round trip). Server and client are kept (roughly) in sync, and the game is a little less responsive. C’est la vie.

20 thoughts on “The KISS rule, in practice

  • Yo, that’s what’s up truthfully.

  • maod says:

    I just played the new alpha (7.1). The player movement still appears a bit jerky, and the ball is skipping forward a lot when I kick it. Nevertheless, it feels better than it ever has.

    The weird thing is that the game “feels” right, but it doesn’t look right. When I kick a ball, it appears to go nowhere, then to skip forward, but after half a second or so, it’s travelling in a straight line in the same position that I would expect it to be. The visual glitches are especially bad when I do rocket kicks. On the other hand, the game seems quite good when I’m just dribbling the ball, although the player does still snap back by a very small amount every few seconds when travelling in a straight line.

    Also, I”m pretty sure that Haxball doesn’t predict the sound of a kick. You only hear the sound once the client receives the message from the server. When you ghost kick, for instance, you don’t hear the kick sound.

    • maod says:

      Question: are you adding a jitter buffer for updates from the server before they are processed by the client’s copy of the authoritative physics simulation? That is, are you holding game state updates for an extra little bit of time before displaying them on the client, not for the purposes of interpolation, but just to make sure that the game states are released to the simulation in a regular manner?

      I ask, because I still notice a teeny bit of popping back and forth when I move in a straight line.

      • Hi maod,

        First of all, I can’t thank you enough for bearing with me through this thorny problem. Your earlier comments inspired me to have another go, and the result is what you now see.

        To (try to) answer your question, no, the client does not buffer information as it comes in from the server. It is immediately processed and rolled forward with current velocity values until it reaches the time currently being simulated on the client, which is estimated at some lead time ahead of the server’s current time. The popping may be due to the fact that the lead time is an estimate, and can change slightly every frame — it’s based on the measured time of packets sent regularly to determine the latency with the server.

        As you pointed out, the lead time needs to be long enough so that the inputs reach the server in time to be processed (I don’t have any “hurry-up” feedback implemented right now). But also we want the lead time to be as small as possible. My current strategy is to make it equal to the measured latency of the last 10 packets (at 1 per second), averaged. Maybe it would be better for the lead time to be *stable* instead of as short as possible, using a high-water mark measure of measured packets instead of a running average. It would theoretically lead to greater errors in prediction of other players, but greater stability in terms of the amount of time that appears to pass between frames.

        Thoughts?

        • maod says:

          >To (try to) answer your question, no, the client does not buffer information as it comes in from the server.

          Ah okay, that’s good to hear then, because there’s room to play with.

          > Maybe it would be better for the lead time to be *stable* instead of as short as possible, using a high-water mark measure of measured packets instead of a running average.

          > It would theoretically lead to greater errors in prediction of other players, but greater stability in terms of the amount of time that appears to pass between frames.

          tl;dr: Yes, I agree with that. The prediction will be worse, but it will be stably worse. I think the latter is more preferable for humans.

          corollary tl;dr: Everything I’m saying about lead-time adjustment (how long outgoing client messages are sent in advance) could also be applied to the jitter buffer adjustment (how long incoming server messages are held before processed).

          I *strongly* suspect that this would result in a more enjoyable experience. I theorized in my last message that, “It’s better to have a slightly higher average lead-time than a jittery one.” And evidently, people have even done studies on this: http://www.alinenormoyle.com/research/normoyle14DelayAndJitter.pdf They describe situations in which small amounts of jitter can be as frustrating as large amounts of latency.

          Anyway, I would agree that you’d have to be very conservative in reducing the buffer size. You say you’re using a 1-second moving average; I think this is a good idea for the first few seconds that the player has joined, because you’ll need to rapidly find the lead-time. But after a while something more like a one-minute moving average would be better.

          The “simple binary congestion avoidance” that Fielder describes might be worth a look. http://gafferongames.com/networking-for-game-programmers/reliability-and-flow-control/. Basically, you need to find some way to set your high-water mark so that it conservatively lowers the lead-time approximation in the “good” times, and rapidly raises it during “bad” times, without being thrown off by a single spike now and then.

          Another thought: Generalizing the idea of a “hurry up” message, perhaps, on every tenth game-update that the server sends, the server could send an additional message that tells the client the margin by which he made or missed. So, in addition to a “hurry up,” message, the client also gets “you arrived on time :D” messages as well; but these aren’t separate message “types” or anything; it’s just an extra integer that the client can interpret for the purpose of more rapidly adjusting it’s lead-time (kind of like a tracer round in a machine gun belt :p). In any case, you should probably have some way of measuring what’s going on.

          Maybe it would be worth it to add some slider bars on the UI that would allow the player to fiddle with the client side prediction values. Not for release, but just for “debugging” purposes. I think that being able to alter the size of buffers on “both sides” of the information flow would help in visualizing what’s going on. You could also overlay the slider bars on top of a graphical history of lead-time hit margin, just so you can see how raising or lowering your high-water mark will affect game play. Just an idea if you’d think it would help.

          Lastly, I think that much of I’m saying about lead-time approximation (outgoing information) also applies to the jitter buffer (incoming information), because you’re dealing with two half-connections, not one whole-connection. The client needs to know how long it’s holding game updates in the jitter buffer before it processes and renders them, and it needs to try to make this duration as low as enjoyably possible. Like you posited, a stable buffer duration that is slightly higher is probably going to be better than a jittery one that is smaller on average.

          Also note that neither the jitter buffer nor the lead-time approximation need to be adjusted in multiples of the rate at which packets are sent.

        • maod says:

          Regarding implementation, these are just my thoughts and you obviously know way more about this than I, but what about two-step process:

          1. Make the simulation, prediction, and rendering module(s) so that they respond to dynamically resizable lead-approximation and jitter buffers. But don’t actually include any algorithm to dynamically resize the buffers. Do include a debug UI panel that will allow you to manually adjust them. This game will be playable, just like your current prototype, because it sends and reads updates to and from the server and updates the game state accordingly. Certain events within the simulation would be predictable (e.g., player movement). Other events (like goal scoring, team switching) would definitely not be predictable. You wouldn’t want to accidentally predict a goal.

          2. On top of all this, write a module that takes two input streams: the stream of the “hurry-ups/tracer round” messages that I described before, and the contents of the jitter buffer. Based on the history of these two inputs (that this module would store internally for however long it deems necessary) its function is to tell the game (i.e., the thing you made in step 1), how big the jitter buffer and the lead approximation should be, at all times.

          This is just sort of how I have this whole scheme arranged in my brain. Basically, I’m suggesting the construction of kind of a “virtual human player” module in step two. If you simply gave a human the game described step one, and made him fine tune the jitter buffers and lead approximator until his liking, he could probably do a good job in finding good values; it would just take a while to find the right combination, and he wouldn’t be able to dynamically readjust them while he plays.

          The point I’m trying to argue, though, is that the actual simulation (and prediction thereof) can be abstracted away from the network condition monitor/responder, at least for a simple game like this, so that you only have to focus on building one thing at a time. Specifically, the simulation/prediction *should* be able to operate uninterupted while its parameters (the buffer and lead approximation size) are dynamically modulated by the network condition monitor that has been built around the simulation.

          If that helps in breaking down a bigger problem into two smaller ones, then you’re welcome. Otherwise, forget I said anything :p

        • Happy Holidays, whatever you call it. If you don’t mind giving your mailing address to a stranger that you only know on the internet, will you send it to me at kalynskitchen AT comcast DOT net. I want to send you something.

  • maod says:

    > To correctly complete this idea, the server needs to apply inputs it receives as though they arrived in the past.

    Really? The server should not have to replay moves for anyone. It’s the client’s responsibility to make sure that his movement arrives before the tic is processed. If the client misses, then the server should just make up information for him and alert him that he needs to send his packets sooner. The client should respond to this notification by moving his simulation further ahead of time (while simultaneously predicting further ahead of time by the same amount).

    The server should just duplicate the last input it receives from the client if it doesn’t receive any information in time. I think this is the cause of “sliding” in Haxball. (Were you using an unreliable messaging protocol, the client could also send his inputs redundantly).

    • maod says:

      Also, the client side prediction must be perfect. Even doing it halfway like you’re suggesting will be noticeable, and few will want to play the game.

    • Hi maod, thanks for your thoughts. A few comments:

      > It’s the client’s responsibility to make sure that his movement arrives before the tic is processed
      It’s not feasible. The server runs 60 tics per second, so unless the latency is under 16ms, this will not be possible.

      > The server should duplicate the last input …
      Yes, I’m sort of doing something like this now. The client only sends out an input when it changes. If you press and hold RIGHT for awhile, then let go, then a RIGHT is sent now, and a NOTHING is sent later. No inputs are sent in the meantime. The server simply maintains the last received input from every client and applies them during every tic.

      Having said all that, the idea is quite interesting, and bears investigating. My strategy was rolling the server update forward until it matched the client’s *current* time (10 050 in the example) — perhaps it should be rolled even slightly more forward to account for the fact that our inputs will not reach the server in time. So in effect, our client is predicting the slight future instead of displaying the corrected present, and our client is showing the player what it expects the server *might* look like in a few moments time. So the player makes an input and sends it to the server, where it will be applied at the correct time (more or less).

      There remains the possibility of jitter as the predictions turn out to be false. I suppose it’s a trade-off that needs to be experimented with.

      • maod says:

        > It’s not feasible. The server runs 60 tics per second, so unless the latency is under 16ms, this will not be possible.

        Nononono, what I mean is that the client needs not just to send his move information, **but also a time that tells the server when this move information should be processed.** The client should always know his ping time, and he can also deduce the server’s current gametime from the constant stream of gamestate updates he receives.

        For example, if the client has a ping of 200 ms, then he can approximate that he is running 100 ms behind the server. Therefore, when the client receives a gamestate update for t = 5000, he should make a note of that and send the server a message that says “Here is my input for t = 5100” when he sends his next input. It’s the client’s responsibility to send that packet early enough so that the server gets it before the server processes the physics for t = 5100, because the server is authoritative and cannot rewind time for anyone.

        Of course, it can’t be assumed that the time to the server is strictly equal to ping/2. So, if the lead-time approximation of ping/2 is still too slow, and the movement information doesn’t arrive on the server at t = 5100, but t = 5125, then the server should respond with a “hurry up notification,” optionally telling the player how much he missed by (25 ms). The client’s goal is to adjust the lead-time so that his moves arrive JUST before the server processes them; that is, to minimize the lead-time without receiving hurry-up notifications. If the ping stays steady over time, then this is easy, but if there is jitter, then the client needs to make a safe assumption and increase his lead-time. It’s better to have a slightly higher average lead-time than a jittery one.

        Meanwhile, the client must predict ahead by the lead-time, because as soon as the client sends his move information, it must rendered on screen to the player by the client-side prediction. The lower the lead-time, the more accurate the simulation will be.

        > Yes, I’m sort of doing something like this now. The client only sends out an input when it changes. If you press and hold RIGHT for awhile, then let go, then a RIGHT is sent now, and a NOTHING is sent later. No inputs are sent in the meantime. The server simply maintains the last received input from every client and applies them during every tic.

        Oh, well that’s different. You’re talking about sending movement deltas instead of one input packet at regular intervals. What I meant is that, if the client doesn’t get his movement in on time, then the server should not rewind, but simply repeat whatever the client’s previous movement was.

        Nevertheless, the client can still send delta-movements in the same way, so long as the client also includes the time at which the delta-movement should be processed, and also that it keeps a history of its own move commands in case it misses and the server needs to make up information for it.

        Are delta movement commands really necessary though? The movement information that the client sends are so small anyway (literally, 5 bits for 5 buttons, most of the time).

        Also, another link of interest http://gafferongames.com/2016/03/07/ive-started-up-my-own-company/

        • I now understand completely. Thanks for having the patience and bearing with me. When I go back to try it again, I will definitely apply these ideas.

          Also, thanks for pointing out gaffer’s news — it’s good to have the option of retaining his services in our back pocket!

    • arizona car says:

      Websites we think you should visit…we like to honor many other internet sites on the web, even if they aren’t linked to us, by linking to them. Under are some webpages worth checking out…

  • hubeh says:

    I can’t see how delaying input on the client side is going to work at all, it’s absolutely necessary that a client reacts as soon as a key is pressed. Are these changes already live? The game atm is pretty awful movement wise as there’s a significant delay when moving.

    You say there’s an oversight in your strategy but this is pretty much exactly how haxball works. Client moves instantly locally, send timestamped move to host, broadcast move to other clients, host + clients rewind and apply move at correct position. Of course at pings 150+ this leads to jitter but this is the compromise you make, delaying client side inputs isn’t the answer and is only going to make the player impossible to control.

    I think you’re also exaggerating the consequences of high ping. In haxball you need a pretty high ping 200+ before the ball really starts teleporting all over the place, but why are you concerned about playability at these pings? If the ball ends up in the goal then jumps out again so what? If I have crap ping then tough, that’s what happens. Don’t sacrifice playability at normal pings for situations the game isn’t designed for anyway.

    I see your concern with the second problem but I think this is pretty easily solved by only maintaining n amount of past frames, that you’d have to have poor ping to be so far behind. If an update from a client comes in timestamped > n then its simply rejected. You wouldn’t apply a move timestamped anywhere near a second ago. If you’ve played haxball at ridiculous pings like 700+ you’ll have seen the effect where you move locally but are then dragged back to your original position.

    • Hi there,

      it’s absolutely necessary that a client reacts as soon as a key is pressed

      I thought the same thing, and that’s why I spent so long trying to get it right. I was doing the rewind thing at the clients, but not the server, and that’s why it didn’t work. I may yet go back later and try it again.

      dragged back to your original position

      That was the exact effect that was defeating my previous strategy. The client was always responsive but there was a constant dragging effect that erased the benefits of the responsiveness. It was equally unplayable.

      Don’t sacrifice … for situations the game isn’t designed for anyway.

      It’s a fair point. Firstly, at low pings, the effect isn’t bad (I don’t really notice it). So the game still feels responsive when there’s low ping. The targets we’re aiming for is something like this:

      < 100ms ping: Smooth and responsive
      100-200ms ping: Playable (maybe laggy, maybe jittery — currently leaning in favour of lag
      > 200ms: No guarantee

      We will aim to improve those targets if I go back and tackle the problem again.

  • Michael DiFranco says:

    That’s a huge bummer that it isn’t working right. I didn’t understand half of what you said, but there is just one question I want to ask you:

    Haxball seemed to have perfect client side predictions that went perfectly with what was happening on the internet (I have no idea how the creator pulled that off) Can’t you just look at the haxball source code and find out the creators secrets? I don’t wanna sound like I’m demanding. I’m just more curious about how everything works.

    • It’s a fair question.
      Admittedly I haven’t read the Haxball code yet, but from what I’ve read (and what others have told me), Haxball works by sending player inputs to all connected peers, AND simulating all interactions on the client. I think the host client regularly sends out an authoritative snapshot of all the positions.

      Haxball is perfect when you’re playing by yourself — all inputs occur instantly, on your machine. When other players get involved, it gets tricky: each client looks perfect for itself, and everybody else jitters. When there’s latency to the host machine, it gets worse: even your own player can jitter as the client adjusts for the authoritative positions.

      In HaxArena, the central server is the authority. For the time being (until I try to tackle it again later on), the client will try to simulate exactly what’s happening on the server, and that means delaying the inputs a tiny bit. At normal pings it’s not even noticeable. At higher pings there’s a noticeable lag, but I think that’s better than a responsive client that jitters terribly when the laggy server’s updates come in.

      • drfeli says:

        I think looking at the source code can help a lot. I got it if you need it.

      • Slow and steady is the best way to lose weight. Too many people go on radical diets and shed the pounds but then put it all on again when they come off the diet. Much better to eat properly and you’ll find you slowly lose weight and keep it off.

      • actually i like your comment bro but i love more graphic that why i love ps3 cause i play this consle from 1999 bro ^^ that’s the most thing that i love PS and i don’t know why ppl saying to me am fanboy whatever they call i don’t care and because i love metal gear solid my best game for ever and now become uncharted i play all of them its awesome exept uncharted 3 its damn great motion

Leave a Reply

Your email address will not be published. Required fields are marked *

ERROR: si-captcha.php plugin says captcha_library not found.