RollbackPseudoCode.txt

Readme: In the following pseudo code, [] indicates a subroutine.
Sometimes I choose to write the subroutine inline under the [] in order to maintain context. 
One important fact about the way rollbacks are handled here is that we are storing state for every frame. 
In any real implementation you only need to store one game state at a time. Storing a game 
state for every frame allows us to only rollback to the first frame where the predicted inputs don't match the true ones.


==Constants==
MAX_ROLLBACK_FRAMES     := Any Positive Integer         # Specifies the maximum number of frames that can be resimulated
FRAME_ADVANTAGE_LIMIT   := Any Positive Integer         # Specifies the number of frames the local client can progress ahead of the remote client before time synchronizing. 
INITAL_FRAME            := Any Integer                  # Specifies the initial frame the game starts in. Cannot rollback before this frame.

[Initialize Variables]
    local_frame   := INITAL_FRAME                       # Tracks the latest updates frame. 
    remote_frame  := INITAL_FRAME                       # Tracks the latest frame received from the remote client
    sync_frame    := INITAL_FRAME                       # Tracks the last frame where we synchronized the game state with the remote client. Never rollback before this frame.
    remote_frame_advantage := 0                         # Latest frame advantage received from the remote client.

[Store Game State]
    Stores the game state for the current frame 
    
[Restore Game State]
    Restores the game state to the frame set in sync_frame

[Update Input]
    Predict the remote player's input if not available yet.
    Setup the local player and remote player's input for use in [Update Game] 
                
[Rollback Condition]
    local_frame > sync_frame AND remote_frame > sync_frame      # No need to rollback if we don't have a frame after the previous sync frame to synchronize to.

[Time Synced]
    Let local_frame_advantage = local_frame - remote_frame                                   # How far the client is ahead of the last reported frame by the remote client
    Let frame_advantage_difference = local_frame_advantage - remote_frame_advantage          # How different is the frame advantage reported by the remote client and this one.
    local_frame_advantage < MAX_ROLLBACK_FRAMES AND frame_advantage_difference <= FRAME_ADVANTAGE_LIMIT     # Only allow the local client to get so far ahead of remote.

Start Program:
    [Initialize Variables]

    loop:

    [Update Network]
        Let remote_frame = latest frame received from the remote client
        Let remote_frame_advantage = (local_frame - remote_frame) sent from the remote client

    [Update Synchronization]
        [Determine the sync_frame]
            Let final_frame = remote_frame                                          # We will only check inputs until the remote_frame, since we don't have inputs after.
            if remote_frame > local_frame then final_frame = local_frame           # Incase the remote client is ahead of local, don't check past the local frame.
            select frames from (sync_frame + 1) through final_frame and find the first frame where predicted and remote inputs don't match
                if found then
                    sync_frame = found frame - 1        # The found frame is the first frame where inputs don't match, so assume the previous frame is synchronized.
                else
                    sync_frame = final_frame            # All remote inputs matched the predicted inputs since the last synchronized frame.

        if [Rollback Condition] then
            [Execute Rollbacks]
                [Restore Game State]
                select inputs from (sync_frame + 1) through local_frame     # Use all the inputs since the last sync frame until the current frame to simulate
                    [Rollback Update]
                        [Update Input]
                        [Update Game]
                        [Store Game State]
                                            
    if [Time Synced] then
        [Normal Update]
            Increment local_frame
            [Get Local Player Input]
                Read the joystick/pad/keyboard for the local player and store it, associating it with local_frame
            [Send input to remote client]
                Send the input and the local_frame to the remote client so it arrives asap.
                
            [Update Input]
            [Update Game]
            [Store Game State]
    goto loop

End Program

When you initialize the variables, Player A will set their initial frame to 3, and Player B will set their initial frame to 1. Note that Player A cannot have a initial frame less than 3, and Player B's initial frame is less than that. Then they will give their initial frame to each other for them to save it to their remote_frame variables.

When you first invoke [Update Network], Player A will get Player B's local_frame and vice-versa. because [Initialize Variables] and the first [Update Network] is ran on the same frame, the local_frame will equal to the initial frame, so

Player_A.remote_frame = 1, and Player_B.remote_frame = 3.

On the very first invocation of [Update Synchronization] [Determine the sync_frame], Player B set its final frame to Player A's frame, which is 3. Then checks if Player A's frame has a greater value than its own. Because Player A is on frame 3, and Player B is on frame 1, Player B will set the final frame to check to 1, likewise, Player A will set the final frame to Player B's frame, which is 1. Since 1 is not greater than 3 the final frame stays to 1.

Now it's time to check for desync. Now, because it has never been synced before, both player's sync_frame is 0. Both Player's will find that the very first frame is not synced, Player A will Rollback to the first frame.

Ah thank you, I kind of understand. I used frame 3 and 1 arbitrarily. This differs depending on the ping to the players. But from what I gather from this both players need to be able to accurately assume the remote player's current frame?

If the ping is 30 and we're updating at 60fps then we can assume it takes about a single frame for the packet to reach the remote player. If player A is on frame 2 when player B sends its initial packet, this means now player B is on frame 2 and player A is on frame 3 when the packet is received. So player A has to realise that it took roughly 15ms or about the length of a single frame for that packet to arrive ?

So before the game realistically even starts to both players have to determine ping to eachother and guess what frame the remote player is on by the time they receive the initial frame?

I'm slightly confused about the initialization process.

It seems I baked in an assumption into the pseudo-code without actually realizing it. I always assumed the initial frame would be the same for both clients. Looking back at this, if I had just set it to 0 it would have caused less confusion. I wrote "the initial frame the game starts in", but it should be something more like "the initial frame the game starts in, which is the same value on all clients"

I'm slightly confused about the initialization process.

It seems I baked in an assumption into the pseudo-code without actually realizing it. I always assumed the initial frame would be the same for both clients. Looking back at this, if I had just set it to 0 it would have caused less confusion. I wrote "the initial frame the game starts in", but it should be something more like "the initial frame the game starts in, which is the same value on all clients"

Yes that is correct. We can not assume that both peers are going to have the same initial frame.

if you dont have the same initial frame. frame advantage estimates would be all screwed up. it should be assumed that the clients start at the same frame. im pretty sure one client wont even progress and get stuck if you dont
.

if you dont have the same initial frame. frame advantage estimates would be all screwed up. it should be assumed that the clients start at the same frame. im pretty sure one client wont even progress and get stuck if you dont
.

That depends on the implementation though of how big the frame advantage is. But the most important thing to remember is they have to calculate what their initial frame is . Myself as a client on frame 0 can not assume that the remote client is also on frame 0.