Synchronized games and floating point
Author
Yeah, doubles have about 15 digits of precision, so if I take 10 of those and throw them into an integer, I'm almost guaranteed not to have any issues. Thanks to everyone for clearing this up!
It doesn't matter what the precision is, if one computer says something is 9.99999999999999999999999 and another one says 10.0000000000000000000001 and you convert the numbers to ints then the game will diverge. The only way to be sure that everything will stay in synch (besides using identical computers, ie. consoles) is to only use fixed-point math. Trig functions like sin and cos can be replaced with a pre-calculated look-up table.
Quote:Original post by Fingers_
It doesn't matter what the precision is, if one computer says something is 9.99999999999999999999999 and another one says 10.0000000000000000000001 and you convert the numbers to ints then the game will diverge. The only way to be sure that everything will stay in synch (besides using identical computers, ie. consoles) is to only use fixed-point math. Trig functions like sin and cos can be replaced with a pre-calculated look-up table.
If one computer says x=9.99999999999999999999999 and another one says x=10.0000000000000000000001 and you compare them like this: if(abs(x-y) <= epsilon), comparisons will be quite accurate within epsilon. (epsilon should be 0.00000000001 or something.) That way, both computers will get the same way unless the errors are bigger than epsilon.
Using sin and cos should be safe, as long as the inputs are converted from fixed point to floats immediately before conversion and immediately afterwards, assuming the fixed point uses something like 8 or 16 bits for the fractional part. The output from sin and cos is always between -1 and 1, so all of the bits of the mantissa are used to express some fraction. The mantissa definitely has more than 16 bits, so there's no room for imprecision, as long as the conversions between fixed and floats are handled in a robust manner (maybe a multiplication + floor or ceil would work to go from floats to fixed).
nagromo: That is incorrect. Using an epsilon value works well for comparisons between floats in a simulation on a single machine, but in this case multiple machines are running the simulation and they must stay perfectly in sync. Floating point errors like that could potentially build up over time until they are no longer within that epsilon value.
Hmm...actually as long as you're careful, it seems like it could take quite a while for minor precision errors like that to diverge beyond an epsilon value. I wonder if that's why Age of Mythology sometimes desynced in multiplayer when I played it.
nagromo: That is incorrect. Using an epsilon value works well for comparisons between floats in a simulation on a single machine, but in this case multiple machines are running the simulation and they must stay perfectly in sync. Floating point errors like that could potentially build up over time until they are no longer within that epsilon value.
Hmm...actually as long as you're careful, it seems like it could take quite a while for minor precision errors like that to diverge beyond an epsilon value. I wonder if that's why Age of Mythology sometimes desynced in multiplayer when I played it.
precision errors build up fast, the moment two boxes disagree on simulation results (even if they are small) you can get into very challenging situations, to make thinks worst different processors can give you different floating point results (AMD vs Intel)
Fixed point is the usual answer to this problem, or having an authorative server, and local simulations that are corrected by the a state update from the server.
One thing you can do is to split up your simulation into deterministic and non-deterministic state, deterministic state should always be perfectly in sync, non-deterministic should be simulated locally and the outcome should not affect gameplay.
Fixed point is the usual answer to this problem, or having an authorative server, and local simulations that are corrected by the a state update from the server.
One thing you can do is to split up your simulation into deterministic and non-deterministic state, deterministic state should always be perfectly in sync, non-deterministic should be simulated locally and the outcome should not affect gameplay.
To avoid some issues with comparison use a precision amount. By this i mean if (10.00001 - 9.99999) < PRECISION
x = true
This may solve some issues but not all.
x = true
This may solve some issues but not all.
In a non-client-server (p2p) game network, if precision errors can make the game fall out of synch, then hackers can also force the game to de-synch.
[edit : semi-rant warning!]
This is bad. If you're about to lose a ranked game, you just run your little hacker program and BAM! the game falls out of synch and you get a draw instead of a loss.
This is the kind of thing that can make or break a competitive online game.
What I'm saying is that you're asking the wrong question.
The answer to "how can I make sure that all clients simulate the same values?" is "you can't!". Even if you use fixed-point math etc, each client can still hack their game and change the outcome of the simulation.
Instead you should be asking "What can I do if clients simulate different values?".
1) Every time clients exchange input updates (every network tick), also exchange a compressed delta of the last simulation tick.
2) Ensure that these deltas are the same, if they're not, then the simulation has lost synch through error (loss of precision, which you can prevent), or through hacking (which you can't prevent).
3) When synch is lost, make all clients pause and rewind the game-state the the last agreed upon result.
4) Then you need to make a choice about which client's version of the simulation is "correct". - You can make this arbitrary by saying the host's version of events is always the correct delta (but then the host can cheat), or if there's more than 2 players you could see if the majority of clients agree on one version of events and use their delta.
It doesn't matter too much how you do it, just as long as you have a process in place to validate simulation results between clients and reject bad data.
Which ever way you do it, you have to remember that you cannot ever trust any network data, ever. You have to be suspicious of all network inputs because network data is easily hacked, and if you don't inspect this data for validation, then hacking cheaters will ruin your game.
[Edited by - Hodgman on May 28, 2007 2:37:25 AM]
[edit : semi-rant warning!]
This is bad. If you're about to lose a ranked game, you just run your little hacker program and BAM! the game falls out of synch and you get a draw instead of a loss.
This is the kind of thing that can make or break a competitive online game.
What I'm saying is that you're asking the wrong question.
The answer to "how can I make sure that all clients simulate the same values?" is "you can't!". Even if you use fixed-point math etc, each client can still hack their game and change the outcome of the simulation.
Instead you should be asking "What can I do if clients simulate different values?".
1) Every time clients exchange input updates (every network tick), also exchange a compressed delta of the last simulation tick.
2) Ensure that these deltas are the same, if they're not, then the simulation has lost synch through error (loss of precision, which you can prevent), or through hacking (which you can't prevent).
3) When synch is lost, make all clients pause and rewind the game-state the the last agreed upon result.
4) Then you need to make a choice about which client's version of the simulation is "correct". - You can make this arbitrary by saying the host's version of events is always the correct delta (but then the host can cheat), or if there's more than 2 players you could see if the majority of clients agree on one version of events and use their delta.
It doesn't matter too much how you do it, just as long as you have a process in place to validate simulation results between clients and reject bad data.
Which ever way you do it, you have to remember that you cannot ever trust any network data, ever. You have to be suspicious of all network inputs because network data is easily hacked, and if you don't inspect this data for validation, then hacking cheaters will ruin your game.
[Edited by - Hodgman on May 28, 2007 2:37:25 AM]
Author
I'm not worried about intentional de-syncing. I'm not going to have any record keeping, so de-syncing will be the same as just closing the game. Thanks a bunch for the tips, though.
Is the only solution a look-up table for sin/cos? That seems... bad.
Is the only solution a look-up table for sin/cos? That seems... bad.
No you do not need to use a lookup table for sin/cos. A float will have more than 16 bits of precision, and 16 bits should be more than enough for the fractional part of the fixed point numbers (8 bits could also work). Just avoid doing sequences of operations with floats. To get the sine of a fixed point number, convert it to a float, call sin, and convert the result back to fixed point. There is no room for different internal precisions to affect the result since you're not even using the precision guaranteed by the floating point standard. It's probably best to get the angle within the -pi to pi range before converting it to a float for using sin.
On the subject of intentionally altering values to abort the game and cause a draw: in a 2 player p2p game, there is absolutely no way to prevent this no matter what you do, since an authoritative server is not involved in the communication. The hacker can always hack it so that it looks like they did nothing, after causing the desync. They can just as easily disconnect instead. There's no way to tell who lost the connection. Having the games decide that one player's simulation is right and the other was wrong does not help, because there's nothing to prevent them from chosing the hacker's simulation. Then the hacker could freely alter the game, and sometimes the simulation would allow it.
On the subject of intentionally altering values to abort the game and cause a draw: in a 2 player p2p game, there is absolutely no way to prevent this no matter what you do, since an authoritative server is not involved in the communication. The hacker can always hack it so that it looks like they did nothing, after causing the desync. They can just as easily disconnect instead. There's no way to tell who lost the connection. Having the games decide that one player's simulation is right and the other was wrong does not help, because there's nothing to prevent them from chosing the hacker's simulation. Then the hacker could freely alter the game, and sometimes the simulation would allow it.
Quote:Original post by Vorpy
No you do not need to use a lookup table for sin/cos. A float will have more than 16 bits of precision, and 16 bits should be more than enough for the fractional part of the fixed point numbers (8 bits could also work).
The precision does not matter; the problem is quantization of values where an *arbitrarily small* difference can go across a threshold between two quantization levels.
For example:
Computer A says sin(pi/6) = 0.499999999999999999999999999999999999999999999999999
Computer B says sin(pi/6) = 0.500000000000000000000000000000000000000000000000001
When you quantize these into a 16-bit fixed point fraction, A returns 32767 and B returns 32768. The simulation diverges and all hell breaks loose.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
