Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
4  
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. –  jhocking Jul 13 '11 at 12:45
    
@jhocking Yet it is probably the best answer. –  Jonathan Connell Jul 13 '11 at 12:51

8 Answers 8

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.

share|improve this answer
1  
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! –  BlueRaja - Danny Pflughoeft Jul 13 '11 at 3:58
2  
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. –  Stephen Jul 13 '11 at 12:40
3  
@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. –  AttackingHobo Jul 13 '11 at 15:56
3  
@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 –  AttackingHobo Jul 13 '11 at 18:04
2  
@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. –  Keeblebrox Jul 15 '11 at 14:40

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.
share|improve this answer

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.

share|improve this answer
    
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... –  BlueRaja - Danny Pflughoeft Jul 13 '11 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. –  Nevermind Jul 14 '11 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. –  BlueRaja - Danny Pflughoeft Jul 14 '11 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. –  Nevermind Jul 14 '11 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.

share|improve this answer
    
decimal would work fine for that too; but, this still has the same problems as using int - how do I do trig with it? –  BlueRaja - Danny Pflughoeft Jul 13 '11 at 4:05
1  
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. –  LukeN Jul 13 '11 at 4:12
    
Alternatively, you may be able to replace trig calls with imaginary numbers or quaternions(if 3D). This is an excellent explanation –  LukeN Jul 13 '11 at 4:14
    
This may also help. –  LukeN Jul 13 '11 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. –  LukeN Jul 13 '11 at 4: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.

share|improve this answer

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.

share|improve this answer
    
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. –  LukeN Jul 13 '11 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. –  Nicol Bolas Jul 13 '11 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? –  BlueRaja - Danny Pflughoeft Jul 13 '11 at 4:03
1  
> 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 –  Romanenkov Andrey Jul 13 '11 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. –  Nicol Bolas Jul 15 '11 at 9:22

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.

share|improve this answer

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!

share|improve this answer
    
This is what the OP wants to know how to do, with floating point. –  The Communist Duck Jul 13 '11 at 9:11

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.