Fabien Sanglard's non-blog
Quake Engine code review (3/4)
March 9th, 2009
Keys to life are running and reading
Here is a very usefull article by John Carmack with a few words about prediction.
An other article (archive) by Valve describing Half-life engine (as Half-life is using Quake engine, it's worth reading).
Prediction is probably the hardest, the least documented and the most important piece of Quake World Engine. The goal of the prediction is to beat latency, namely compensate the delay it takes for the medium to transmit informations. This is done on client side, the process is called "Client Side Prediction", there is no Lag Compensation technique on server side.
So gamestate is latency/2 old. If we include the time to sent the command, we have to wait a round trip (latency) to see the result of our actions:
The key to understand Quake prediction system is to understand how NetChannel populate the "
frames" variable (an array of
Every command sent to the server is saved in
frames, along with the
senttime, at index
When the server acknowledge the reception of the command via
sequenceACK, we can retrieve the sent command and calculate latency:
latency = senttime-receivedtime;
At this point, we have the world the way it was a latency/2 ago. On a NAT latency is fine (<50ms) but on Interet, it's huge (>200ms) and prediction have to be done to simulate the world right now. This is done differently for local player and other players
For local player, latency is pretty much reduced to 0, by extrapolating what will be the server state. This is done by using the last received state from the server and play all commands sent since.
The client hence predict what will be its position on the server at t+latency/2.
From a code perspective, this is done in the
CL_PredictMove method, first Quake engine decide the sentime limit for playable commands:
cl.time = realtime - cls.latency - cl_pushlatency.value*0.001;
cl_pushlatency is a cvar set on client side, equals to minus the client latency in milliseconds. Hence we can pretty much conclude:
cl.time = realtime .
Then every other players are turned solid via
CL_SetSolidPlayers (cl.playernum); (so collision can be tested) and commands sent since the last received state are played until:
cl.time <= to->senttime (collision are tested each iteration via
For other players, Quake engine doesn't have the "commands-sent-but-not-yet-acknowledged" so extrapolation is used instead. Starting from the last known position,
cmd are extended to predict used position. Angle rotation are not predicted, only position.
Quake World also takes into account other player's latency. Each client's latency is sent along with worldupdate.
The prediction and collision code can be summarized as follow:
CL_SetUpPlayerPrediction(false) CL_PredictMove | /* Local player is moved */ | CL_SetSolidPlayers | | CL_PredictUsercmd | | PlayerMove | Interpolate linearely CL_SetUpPlayerPrediction(true) CL_EmitEntities CL_LinkPlayers | /* Other players is moved */ | for every players | | CL_SetSolidPlayers | | CL_PredictUsercmd | | PlayerMove CL_LinkPacketEntities CL_LinkProjectiles CL_UpdateTEnts
This part is complicated because not only Quake Work perform predictions on players but also it has to perform collision detection on predictions.
The first call do not perform any prediction, it only setup other players as they were received from server (so in the past at t-latency/2).
This is where the local player movement is performed:
- Orientation is not interpolated and is full realtime.
- Position and velocity: all commands sent until now (
cl.time <= to->senttime) are applied to the last position/velocity received from the server.
More on Position and velocity update:
- Other players are first turned solid (in there last know position, set in
- Engine loops against sent commands, checking for collision and predicting the position via
CL_PredictUsercmd, collision against other players are also tested.
- Resulting position and velocity are stored in
cl.sim*, this will be used later for POV setup.
In the second call, other players position are predicted at the current time on server side(but no movement is performed yet). Position is extrapolated with the last known commands and last know position.
Note: There is a bit of a problem here: Valve recommendations (for
cl_pushlatency), end up having local player predicted at t+latency/2 on server side. However, other players position is predicted at t on server side. Maybe
cl_pushlatency best setting for QW was -latency/2 ?
Here is where visibiliy edicts are generated. They will feed the rendered.
- CL_LinkPlayers : Other players movment is performed, other players are turned solid in turn and collision detection is performed against their predicted position.
- CL_LinkPacketEntitiesPacket : entities from last state received from server are predicted and linked to visibility edicts. This is why the missile you fire is lagged.
- CL_LinkProjectiles : Nails and stuff
- CL_UpdateTEnts :Standard Light beams and entities update.
Return to main Quake Source Exploration page.