non-deterministic floating point calculations

Community Forums/General Help/non-deterministic floating point calculations

Richard Betson(Posted 2012) [#1]
Hi All,

I am looking for tutorial to work around non-deterministic floating point calculations that are inherent in a PC (you may not get the same result twice on the same machine) and cross platform floating point calculations.

I am working on client side prediction and this is a problem. Any advice or a link would be appreciated. :)

Thanks

Last edited 2012


Richard Betson(Posted 2012) [#2]
Perhaps truncating the floating point number to say 4 decimal places (for example) and convert to integer like this ( float * 10000 ) =Int and then converting it back to a float like this ( Int / 10000 )=Float. Or just using truncated floating point numbers.

Edit- In effect lowering the precision of the floating point number but getting improved accuracy.

Last edited 2012


Matty(Posted 2012) [#3]
Do you need to use floats or can you use integers and simply scale them to floats client side?


Richard Betson(Posted 2012) [#4]
Hi,

Well,.. yes I do. At least I am not ready to concede to using integers yet. I have a client side prediction framework that both the client and the server use and the same exact physics. So the floating point numbers need to match. My collision system would suffer the most under integers.

I am thinking the differences in the floating point numbers between two platforms might be very small at 4 decimal places and I could handle it in my client side prediction framework.

Also the precision at 4 decimal places should be good enough for the collision and physics framework.

Last edited 2012

Last edited 2012


Floyd(Posted 2012) [#5]
If there is any hope for this approach it would involve rounding to fewer digits, not truncating.

The numbers 1.999999 and 2.000001 are nearly identical but would truncate to 1 and 2 when the precision drops to anything less than seven digits. They both round to 2.

I'm not optimistic about this in any case. Is it really essential that the server be able to predict the results of calculations done by the client? Perhaps you could design things so the client reports results and the server just knows what state each client is in. If not then the only reliable solution may be to have the server do all the calculations. But then the server may not be able to handle the load.


Yasha(Posted 2012) [#6]
The short answer is always to use integers, or more specifically scaled fixpoint numbers (which are usually implemented as integers behind-the-scenes and would be if you used them in Blitz). There is no way to solve this problem for realsies, because you've hit on one of the problems with floating-point in general: it's not accurate. It cannot be used to represent accurate numbers. It can't even be relied upon to give consistent results on the same machine, let alone different machines. Floats were developed for high performance, and throw accuracy out of the window to achieve it (resulting in one of the golden rules of programming: if you ever use a float for a financial calculation, quit your job and become Amish).

Fixpoint also offers excellent performance, but it can be rather hard to use in a language that doesn't have code-level support for it (since you can't write 1.5:Fix and have it auto-translated by the BlitzMax compiler to 150000:Long or whatever).


Anyway, the other obvious solution (more obvious, I just wanted to get the "floats are useless" bit done first), is that this problem doesn't matter. Firstly, in a client-server game, the server should absolutely never accept physics or movement calculations from the client. Clients do what they are told: if it were negotiable, it'd be P2P. So when the physics information comes in from the server, it has to overrule whatever the client came up with for its prediction.

In turn this means that if the predicted positions are different from those delivered from the server, they need to be changed. The thing is, there's nothing really wrong with this: in the same way that player movement position won't be completely accurate because the prediction system can't predict when someone's going to make a sharp turn. Even AAA games allow objects to simply be corrected into the new position and abandon the predictions, and then the new prediction can be made with 100% juicy natural server-delivered data. If the player actually sees the effect of this (players suddenly teleporting six feet in the wrong direction, objects jerking into different orientations), it means their connection is too slow for a high-speed physics-based game, and that's that: your game has a minimum system requirement of a consistently fast internet connection. In this day and age that's not much to ask.

For only one or two prediction steps, you can probably smoothly move objects back into the right position, because they shouldn't have moved too far anyway (again, this will not affect anything if you remember not to use client-side data for predictions at any point where server-side data is available): for more prediction steps, the client is being too slow. Not your fault.

But to reiterate the point: there should be no real need for the figures to match, because at the end of the day the client's take on events is unimportant: its generated data should never be used in the next prediction step anyway if more recent server data is available (if you miss intermediate packets from the server, better to generate interpolated data based on the server than to try to fill it in with client simulation).


Richard Betson(Posted 2012) [#7]
Hi,

In my frameworks there are just a few variables that need to match on the both the client and the server. Those would be object position (x,y), object velocity (dx,dy) and object rotation. There are other variables involved but I'll use these as an example. At 4 decimal places there is likely to be little difference in the values of two floating point numbers on two separate platforms. So I might get values like these using single precision:

Platform A - 1.999991
Platform B - 1.999993

Truncated to 4th decimal place I would have 1.9999 on both platforms. In the case of:

Platform A - 1.999998
Platform B - 2.000000

If platform A is the server I could then correct the client (platform B ). This is what I was envisioning and why I suggested higher accuracy in matching between the two platform values.

The reason I want the values to match on both the sever and the client is the reduced latency that client side prediction offers. If two simulations are running they should both have the same results on each side. But since floating point numbers are non-deterministic I felt that reducing the precision would increase the rate at which the simulations match values. Since I may have hundreds of clients the need to reduce server corrections is paramount.

Last edited 2012


xlsior(Posted 2012) [#8]
Depending on what you're trying to accomplish: Brucey has a blitzmax module that can handle 'proper' math with arbitrarily large numbers without having to resort to inaccurate floats. (Don't remember the module name, unfortunately)

(Of course it is slower than native maths on the standard datatypes, but depending on your use that may not be a huge issue)


Noobody(Posted 2012) [#9]
Just to clear up a few misconceptions:

you may not get the same result twice on the same machine

Floating point operations are deterministic on the same machine. It would indicate a serious design problem if a floating point unit returned different results for the same input. The behaviour of the floating point unit is standardized and does not involve randomness.

Floats were developed for high performance, and throw accuracy out of the window to achieve it

Actually, quite the opposite is true. The IEEE float standard was developed with mainly numerical considerations in mind - the rules for overflow, underflow, floating point exceptions, rounding modes, subnormal numbers etc. are very strict! This is one of the main reasons why making a fast floating point unit was so damn hard when the standard first came out; all the special cases and precision constraints make FPUs extremely complex.
Representing arbitrary decimal numbers with a limited number of bits is inherently inexact, but imo the float standard did a very good job at defining a numerically usable format.

There are a few important things to know about floats, though:

1. Not all finite decimal numbers can be represented with a finite binary number. 0.1 in decimal, for example, corresponds to the infinite binary number 0.000110011001100110011001100....... This doesn't have anything to do with floats or doubles or even computers - this is simply a mathematical fact.
Obviously, once you try representing that number with a finite number of bits, you have to truncate the infinite sequence - which is why you get numbers like 0.12999999 or 0.100000001.
It is understandable that the first intention is to think that the operations (+, -, /, *) are extremely inexact and have a random number generator attached that switches out the last few digits when it feels like it, but in most cases the problem is simply that the operands can't be represented in binary in the first place. (for example, 0.1 + 0.1 is not exactly 0.2, but 0.0625 + 0.0625 is exactly 0.125 - this is not a problem of the + operation, but of the representation)

2. While floating point operations are standardized across platforms, auxiliary math functions (sin, cos, tan, sqr, exp, pow etc.) are not. Depending on the platform and the library version, you might (and probably will) get different results if you use these.

3. The order of operations matters! The CPU rounds after every operation to fit the result back into float accuracy, so it is important which operations are executed first. For example, when calculating a*b*c, it may matter whether a*b or b*c is calculated first. Most compilers (including the BRL ones) don't specify the order of operations (especially because it might change when the compiler optimizes), so the results of floating point code might differ between compilers and compiler settings.


There are many AAA games out there that rely on deterministic floating point operations. Many multiplayer RTS games for example usually only send the user input over the network and don't sync every unit specifically, and most games with a "replay" function simply save the user input, not every piece of data at every point in time during the game.

You might find this article interesting which has a massive list of resources about the topic.

The basic gist of it: The problem lies not within the floating point implementation, but with math libraries and the compiler. You can make floating point deterministic if you're very careful and tune your compiler and libraries appropriately (which is most likely not possible in BB/BMax).

Last edited 2012


Floyd(Posted 2012) [#10]
Floating point operations are deterministic on the same machine.

That's usually true but not always. Floating point results depend not only on the hardware but also on the "state" of the floating point unit. The precision defaults to, I think, 80-bit for Windows. Some programs set it to 64-bit and 3D programs may even set it to 32-bit.

There was a remarkably baffling example of this many years ago. It was so long ago that the thread no longer exists. Somebody had an example which he claimed sometimes produced different numerical results, but the Blitz3D code he posted didn't have that problem when other people tried it. It turned he was using GameCam to record in-game video. It was a DLL and recording could be turned on or off with a Blitz3D program. That silently changed the FPU precision mode. The Blitz3D program then got different numerical results depending on whether GameCam was running.


Richard Betson(Posted 2012) [#11]
It is looking like the best approach is to just deal with the non-deterministic nature of floating point numbers by correcting clients when they (a client object) drift out of position due to differences in floating point values as they accumulate over time.


*(Posted 2012) [#12]
Rich couldnt you use two ints or shorts to get the same effect as a float for and just do some simple math pokery to get the fraction part to the fraction bit of whatever your doing. Iirc this is what sage does for accounting :)


Richard Betson(Posted 2012) [#13]
Hi Ed,

I could but...

The real issues here for me is efficiency. Once you start to go fixed point or other option I would end up having to process operators and math function as well as the floating point number I'm trying to avoid. So that's a whole level of computation over hundreds of clients from the servers point of view. In client side prediction the server maintains a master game state so not only would the clients have to handle all this calculation load but the server as well; not good.

The server will have to check the clients to see if there is any cheating say every three seconds (for example). So the server sends a position verification command and the client responds with it's position. Since this has to be done anyway the correction to position is a simple send float. The hit to band width is small and should be acceptable. The server only compares two floating point values and that's it. Minimal computation load there. In addition I'm using input commands to/from the clients so no (essentially) floating point numbers are sent/received other then position corrections.

Ideally both the the server and client would always have the same floating point values but that is not possible. So the issues is how big is this effect and what impact does it have on the client side prediction model. The differences are likely to be 'very small' so the effect is cumulative over time. That accumulation time for my model is acceptable due to the corrections from the server.

In first posing this question I was seeking a workaround but the more I look into it the more I'm convinced server corrections to the clients is the way to go and keep the floating point math in place.


D4NM4N(Posted 2012) [#14]
Use doubles? Arent they supposed to be more accurate? Afaik they are.
If that is not possible then you could either do what Richard said, although that does not guarantee results.. alternatively you could store the value as a class using 2 integers with its own maths code.
I guess it depends on what you are doing and how fast it neds to be.

Last edited 2012


*(Posted 2012) [#15]
Rich: I can see where your coming from on those one I too would get the server to 'correct' the client ever second this keeps it smooth and running fine, it should also keep the floats in order. Unfortunately its the way of the beasty as soon as CPU's went Pentium (586) and up the error was there strangely enough they didnt find it on 486 IIRC.