Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
@HeatXD
Copy link

HeatXD commented Oct 19, 2020

Hey thanks for the pseudo code!
I've got one question about it tho, at line 49 it says:

if remote_frame > local_frame then final_frame = remote_frame # Incase the remote client is ahead of local, don't check past the local frame.

Shouldn't it be:

if remote_frame > local_frame then final_frame = local_frame

if you don't want to check past the local frame?

Loading

@Brassens
Copy link

Brassens commented Oct 28, 2020

As mentionned above, l49 doesn't do anything as is

Loading

@rcmagic
Copy link
Author

rcmagic commented Oct 28, 2020

Hey thanks for the pseudo code!
I've got one question about it tho, at line 49 it says:

if remote_frame > local_frame then final_frame = remote_frame # Incase the remote client is ahead of local, don't check past the local frame.

Shouldn't it be:

if remote_frame > local_frame then final_frame = local_frame

if you don't want to check past the local frame?

Yes this is what it should be. I went ahead and made the correction. Thank you!
https://gist.github.com/rcmagic/f8d76bca32b5609e85ab156db38387e9/revisions?diff=split

Loading

@bmarquismarkail
Copy link

bmarquismarkail commented Jan 19, 2021

I am confused by l46 and l57, as it looks like both is a declaration of [Process Rollbacks]. is l57 a separate method, or is it intended to execute [Process Rollbacks] twice?

Loading

@HeatXD
Copy link

HeatXD commented Jan 19, 2021

I am confused by l46 and l57, as it looks like both is a declaration of [Process Rollbacks]. is l57 a separate method, or is it intended to execute [Process Rollbacks] twice?

I think l46 is a subroutine containing the [determine sync frame] and the the [process rollbacks ] subroutines. I think it was meant for some context that there might be rollbacks happening in this subroutine. that's at least how I've done it in my implementation

Loading

@rcmagic
Copy link
Author

rcmagic commented Jan 19, 2021

I've renamed the sections to be more clear. Thank you for pointing out the issue!

I am confused by l46 and l57, as it looks like both is a declaration of [Process Rollbacks]. is l57 a separate method, or is it intended to execute [Process Rollbacks] twice?

I think l46 is a subroutine containing the [determine sync frame] and the the [process rollbacks ] subroutines. I think it was meant for some context that there might be rollbacks happening in this subroutine. that's at least how I've done it in my implementation

I've renamed the sections to be more clear. Thank you both for raising the issue.

Loading

@nicolestahl
Copy link

nicolestahl commented May 24, 2021

I duplicated this as closely as possible, but I am encountering extreme desync glitches where the remote player seems to be getting many many more updates than they should. I have written a 100% homebrew rollback netcode that works significantly better in the same engine (i'm only saying this to prove that my save state system works) but my custom netcode also has desyncs (but its more like 1 frame in 300 is desyncing rather than every single possible frame). I don't know what I'm doing wrong. Here is my code https://pastebin.com/PPzNjJnM

I know some of the things I do here have bad time complexity such as iterating over lists, but the fundamental logic in the code is completely broken. Any help would go a long way for me.

EDIT: I wasn't setting the predicted_input value to be equal to remote_input after rolling back a frame, which caused a lot of strange problems. Now, I am dealing with a glitch where the time is able to get dramatically out of sync (one client is getting way behind the other)

EDIT 2: Setting the rollback frames and the max advantage to be 5 and 3 respectively (from 30 and 6) seems to have got my game in sync. I tested with two bots spamming a completely random input every frame and every single action was in sync. I've been trying to write rollback netcode since February, pouring hundreds of hours into my own (malfunctional) homebrew attempts, and this github page might have been the first thing to actually help me.

EDIT 3: I currently have everything up and running, but my game has an issue (based on this code) where one client can get really ahead of the other. It feels like there are one-sided rollbacks where one person has 0-1 rollbacks and the other has 7-10 (max rollback set to 10) as if the maximum advantage frames is being ignored. Is this a known issue with this pseudocode?

FINAL EDIT: The way that line 44 is written confused me at first, but now that I'm correctly sending the frame advantage remotely my rollback netcode is 100% functional. it's so beautiful it took me soo long to get this to work T_T

Loading

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment