Prediction

gistfile1.txt

Here's the basic loop. We have two sides, which I'll call the "encoder" and "decoder".

The encoder sends snapshots. The decoder receives them and sends ACKs back. We use
delta coding, so the encoder needs to make sure that the decoder has received the
data it's delta-ing *from*. What this boils down to is that the encoder always
codes relative to the most recently ACKed frame: the encoder knows all frames
(conceptually - in practice it can throw away old frames once a new frame has been
ACKed), and we know the decoder has that particular frame since it's acknowledged it,
so both sides know the reference frame. For something to ever be useable as a
reference frame, the decoder side must have acknowledged receipt.

As long as both encoder and decoder only work from data that was either present
in the agreed-upon reference frame, or is present in the parts of the current frame
that have already been sent, they will stay in sync. I think this isn't controversial
so far.

Now what I do is store some extra state per-frame along with the world simulation
state. That state follows the same rules - i.e. the data we store either comes from
*that* frame, or from an earlier reference frame (i.e. an even earlier frame that the
encoder and decoder agree was received).

That's where the velocity comes from. After decoding a frame B, we compute what its
effective velocity was relative to its reference frame A. Now if (and only if!) B
later gets used as a reference for some new frame C, we make use of the velocity
estimate we computed from (and stored along with) B.

Example timeline: (ref frame -1 is agreed-upon "initial state" of sim)

 t         Encoder                                    Decoder
  
 0  Send frame 0 (ref = -1) 
 1  Send frame 1 (ref = -1)
 2  Send frame 2 (ref = -1)
 3  Send frame 3 (ref = -1)                     Receive frame 0 (ref = -1), send ack 0
 4  Send frame 4 (ref = -1)
 5  Send frame 5 (ref = -1)                     Receive frame 2 (ref = -1), send ack 2
 6  Recv ack 0; send frame 6 (ref = 0)          Receive frame 1 (ref = -1); stale, drop it.
 7  Send frame 7 (ref = 0)                      Receive frame 4 (ref = -1), send ack 4
 8  Recv ack 2; send frame 8 (ref = 2)          Receive frame 5 (ref = -1), send ack 5
 9  Send frame 9 (ref = 2)                      Receive frame 6 (ref = 0), send ack 6
10  Recv ack 5; send frame 10 (ref = 5)         Receive frame 7 (ref = 0), send ack 7
11  Recv ack 6; send frame 11 (ref = 6)         Receive frame 8 (ref = 2), send ack 8
12  Recv ack 7; send frame 12 (ref = 7)         Receive frame 9 (ref = 2), send ack 9
13  Recv ack 8; send frame 13 (ref = 8)         Receive frame 10 (ref = 5), send ack 10

We only ever use the velocity (and other derived state) for coding if we got an ACK from
the decoder side for that frame. Frame 3 never arrives at the decoder, and it never gets
used as a reference frame. Frame 1 arrives out-of-order, and it never gets used as a
reference frame either. Frame 4 arrives just fine at the decoder, but the ACK packet
doesn't make it back to the encoder, so frame 4 never gets used as a reference frame
either. I don't have an example for ACKs arriving out-of-order at the encoder here, but
it's trivial; since you only care about the most recent ACK you just drop it.