Client-Side Physics Prediction

Topics: Developer Forum
Feb 29, 2012 at 1:18 PM

Hey guys!

I've been writing an MMORTS game that's a 2d top-down space shooter style game. We have multiple players that can shoot bullets and fire at each other, it's pretty spiffy. Farseer is amazing for what we're doing and I'm so glad we didn't have to code all of this ourselves! We tried... But when we started getting into Einstein's theory of relativity to solve gravity and light speed related equations... yeah. I don't know how the devs here do it!

So, what we're working on right now is a client-side prediction algorithm that we can use to close the gap with latency. 100-250ms latency is a case that I know will exist pretty normally, and having an algorithm that can cleanly predict player movement will be very nice.

Our game has every client running it's own physics simulations. (we'll change it later) Each client sends the server it's position and the server relays this to all other clients. My question can be broken into two sections.


Section 1 - Non-Jittery Movement:

  • Clients are updated between 16-24 times per second depending on load
  • Rate of update is not high enough for 'smooth' stepping of each player
  • Need basic algorithm that hides the movement time between each step 

Each Message that the client sends/receives contains:

newPosition
newRotation
newLinearVelocity
newAngularVelocity

That looks much better adding velocity, but it's still bad. I was thinking a simple check that prevents the classic 'rubberbanding' effect in most cases. Here's some pseudocode of what I'm thinking.

- every ship on every client is located at some currentPosition and
moving at some currentVelocity
- define 2 radii around every ship: smallRadius, mediumRadius
- then say a message is received with another player's newPosition and
newVelocity, do the following:

(1) if the other player's currentPosition is within smallRadius of the
newPosition in the message,
then leave the ship where it is and set currentVelocity = newVelocity

(2) else if the other player's currentPosition is within mediumRadius
of newPosition in the message,
leave the ship where it is and set it's velocity to (newPosition -
currentPosition) to make it move to where it should be

(3) else if the other player's currentPosition is outside both radii, then
teleport the ship to the newPosition and set the currentVelocity to
the newVelocity

 Has anybody tackled this problem before here, and does this look alright?


Section 2 - Time Sync Between Clients:

  • Clients add LocalTime to Update Message
  • We calculate the time in the message and the current time
  • We then step the object to it's projected position based on that information

This would be taking the time difference (latency) between the clients and predicting the future physics simulation of that object. My problem is that I don't know how to step a specific object forward in time inside of Farseer. I don't want to do a World.Step() because that would update all objects, and that is the opposite of what I want.

Has anybody had to do this before or something similar? A check around the board here didn't reveal anything. Does anybody have any suggestions or talk a bit about how they perform their network-physics management?

Thank you guys!
-Free

P.S. For more info of what I'm doing, check the screenshots on my blog at http://spacerambles.com/ 

Feb 29, 2012 at 5:31 PM

Hi - you're asking a very difficult question. It's really one of toughest things to do for a game and no one has the perfect solution. I don't have any direct experience (although I had myself dealt with similar issues in P2P networking) but being an EVE online veteran I can tell you stuff like this is CCP's daily bread and their solutions is what makes their game absolutely top in terms of technical excellence. Funny enough it's a space shooter like yours :) Sometimes they talk about it in the blogs (mostly around 2009-2010 afair, recently they have developed an ingenious algorithm for huge battles called time dilation). 

One thing that stroke me immediately in your post is you never talk about interpolation. That makes me think you are not actually trying to sync the physics but rather trying to obtain an exact simulation on more than one client. That would require determinism which is really a can of worms and not supported (at the minimum you'd need fixed point math due to floating point rounding errors). For syncing you're much better off with predicting the physics and peroidically correcting the errors (that means teleporting objects rather than stepping the world). I have a few links that might help:

Here's how valve do it:

https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Your line of thinking is somewhat similar to one family of algorithms so-called "dead reckoning":

http://www.gamasutra.com/view/feature/3230/dead_reckoning_latency_hiding_for_.php

I hope these help depeing on how deep you are willing to go with this.

P.S: If you are writing a competitive multiplayer game - never trust the client.

Feb 29, 2012 at 11:41 PM

 

jerrysb wrote:

One thing that stroke me immediately in your post is you never talk about interpolation. That makes me think you are not actually trying to sync the physics but rather trying to obtain an exact simulation on more than one client. That would require determinism which is really a can of worms and not supported (at the minimum you'd need fixed point math due to floating point rounding errors). For syncing you're much better off with predicting the physics and peroidically correcting the errors (that means teleporting objects rather than stepping the world). I have a few links that might help:

I hope these help depeing on how deep you are willing to go with this.

P.S: If you are writing a competitive multiplayer game - never trust the client.

Hey Jerry,

I didn't know about the concept of interpolation. Or atleast that it was well established, I had spent all night abstracting the concept of it!

Now that I know what interpolation is. That leads me to needing some way of interpolating. The method with the radius around the ships sounds like it could work still, you've got your margin of error and velocity allows for the physics engine to 'lerp' between updates.

The end goal of that would be, "predicting the physics and periodically correcting the errors" like you said. That is a doozey though! If you have anymore details on this, I could use them. This valve page is an interesting read.

And as for trusting the client, I'll be tackling serverside physics at a later time. We're going to be entering a private alpha. I don't want to code all of that immediately, there are much more pressing issues.

Thank you very much!

Mar 4, 2012 at 5:45 PM

I've dug some more links from my archive on the topic that you might find interesting:

http://gamedev.stackexchange.com/questions/249/how-to-write-a-network-game

http://www.gabrielgambetta.com/?p=11

http://www.gameproducer.net/2006/12/16/planning-is-essential-in-writing-multiplayer-network-code/

http://gafferongames.com/networking-for-game-programmers/

BTW there is another way approach to the whole networking part that might even be simpler for a game like yours: instead of sending physics around just send user input and syncronize every x seconds.  If you read gafferongames it seems recently he has taken quite a liking to this approach although there is still no "recommended" way to do it.