Sign in to follow this  
Daniel Miller

Synchronized games and floating point

Recommended Posts

There has been discussion about this already, but no real answer was given. How do modern RTS games (which all employ synchronized simulations for each client) handle floating point numbers? Normally, floating point numbers can vary slightly between different computers, which would throw each and every game off sync. Does anyone know how they pull this off? Games can't trust one of the clients for "corrections", that would completely open the door for all sorts of hacking.

Share this post


Link to post
Share on other sites
I don't think it's any different than any other network game. The server keeps the best record of what is really going on, and sends out updates to the clients at intervals. Inconsistancies due to floating point numbers won't even show up before the next update.

Share this post


Link to post
Share on other sites
Interesting question.

One thing you can do if you're windows only and using MSVC is to enable fixed floating point accuracy. It has some overhead though, so I wouldn't call it a solution.

Using a certain amount of bits, perhaps?

[Edited by - SymLinked on May 22, 2007 6:19:38 AM]

Share this post


Link to post
Share on other sites
Quote:
Original post by Daniel Miller
How do modern RTS games (which all employ synchronized simulations for each client) handle floating point numbers?

What modern RTS games do employ synchronized simulations? I don't have any actual info, but I'm quite sure that a client-server model is usually used.

Share this post


Link to post
Share on other sites
We had a big thread on this recently: http://www.gamedev.net/community/forums/topic.asp?topic_id=446873

Quote:
Original post by CTar
Quote:
Original post by Daniel Miller
How do modern RTS games (which all employ synchronized simulations for each client) handle floating point numbers?

What modern RTS games do employ synchronized simulations? I don't have any actual info, but I'm quite sure that a client-server model is usually used.

Probably the Age Of Empires games ( http://www.gamasutra.com/features/20010322/terrano_01.htm ), and judging from the sheer number of units probably Supreme Commander as well.

Share this post


Link to post
Share on other sites
Quote:
Original post by CTar
Quote:
Original post by Daniel Miller
How do modern RTS games (which all employ synchronized simulations for each client) handle floating point numbers?

What modern RTS games do employ synchronized simulations? I don't have any actual info, but I'm quite sure that a client-server model is usually used.


Supreme Commander does, it was mentioned in an interview. Warcraft 3 does as well, judging from their replay files.

Share this post


Link to post
Share on other sites
Thanks for the link. How would I get sin and cos values if I only used integers?

edit: I should elaborate. If sin and cos return doubles, I couldn't trust the returned value to be the same across all systems.

[Edited by - Daniel Miller on May 23, 2007 1:00:32 AM]

Share this post


Link to post
Share on other sites
The differences are tiny - by the time you've rounded them up to the 'safe' range they're almost guaranteed to be the same.

Ultimately, if you're not going to have an authoritative owner of the simulation, then you're always open to synchronisation issues, whether deliberate (hacking) or accidental (loss of precision). Luckily the chance of the latter being an issue is statistically minimal compared to the first.

Share this post


Link to post
Share on other sites
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!

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Quote:
Original post by Fingers_
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.


Is that really what would happen? In binary, that isn't how those numbers look. The first bits would be the same, but the bits "past" your needed precision would be different.

Wouldn't taking the first 16 bits be safe?

Share this post


Link to post
Share on other sites
Quantization errors between two different computers can theoretically happen, but they are so rare that in the last couple years that I've been working on games that use this type of networking, I've never seen one happen. I have seen plenty of sync errors caused by programming mistakes though.

What we do where I work is just use floating point, run the simulation on all machines, and terminate a network game if it goes out of sync instead of trying to get it back into sync. It works well enough.

j

Share this post


Link to post
Share on other sites
Quote:
Original post by jdi
Quantization errors between two different computers can theoretically happen, but they are so rare that in the last couple years that I've been working on games that use this type of networking, I've never seen one happen. I have seen plenty of sync errors caused by programming mistakes though.

What we do where I work is just use floating point, run the simulation on all machines, and terminate a network game if it goes out of sync instead of trying to get it back into sync. It works well enough.

j


That's good! Haha

What sort of games are you talking about? How are floating point values used in the game?

Share this post


Link to post
Share on other sites
Quote:
Original post by Fingers_
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.


Hmmmm yeah, you're right. I guess if you need deterministic transcendental functions you need to implement them yourself, or find a library that does.

On the other hand, trig functions can often be avoided. Sines and cosines for angles that are known in advance can be precomputed. Unit direction vectors can work just as well for some purposes, and finding the direction vector from one point to another involves just some subtractions and normalizing a vector (I guess you'd still need a fixed point square root or reciprical square root routine). You can check if the angle between two direction vectors is less than or greater than an arbitrary angle known in advance by precomputing the cosine of the angle and comparing it to the dot product of the vectors. Rotations can be performed using precomputed rotation matrices.

[Edited by - Vorpy on May 26, 2007 1:04:38 AM]

Share this post


Link to post
Share on other sites
The angles could not be pre-computed. They would be movement and firing angles for each unit. I think I'll just waltz ahead and use floating point, and if it doesn't work I'll just break down crying.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this