How to properly predict movement on a server authoritative game

I'll offer some advice, this by no means is a complete answer nor the only answer, but it may give you some food for thought.

Bear with me as I explain this, because although we are using two different network models, the ideas (really, input and synchronisation) are not that different between the two approaches.

Authoritative simulation and timing: Turns

I'm developing a hybrid RPG/RTS using the P2P lockstep network model. There is no authoritative server in this network design pattern. However, given all the necessary inputs from other clients, the output on each client is deterministic and definitive across all clients (with strict use of integer arithmetic in simulation calcs). Even in an authoritative client-server setup, we strive for this level of synchronisation, although the server often has to issue authoritative corrections to enforce this.

It's clear in P2P lockstep -- because it is serverless, very strict and leaves absolutely no room for discrepancies between clients -- that there is only one correct simulation outcome, per frame, even though it is not coming from any designated server, it is still the equivalent of your server's authoritative view of the world. This is the true state of the simulation.

On the other hand, to implement extrapolation, then from an MVC perspective, that will be a completely view(render)-side decision, and this has nothing to do with the true state of the simulation. It is just a pleasant illusion that may or may not be accurate. To derive this illusion, we'll need a record of several gamestates to integrate over, in order to arrive at our best possible guess of what the current position and orientation of the opponent's entity will be.

In my project, processing of the simulation works on a turns system (much like Age of Empires). Turns execute at 10fps (well, ticks per second, or tps), while rendering happens at 60fps. Turns (10tps) are what take player inputs (read that again). Render frames (60fps) then simply do interpolation between the states produced by each of those turns (10tps), using the turn state just calculated and the previous turn state calculated, which we keep available. (You could store three or more turns states to integrate over, for more accurate predictions.) Thus, you will store a history of turns (or gamestates associated with turns) to derive your extrapolations from.

I believe (???) Quake networking used something similar, i.e. a concept of turns which act as an essential basis for timing and processing. I could be wrong. All clients should be aware of which turn is currently in progress (whether via each other, or as informed by a server).

Sending & Applying Inputs

Regardless of whether you're using a client-server or P2P-lockstep approach, you should be sending nothing more than (1) booleans of whether or not the key / button was pressed, or (2) amounts by which mouse or analog stick was moved in each axis. On basis of that raw input only, you can perform the same logic across all clients and the server, or however your topology works.

If these inputs are, frame after frame, applied as deltas to the last known gamestate, across all clients (in my case of P2P lockstep) and all such gamestates remain in sync turn after turn, then all gamestates should continue to remain in sync, indefinitely.

And the packets in which these inputs are sent, is marked with a unique turn number as well as the sending client's ID. In this way, we can easily allocate to the correct turn & client on arrival.

Prototyping network programming models and concepts, easily

The easiest way to begin understanding these problems, is to experiment on them within the confines of your dev system. I suggest modelling the system within a single app or within a client app so you can instantiate multiple times against the same server running on your dev system. If you implement this in a layered fashion, using just asynchronous programming, you can later plug in lower-level network layer support (RUDP, TCP sockets, or even higher level libraries) I got a prototype running and syncing between clients within a few days.

This consists of nothing more than asynchronous programming, based on the concepts of packet loss and packet delay. I'm sure there are other concepts involved, or finer distinctions to be made (such as network congestion, for instance) but for my purposes these have helped enormously in getting a running, synced prototype going without touching any true networking code so far.

"1 step" into that direction, how can I make sure that they wouldn't just send a bunch of messages to tell the server to move into that direction and bypass the defined speed for the player?

Updates should indicate the current position, in terms of change from last server update (not to exceed max speed since last update, capped by an arbitrary time limit, say .7 seconds) and velocity vector(not to exceed max speed). The movement steps are then performed by the server timing(incorporating the 1/2 average RTT time delta) and applying a LERP with a small alpha value, varies by FPS say .05 for 60 FPS, as a nonlinear correction factor to allow a catch-up over time. The client will receive the new value from the server and adjust the client current position every step with a larger LERP alpha value of .1 the between the client current position and last server position + local applied changes since 1/2 average RTT before receipt of the update.

By setting the client adjustment higher than the server adjustment, the server and client will converge towards the servers version of position, while honoring client input and not allowing cheating via delayed false updates.

Consistent aberrations across multiple round trips indicate cheating since the client position must tend towards convergence.

Clients with consistantly high average round-trip-times > 200ms should be warned and dropped from the server, for FPS style games.

Rate Limiting

The packets should include a small timestamp or increasing packet number. Validation code on the server will time the arrival differences giving the number of elapsed seconds since the last packet, providing a means to rate limit the server from applying more than the maximum speed allowed.

Queue the packets and apply them in order, effectively delaying new commands until the queue catches up to real-time(you could even halt the client on the next server to client update). The time delay alone should discourage cheating.

The client and server should run the same code.

The client sends its state(position, velocity, firing, jumping, inventory delta...) to the server; where it is validated(collisions, distance since last update within possible range), applied to the server state, and sent back to the client.

In non-realtime or slower games like an RTS, time can be unwound and replayed with the updates in the course of a single server timestep or drawn out across several steps to allow animation to show the correction. This configuration enables the client to predict movement of non-local objects during times of packet loss or jitter.