c++ - How are deterministic games possible in the face of floating-point non-determinism?

To make a game like an RTS networked, I've seen a number of answers here suggest to make the game completely deterministic; then you only have to transfer the users' actions to each other, and lag what's displayed a little bit in order to "lock in" everyone's input before the next frame is rendered. Then things like unit's positions, health, etc. don't need to be constantly updated over the network, because every player's simulation will be exactly the same. I've also heard the same thing suggested for making replays.

However, since floating-point calculations are non-deterministic between machines, or even between different compilations of the same program on the same machine, is this really possible to do? How do we prevent that fact from causing small differences between players (or replays) that ripple throughout the game?

I've heard some people suggest avoiding floating-point numbers altogether and using int to represent the quotient of a fraction, but that doesn't sound practical to me - what if I need to, for example, take the cosine of an angle? Do I seriously need to rewrite an entire math library?

Note that I am mainly interested in C#, which as far as I can tell, has exactly the same problems as C++ in this regard.

Answer

Are floating-points deterministic?

I did a lot of reading on this issue a few years back when I wanted to write an RTS using the same lockstep architecture you do.

My conclusions about hardware floating-points were:

• The same native assembly code is most likely deterministic provided you're careful with floating point flags and compiler settings.


• There was one open source RTS project that claimed they got deterministic C/C++ compiles across different compilers using a wrapper library. I didn't verify that claim. (If I recall correctly it was about the STREFLOP library)



• The .net JIT is allowed quite a bit of leeway. In particular it is allowed to use higher accuracy than requires. Also it uses different instruction sets on x86 and AMD64 (I think on x86 it uses the x87, AMD64 it uses some SSE instructions whose behavior differs for denorms).


• Complex instructions (including trigonometric function, exponentials, logarithms) are especially problematic.

I concluded that it's impossible to use the built in floating point types in .net deterministically.

Possible Workarounds

Thus I needed workarounds. I considered:

1. Implement FixedPoint32 in C#. While this is not too hard(I have a half finished implementation) the very small range of values makes it annoying to use. You have to be careful at all times so you neither overflow, nor lose too much precision. In the end I found this not easier than using integers directly.


2. Implement FixedPoint64 in C#. I found this rather hard to do. For some operations intermediate integers of 128bit would be useful. But .net doesn't offer such a type.


3. Use native code for the math operations which is deterministic on one platform. Incurs the overhead of a delegate call on every math operation. Loses ability to run cross platform.



4. Use Decimal. But it's slow, takes a lot of memory and easily throws exceptions (division by 0, overflows). It's very nice for financial use, but no good fit for games.


5. Implement a custom 32 bit floating-point. Sounded rather difficult at first. The lack of a BitScanReverse intrinsic causes a few annoyances when implementing this.

My SoftFloat

Inspired by your post on StackOverflow, I've just started implementing a 32 bit floating-point type in software and the results are promising.

• The memory representation is binary compatible with IEEE floats, so I can reinterpret cast when outputting them to graphics code.


• It supports SubNorms, infinities and NaNs.


• The exact results are not identical to the IEEE results, but that usually doesn't matter for games. In this kind of code it only matters that the result is the same for all users, not that it's accurate to the last digit.


• Performance is decent. A trivial test showed that it can do about 75MFLOPS compared 220-260MFLOPS with float for addition/multiplication(Single thread on a 2.66GHz i3). If anybody has good floating point benchmarks for .net please send them to me, since my current test is very rudimentary.



• Rounding can be improved. Currently it truncates, which roughly corresponds to rounding towards zero.


• It's still very incomplete. Currently division, casts and complex math operations are missing.

If anybody want to contribute tests or improve the code, just contact me, or issue a pull request on github. https://github.com/CodesInChaos/SoftFloat

Other sources of indeterminism

There are also other sources of indeterminism in .net.

• iterating over a Dictionary or HashSet returns the elements in an undefined order.


• object.GetHashCode() differs from run to run.


• The implementation of the built in Random class is unspecified, use your own.



• Multithreading with naive locking leads to reordering and differing results. Be very careful to use threads correctly.


• When WeakReferences lose their target is indeterministic because the GC may run at any time.