# 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.

• This isn't an answer to your question, but to address the RTS networking problem I would recommend occasionally syncing up unit positions and health in order to correct for any drift. Exactly what information needs to be synced will depend on the game; you can optimize bandwidth usage by not bothering to sync up stuff like status effects. Commented Jul 13, 2011 at 12:45
• @jhocking Yet it is probably the best answer. Commented Jul 13, 2011 at 12:51
• starcraft II infacti exactly sync only everywhile, I looked at gameplay replay with my friends each computer side by side and there where differences (also significative) especially with high lag (1 sec). I had some units that where 6/7 map squares far aways on my screen respect to his own Commented Jan 10, 2015 at 23:13

## 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<TKey,TValue> or HashSet<T> 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.

The answer to this question is from the link you posted. Specifically you should read the quote from Gas Powered Games:

I work at Gas Powered Games and i can tell you first hand that floating point math is deterministic. You just need the same instruction set and compiler and of course the user’s processor adheres to the IEEE754 standard, which includes all of our PC and 360 customers. The engine that runs DemiGod, Supreme Commander 1 and 2 rely upon the IEEE754 standard. Not to mention probably all other RTS peer to peer games in the market.

And then below that one is this:

If you store replays as controller inputs, they cannot be played back on machines with different CPU architectures, compilers, or optimization settings. In MotoGP, this meant we could not share saved replays between Xbox and PC.

A deterministic game will only be deterministic when using the identically compiled files and run on systems that adhere to the IEEE standards. Cross platform synchronized network simulations or replays will not possible.

• As I mentioned, I'm interested primarily in C#; since the JIT does the actual compiling, I cannot guarantee that it is "compiled with the same optimization settings" even when running the same executable on the same machine! Commented Jul 13, 2011 at 3:58
• Sometimes the rounding mode is set differently in the fpu, on some architectures the fpu has a larger-than-precision internal register for calculations ... while IEEE754 doesn't give leeway with regards to the way FP operations should work, it doesn't specifiy how any particular mathematical function should be implemented, which may expose the architectural differences. Commented Jul 13, 2011 at 12:40
• @3nixios With that kind of setup, the game is not deterministic. Only games with a fixed timestep can deterministic. You are arguing something already is not deterministic when running back a simulation on a single machine. Commented Jul 13, 2011 at 15:56
• @3nixios, "I was stating that even with a fixed timestep, nothing ensures that the timestep will always stay fixed." You are entirely wrong. The point of a fixed timestep is to always have the same delta time for each tick in updating Commented Jul 13, 2011 at 18:04
• @3nixios Using a fixed timestep ensures the timestep will be fixed because we developers don't allow otherwise. You're misinterpreting how lag should be compensated for when using a fixed time step. Each game update must use the same update time; therefore, when a peer's connection lags it must still calculate each individual update that it missed. Commented Jul 15, 2011 at 14:40

I've worked on a number of large titles.

Short answer: It's possible if you're insanely rigorous, but probably not worth it. Unless you're on a fixed architecture (read: console) it's finicky, brittle and comes with a host of secondary problems such as late join.

If you read some of the articles mentioned, you'll note that while you can set the CPU mode there are bizarre cases such as when a print driver switches the CPU mode because it was in the same address space. I had a case where an application was frame-locked to an external device, but a faulty component was causing the CPU to throttle due to heat and report differently in the morning and afternoon, making it in effect a different machine after lunch.

These platform differences are in the silicon, not the software, so to answer your question C# is affected too. Instructions such as fused multiply-add (FMA) vs ADD+MUL change the result because it rounds internally only once instead of twice. C gives you more control to force the CPU to do what you want basically by excluding operations like FMA to make things "standard"--but at the cost of speed. The intrinsics seem to be the most prone to differ. On one project I had to dig out a 150 year old book of acos tables to get values for comparison to determine which CPU was "right". Many CPUs use polynomial approximations for trig functions but not always with the same coefficients.

My recommendation:

Regardless of whether you go integer lock-step or sync, handle the core game mechanics separately from presentation. Make the game play accurate, but don't worry about accuracy in the presentation layer. Also remember you don't need to send all the networked world data at the same frame-rate. You can prioritize your messages. If your simulation is 99.999% matched you won't need to transmit as often to to stay paired. (Cheat prevention aside.)

There's a nice article about Source engine that explains one way to go about sync: Source Multiplayer Networking.

Remember, if you're interested in late join, you're going to have to bite the bullet and sync anyway.

Use fixed point arithmetics. Or choose an authoritative server and have it sync game state once in a while - that's what MMORTS do. (At least, Elements of War works like this. It's written in C# too.) This way, errors do not have a chance to accumulate.

• Yes, I could make it a client-server and deal with the headaches of client-side prediction and extrapolation. This question is about peer-to-peer architectures, which are supposed to be easier... Commented Jul 13, 2011 at 16:20
• Well, you don't need to do prediction in an "all clients run the same code" scenario. The role of server is to be the authority on synchronization only. Commented Jul 14, 2011 at 4:40
• Server/client is only one method of making a networked game. Another popular method (especially for eg. RTS games, like C&C or Starcraft) is peer-to-peer, in which there is no authoritative server. In order for that to be possible, all calculations must be completely deterministic and consistent across all clients - hence my question. Commented Jul 14, 2011 at 6:11
• Well it's not like you absolutely HAVE to make the game strictly p2p with no servers/elevated clients. If you absolutely have to, though - then use fixed-point. Commented Jul 14, 2011 at 12:36

Edit: A link to a fixed point class (Buyer beware! - I haven't used it...)

You could always fall back on fixed point arithmetic. Someone (making an rts, no less) has already done the leg work on stackoverflow.

You will pay a performance penalty, but this may or may not be a problem, as .net will not be especially performant here as it won't use simd instructions. Benchmark!

N.B. Apparently someone at intel appears to have a solution to allow you to use the intel performance primitives library from c#. This may help vectorising fixed point code to compensate for the slower performance.

• decimal would work fine for that too; but, this still has the same problems as using int - how do I do trig with it? Commented Jul 13, 2011 at 4:05
• The easiest way would be to build a lookup table and send it alongside the application. You can interpolate between value if precision is a problem. Commented Jul 13, 2011 at 4:12
• Alternatively, you may be able to replace trig calls with imaginary numbers or quaternions(if 3D). This is an excellent explanation Commented Jul 13, 2011 at 4:14
• This may also help. Commented Jul 13, 2011 at 4:18
• At the company I used to work for, we built an ultrasound machine using fixed point maths, so it will definitely work for you. Commented Jul 13, 2011 at 4:22

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.

Yes, C# has the same problems as C++. But it also has a lot more.

For example, take this statement from Shawn Hawgraves:

If you store replays as controller inputs, they cannot be played back on machines with different CPU architectures, compilers, or optimization settings.

It's "easy enough" to ensure that this happens in C++. In C#, however, that's going to be a lot harder to deal with. This is thanks to JIT.

What do you suppose would happen if the interpreter ran your code interpreted once, but then JIT'd it the second time? Or maybe it interprets it twice on someone else's machine, but JIT's it after that?

JIT is not deterministic, because you have very little control over it. This is one of the things you give up to use the CLR.

And God help you if one person is using .NET 4.0 to run your game, while someone else is using the Mono CLR (using the .NET libraries of course). Even .NET 4.0 vs. .NET 5.0 could be different. You simply need more control over the low-level details of a platform to guarantee this kind of thing.

You ought to be able to get away with fixed-point math. But that's about it.

• Aside from the maths, what else is liable to be different? Presumably, "input" actions are being sent as logical actions in an rts. E.g. Move unit "a" to position "b". I can see a problem with random number generation, but that obviously needs to be sent as an simulation input as well. Commented Jul 13, 2011 at 3:07
• @LukeN: The problem is that Shawn's position strongly suggests that compiler differences can have real effects on floating-point math. He would know more than I do; I'm simply extrapolating his warning out into the realm of JIT and C# compilation/interpretation. Commented Jul 13, 2011 at 3:50
• C# has operator overloading, and also has a built-in type for fixed-point math. However, this has the same problems as using an int - how do I do trig with it? Commented Jul 13, 2011 at 4:03
• > What do you suppose would happen if the interpreter ran your code > interpreted once, but then JIT'd it the second time? Or maybe it > interprets it twice on someone else's machine, but JIT's it after > that? 1. CLR code is always jitted before execution. 2. .net uses IEEE 754 for floats of course. > JIT is not deterministic, because you have very little control over it. You conclusion is quite weak cause of false false statements. > And God help you if one person is using .NET 4.0 to run your game, > while someone else is using the Mono CLR (using the .NET libraries of > course). Even .NET Commented Jul 13, 2011 at 12:18
• @Romanenkov: "You conclusion is quite weak cause of false false statements." Please, tell me what statements are false and why, so that they can be corrected. Commented Jul 15, 2011 at 9:22

I realized after writing this answer that it doesn't actually answer the question, which was specifically about floating-point nondeterminism. But maybe this is helpful to him anyway if he's going to make a networked game in this manner.

Along with the input sharing that you're broadcasting to all players, it can be very useful to create and broadcast a checksum of important game state, such as player positions, health, etc. When processing input, assert that the game state checksums for all remote players are in sync. You are guaranteed to have out of sync (OOS) bugs to fix and this will make it easier - you will have an earlier notice that something's gone wrong (which will help you figure out reproduction steps), and you should be able to add more game state logging in suspect code to allow you to bracket whatever is causing the OOS.

I think the idea from the blog linked to still needs periodic synchronisation to be viable - I've seen enough bugs in networked RTS games which don't take that approach.

Networks are lossy, slow, have latency and might even pollute your data. "Floating point determinism", (which sounds buzzwordy enough to make me skeptical) is the least of your worries in reality... esp if you use a fixed time step. with variable time steps you will need to interpolate between fixed time steps to avoid determinism problems too. I think this is usually what is meant by non-deterministic "floating point" behaviour - just that variable time steps cause integrations to diverge - not anything to do with math libraries or low level functions.

Synchronisation is key though.

You make them deterministic. For a great example, see Dungeon Siege GDC Presentation as to how they made the locations in the world networkable.

Also remember that determinism applies to 'random' events as well!

• This is what the OP wants to know how to do, with floating point. Commented Jul 13, 2011 at 9:11