Jump to content

  • Log In with Google      Sign In   
  • Create Account

Zen of Networked Character Physics


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
21 replies to this topic

#1 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 28 December 2004 - 12:26 AM

Hey all, I've just released the presentation and demo used in my AGDC 2004 talk "Zen of Networked Character Physics" including full source code for the demo. The talk shows how to apply standard fps netcode techniques such as client side prediction and important moves to any physics simulation, provided that it is deterministic, driven by input and each client has strong ownership over one object on the server. See www.gaffer.org for details and a download cheers all

Sponsor:

#2 hplus0603   Moderators   -  Reputation: 5706

Like
0Likes
Like

Posted 28 December 2004 - 05:59 AM

Thanks for posting that presentation!

One question: we've found that packet loss is typically "bursty"; i e, with 20% packet loss, we don't lose 1 packet of every 5; instead, we'll get 2 seconds of packet loss out of every 10 seconds of traffic. This is likely due to how routers on the internet work. Do you have any data on how double-sending user input copes with those situations?


#3 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 28 December 2004 - 01:02 PM

Quote:
Original post by hplus0603
Thanks for posting that presentation!

One question: we've found that packet loss is typically "bursty"; i e, with 20% packet loss, we don't lose 1 packet of every 5; instead, we'll get 2 seconds of packet loss out of every 10 seconds of traffic. This is likely due to how routers on the internet work. Do you have any data on how double-sending user input copes with those situations?


sure, ok. firstly because the server runs on client time, this bunching up doesnt affect this type of netcode in the slightest - the server just catches up perfectly when it receives the latest packet from the client with time say 20 steps ahead, it does 20steps in a row immediately to catchup.

because the important moves are sent redundantly with every input rpc sent from client to server, even under 99% packet loss, as soon as the server gets an input packet, it has complete information to advance ahead without desyncing the client -- eg. the important moves are a perfect summary of the client input since the last server ack. this redundancy is what allows the system to handle high packet loss perfectly

important moves are is easy if you have binary input, because the important moves are simply the deltas. in the source code here, the important moves are whenever the boolean inputs change (ie. left is released, or right is pressed etc.)

what if your inputs are floats? say if you have an analogue controller, surely everymove for the last 2 seconds is important, and it quickly become impractical. in this case, you need to use splines and control points to approximate the analogue inputs instead of just sending important moves. this is tricky, and i havent done it yet, but its the best you can do in the situation. i dont know of any fps that currently does this, but in theory it works, and the amount of error in the approximation if done well, should be small enough that snapping is not noticeable, and your smoothing will handle any tiny snaps nicely

cheers

#4 hplus0603   Moderators   -  Reputation: 5706

Like
0Likes
Like

Posted 28 December 2004 - 02:40 PM

Quote:

even under 99% packet loss, as soon as the server gets an input packet, it has complete information


So you just keep tacking on more and more input data with each packet until you somehow gets acknowledge that the data made it through? This works until the packets get too big :-) Luckily, movement data typically RLE compressed really well, so this is probably still OK. If you allow very long times of drop-out, though, you may get some of the Counterstrike-type cheats where people would install on/off switches on ports on their network hubs :-)

Quote:
floats as inputs


I've found that most "analog" inputs have, at best, 256 levels, i e 8 bits of precision. Thus, you can quantize your analog input to 256 discrete levels, and nobody will know the difference. These will likely still compress well, if you use a variable-bit-width encoding that favors small deltas.

The play-forward of received data gives rise to a bit more curiosity: what happens to other players at the point where you catch up? Are they re-stepped in sync, or do they remain wherever they were at the last step (that the catcher-upper is stepping up to)? Do you use a log of positions on the server for accelerating this case? Will you send correction ("snap") packets "in the past" to clients if they end up colliding?


#5 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 28 December 2004 - 04:11 PM

no actually the server acks in the ping round trip time, so under normal conditions you only ever need to send the important moves (input deltas) for the last 250ms or so.

how often can the typical user change left/right/forward/back input values in a 1/4 of a second? even if every move was important, you're only sending a max of 25*5bits in the example i've presented :)

its quite a practical technique, and it works perfectly even on low bandwidth connections - read the article/source and you'll see that the server ack is the 'synchronize' correction send back with a timestamp so the maximum size of the redundant input is bounded nicely

if this still makes you nervous, just clamp the maximum number of important moves to some number (say 5?) and you should cover most cases perfectly for real-world input. i just wanted to present an implementation that was perfect (never snapped, ever) to show that the technique is flawless.

cheers

#6 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 28 December 2004 - 04:14 PM

regarding other clients, this is what i call a "proxy" in the article and source code. you can think of proxy as being the other clients' view of your character remotely, or alternatively, the 'round trip' of your input being sent to the physics and corrections arriving back to your client.

while the server is in lock-step with the client, the proxy runs on its own concept of time. as you pointed out, if you dont do this, the proxy will lock up while packet loss starves it of input packets, which is unacceptable.

so effectly, the proxy is just a physics simulation extrapolating continuously from the last snapped input/state sent from the server, and everytime a snap comes from the server, it just snaps to it, then extrapolates again -- smoothing is used to make it all nice and continuous so the snapping cant be seen

remember, the proxy is just an approximation so its ok, but the client/server require a much greater coupling of physics, which is why they run lockstep

cheers

#7 sit   Members   -  Reputation: 174

Like
0Likes
Like

Posted 28 December 2004 - 08:24 PM

I see how this works right

except, how would I deal with multiple clients colliding? neither client is guarnteed to see the other client at the same spot so the collisions can't really be assured to be deterministic

any ideas?

all I can think of is some kind of hack where somebody is the authority and over some period of time all cubes are put in some path this authority specifies [to get back to being able to use that the phyiscs is deterministic]. Still, this is a hack and will not likely work well if the bodies remain touching [like, a stack]

#8 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

0Likes

Posted 28 December 2004 - 08:51 PM

this is the fundamental cost of client side prediction. yes the collision will be deterministic, but each client will have a different result from the server, which will cause a snap for both clients.

my take on the future of networking: as multiplayer games become more focused on player-player interaction, they will be forced to trade back latency by dropping client side prediction to eliminate the snapping when players interact. you'll also need to drop the client-server lockstep and make sure the entire scene physics advances ahead in lockstep - effectively forcing all players to run at the latency of the most lagged player.

obviously this isnt practical in the near future, we need regular packet delivery, low latency, and low packet loss for this to be practical - but over the next 5 years i think we'll start seeing a swing towards this for interaction heavy type network games

cheers

#9 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 28 December 2004 - 08:55 PM

erk. silly anonymous postings - anyway as i was saying during my talk, consider a physics simulation with a stack of blocks and n clients connected to a server. each client can interact with any of the blocks, so no one block is clearly owned by a single client.

consider what needs to be done to ensure that the blocks stack correctly and dont snap, firstly the entire physics block simulation needs to advance ahead in time in sync (each block cant go ahead itself as it recieves input from the client), which makes it different from the technique i present in zen of networked physics. there are two things you can do, first you could just completly decouple client and server time, which can cause problems under packet loss or packets bunching up (you dont normally receive packets sent at 100fps at nice 0.01 intervals for example...), OR the halfway option, clients still have their own time concept, but the server locksteps ahead only when ALL client input is received. this effectively makes everybody run with the latency of the most lagged client, so clearly this second option is only good if everybody has around the same ping, but it does fix up the issues of timeshifting of packets over the network.

next, each client needs to stop performing client side prediction - which means they need to accept the round trip latency when interacting with the simulation. otherwise if two players are interacting with the same block (or two players blocks are interacting) snapping will always occur. there is simply no way to resolve this short of eliminating the erroneous client side prediction, so you have to wait for that round trip.

hope this clears things up, cheerio

#10 sharkyx   Members   -  Reputation: 127

Like
0Likes
Like

Posted 29 December 2004 - 06:09 AM

Why is it necessary to completely eliminate the client side prediction? As in most cases, you still have some possibilities between using and not using csp. Lots of players influencing a stack of boxes is an extreme example, IMHO. In games, how often does it happen that two players directly influence the same object at the same time? You can always use client-side prediction, but instead of just predicting the player itself, you predict the whole world. If another player is moving in the clients direction, it knows that they will collide, unless the collision is caused (or avoided) by simultaneous user input on both sides. So it does (and will) depend largely on the type of game if csp can be performed.

You could even go one step further and use csp on an object while it is under direct control of the client (think HL2's gravity gun) and as soon as the object is released, you turn it off, smooth the object into a non-predicted state. If you incorporate all the game's knowledge into the network system, you can minimize the snapping by just using prediction where it is safe, and waiting for the roundtrip where it is not safe (e.g. when the game knows already that two players are influencing the same object). The only problem I see here are the possible side-effects of turning csp on and off all the time, which will result in little snaps in itself.

RFC, I have never tested anything like this.
Regards



Jörg RüppelZoidcom - Game Networking System

#11 hplus0603   Moderators   -  Reputation: 5706

Like
0Likes
Like

Posted 29 December 2004 - 06:20 AM

Quote:
the maximum size of the redundant input is bounded nicely


My only point was that, in the case of 2-second congestion, you need to bound the amount of data to a copy of the last 2 seconds sent. You're seldom constrained on the upstream anyway, and this data compresses well, so I think we agree. (I know other games do the same thing, too)

Regarding interactions and time-steps: you can subtly adjust the time step at which you display and interact with objects to hide a lot of the interaction latency and ownership ambiguity. We started doing this in 1999, and it's worked pretty well for us (we do have a patent on that technique, btw, so anyone can read up on what we do: 6,628,287).

#12 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 29 December 2004 - 12:21 PM

Quote:
Original post by sharkyx
Why is it necessary to completely eliminate the client side prediction? As in most cases, you still have some possibilities between using and not using csp. Lots of players influencing a stack of boxes is an extreme example, IMHO. In games, how often does it happen that two players directly influence the same object at the same time? You can always use client-side prediction, but instead of just predicting the player itself, you predict the whole world. If another player is moving in the clients direction, it knows that they will collide, unless the collision is caused (or avoided) by simultaneous user input on both sides. So it does (and will) depend largely on the type of game if csp can be performed.

You could even go one step further and use csp on an object while it is under direct control of the client (think HL2's gravity gun) and as soon as the object is released, you turn it off, smooth the object into a non-predicted state. If you incorporate all the game's knowledge into the network system, you can minimize the snapping by just using prediction where it is safe, and waiting for the roundtrip where it is not safe (e.g. when the game knows already that two players are influencing the same object). The only problem I see here are the possible side-effects of turning csp on and off all the time, which will result in little snaps in itself.

RFC, I have never tested anything like this.
Regards


client side prediction is the fundamental cause of the snapping, remember, its the error in your prediction being snapped back by the server. yes if you could maintain locks on the objects perfectly somehow an only predict when you had the lock then it would be ok, but if you are predicting ahead and other clients *can* acquire the same object (as it my stack of blocks with multiple players), then eventually two players will aquire the lock while predicting ahead then get snapped back.

i'm just talking a severe case here, but just think if every player affected each other player then client side prediction cant be used. if running around on a static level very occasionally bumping into other players is your game, then client side prediction works very well -- eg. fps which is the technique i describe in my talk

cheers

#13 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 29 December 2004 - 12:39 PM

Quote:
Original post by hplus0603

Quote:
the maximum size of the redundant input is bounded nicely

Regarding interactions and time-steps: you can subtly adjust the time step at which you display and interact with objects to hide a lot of the interaction latency and ownership ambiguity. We started doing this in 1999, and it's worked pretty well for us (we do have a patent on that technique, btw, so anyone can read up on what we do: 6,628,287).


ah, there inc. nice work

do you know of any fps type network games that send mouse input as deltas (these real values i was talking about), instead of sending the raw orientation yaw/pitch?

the reason i ask is that one of the things i'm playing around with is making the server authoritative over orientation with the client driving it by sending mouse deltas - would completely fix aimbot hacks, and if you were able to perfectly delta encode the important moves, you'd never get packet loss snaps for orientation

i know current unreal games use say 2-3 approximate important moves, but they dont go to the length of *really* encoding all the important input since the server ack. actually, its quite primitive really compared to what you can do, and of course, they still send raw yaw/pitch... =p

cheers

#14 hplus0603   Moderators   -  Reputation: 5706

Like
0Likes
Like

Posted 29 December 2004 - 12:47 PM

Quote:
do you know of any fps type network games that send mouse input as deltas


Well, we do :-) I'm working on the military product which is more FPS-like than the online Club Med-like experience (we are not affiliated with Club Med, the real-world travel company).

I think all others I've heard of just send orientations. It really is the easiest to deal with, and lead to smaller (and sometimes fewer) corrections in the case where there is packet loss to the viewing clients (i e, proxies in your demo). Perhaps the best way is a hybrid: send mickeys to the server, but the server then sends orientations to the proxies.

Note that you still won't get rid of aimbots, unless you want to limit the player's rate of turn per physics step. And you may find that a FPS where you can't wrist-snap 180 degrees in a single frame may be reveiwed as "sluggish" or "difficult to control." Wasn't this one of the problems with Halo and the console controller, for example?

[Edited by - hplus0603 on December 29, 2004 11:47:46 PM]

#15 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 29 December 2004 - 12:59 PM

Quote:
Original post by hplus0603
Quote:
do you know of any fps type network games that send mouse input as deltas


Well, we do :-) I'm working on the military product which is more FPS-like than the online Club Med.

I think all others I've heard of just send orientations. It really is the easiest to deal with, and lead to smaller (and sometimes fewer) corrections in the case where there is packet loss to the viewing clients (i e, proxies in your demo). Perhaps the best way is a hybrid: send mickeys to the server, but the server then sends orientations to the proxies.

Note that you still won't get rid of aimbots, unless you want to limit the player's rate of turn per physics step. And you may find that a FPS where you can't wrist-snap 180 degrees in a single frame may be reveiwed as "sluggish" or "difficult to control." Wasn't this one of the problems with Halo and the console controller, for example?


heheh. club med :)

nice to hear somebody else is doing it, seems a lot of the standard fps these days are caught in the quake/unreal does it this way, i'm not going to think how i can do it better rut...

what i do is the hybrid method at the moment, client streams mickeys and important moves to server, and the proxies receive 8bit encoded yaw/pitch for orientation, which is good enough for the proxy - its just an approximation after all.

and yeah you are right about not fixing the aimbot, doh :)

[Edited by - Gaffer on December 30, 2004 2:59:52 AM]

#16 sit   Members   -  Reputation: 174

Like
0Likes
Like

Posted 29 December 2004 - 08:11 PM

Quote:
Original post by hplus0603
Quote:
do you know of any fps type network games that send mouse input as deltas


Well, we do :-) I'm working on the military product which is more FPS-like than the online Club Med-like experience (we are not affiliated with Club Med, the real-world travel company).

I think all others I've heard of just send orientations. It really is the easiest to deal with, and lead to smaller (and sometimes fewer) corrections in the case where there is packet loss to the viewing clients (i e, proxies in your demo). Perhaps the best way is a hybrid: send mickeys to the server, but the server then sends orientations to the proxies.

Note that you still won't get rid of aimbots, unless you want to limit the player's rate of turn per physics step. And you may find that a FPS where you can't wrist-snap 180 degrees in a single frame may be reveiwed as "sluggish" or "difficult to control." Wasn't this one of the problems with Halo and the console controller, for example?

a combination solution would be to send deltas as a 3 or 4 bit lookup in a table, with values like [-pi/2, -pi/4, -pi/8, -pi/16, pi/16, pi/8, pi/4, pi/2], giving those trying to create an aimbot an interesting time in that they have to generate good motions for SEVERAL time steps which add up to the correct aim. [I assume a proceeding bit for if the value has actually changed]

inspiration

thus complicating things significantly, if running on the local machine. If another machine [intercepting and modifying the packets] knew how to change the orientation it probably will not have as challenging of a time.

I wonder what humans aiming with such a system looks like if you plot the motions... Although a touchy subject a human would probably not aim accurately in a small number of timesteps [say, 4 or 5, with 30 a second] very frequently, but a cheater [who uses their aimbot a lot] would. What are skilled players like?

#17 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 29 December 2004 - 08:34 PM

sit you are right, but thinking about it now i think that all that can be done is some security through obscurity - fundamentally if a local user can aim, then with varying degrees of difficulty, an automated aim bot could do so also.

i guess its such a serious in counterstrike problem because of their instant hit weapons and their lag correction for weapons (ie. aim at target intead of leading), and i'm guessing that they send orientation yaw/pitch directly as well

so if you make it a bit harder (ie. send mickeys instead of direct orientation, dont have lag correction, dont have instant hit) then it gets harder, but its always possible to make an aim bot unfortunatly :(

#18 markf_gg   Members   -  Reputation: 170

Like
0Likes
Like

Posted 30 December 2004 - 01:10 PM

You know, there's no reason you should have to 'snap' when a client-side prediction disagrees with the server. In Zap (www.zapthegame.com) all clients interpolate all objects, including the player controlled object to their predicted locations.

The real "problem" I've had with networked physics and client-side prediction is that the server will receive input/time advance from different clients at different times, so that if two objects are touching, each controlled by different clients, the input/passage of time will be simulated for each seperately.

Also, for reference, Tribes 1 and 2 sent pitch/yaw deltas rather than absolute camera positions with each move. Each move would also be sent until acknowledged by the remote host, but as hplus points out, these delta compress really well, and are quite small, so it's unlikely to overflow the maximum size of a client->server packet. In practice, if you have that much packet loss, the client is going to notice it anyway.

#19 Gaffer   Members   -  Reputation: 422

Like
0Likes
Like

Posted 30 December 2004 - 05:44 PM

nice work on tribes netcode mark, that really set a benchmark for the rest of the industry to follow. i've compared TNL, and Unreal style networking, and when it comes to the core physics replication, TNL is simply much more advanced.

and i didnt know you guys encoded the mouse deltas all the way back then, thats pretty impressive :)

regarding interpolation mark, my preferred technique is to use an exponentially smoothed moving average - however i keep it completely separate from the physics. point is when i snap physics, i want the determinism of an extrapolation from the exact server snap physics state and input, so i just 'snap' the primary simulation, i have a separate smoothed object that follows with an exponentially smoothed moving average for the primary quantities (eg. smoothed position, orientation, i snap everything else)

this technique works very well for the cube, and i can even change the smoothing tightness adaptively to smooth over large snaps nicely, without introducing too much latency in the smoothed cube following the real snapping physics under normal conditions.

unreal does a similar technique for its "simulated proxies" of characters, except it only does a basic linear or physics + gravity approximate physics + collision, instead of running the same physics sim for characters on the proxy side. the main difference in its smoothing is that it doesnt seperate the main physics and smoothed physics, but just exponentially smooths towards the target snap by say 0.5 if the difference in position is above some threshold (say 10cms or so). this ends up introducing more error in the sim proxy physics which needs more smoothing over time, but for them its just a rough apporimation, you can do much better.

mark, how does your ghost stuff work in TNL, also, did you guys use integer time (eg. fixed physics timestep) for tribes, or variable? one of the biggest things i've learned just recently is that integer time for networking really simplifies a lot, especially on the proxy/ghost side. running at 100fps integer time and your time goes from 1000->1004 you know you've lost two packets for example. etc.

also, mark - how hard would it be for me to strip down TNL and use it as a low level layer, eg. unreliable, reliable ordered and nat punchthru only, plus your bitstream and compression etc. what i want to do is build my own rpc/network object layer in LUA or Ruby. i'm currently using RakNet for my personal project because i could easily discard most of its simple rpc and network object stuff -- tnl seemed at first glance much more framework like, and harder to strip down. but i'd be interested in using instead it if this is possible

cheers =)

[Edited by - Gaffer on December 31, 2004 1:44:48 AM]

#20 markf_gg   Members   -  Reputation: 170

Like
0Likes
Like

Posted 31 December 2004 - 08:57 AM

Quote:

regarding interpolation mark, my preferred technique is to use an exponentially smoothed moving average - however i keep it completely separate from the physics. point is when i snap physics, i want the determinism of an extrapolation from the exact server snap physics state and input, so i just 'snap' the primary simulation, i have a separate smoothed object that follows with an exponentially smoothed moving average for the primary quantities (eg. smoothed position, orientation, i snap everything else)

Yes, we also extrapolate from the exact server position -- but the player never sees the snap - since the player sees the interpolated object positions. I haven't actually played around with many different smoothing algorithms -- mostly I just dorked with it until the interpolation looked good. As far as latency goes, eventually the interpolation catches up with the extrapolated position, at which point it just extrapolates (until the next server correction).

Quote:

mark, how does your ghost stuff work in TNL, also, did you guys use integer time (eg. fixed physics timestep) for tribes, or variable? one of the biggest things i've learned just recently is that integer time for networking really simplifies a lot, especially on the proxy/ghost side. running at 100fps integer time and your time goes from 1000->1004 you know you've lost two packets for example. etc.

With Tribes we used a fixed 32 ms timestep, with Zap I changed it to be whatever framerate the client is running at. But there is no notion of time encoded in the network protocol itself, rather each connection just tracks a running round trip time, and this information can be used in the interpolation and extrapolation of the higher level objects.

Quote:

also, mark - how hard would it be for me to strip down TNL and use it as a low level layer, eg. unreliable, reliable ordered and nat punchthru only, plus your bitstream and compression etc. what i want to do is build my own rpc/network object layer in LUA or Ruby. i'm currently using RakNet for my personal project because i could easily discard most of its simple rpc and network object stuff -- tnl seemed at first glance much more framework like, and harder to strip down. but i'd be interested in using instead it if this is possible


Actually, in TNL it is very easy to strip out layers you don't need. The basic (game) connection class hierarchy looks:

NetConnection -> EventConnection -> GhostConnection

NetConnection provides an unreliable "notify" protocol -- it simply tracks which of the packets were successfully received by the remote host and which ones were dropped.

EventConnection adds "events" - unguaranteed ordered, guaranteed and guaranteed ordered messages. RPCs are just "syntactic sugar" on top of events.

GhostConnection manages object replication, partial object state updates, prioritization, scoping, etc.

You can derive a new class at any point in the hierarchy - for example, in Zap, we derive a GameConnnection from GhostConnection for game communication and a CommServerConnection from EventConnection for the community login server.




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