Server-authoritative multiplayer without network-wide rollback about netfox

[bryanmylee]

I think I've figured out the issue somewhat.

Verified state is sent from server to client at a consistent tick rate. This works fine if input messages are also received on the server at a consistent tick rate to be processed before each server-to-client tick.

There's no issue if server-to-client state sync messages are inconsistent since each message has a tick number attached and the client verifies the state by looking into history.

However, if client-to-server input messages have any latency variance, it causes the server's state computation to be incorrect because the inputs between client and server mismatch. If server-to-client state sync messages are sent in this period, we run into the sync issues mentioned before.

I'm going to test two solutions:

1. only send server-to-client state sync messages if a new input message is received. I already track a _latest_received_input_tick for the tick number of server-to-original-client sync messages. I'll add a _latest_confirmed_input_tick to only send messages when _latest_received_input_tick increments.
2. perform a localized rollback on the server for a player x whenever inputs for x are received. Unlike the current implementation where rollback occurs across the entire game state, this should minimize the cascading effects of having one player rollback the entire game.

[bryanmylee]

@elementbound Please correct me if I'm wrong here, my understanding of prediction and rollback is surface level at best so I might have made some mistakes in the description.

[bryanmylee]

My current implementation strategy is:

For an originating tick k on client:

1. before_tick_loop, for all clients x, gather input for control Ax(k)
2. on_tick, for all clients x, apply Ax(k) to state Sx(k) to produce predicted state S*x(k+1)
3. after_tick_loop, for all clients x, send Ax(k) to server

For the server handling the request at tick k1:

1. for any originating tick j, server receives input Ax(j) and treats it as Ax(k1)
2. on_tick, for all clients x, server applies Ax(k1) to S(k1) to produce S(k1+1)
3. after_tick_loop, server broadcasts S(k1+1) to all players x

On all peers handling the response at tick k2:

1. before_tick_loop, client x receives S(k1+1)
2. on_tick, client x reads node states Sy(k1+1) for all nodes y in S(k1+1)
3. on_tick, if x != y, treat Sy(k1+1) as confirmed Sy(k2)
4. on_tick, if x == y, check S*x(k1+1) against Sx(k1+1)
5. on_tick, if k1+1 < k2 - Q, tick is too late and we have no history, ignore
6. on_tick, if S*x(k1+1) is_approx_equal Sx(k1+1), confirm S*x(k1+1) as Sx(k1+1)
7. on_tick, otherwise, confirm Sx(k1+1) and resimulate S*x(k1+2..k2+1) with Ax(k1+1..k2)

[elementbound]

Thanks @bryanmylee, much appreciated!

One of my concern is coding an older input as current on the server ( e.g. taking Ax(t=0) as Ax(t=2) ). Imagine the following timeline:

1. P1 sends input A1(t=0) to move right, updates state S1(t=0) = (1, 0)
2. P1 sends input A1(t=1) to move right, updates state S1(t=1) = (2, 0)
3. Server receives input A1(t=0), uses as current input A1(t=2), broadcasts state S1(t=2) = (1,0)
   1. Let's say P1 is still going right, sends input A1(t=2), updates state S1(t=2) = (3, 0)
4. Server receives input A1(t=1), uses as current input A1(t=3), broadcasts state S1(t=3) = (2,0)
   1. Let's say P1 is going north, sends input A1(t=3), updates state S1(t=3) = (3, 1)
5. P1 receives state S1(t=2) = (1, 0), local state for t=2 is (3, 0), no match, let's do a course correct
6. P1 receives state S1(t=3) = (2, 0), local state for t=3 is (1, 1) after course correction, no match, let's do a course correct

So if I'm right, we would bake in the delay into the simulation, since we get the same state, but with some delay. I think this can be solved by retaining the original time code received from the client, and either:

1. Apply the client's old input on the simulation's current state, and hope it's not too inconsistent to glitch out
2. Rewind the game state and apply the player's input

The second option has a "rollback lite" sound to it, while the first one might break down in more complex scenarios with multiple game state affecting things interacting with each other. I'm just guessing though.

---

For the implementation approach, it makes sense and reflects the plan well. I would prefer to gather and send the inputs for every tick, to avoid issues where people do something "unexpected" with their input classes ( like not using BaseNetInput and rolling their own logic, which might not fit gathering input only at the start of the loop, but still be a valid approach ).

The other is to have the same way to configure synced properties as RollbackSynchronizer does, but I'm lenient on that - feel free to just implement the data that you need for your specific project, I can just add the property config part after.

---

on_tick, otherwise, confirm Sx(k1+1) and resimulate S*x(k1+2..k2+1) with Ax(k1+1..k2)

I was also considering a delta mechanism here. So, instead of resimulating ticks, we could also store deltas between local states. Then, when we receive a new state from the server, we can just apply all the deltas to get an up-to-date, predicted state. This would still incur some kind of rollback, but I expect it to be way faster, since no actual simulation is happening.

The slight drawback would be that it would need a class similar to Interpolators, that would have a type-based registry on how to calculate deltas and apply deltas. But I think that's ok for this project.

This way we could also just remember the latest authoritative tick received from the server, and if we receive anything older than that, just ignore. This would also mean that we can forget delta- and input history that's older than the state received from the server.

Let me know what you think!

[bryanmylee]

@elementbound Thanks for the feedback, and yeah I realized during implementation that broadcasting Sx(k1+1) to players means that the original client would have to reconcile state for k1+1 with input A(k) and state S(k).

For the updated approach, the server handling the request at tick k1:

1. for any originating tick k, server receives input Ax(k) and treats it as Ax(k1)
2. on_tick, for all clients x, server applies Ax(k1) to S(k1) to produce S(k1+1)
3. after_tick_loop, for all clients x, for other clients y, server broadcasts Sx(k1+1) to y but Sx(k+1) to x

On all peers handling the response at tick k2:

1. before_tick_loop, client x receives either S(k+1) or S(k1+1)
2. on_tick, client x reads node states Sy(k1+1) for all nodes y in S(k1+1) and Sx(k+1) for itself
3. on_tick, if x != y, treat Sy(k1+1) as confirmed Sy(k2)
4. on_tick, if x == y, check S*x(k+1) against Sx(k+1)
5. on_tick, if k+1 < k2 - Q, tick is too late and we have no history, ignore
6. on_tick, if S*x(k+1) is_approx_equal Sx(k+1), confirm S*x(k+1) as Sx(k+1)
7. on_tick, otherwise, confirm Sx(k+1) and resimulate S*x(k+2..k2+1) with Ax(k+1..k2)

I've managed to get state replication to work well on the server and other clients, but the biggest issue I have right now is getting the local client to sync properly and getting single-fired events like "jump" to be recognized consistently on the server.

Sometimes, the players jitter rapidly for extended periods, which makes me think there's some time sync issues.

I'm also not sure how to integrate NetworkRollback into my approach and I might be doing the resimulations incorrectly. I basically run resimulations by running my on_tick function multiple times:

# verification_synchronizer.gd

func _ready() -> void:
	NetworkTime.before_tick.connect(# ... records input for local
	NetworkTime.on_tick.connect(_run_tick)
	NetworkTime.after_tick.connect(# ... run the rpcs


func _run_tick(delta: float, tick: int) -> void:
	# Set state to tick `t`
	var state := _get_latest_until_tick(_states, tick)
	PropertySnapshot.apply(state, _property_cache)
	# Set input to tick `t`
	var input := _get_latest_until_tick(_inputs, tick)
	PropertySnapshot.apply(input, _input_property_cache)

	# Applying input `t` to state `t`
	for node in _nodes:
		node._verified_tick(delta, tick)
		

## Only gets called on the clients, never on the server.
@rpc("unreliable_ordered", "call_remote")
func _submit_confirmed_state(state: Dictionary, tick: int) -> void:
	if tick < NetworkTime.tick - NetworkRollback.history_limit and _latest_confirmed_state_tick >= 0:
		_logger.debug("Ignoring state %s older than %s frames" % [tick, NetworkRollback.history_limit])
		return
	
	if state.is_empty():
		_logger.warning("Received invalid state for tick %s" % [tick])
		return
	
	# I've defined a separate input root to help determine authority over each player.
	# For not-my-player, just sync the received state naively. This works great.
	if not input_root.is_multiplayer_authority():
		_latest_confirmed_state_tick = NetworkTime.tick
		_states[NetworkTime.tick] = PropertySnapshot.merge(_states.get(NetworkTime.tick, {}), state)
		return
	
	if tick <= _latest_confirmed_state_tick:
		#_logger.warning("Already received confirmed state for tick %s" % [tick])
		return

	_latest_confirmed_state_tick = tick
	# Compare S*x(k+1) to Sx(k+1) (`state` passed into this RPC)
	var predicted_state = _states.get(tick, {}) # S*x(k+1)
	var invalid_server_state := {}
	for property in predicted_state:
		var value = state[property]
		var predicted_value = predicted_state[property]
		# _verifiers just checks that a is_approx_equal b with some margin.
		var is_property_valid = _verifiers[property].call(value, predicted_value)
		if not is_property_valid:
			invalid_server_state[property] = value
	
	# Apply invalid server state and resimulate to current tick.
	if not invalid_server_state.is_empty():
		# Apply state from server and resimulate to current tick.
		_states[tick] = PropertySnapshot.merge(_states.get(tick, {}), invalid_server_state)
		# For NetworkTime.tick = t, we will already be processing state t and action t to produce state t+1 later on `NetworkTime.on_tick`.
		# If we receive a confirmed state tick = k, we need to produce state k+1 up to state t non-inclusive.
		if tick < NetworkTime.tick:
			# Apply actions from k up to NetworkTime.tick non-inclusive.
			NetworkTime.before_tick_loop.emit()
			for resim_tick in range(tick, NetworkTime.tick):
				_run_tick(NetworkTime.ticktime, resim_tick)
			NetworkTime.after_tick_loop.emit() # clears jump input from simulations.

On my input node:

func _ready() -> void:
	set_process(is_multiplayer_authority())
	set_process_input(is_multiplayer_authority())
	if is_multiplayer_authority():
		NetworkTime.before_tick_loop.connect(_gather_input)
		NetworkTime.after_tick_loop.connect(_clear_input)


func _gather_input() -> void:
	is_crouching = Input.is_action_pressed("mod_crouch")
	is_running = Input.is_action_pressed("mod_run")
	direction = Input.get_vector("move_left", "move_right", "move_forward", "move_backward")


func _clear_input() -> void:
	just_jumped = false


func _process(_delta: float) -> void:
	if Input.is_action_just_pressed("jump"):
		just_jumped = true

[elementbound]

Thanks @bryanmylee, keep us posted!

[bryanmylee]

Just a quick update since it's been awhile, but I never got this working properly and had to move on with other features of my project :/

[elementbound]

No worries, I'll keep this issue open, in case I can get around to working on something similar