Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Recommendations for Authoritative Network Model


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
40 replies to this topic

#21 hplus0603   Moderators   -  Reputation: 5509

Like
0Likes
Like

Posted 28 May 2012 - 12:42 AM

Unless your goal is to specifically solve the "wall hack" problem at the expense of everything else (like, finishing the game, and tuning the networking so it feels good and plays well,) then I suggest you go with option 1.
Only when you find that something is a real problem should you actually do work to solve that problem :-)
enum Bool { True, False, FileNotFound };

Sponsor:

#22 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 29 May 2012 - 03:09 PM

I've nearly finished the basic delta implementation. I still have one issue (probably negative feedback) that results in a bottleneck with > 2 clients.
But it is likely this is easily fixeable. However, i seem to be dropping input packets every so often.
In addition, I have a question regarding gamestates.

Questions of the day!:
  • How do the modern shooters deal with dropped input packets? Do they "mind" if the odd batch is dropped, or do they carry on regardless. Also, how often / when is a state update sent? Because of the dropped inputs the two game states can fall out of sync fast.
  • When the server updates a gamestate using inputs from a client, does it apply those inputs to the latest gamestate, or the tick that they were intended for? (E.g if they were synchronised, and the inputs were sent at T100, would the server update the gamestate which may be T102 or find and update T100?

Edited by Angus Hollands, 30 May 2012 - 02:51 PM.


#23 hplus0603   Moderators   -  Reputation: 5509

Like
0Likes
Like

Posted 30 May 2012 - 06:27 PM

1. Typically, you send a RLE compressed set of input states for the last N packets in each packet. This allows the server to recover from lost inputs. There are other options as well, such as only actually simulating the client on ticks where data is received, or correcting the client, telling it that the input it sent wasn't received and correcting it back in time.

2. Typically, the client runs the local agent "ahead" of the server, so that input arrives "in time" for simulation on the server, and is then forwarded to other clients that display remote agents "behind" the server. This means no re-simulation or time-jumps are needed. However, other architectures exist as well -- there are many, many ways to skin this cat, and they all have slightly different trade-offs in how latency is hidden and compensated for.


enum Bool { True, False, FileNotFound };

#24 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 31 May 2012 - 03:02 AM

That's been a useful post hplus! I've never encountered run-length encoding before. In addition, it forced me to look at my input packets and i can probably compress them further by using an index array rather than key based array (dictionary) and also i was sending key states for keys that were just released, which is useless to the server.

Purely out of interest, why not RLE the entire packet, if you're sending batched packets anyway? CPU time?

Edited by Angus Hollands, 31 May 2012 - 10:32 AM.


#25 hplus0603   Moderators   -  Reputation: 5509

Like
1Likes
Like

Posted 31 May 2012 - 05:33 PM

Purely out of interest, why not RLE the entire packet, if you're sending batched packets anyway? CPU time?


RLE on the actual input packet is unlikely to save any space. For most games, your input for a given step really is just three values:
- A bitmask of the input keys (movement, action, ...)
- The mouse left/right value (and/or the heading value)
- The mouse up/down value (and/or the pitch value)

Typically you pack this into 4 bytes -- 1 byte for 8 different input buttons, and 12 bits each for heading and pitch.
Why RLE works, is because those values typically don't change every frame, so the packet can say "here's the current state, and that was the current state for the previous X ticks, and before that there was this other state, that was current for Y ticks before that."
You can easily say that you just pack two separate states, plus the number of ticks of validity for each, to limit the amount of data used (10 bytes total in this case.) This gives you between 1 and 511 ticks' worth of dropped packet resilience, depending on how active the player is in changing the input.
Another option is to just mash the last 5 states into each packet, for the last 5 ticks, and if you drop more than 4 packets, you're toast and get corrected by the server.

enum Bool { True, False, FileNotFound };

#26 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 31 May 2012 - 06:06 PM

Thanks Hplus!
I've taken a slightly different approach here. Firstly, I have used RLE on the entire "batch" of inputs, typically a batch consists of 6 ticks worth of input. The RLE is used on the previous six packets before the current six packets (collected between network ticks). In the event that an input is dropped, it can be retreived during the net packet, or then corrected by the server.
After effectively doubling the packet size in terms of content, the use of run length encoding compresses the packet to 80 bytes, from 300! It's rather useful.

#27 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 01 June 2012 - 07:45 AM

Question n-1:

At the moment, I have the basics working. But, It doesn't account for delay from server to client, so when i receive a gamestate (delta or snapshot) It applies it as the current gamestate.
I'm now trying to remember our discussion earlier..
Leaving input prediction until later, is this correct:
  • Store all received gamestates from the server. This is part of the networking just to set the last received gamestate
  • Calling this every frame; Extrapolate using two or three game states to determine what the server's gamestate should look like at the current tick. And store this as simulated every tick.
  • When you receive a gamestate, get the delta between the simulated gamestate for that tick and the server's gamestate, and then apply the delta.
If this is correct, should input prediction also modify the extrpolated state? I presume so..

Edited by Angus Hollands, 01 June 2012 - 09:35 AM.


#28 hplus0603   Moderators   -  Reputation: 5509

Like
1Likes
Like

Posted 01 June 2012 - 12:59 PM

There are three ways to deal with corrections from the server.

1) Take the "sledgehammer" approach. If you get a correction, which should be very rare, then you snap the user back to the corrected position at the current step on the client. The server needs to remember this correction, too, and apply the same correction on the same step. This is simple, robust, and feels terrible to the user, so only do this if corrections really are rare.

2) Take a "playback log" approach. When you send input to the server, save the state you think the client has for each step. When you get a correction, correct the state at that step, and then re-play the input locally up to the current step number. This uses more RAM and more synchronization, but is less impactful to the user, and will correctly deal with simple "one packet was dropped" problems.

3) Take a "smooth into destination" approach. When you get a correction to the server, don't immediately change the client, but instead keep a value for how much the difference in position is. Then slowly apply this delta in position over some time -- say, half a second, or a second. This requires de-coupling the server-decided state, the client-decided state, and the displayed state, and is a lot more complex. It _can_ smooth out corrections more than the other options, but it's in my opinion too complex to be worth it, and the user will see "non-physical" behavior ("gliding") over more than just a single step.


enum Bool { True, False, FileNotFound };

#29 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 10 June 2012 - 06:59 AM

Im starting on client prediction, but i have to consider a few things. Firstly, are there any good resources for extrapolation of positions and orientations in a fast manner?

#30 hplus0603   Moderators   -  Reputation: 5509

Like
0Likes
Like

Posted 10 June 2012 - 11:35 AM

Im starting on client prediction, but i have to consider a few things. Firstly, are there any good resources for extrapolation of positions and orientations in a fast manner?


A demo of forward-extrapolation, with code.
enum Bool { True, False, FileNotFound };

#31 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 11 June 2012 - 04:42 PM

I am sorry for not clarifying; I cannot read C++ at all, being almost non-identical to Python. I could create it in python if i knew how it was supposed to work :S
If that's too much to ask, then don't worry. I just don't see how it differs from typical extrpolation, though i see it is smoother.

#32 hplus0603   Moderators   -  Reputation: 5509

Like
0Likes
Like

Posted 11 June 2012 - 06:07 PM

If you have positions and velocities at time stamps:
t0, P0, V0
t1, P1, V1
And you want to know the position at time t2 > t1, where t2 is "now" and t0, t1 are "in the past."

Then the math says:
The position at time t2 based on the t0 data is P02 = P0 + V0 * (t2 - t0).
The position at time t2 based on the t1 data is P12 = P2 + V1 * (t2 - t1).
Now, you can extrapolate the error. The error delta expressed as a velocity is Ve = (P12 - P02) / (t1 - t0).
So, take the position as we know it based on the last timestamp, forward extrapolated (P12), and add the error velocity times the extrapolation time (t2 - t1):
Pout = P12 + Ve * (t2 - t1).

Now, each time you receive a new timestamp, and shift t1 -> t0, new -> t1, you will get a discontinuity in display position. To fix this, you can extrapolate by calculating the new "target position" only once, each time you get a new update, and the move towards that position at the appropriate velocity.

Thus, at time t1 (in this case), calculate the position you'd want to be at one network packet's interval from now, plus the forward extrapolation time:
Pout = P12 + Ve * (t2 - t1 + tN)
Snapshot the current player position Pcur. Calculate the needed velocity to get from current player pos to desired target pos at that time.
Vd = (Pout - Pcur) / tN
So, the position at time tx is then simply:
Ppos = Pcur + Vd * (tx - t2)

enum Bool { True, False, FileNotFound };

#33 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 12 June 2012 - 02:54 AM

Ok, This makes sense. I've modified my gamestate structure to include velocities, and I've implemented your code! Posted Image
The problem i have now (there's always a problem!) Is that occaisionally it seems to break when clients jump - the client starts "drifting" downwards, ignoring collisions. This would be fine but it also ignores the actual Z position.
Could it be that the gravity of the Physics engine is affecting it?
I actually get this with or without input prediction, so I can't think of what's causing it.

Edited by Angus Hollands, 12 June 2012 - 11:55 AM.


#34 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 13 June 2012 - 10:42 AM

And, another conceptual question!
With rotation of players, Mouselook that was purely server side would be laggy and almost unplayable. Should it be purely client side and transmitted? or would you use something like epic? - I can recreate that for rotations.

#35 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 13 June 2012 - 01:19 PM

Oh darn this.
I thought it would implement correctly, but it doesn't seem to work - every so often it starts to throw wierd position offsets...

Here is my python interpretation:
# Updated every network recv
tick_rate = 60
network_packet = 6
#tick_0 = ... tick_1 = ... current_tick == ...
position_0, orientation_0, velocity_0 = state_0
position_1, orientation_1, velocity_1 = state_1
position_now = user.worldPosition.copy()
# Extrapolated (current) position according to tick 0
position_acc_tick_0 = position_0 + velocity_0 * ((tick_now - tick_0) / tick_rate)
# Extrapolated (current) position according to tick 1
position_acc_tick_1 = position_1 + velocity_1 * ((tick_now - tick_1) / tick_rate)
# Get the error between two predictions as a velocity vector
velocity_err = (position_acc_tick_1 - position_acc_tick_0) / ((tick_1 - tick_0) / tick_rate)
# Get the estimated position the client needs to be at in one network ticks time, accounting for error
position_out = position_acc_tick_1 + velocity_err * (  (tick_now - tick_1 + network_packet) / tick_rate )
# Get's velocity needed to move from current position to target position within one network tick
needed_velocity = (position_out - position_now) / (network_packet / tick_rate)

# Updated every frame
new_velocity = needed_velocity * ((current_tick - packet_tick) / tick_rate)

Can you see any problems with this? The only other problem i can foresee is a problem with the arrival times.


EDIT;

I beleive it was caused by a side effect of having the logic processed before physics; linv didn't account for friction.
However, my question still remains about orientation and mouselook - where is it handled?

Edited by Angus Hollands, 13 June 2012 - 03:26 PM.


#36 hplus0603   Moderators   -  Reputation: 5509

Like
1Likes
Like

Posted 13 June 2012 - 04:43 PM

And, another conceptual question!
With rotation of players, Mouselook that was purely server side would be laggy and almost unplayable. Should it be purely client side and transmitted? or would you use something like epic? - I can recreate that for rotations.


Typically, an FPS will make mouselook client authoritative. One input from the client is the heading(yaw) and pitch of the forward vector.
Note that doing this makes aimbots easier to write, but that's usually an OK trade-off, because you have to find cheaters through external means anyway.
Thus, the input state from a client is "movement and action keys + mouselook direction."

EPIC can only forward extrapolate based on past data, it's not typically something you use for the local player.
enum Bool { True, False, FileNotFound };

#37 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 17 June 2012 - 08:06 AM

Thanks again Hplus.
In regards to EPIC, how does it compare to spline based extrapolation?

#38 hplus0603   Moderators   -  Reputation: 5509

Like
1Likes
Like

Posted 17 June 2012 - 01:51 PM

Splines may make for softer turns, but also have all kinds of speed derivative problems during interpolation. Epic prefers to make a sharper change in speed at each snapshot, and be linear in between.
Personally, I don't much like the spline and polynomial based methods, because when they go wrong, they tend to go *REALLY* wrong.

enum Bool { True, False, FileNotFound };

#39 Angus Hollands   Members   -  Reputation: 717

Like
0Likes
Like

Posted 18 June 2012 - 06:33 PM

Haha, i see. That does make some sense, considering their nature.
I've really hit a snag now and I could use some help.
Basically, I have the delta updates working fine, and full updates. I am using a physics engine for movement on the server, and for client side prediction.
However, I am correcting the errors between prediction and official server values, and it is horribly juddery.
I don't think it is looking at mismatching data, and i just think that it is a small variation between server and client physics.
The other part i beleive to be the issue is that the server updates in "Bursts" whereby after receiving a packet containing 6 inputs or so, it idles and thus it would show a temporary decrease in velocity.
To be honest, here's my query:
How can I smoothly use both client side and official information from the server? When i apply correction information at the moment, it just dies, especially when going up slopes

Here is my correction code, called every update from server
def correct_errors(self, gamestate_tick):
	    '''Correct error between prediction and server state
	    @param gamestate_tick: tick to correct from'''
	    # Iterate through all predictions, update to reflect corrections
	    simulated_states = self.simulated_states
	    received_states = self.received_states
	   
	    predicted_state = simulated_states.get(gamestate_tick)
	    received_state = received_states.get(gamestate_tick )
	   
	    username = self.username
	    # Try to get the user prediction and server determined gamestates
	    try:
		    user_prediction = predicted_state[username]
		    server_data = received_state[username]	  
	   
	    # If this fails, then return as both states are required
	    except (TypeError, KeyError) as err:
		    return
	   
	    predicted_position, predicted_orientation, predicted_velocity = user_prediction
	    server_position, server_orientation, server_velocity, server_states = server_data
	    # Applies the modification to the predictions
	    position_error = server_position - predicted_position
	    velocity_error = server_velocity - predicted_velocity
	    #position_error
	    # Prevents local and remote collision errors
	    # Update existing user position to reflect packet difference (error)
	    user = self.users.get_user(username)
	   
	    user.object.worldPosition += position_error
	    # Modify predicted state data
	    for tick, state in list(simulated_states.items()):
		    # Ignore & remove old predictions before this gamestate
		    if tick < gamestate_tick:
			    self.simulated_states.pop(tick)
			    continue
		    # Get the data of the local user from the state
		    try:
			    state_position, state_orientation, state_velocity = state[username]
			   
		    except:
			    continue
		   
		    # Get prediction errors
		    corrected_position = state_position + position_error
		    corrected_velocity = state_velocity + velocity_error
		    # Modify the predicted state to reflect corrections
		    state[username] = corrected_position, state_orientation, corrected_velocity


#40 hplus0603   Moderators   -  Reputation: 5509

Like
0Likes
Like

Posted 18 June 2012 - 09:21 PM

You should clock the server at the same rate as the client. If you send 6 inputs in one packet, the last input should be processed the 6th tick after the packet is received. This means you need a queue of input events, and new events from the client get added to the end of this queue. Typically, you also want to time-stamp each input even with which tick it was generated for.

enum Bool { True, False, FileNotFound };




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS