(This post turned into a bit of a rubber-ducking session, apologies for that)

I'm working on a first-person game I've wanted to create for a long time. I'm starting by designing the general architecture, which includes the multiplayer architecture.

I'm very keen on the server being 100% authoritative, such that the client only sends inputs. This is easy. I also want to have client prediction. This is also easy. The problem comes when trying to reconcile what the client predicted against what the server calculated.

Most articles (including the venerable Gabriel Gambetta one) discuss client prediction in combination with rollbacks and resimulation. The issue is, my game is intended to be physics-heavy and I don't want to deal with the cost of resimulating potentially many frames in a single tick, not to mention I'm working with Godot and there's currently no way to manually step the physics engine. I don't care about super precise shooting mechanics or some general desync.

My current rough (untested) plan is to have all entities store a buffer of previous states. The server frequently updates each client with what their current “time” value is based on the server's time + halfRTT. By the time the message arrives, on average, the value the server sent should approximately match the server's wall clock time. The client now has a way to record state against the server's time. Then when the server sends a state update to the client, it includes the current server time along with the state. When the client receives the message, it can check back through its stored entity states to find the nearest on to the given server time. It can then compare that against what the server sent, and if it's close enough, ignore it.

The great thing about doing it this way is that the entity can look at an arbitrarily large range of stored states surrounding the time value received from the server. If any of them match the server state or are close enough, we can ignore the server state. This means we can make the predictions arbitrarily forgiving.

But this is where it gets tough. When a server message arrives on the client, the client is already halfRTT ahead of the server. It looks back through its history of previous states and finds the appropriate one that should be close to the server's state at the point it sent its message to the client. If they match, good. If not, what do we do? Well, naively, you could just set the client state to the server state. The problem is, now you've forced the client entity into the past. When the next server update arrives, the client will once again mismatch and be forced to snap to the server states. At this point, unless the player stops moving for a while, you'll be stuck in an endless loop of forcing predicted state back to server state.

I've been wondering whether I could “nudge” the client state towards the server state. Something like this:

Vector3Double positionDelta = State.Position - recordedEntityState.Position;
float positionNudgeRate = 0.01f;
Vector3Double newPosition = Vector3Double.Lerp(recordedEntityState.Position, serverState.Position, positionNudgeRate);
State.Position = newPosition + positionDelta;

That might work. It assumes the prediction was mostly correct. I believe it has the potential to put clients inside walls (and thus subsequent recorded states could be wildly inaccurate if the physics spits them out the other side), but I think it will correct itself over time. As long it's “eventually correct” it should be ok.

For boolean values (like whether the player is holding a weapon currently) it's not such a big deal. We can snap to the server state without too much risk of glitchy behaviour because the value is unlikely to change again soon.

I know most RTSes and MMOs don't do client prediction, but they're also not usually high-speed games and tend to be have point-and-click interfaces. I find it hard to believe that very large FPS games like Star Citizen would be resimulating in the event of a misprediction (the cost and complexity!!), yet they clearly do client prediction.

Are there any resources I could look at for doing client prediction without resimulating? Or if anyone has any clever suggestions I'd love to discuss. Perhaps I should run the client in the past? I'm not sure, I can't get my head around how that would work. I know I've done a pretty rough job of explaining my plan and maybe what I want simply isn't possible but any thoughts welcome.

Yes, it is absolutely possible to just run forward extrapolated entities, without re-simulation.

There are two options; one is to simply replicate all physical state (position, velocity, orientation, spin) and forward extrapolate all of them each frame. You won't simulate the objects at all then, just display their predicted positions.

The other option is to apply forces/torques to make the objects you simulate/display “trend towards” the forward extrapolated positions, but only run one simulation step per frame. And when the object is “too far” from where it's supposed to be, you will want to teleport/snap it to where it's supposed to be. This option is probably closer to what you suggest above, except you nudge the client towards the forward-predicted state.

Which of these models works better for you, depends on your specific level design and gameplay.

@hplus0603 Thanks, that's helpful! I now realise that what I was describing was essentially extrapolation of positions etc.

I've done a lot more thinking, flow-charting and searching for resources. The Source Multiplayer Networking document seems to indicate that predictions are somehow corrected without resimulating, but it's pretty vague, and the related Prediction page says it resimulates all commands since the correction. The docs for the UDK talk about resimulating inputs on the client in the case of a misprediction. Glenn Fiedler doesn't say much about misprediction corrections in his GDC talk about multiplayer architectures or his related article on state synchronisation (which turns out to be my planned architecture), but he's pretty specific about resimulating inputs in his article describing what every network programmer should know. We all know that the Gabriel Gambetta one describes resimulating. And finally there's the well-known Overwatch and Rocket League GDC talks, which both describe resimulating, and the Halo Reach GDC talk, which describes giving the client authority over its own player's position.

I'm starting to think there's simply no way to do client prediction and correction of a player-controlled, server-authoritative rigidbody without resimulating the physics scene. If we detect a misprediction and snap the player to the server's state, we'll force the client to go back in time. It will no longer be ahead of the server and will continuously mispredict until the player stops moving, at which point the client's predictions will eventually line up with the server's state again and it can again be considered ahead of the server.

If, instead of snapping the player's current previous position, we take the offset from their previous predicted position to the current predicted position and add that to the server's given position, that allows us to remain ahead of the server in our predictions, but the predictions are now likely to be wildly inaccurate. Since we're just taking the position offset from an old predicted position to the latest predicted position and applying that to the server's given position, we don't actually simulate what happened in between. Imagine we walk through a door and turn left down a hallway. If the door was actually closed on the server, it would force us back to the point where we would have run into the door. We then apply our “prediction offset”, which might put our player outside the level. At this point they might begin falling, and no matter how many times the server corrects our past state, we would never fully return to inside the level because we always add our “prediction offset” onto what the server gives us.

Maybe I'm trying to achieve the impossible here by having client prediction and correction without resimulating inputs while maintaining full server authority. Actually it's very easy, but only for non-locally-controlled entities (in other words, for all entities other than the locally-controlled player entity). I'd love to hear more suggestions if anyone has them.

My backup plan is to make the client authoritative for its own entity's position/rotation/velocity, but do validation on the server. I'd rather avoid this though.

Clonkex said:
I'm starting to think there's simply no way to do client prediction and correction of a player-controlled, server-authoritative rigidbody without resimulating the physics scene.

Unless they're lockstep and deterministic, you will ALWAYS have differences between the systems. That means you will ALWAYS need to do something to handle it.

What you do is up to you, and there are many options as mentioned here. You might rewind and repredict which gives better results in many ways. You might nudge them toward the authority's spot. You might snap or rubber-band. In one game where we weren't as concerned about identical displays, we'd have a local walk/run animation to get them into place. Some games will give preference to what was viewed on clients in certain results, some games even go so far as showing the victor's simulation to everyone as a replay rather than the server's simulation, just so everyone sees the “winning” view.

It really depends tremendously on the game. A high-precision shooter like CS:GO is going to be different than a turn-based game like Hearthstone, which will be different from networked RPG like Stardew Valley, or an RTS or a sport simulation, or a platformer, etc. In the high-precision shooter you've got to do everything imaginable to give precisely the same results to each player, including resimulating and doing all kinds of lag compensation. In a game like Stardew you've got things moving and bouncing around, but if one goes to the left around a tree and the other goes to the right around the tree, nobody cares. What works best for your game will be unique to yours.

frob said:
Unless they're lockstep and deterministic, you will ALWAYS have differences between the systems. That means you will ALWAYS need to do something to handle it.

I know. For server-controlled entities (including other players), that's easy. Interpolate or extrapolate. But for the player, I'm trying to figure out how to reconcile server states against past client states. Maybe it's impossible without resimulating but that's what I'm here to find out (hence the thread title).

frob said:

What you do is up to you, and there are many options as mentioned here.

I only see two options, and neither are favourable. Resimulation is off the table because it's too expensive, and client-authoritative player movement isn't ideal, though as I say, it's my fallback plan.

frob said:
You might nudge them toward the authority's spot. You might snap or rubber-band.

The issue is, this is what I want to do, but I don't see how (though I initially thought it would work). If I nudge or snap the player towards the server's given position, that nudges or snaps them into the past. They're no longer predicting and could be stuck infinitely mispredicting. If you see some obvious way around this, please let me know! I may be unable to see the forest for the trees.

For some context, my game is intended to be a space FPS. You can walk around ships, collect stuff, interact with things, etc. Maybe I'll get bored and create something else but my game designs generally involve these ingredients: FPS, multiplayer, non-competitive. Even if I change the direction I'm going, I'll still always want a relatively straightforward and general network architecture. I don't care about doing lag compensation for shooting or if there's some MMO-style glitchyness (such as other players or objects rubber-banding), but I do very much care about the player being able to move freely and reliably even at higher pings, and I care about being server-authoritative.

I think the answer there is a tolerance for when it is close enough.

For example, Unreal has a tolerance which comes along with their floating point number packer that goes to two decimal digits. You can adjust it for anything in Unreal by providing a packing function.

For less critical physics in some games each might control their own and then sync up with nudges at completion. For an RPG style if exact replication is not needed this can work really well.

In one series I worked on, we simply called a MoveTo() function that triggered pathfinder navigation to the destination. MoveTo() had a tolerance built in. The various objects would use their default motion action to get in place, or slide in the worst case. Since the Role Playing nature was just running around the world in a friendly environment the minor difference was unimportant.

Hmm. I absolutely intend (and always intended) to allow “near enough is good enough”, but the issue is when near enough isn't good enough, I need to a way to get back to “good enough”. I just can't see how it can be done. If I decide that the player has drifted too far from the server's state, I can't just snap them to that state. That state was intended for the player in the past so if I snap them to it in the present, I force them back to a position from the past. The server won't know that I changed the client position (nor should it; it's the Source of Truth) so it will continue simulating the player as if nothing happened. To the player, if they were running forwards (for instance) this would look like they suddenly reversed some distance (that's fine, I can interpolate and so on to hide those corrections).

The issue is, and I know I keep saying this but it's important, the player is now in the past. They're predicting movements that are now in sync with the server by wall clock time, when they should be ahead of the server. If they stop moving, they'll get dragged forwards by the server's corrections (since the server won't know the player stopped pressing forwards until halfRTT later). But you know what, maybe this is ok. I try to plan for players being on 100-200ms because I don't enjoy playing games that work poorly on higher pings, but maybe the mispredictions will be uncommon enough to not make this a problem. It would rarely be an issue on lower pings so maybe it will be ok overall.

I guess I'll set it up and try it out. The reason I haven't tried it so far is because I was hoping for someone to say “this game did it the way you're thinking” and then I would have some confidence that it could work. Or if my plan was bad, I was hoping someone would say “nah do it this tried-and-tested way instead”.

Thanks for helping me out btw, I know it sounds like I'm complaining but I appreciate the help a lot!

Clonkex said:
there's simply no way to do client prediction and correction of a player-controlled, server-authoritative rigidbody without resimulating the physics scene.

So you have to change the problem statement!

You could make the client authoritative for the client physics body state. A bunch of Unreal Engine based games do this, and it's largely fine – you can reject “obviously bad” updates that break the limits of what the simulation will allow.

The main challenge comes when you have players interacting with each other. It's essentially not possible to make one player block another, while keeping this model. or, more accurately, the two players will see different things, including player A being blocked by the replica of player B while player B doesn't see them at the same place. And the client will choose to enforce being blocked, even though the server wouldn't. And you can't let player/player blockage happen on the server.

There are plenty of cases where this is good enough. Any MMORPG where “select target and perform action” is what matters, rather than physical contact, can do this, for example. In fact, MMORPGs may not even want player/player blocking, because that allows griefing where players can prevent other players from getting to important places.

hplus0603 said:
So you have to change the problem statement!

If it turns out that what I want isn't possible, sure. But until I've proven to myself that it's not possible, I'll keep trying to find ways to make it work. I'm pretty good at problem-solving these days, so long as I can fully understand the problem (which I didn't at the time of the OP).

Certainly I could make the client authoritative, and I understand that it would make some situations wonky (pushing against other players, as you say). However the original point of this post was the find out if I could do client prediction with a fully authoritative server (although I was struggling to describe what I wanted at the time so I wasn't super clear on that point).

I've come back to my original idea of correcting the player's position by the delta of the previous/recorded position and the server's given position. I now believe it might work, although with some caveats that will require testing and some special-case handling to make sure players can never be permanently stuck outside the world (or their ship). I'm implementing it now and I'll report back when I've tested it. If it doesn't work, I'll look into making the client authoritative of its own position, though that comes with its own difficulties (such as poor interactions between the player and other physics objects, and the fact that the server is no longer the Source of Truth™ and now you have an architecture that in other software domains would be considered really bad).

if I could do client prediction with a fully authoritative server

And, to be clear, if you're OK with re-simulating on correction, then you can do this! (Your initial question actually qualified this as “without re-simulation,” so it's still true that, as stated, it's not possible.)

You kind of get to pick any two :-) Server authoritative, Client predicted, No resimulation.

correcting the player's position by the delta of the previous/recorded position and the server's given position

In case the client is accelerating, braking, or turning, then this won't give you a perfect correction. There's also still the problem that you have to re-simulate at least one step, because the predicted correction position might be inside a wall or something. One option is to decide on this position, then sweep the players collision proxy along a line segment made up by current/predicted positions, and then stop the closest you can get.