Tuesday, 7 February 2012

Client-side Prediction in Unity

If you're making a multiplayer game in Unity and your networking model includes a fully authoritative server, you might have found movement to be a bit of a stumbling block. Client-side prediction is how lag tends to be hidden, Glenn Fiedler has an awesome series of articles, this one explains client-side prediction nicely.

To summarise - clients send their input (e.g. key presses) to the server which computes their updated position in the game world, and sends it back to them. To hide the lag, the client runs the movement code locally, and records its input and position each frame. When an update is received from the server, it looks through all the recorded positions and compares it with the data received from the server. If the two are out of sync by too large a margin, it retrospectively corrects the client by moving them to the correct position, and then runs through all the stored inputs, replaying the users actions up to the present time. This "rewind and replay" system is fine under certain circumstances, but a big problem in Unity is physics.

For about two years I've been developing a Unity multiplayer FPS on and off. Naturally, players can run about, jump up and down, collide with objects, and so on. I have no way of triggering the Rigidbody component on the player to simulate a frame, so I can't rewind and replay can I? Well I can, if I roll my own basic Rigidbody class:

public class NetRigidbody : MonoBehaviour
{
private Vector3 velocity;


public void Simulate( float dt )
{
// s = ut + .5at^2
Vector3 movementDelta = ( this.velocity * dt ) + 0.5f * ( Physics.gravity * dt * dt );
this.transform.position = this.transform.position + movementDelta;
this.velocity += Physics.gravity * dt;
}


public void FixedUpdate()
{
this.Simulate( Time.fixedDeltaTime );
}
}

Big problem here though - collisions! Currently a GameObject with one of these attached would just clip through everything, it doesn't process any collisions, and wont receive OnCollisionEnter() messages without a standard Rigidbody attached. One way we could approach this, is make gravity zero and attach a standard Rigidbody to process collisions for us. However, this wouldn't work for rewind and replay as we still have no ability to tell Unity when to simulate the physics.

The Physics class in Unity provides some useful static functions which would allow us to process collisions ourselves, for example RayCast, SphereCast, and CapsuleCast. I'd rather not do this myself, but there's a nice shortcut in the form of CharacterController. This class moves a GameObject by calling the Move( Vector3 motion ) method, and automatically does some collisions processing (i.e. stops the CharacterController's capsule from intersecting with other colliders). It also directly calls OnControllerColliderHit() when a collision occurs - that is to say, it calls OnControllerColliderHit() before Move() exits. So the updated NetRigidbody implementation is:

public class NetRigidbody : MonoBehaviour
{
private CharacterController _characterController;
public CharacterController characterController
{
get
{
if( this._characterController == null )
{
this._characterController = this.GetComponent<CharacterController>();
}

return this._characterController;
}
}

public Vector3 velocity;

public void Simulate( float dt )
{
if( this.characterController == null )
{
return;
}

Vector3 movementDelta = ( this.velocity * dt ) + 0.5f * ( Physics.gravity * dt * dt );
this.characterController.Move( movementDelta );

this.velocity += Physics.gravity * dt;
}

public void OnControllerColliderHit( ControllerColliderHit hit )
{
// Negate some of the velocity based on the normal of the collision by projecting velocity onto normal
this.velocity += Vector3.Dot( this.velocity, hit.normal ) * hit.normal;
}

public virtual void FixedUpdate()
{
this.Simulate( Time.fixedDeltaTime );
}
}

With this we can now effectively achieve rewind and replay in Unity, full client-side prediction! Huzzah! So what are the downsides? For one, using a CharacterController like this means that a GameObject which needs to rewind and replay (i.e. player controlled entities) will only use a single CapsuleCollider for movement collisions. This is fine for something like counter strike, but what if you want to put vehicles in like Battlefield? I fear that this approach is like building a structure on jelly, it might stay up, but it might all come crashing down.

What alternatives do we have?
1) Instead of using CharacterController, use Physics static functions to properly process collisions for all colliders attached to the GameObject and its children.

2) Just don't rewind and replay. When the server disagrees with the client to a significant degree, stop sending input to the server, and stop predicting movement. Wait for the server to completely catch up and process all of the input we've sent, and once that's happened we resume control of the player. This will result in very noticeable snaps. This should be fine for a game that will only be played on LANs.

3) Take a popular open source physics library such as Bullet, and either port it to .NET (or use an existing port), or Unity Pro users could compile it down to a native .DLL. You'd still need to build a bridge between Unity and that physics library. Keep in mind that Bullet (like many physics libraries) does not simulate physics objects individually, the entire system is stepped forward as a whole. So if you want to rewind and replay, you need to either create a temporary physics world containing just the things you're rewinding and replaying, or you need to rewind and replay absolutely everything.

What did I choose to do? Well, I realised that I just wanted to implement client-side prediction like this because I found it an interesting programming excercise after reading Glenn Fiedlers excellent series of articles. I'd advise others making multiplayer games in Unity to consider semi-authoritative network models. In the case of the game I'm trying to make, it's cooperative, so cheating isn't really a big issue - I could essentially just use the server as a way to connect players, and provide some validation.

But what happens if (like me) you worry that one day you might want to add another game mode where players compete directly with eachother? My answer - I downloaded UDK.

38 comments:

  1. I'm a garage dev that just reached this point and it's killing me. My single player physics are awesome, I'm starting to dig what Unity can do for me and have a workflow going that minimizes despite it's (massive) warts, I've got a partial multiplayer implementation working that I just need to flesh out... and then... BAM, it falls apart.

    It's a shame because it's all there under the hood, but as usual, Unity puts all their effort into checklist features that have pizazz factor, but neglects the hell out of the actual process of writing / maintaining a game.

    Ages old Mono, half baked Physx (though it's obviously there since Character Controller can use it), the laughable framing of non-nesting prefabs as being for our own good, etc, etc... But, oh man, there's that new particle system (that also can't be properly scripted) and shaders for XBox!

    Ugg. I'm starting to like C# too. Or at least the parts of it that are actually available.

    ALL I NEED IS A WAY TO GET THE COLLISIONS! ARRRG!

    ReplyDelete
    Replies
    1. I hear ya =)

      When Unity 4 was announced I tweeted to Unity Technologies along the lines of "Still the same old horrible GUI, but it's ok because there are real time shadows on mobile! Good to see you've got your priorities straight..". David Helgason replied, justifying it by saying Unity GUI performance had been improved, but I really think they don't get the point sometimes. There are some really crucial things holding the engine back from being able to properly rival the likes of Unreal, Cryengine, etc.

      I've actually switched back to Unity from UDK for my multiplayer FPS (UDK has more limitations on procedural content unfortunately, otherwise it'd be perfect). I've just come to accept that without control over physics I can't properly do client-side prediction. I'm using a priority updating system not unlike Unreal so that I can drop lots of objects into a scene without the networking side of things falling over. This however makes lag compensation even more complicated - still completely doable though.

      With all that in mind - and given I'm only one programmer, I've decided to massively relax the networking model and start trusting the client more. Players send their position data and input to the server, which just does some simple validation to protect against speed-hacks. As for lag compensation, I just let players tell the server when they've scored a successful hit. Yes, this is more hackable, but it reduces development time, as well as lowers the CPU load on both the server and the client.

      Delete
    2. Oh, and I can't emphasise enough - send your data via sockets rather than the standard Unity networking system. It's bloated, slow, erratic, and it's pretty damn important to be able to control every byte sent across the network.

      Delete
    3. At the moment I'm using uLink for networking, which seems to do a decent job so far. I've love to have the time to roll my own socket based layer with priority queued RPCs, but much like Unity, uLink gives me at least the foundations of what I need without writing everything from scratch (and I can control RPC payload down to the byte, which I do). And I'm also just one guy. :)

      It really, really kills me that they didn't update Mono in 4.0 (or fix prefab nesting). One of the huge selling points of Unity for a lot of people is that it uses a real language. But it's a severely out of date version of a language that has improved MASSIVELY. I mean... on top of all the other things we're missing that are available and awesome in the current or semi-current C# / Mono, we're stuck with an invariant IEnumerable[T] of all things!

      I'd love to talk about this directly as it seems like you've been exactly where I'm at now and have done your research... I'm actually thinking of going with kinematic rigidbodies and Physics.SweepTest and controlling everything manually. I'm not sure if SweepTest was available when you did your experiments as I think it's a newer addition to the API, but this *should* definitely work, though it will be a MUCH larger undertaking that should be necessary (My physics are already working well and I know manual stepping like this is possible in Physx, but the API just isn't properly exposed! Dammit!)


      Things I'd gain:

      Better control over terrain bounces, as no matter what I do with PhysicMaterials they never seem to work right.

      Better control over collision forces, ie: use masses correctly and don't jitter like with maxPenetrationForPenalty (My game is projectile based an I already had to make my projectiles kinematic because of these issues).

      "Perfect" rewind / replay, at least to the level of moving one entity at a time.

      Proper extrapolated prediction on the client.


      Things I'd lose:

      A lot of effort that could be spent elsewhere.

      A lot of performance? (Unknown, but seems likely, and though my game won't have tons of entities, I do want a timestep of 10 ms or less).


      So I'm wondering if using CharacterController would be good enough. I see that it gives the collisions immediately, which is great. But can I get it to behave like a rigidbody and ignore all the walking based stuff. Or am I back to rolling my own again. Maybe CharacterController + roll my own is the best way, as I *think* using SweepTest would require both a SweepTest + MovePosition on every move, which may double the physics, though it *shouldn't* if the rigidody.detectCollisions = false

      (From what I can tell, setting transform.position directly would leave the collider in the wrong place until the next FixedUpdate... but it would help if the APIs were properly documented, and as far as the performance, I've learned not to trust ANYTHING about the physics code to "do what it should" until I've seen it work).

      Anyway, yeah... I'm sure you know where I'm coming from, and it's not a good place right now. :)


      (I'll note that my game is an physics-based FPS with very predictable movement and projectile based weaponry. Aka: A Tribes-like. And I've already put enough effort in that I'm going to try to monetize it somehow, so full server authority is required)

      Delete
  2. BTW, have you seen this:

    http://www.youtube.com/watch?v=tHn50_-zsyo

    Apparently the guy isn't working on it anymore, but having access to Bullet from Unity would elevate the physics side of the engine from "toy" to "pro" right quick. And even with a bridge it would probably outperform Unity's Physx implementation (and be able use all those extra cores we have lying around).

    ReplyDelete
    Replies
    1. I just saw this (I mention Bullet in my other reply) and no I haven't! Holy shit I can't believe someone did it, this might well be the answer to your problems..

      Delete
    2. Unfortunately the guy doing the Bullet physics implementation hasn't reported in for quite a while. Here's his thread on the Unity forums: http://forum.unity3d.com/threads/135293-Unity-Bullet-Physics-Plugin-Demo

      Last post from him was in December 2012 where he says he's working directly with the Bullet team. Would be great if he released the partially-complete source code even if he never finishes it. Although, his first post suggests a July 2012 release so maybe he's just very slow. :)

      Also, great post! I was running into all these same problems with multiplayer in my game and this really helped me consolidate my thoughts - and confirm that proper prediction just isn't possible. I'm working with vehicles (www.scrapsgame.com) so I can't even use character controller capsule colliders. I have a reasonable system working now but it still doesn't have real prediction.

      You're the only person I've seen who hasn't just dodged around the real problem. Now everyone who's banging their heads against Unity physics + networking are slowly converging here.

      Delete
    3. Thanks man, glad it was helpful to you. For what it's worth, I've since abandoned this kind of networking model. In most games you can only afford 1 physics update per frame, let alone 5-10. If your game has a static world and just moving players (like counter strike or something) then you may get away with it, but if not then the cost of rewinding and replaying all the rigidbodies which the player might bump into will often be too great.

      Delete
    4. Yeah another good point. I've managed to avoid rewinding and replaying (and my world isn't too complex anyway) but I can imagine it'd get too much pretty fast. Do you know anything about how multiplayer racing games handle their physics? (although after playing some, I'd say the answer is often just "badly")

      Delete
    5. I have very little knowledge about such things, I've not yet seen any articles or lectures that go into it in any detail. I did ask a guy who used to work at Black Rock about it, and what he said implied that you just race against cars which are slightly "in the past". If as a result of lag they happen to move through you, they just push you out of the way.

      Delete
  3. The physics system is a bit weird sometimes - a problem I came across when doing lag compensation was that if I moved a transform, it didn't update the colliders, so Physics.Raycast didn't work properly. I'm told by Heks from the Interstellar Marines team that disabling the collider, and then re-enabling it will force the collider to update but I haven't tried that. The other way to work around it is to directly call Raycast on the specific collider instance, and then it returns the correct results.

    Sweeptest was available when I tried doing this, but all it does is tell you if something WOULD collide, it won't tell you for example the angular velocities generated when two cubes collide at strange angles. This is why I used CharacterController, as the Move() function will handle all the sliding along colliders that it hits and so on. These sort of roll-your-own hacks work fine for a player in an FPS, as they tend to remain upright, but I think it would fall apart if you tried it with objects that tumbled about.

    Like you, my FPS has mostly projectile weapons, something to bear in mind is that this will make lag compensation more work for the server than hitscan.

    As for uLink, I remain sceptical of networking middleware, but I'm sort of a "networking guy" and therefore don't mind coding the networking system myself.

    One way you *could* do it, would be to make a native plugin to allow you to use Bullet physics. I don't think you do need full server authority though, with validation you can protect against most cases of cheating, and anyone who wants to cheat bad enough will always find a way.

    ReplyDelete
  4. Objects tumbling around is one reason I'm looking for something more robust than CC. Characters remain upright until they ragdoll and have yaw under full player control, projectiles are fine with SweepTest or CC as they don't need rotation, but stuff like item drops (and I do have a dropped cube that bounces and slides around nicely) would be... problematic.

    The thing about using CC for my pawns is that: (1) I use ground friction, and (2) vertical movement should conserve energy. Actually, now that I think about it, gravity is most likely just applied per timestep anyway, so (2) isn't an an issue. And I guess I could do friction manually. This would still leave me with the cubes to deal with though.

    It's really quite insane that one has to go to these lengths to do something that should be simple enough with a properly exposed API. Even CC like colliders called BoxController, SphereController, CapsuleController with Move() functionality, unlocked rotation, and none of the other character oriented stuff would be good enough and make Unity's physics 10x more robust.

    Or:

    OnCollisionImmediate()

    Which would immediately solve it all (including those pesky bounces that have plagued me since day one).

    ReplyDelete
    Replies
    1. Yep I had the same issue with CC limiting me to upright objects. The only way I can see it working nicely without dropping some server authority is the bullet fix.

      As for gravity I've done tests in the past and can confirm that gravity is applied in unity with this formula:

      pos += ( velocity * dt ) + ( 0.5 * gravity * dt * dt);
      velocity += gravity * dt;

      Delete
    2. Good to know. I'm refactoring my movement code for manual control and will accumulate acceleration where applicable rather than directly applying velocity changes.

      Delete
  5. To clarify, for robustness OnCollisionImmediate would need a signature like:

    OnCollisionImmediate(Collision collision, out Vector3 dv, out Vector3 dav)

    And would be called before applying the velocity changes, which you could modify as you see fit.

    ReplyDelete
  6. A question: when you run through all the stored inputs, replaying the users actions up to the present time. Is that replay process instant or does it just play out at normal speed? I'm having a hard time doing that part. Thank you.

    ReplyDelete
    Replies
    1. It's instant, though if the difference in position is too jarring then you might want to interpolate between the original and corrected states to ease the transition.

      Delete
    2. Thanks for the reply. I am very new to client side prediction, and know that it is a mess to get into, but I still want to try. I am somewhat confused as why to re-simulate rather and just update the entity data such as position and velocity to the most recent received from the server because the replay is instant anyhow. "If the two are out of sync by too large a margin, it retrospectively corrects the client by moving them to the correct position" does this mean that it sets the position to the latest update received from the server or does it rewind? Sorry for all these questions, but all I seem to find on the internet is a simplified summary about client side prediction.

      Delete
    3. Sorry for any ambiguity. What you have to remember is that when the client receives data from the server, from the clients point of view, that data happened at some point in the past. So it rewinds to where the client predicted it would be at that same time stamp, and if the value it had in the past is too different from what it just received from the server, then it does an instant rewind-replay to figure out where it would be now. The re-simulate happens because:

      Lets say when the client sends a packet to the server, it takes 50ms to get there, then it will take approx 100ms to hear back from the server what the result of its user input will be. So when the client receives an update, the data is 100ms old, so if the client was to update the entity data to that which was received from the server, there would be another 50ms-worth of user input data that the server had not yet processed. Re-simulating aims to get the client back in sync with the server given that they operate on different time streams.

      Delete
    4. Do you check whether you need to rewind or not with every entity or only players / entities that take user input / are modified by user?

      Delete
    5. Only entities which take user input, I just interpolate all the others.

      Delete
  7. This comment has been removed by the author.

    ReplyDelete
  8. After a few false starts and much physics hackery, egregious object pooling, and all the rest of the shenanigans that come with doing anything complex in Unity, I have fully functional, fully authoritative rewind/replay with projectiles.

    Pawns are moved with a CharacterController, projectiles are strictly raycast (sweeptest doesn't work properly unless your projectiles move at a snail's pace), and as far as bouncing, rotating objects that can settle on surfaces as while giving proper collision info... well, as far as I can tell you simply can't do that without writing an entire physics engine. So "items" are also moved with CCs.

    If I could / wanted to go back, I might try doing things the Unity way with forces and FixedUpdate (which I used to use, and it worked "ok", though CC + raycast holds up a lot better at high speed), then mess with fixedDeltaTime and timeScale to catch up during replay. But that would come with significant problems of its own.

    Here's hoping for Bullet and a half decent GC in unity 4.5+...

    http://www.reddit.com/r/legacyfps/

    ReplyDelete
    Replies
    1. Good to hear! Yeah CCs seem to be the only way forward. However, I don't think integrating Bullet with Unity would be too hard to do, only thing is you wouldn't be able to build a webplayer version of your game.

      Delete
  9. I know this is old, but I hope you are still open to questions. I'm getting into this now and I understand the other aspects like lag compensation and entity interpolation of other clients on my machine, but my question is about frequency of sending and receiving this client data. How often is the client sending it's commands? Every frame? That would seem like a ton of messages to send wouldn't it? Also, how often is the server sending back it's response? Is this instantly after it does it's simulation or is it at a given interval? My understanding is that I'm timestamping my commands that I send to the server like "MOVE FORWARD 1", "MOVE FORWARD 2", etc while my 'w' key is down if that's what's mapped to moving forward and where 1 and 2 represent an actual "global" timestamp. So those commands could be sent 60 some times a second if my fps is 60?

    The hard part I have with this is I use a different engine than Unity that uses Newton, but the character controller that this engine has just has us passing parameters like speed, strafe, angle, jump and then it does it's simulation. So if my client sends RUN FORWARD the server sees RUN and translates it to a run speed value, and FORWARD so it puts that value in say the first parameter of UpdateController. However when the server sends snapshots it's sending positions along with a timestamp. My client is storing it's controller position along with timestamp every frame (60+ a second) and it finds the last timestamp from the server message (again is this at an interval or instantly?) and sets the client controller to this position, but I don't think I can then replay the controller given it accepts speed and angle instead of any actual position values. I can move it to the actual positions values but then I lose collision. I didn't think any physics engine really allows you to snap bodies to actual positions and still maintain collision/physics simulation.

    ReplyDelete
    Replies
    1. Firstly with client side prediction and lag compensation systems, it simplifies a lot of things if you deal with fixed time steps. Say 60fps, and then you have the client send user input to the server every frame. This may sound like a lot, but remember each different key only need take up 1 bit each. The server sends updates less frequently, a good rule of thumb is 256byte packets, 30 times per second.

      I'm not entirely sure I get the problem of losing collisions? You only snap the body position/rotation to the data in the update you receive from the server, and then you resimulate your state history.

      Delete
  10. Is there somewhere I could possibly learn a bit about the core components of this? I was able to get my own custom game working and logging in but when I try to do things like physics and such it makes me unable to move and though I think I know how it's all working it's hard to debug as I don't quite know if it's the issue I think it is or not. Examples don't help a lot as they usually are accompanied by "look at the code" .

    ReplyDelete
  11. This comment has been removed by the author.

    ReplyDelete
  12. There is a Unity feedback ticket open requesting a physics simulation API here: http://feedback.unity3d.com/suggestions/function-for-manually-simulating. Perhaps it will be prioritized with enough votes.

    In the meantime, I'm going to start with someone like this answer suggests: http://answers.unity3d.com/questions/21559/how-do-i-reduce-lag-in-my-networked-game.html. If it's not robust enough I imagine I will be digging into rewind/replay as well.

    Thanks for the insightful post, Joe!

    ReplyDelete
    Replies
    1. No problem, glad it was of use! Yeah, as I wrote about in this article you can do rewind and replay in Unity, but the physics driving the objects you want involved in rewind/replay needs to be based on your own code, or a third party plugin. I think the best solution for anyone who really really needs this is to look at making a plugin for bullet physics. These days I'm mostly programming stuff intended for coop play, so I can afford to trust the clients more and hence alleviate a lot of lag issues in a nice simple way. As soon as you have competitive multiplayer though, you have to start being stricter - which is where the issues begin.

      Delete
  13. This post a joke at best, it's obvious that the author has completely missunderstood several core concepts of client p rediction and server rewinding, etc.

    ReplyDelete
    Replies
    1. If you're not just trolling, perhaps you'd like to elaborate :)

      Delete
    2. Well there's clearly a huge knowledge gap somewhere in the authors understanding of how you do rewind/forward, and when you need to do it, etc.

      Because it is 100% workable to implement predicted/rewind-able movement with the CC in Unity. And vehicles have no need for rewinding as they would be simulated on the server (as you can hide the network latency in the vehicle acceleration, etc.)

      Delete
    3. Sorry I ment to say "vehicles have no need for *prediction* as they are simulated on the server.

      Delete
    4. I am "the author", you can just call me "you", or "Joe" if you'd prefer, up to you though.

      CC's are ok for most situations, this post is about how you need to not have PhysX driving the movement in any way. So if you want physics to affect movement then that needs to be written in code, and this article shows how to handle just basic jumping and stuff. This is fine for something similar to counter strike, but if you had rigidbodies that the player could potentially bump into (and hence affect the velocity etc of both the rigidbody and the player), they would also need to be rewound and replayed - as the effects of a retrospective snap could change where they end up at the current time. It's these kinds of situations where being able to control the physics simulation is needed - or you need to design the problem out!

      Indeed vehicle lag being hidden in acceleration is a great trick, I've personally had better results predicting them, but two vehicles colliding can be such a headache that it's just better not to predict at all as I'm sure you've found too. Though if you have vehicle combat I think it's a good idea to have lag compensation for the bullets players fire at eachother.

      I welcome debate and being challenged, you obviously know a thing or two about networking, I would however gently advocate for respectful discourse.

      Thanks for your comments
      Joe

      Delete
    5. I don't know of any AAA FPS which rewinds the entire physics state and re-simulates it using the physics engine. I feel like this is something a lot of people "think" they need, when you really don't.

      Delete
    6. Indeed they usually don't, the important point is to re-simulate the things that will affect the players movement. Largely in AAA games it's designed out though - something that's more obvious if you look at the older Valve games, but it's camouflaged with bells and whistles more and more. There does seem to be more people shifting away from the traditional Valve way of doing things nowadays though, and all these interesting developments are frankly why I choose to be a network programmer, it's great fun.

      Delete
  14. This comment has been removed by the author.

    ReplyDelete