Game network physics collision

Question

How to simulating two client-controlled vehicles colliding (sensibly) in a typical client/server setup for a network game? I did read this eminent blog post on how to do distributed network physics in general (without traditional client prediction), but this question is specifically on how to handle collisions of owned objects.

Example

Say client A is 20 ms ahead of server, client B 300 ms ahead of server (counting both latency and maximum jitter). This means that when the two vehicles collide, both clients will see the other as 320 ms behind - in the opposite direction of the velocity of the other vehicle. Head-to-head on a Swedish highway means a difference of 16 meters/17.5 yards!

What not to try

It is virtually impossible to extrapolate the positions, since I also have very complex vehicles with joints and bodies all over, which in turn have linear and angular positions, velocities and accelerations, not to mention states from user input.

Answer 1

Perhaps the best thing that you can do is not so show the actual collision real time, but give the illusion that things are happening in real time.

Since the client is behind the server (lag), and the server needs to show the result of the collision, perhaps what you can do, client side, is to show a flash or explosion or some other graphic to distract the user and buy enough time on the server side to calculate the result of the collision.. When you are finished with the prediction, you ship it back to the client side for presentation.

Answer 2

Sorry to answer with "What not to try", but I've never heard of a solution that doesn't involve predicting the outcome on client side. Consider a simplified example:

Client A is stationary, and watching client B's vehicle approach a cliff. Client B's vehicle is capable of reducing speed to 0 instantly, and does so at the last possible moment before going over the cliff.

If Client A is attempting to show Client B's state in real time, Client A has no choice but to predict that Client B fell off the cliff. You see this a lot in MMORPGs designed such that a player's character is capable of stopping immediately when running full-speed. Otherwise, Client A could just show Client B's state as the state updates come in, but this isn't viable, as Client A needs to be able to interact with Client B in real time in your scenario (I assume).

Could you try simplifying the collision models so that extrapolation is possible for real time prediction? Maybe make your "joints and bodies all over" have processor-less-intensive physical models, like a few cubes or spheres. I'm not too familiar with how to improve the efficiency of collision detection, but I assume it's done by detecting collisions of models that are less complex than the visual models.

Answer 3

Ross has a good point. You could simplify the model you use to detect collisions by abstracting it to some simpler volume (i.e. the rough boxy outline of the vehicle). Then you can do the predictions based on the simple volume and the detailed calculations on the exact volumes while you have the user distracted by the "explosion". It may not be perfect but would allow you to speed up your collision detection.

Answer 4

In addition to predicting on the client side where the other user might be and sending the collision information and how you handled it to the server, what most mmo's do to deal with lag is they have the server run "in the past" as it were. Basically they buffer the recent inputs but only react to what happened .1sec in the past. This lets you "peek into the future" when you need to (ie when a collision is about to happen in your time frame, you can look at the buffered input to see what will happen and decide if the collision is real).

Of course, this adds an extra layer of complexity to your program as you have to consider what data to send to your clients and how they should react to it. For example you could send the entire "future" buffer to the clients and let them see which possible collisions will actually happen and which won't.

Answer 5

Regarding "What not to try". You are assuming that you need to predict perfectly, but you are never going to find a perfect solution in a game with complex physics. An approximation is probably the best you can do (for example, most commercial physics engines can cast a shape into the physics scene and return the first point of collision).

For example, I implemented some critical parts of the network physics for Mercenaries 2 under the guidance of Glenn (the blog poster you mentioned). It was impossible to push all of the necessary physics state across the wire for even a single rigid body. Havok physics gradually generates contact points each frame, so the current "contact manifold" is a necessary part of the physics state to keep the simulation deterministic. It's also way too much data. Instead, we sent over the desired transform and velocities and used forces and torques to gently push bodies into place. Errors are inevitable, so you need a good error correction scheme.

Answer 6

What I eventually ended up doing was simply skipping prediction alltogether and simply doing this:

1. Client has very much say about its own position,
2. Server (almost) only says anything about the owning client's position when a "high energy" collision has happened with another dynamic object (i.e. not static environment).
3. Client takes meshoffset=meshpos-physpos when receiving a positional update from the server and then sets meshpos=physpos+meshoffset each frame and gradually decreases meshoffset.

It looks quite good most of the time (in low latency situation), I don't even have to slerp my quaternions to get smooth transitions.

Skipping prediction probably gives high-latency clients an awful experiance, but I don't have time to dwell on this if I'm ever going to ship this indie game. Once in a while it's nice to create a half-ass solution that works good enough but best. ;)

Edit: I eventually ended up adding the "ownership" feature that Glen Fiedler (the blogger mentioned in the question) implemented for Mercenaries 2: each client gets ownership of (dynamic) objects that they collide with for a while. This was necessary since the penetration otherwise becomes deep in high latency and high speed situations. That soluation works just as great as you'd think when you see the GDC video presentation, can definitely recommend it!