🔒 Locked

Networking - is it safe to assume the results of floating point calculations?

Started by Istrebitel Feb 9, 2010 at 2:35 AM 4 replies 1.4k views

Original Post

Feb 9, 2010 at 2:35 AM

Greetings! Short question: Can i assume that the result of calculations of floating point values (float type in C#) would be the same on every computer? Like, if i run a formula that uses multiple /,*,+,- actions on a set of floating point values, would it return the same value on each of my client's PC's? Long explanation: I am programming a turn-based strategy game. The game process goes this way: 1) Turn starts 2) Every player makes its orders 3) When every player made his orders, the turn "happens" - workers produce, farmers farm, etc, population in cities grows. 4) After turn "happened" the check is made if any battles can happen. If yes, players are given options to initiate combat. Combat happens (not-involved players can chat meanwhile) 5->1)After all battles that could have happened either happened or players did not initiate, new turn starts. There is two ways of making this go in phase 1-3. a) Send complete state of player's kingdom after he finished his turn. This would make alot of data to be sent over wire that didnt actually change (player could only issue one order that changed 2 integers but whole tables of his whole fleets, units, colonies, ahivements, tech tree etc are sent). b) Send only actions of the player. So, each player action is sent over wire, and by the end of player's turn every other player knows everything that player did in his turn. Applying those changes each player's client knows exact state of other player's kingdoms they have on their client. Going the way b), i come to the way of solving phase 3. Again, there are two ways to do it: Locally and on Host. Because every player has the exact same data by the end of the turn (because he received all actions from other players) every player could have ran the "turn happens" on his own client locally. This would indeed be more fast than either getting the data from the host (host calculates and sends all the changes - like "city #5 has grown up by 10.912 people") because the amount of changes can be really big (every fleet moves, every worker produces, every farmer grows crops, every city grows new population...) So, if i want to let every player Locally calculate the effects of the turn, i must be able to trust that every PC would do the same calculations (no random gen involved here). Some of the calculations involve foating point numbers. My question is, can i trust them to be the same on every PC? For example, i have a worker that produces 10 production points per turn, a leader that increases that value by 13%, a building that increases worker's output by 20%, and some negative effect that decreases worker's output by 1/3, and i need to know how many production points did my 7 workers produce this turn, rounded to the nearest integer, would this value be the same on every PC? Or, i have a population growth formula that involves calculating some different floating point values (modifiers from 0 to 1 that show how "Full" is the current city, how "healthy" are my people, also bonuses and penaties to growth apply, it results in some multiplications and divisions of foating point numbers). Same goes for fleets moving - fleet is moving in a 2d space, its coodinate must be an integer each turn but when it moves, it can have a non-integer x or y moving vector (like a fleet with speed of 7 moves from 0,0 to 10,2) so its position must be a result of some trunctation.

samoth

Feb 9, 2010 at 3:53 AM

Quote:
Original post by Istrebitel
Short question: Can i assume that the result of calculations of floating point values (float type in C#) would be the same on every computer?

Definitely no. Like all languages, C# uses native instructions to do floating point math rather than emulating the math in software (otherwise it would be quite slow).

You cannot even rely on the assumption that apparently identical calculations are identical on the same computer, in particular on the x86 architecture. That is because the number of bits in the floating point unit is not well defined, and excess bits are thrown away when writing to memory. Therefore a floating point value might be anything from 32 or 64 bits to 80, 96, or 160 bits.

If your compiler or JIT or whatever is in charge to translate and run your code decides that it needs to store something at one point and decides that it can keep it in a register at another point, the results will differ. And, the problem is, you never know.

Istrebitel

Feb 9, 2010 at 4:09 AM

Thanks! Okay, so, would you advise me to:

1) use integer for storing and operating with numbers, like instead of 1 production point have 1000 production points, then have all percent modifiers in integer form. and then for example, instead of doing 7(workers)*10(points per worker)*(modifiers)(1+0.2-(1/3)) do Math.Floor((7*10000*(100+20-33))/100)?

2) use decimal type for operating with numbers?

samoth

Feb 9, 2010 at 4:56 AM

You could make sure results are stored to memory (writing to an array and reading back, or something) to force a common bit size, or use some other trickery, or you could do similar-compares and say "screw it if something is off a few ticks" for everything else.

Except for comparisons, it does not matter most of the time whether a result is absolutely correct or precise. The player most likely won't know.
However, comparisons will fail terribly, and while it is possible to get them right, it is not trivial (read the "Epsilon is not 0.00001" article by Christer Ericson, it's on the internet for free).

On the other hand, it is a no-brainer to simply use integers, and honestly that's what I would just stick with. The results are automatically always correct and precise, and it's painless. Make up your mind what resolution you need, and multipy everything with a corresponding factor.
For example, if you multiply all numbers with 256, you get a 3.9 mm (0.15 in) minimum resolution, and you can go as big as 16.000 kilometers using a 32 bit integer. That's more than enough for most applications. If 3.9 mm is too coarse for you, use a bigger number. For most games, even 20 cm would probably be enough, but it depends.

EDIT: link

Istrebitel

Feb 9, 2010 at 7:42 AM

yes thank you we are taught in 1st high school grade in russia about floating point storage in the PC, about epsilon, we al did a demo example to verify that (you start with 1 and /10 each time until the result is equal to 0)

What i was asking (and i got my answer) is that i cannot guarantee that the calculations are always made with exact precision. The result can indeed matter because it will ultimately result in a desync. Its can be just 0.00001 more populant on the client 1 than on the client 2, but if thats the matter of 0.49999 on one clien, a 0.00001 difference means one client will still have X population and cient two X+1. Thats when it will make one client finish production (Because one more worker makes it go faster) and other client report that its still in progress. And then i will have an invalid operation when that player says "i'm ordering unit100 to move south" and my client says "there is no unit100 under your control"

Thats why i need precision. Well, i kinda understand i should just use integers for everything that counts and do all operation in integer space, multiplying first and divising last, so everything gets truncated the same way.

I suppose i can assume that if
int a=150
int b=100
then int c=a/b will give the same result, wether it is 2 or 1 i dont really know by heart how's the rounding done by default, but same result across any pc with any hardware? Or i should always do (int)Math.Round(formula) to verify its always the same? Or use either Math.Floor or Math.Ceiling (dunno why but people sometimes dont recommend the use of Math.Round and i've seen that most opensource games prefer to fo Floor(X+0.5) instead of Round(X) for some reason)?

Antheus

Feb 9, 2010 at 7:48 AM

The easiest way is to separate simulation from presentation. Define work unit as 1, indivisible. Let work complete be 100,000. Then it is fairly trivial to define basic work done by worker as 100. Adding 20% efficiency means they'll do 120 units of work.

Above, you would calculate the workload like this: 7(workers)*10(points per worker)*(modifiers)(1+0.2-(1/3)

Instead, turn the problem around.
Modified work unit: 100 + 20 - 33 = 87
Workers contribution: 7 * 87 = 609
Total work += 609

Or, formally, dTotalWork/dt = (wModifiedWork * nWorkers)dt. This equation doesn't suffer from accuracy issues as long as both values are integers. This can then be integrated numberically (aka, add the result to total on each tick).

Quote:
fleet is moving in a 2d space, its coodinate must be an integer each turn but when it moves, it can have a non-integer x or y moving vector (like a fleet with speed of 7 moves from 0,0 to 10,2) so its position must be a result of some trunctation

If working on a grid, moving between points involves some sort of pathfinding anyway, so moving each unit will involve something like A* or shortest path algorithm, or even just bresenham algorithm, all of which are discrete in nature. Or, while s = v/t, ds/dt = vdt.

Detail: assuming the cost of moving diagonally is sqrt(2). If calculating to two points of precision (1.41), then scaling upwards by 71 works (normal cost is 71, diagonal is 100). If one were calculating paths thousands of units long, then rounding error would cause mathematically incorrect results, but the errors would be consistent. In practice, just using 7 and 10 as costs is likely to be good enough.

However, square root can be expanded into Taylor series, and cost of path can be expressed as sum of those. Since constant terms in sqrt(1+x) are same for x=0 and x=1, result up to desired accuracy can be accumulated and can even overflow if needed since it is just a summation.

Anyway....

While it may include some scaling, these approaches are implicit and don't require fixed-point math, which introduces its own set of issues. This approach also plays well with the nature of the simulation and produces accurate results - for example, work contribution could be calculated on per-worker basis, each with their own bonuses. Given that one manages to convert the desired formulas into proper format.

The only upfront decisions that need to be made (and can be adjusted later to an extent) are the primary scales, such as work unit, and expected modifiers on it. Obviously, scaling the unit by less than 1% will simply not work.

Istrebitel

Feb 9, 2010 at 8:07 AM

Unfortunately i do need to round worker's production every turn (so even if my 7 workers do 609 work, i must make it either 6 or 7). And movement on the map can happen not only diagonal/left/right but at any angle. So, that leaves the need for doing foating point calculations. And the need for truncations to happen. Thanks for giving a detailed answer, stil:

Question 1: Will integer division operation always result in same outcome? Is 150/100 equal on each and every pc in the world that will be able to run my program? Or it can be 1 or 2, depending on something?

Question 2: Is it safe to use Math.Round (to closest integer) and why? Is it safer to replace Math.Round with Math.Floor of value+0.5 and why? By "safe" i mean, will Math.Round done on integer division like Math.Round(150/100) always prodive same results on each and every pc in the world that will be able to run my program?

Antheus

Feb 9, 2010 at 8:26 AM

Quote:
Original post by Istrebitel
Unfortunately i do need to round worker's production every turn (so even if my 7 workers do 609 work, i must make it either 6 or 7).

No, why?

Quote:
And movement on the map can happen not only diagonal/left/right but at any angle.

But the coordinates are integers. Which is why I mentioned Bresenham algorithm. There is no reason why coordinates should be floats. Distance traveled can be managed as well through accumulation.

If Bresenham is used to move between pixels, then at pixel resolution, the movement is in one of 8 directions (vertical, horizontal, diagonal). But, due to rounding, this could lead to undershooting long routes. So whenever moving from A-B, keep track of total distance traveled so far. If a unit can move 7 units per turn, but it only travels 6 due to diagonal movement and rounding errors, on next turn it can move (7+7 - 6) = 8 units. Or, on turn n it can move n*max_distance-traveled_so_far. This is a simple accumulator technique which absorbs accuracy errors.

Quote:
So, that leaves the need for doing foating point calculations. And the need for truncations to happen.

No. Why? The only time you need to round to real units is when displaying data, which is done on each client individually and for display purposes only. Everything else is done discretely - the internal state is never rounded.

Quote:
Question 1: Will integer division operation always result in same outcome?

The point of the above is, as far as simulation goes, that divisions aren't needed. Even multiplication isn't needed, only summation.

Quote:
Is 150/100 equal on each and every pc in the world that will be able to run my program? Or it can be 1 or 2, depending on something?

I don't know. As far as floating point goes, if absolute accuracy is really required, I prefer to avoid it completely.

BTW: this is how just about every single Master Of ..., Civilization ... and all other 4X simulations work. Aside from avoiding accuracy issues, it is also incredibly cheap to compute.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.