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

BlueRaja - Danny Pflughoeft
  • How are deterministic games possible in the face of floating-point non-determinism? BlueRaja - Danny Pflughoeft

    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.

  • 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!

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

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

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

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

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

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

Tags
c++ c# networking replays floating-point
Related questions and answers
  • , but at this point I'm thinking HTTP and leveraging either SSL or WS-Security to ensure the encryption of data over the wire. I'd like to avoid middle-man attacks if possible so I'm leaning towards WS-Security even... that alone make the overhead worth it? If not, what should I do here? I want to make sure all of the requests from the client are authenticated but I also don't want to have to jump through hoops to make... leverage it. My client is going to be written in C++ and I can use whatever language makes it easiest (I'm leaning towards Java) to make it happen on the server side. I plan on adding support for users

  • component associated with it). No problem until this point. For this function I want to use a scientifically tested, accurate N-body simulation algorithm (like this). It's my field so I already know how to do that. The challenge is how to make the game activate the function efficiently. This is what I've thought of so far: The algorithm can calculate a lot of time steps in a short time, so I could... there is a totally different and better way to do this, please let me know. Additional info: the game is in C++, and the graphics engine is Ogre3D. EDIT: changed the part about the trajectories of the non

  • . state_->handleEvent(event, this); } That means that I don't really ever need more than one instance of a particular entity state; doing something like entity.setState(new StandState) is therefore highly wasteful. Then again, making each entity state a singleton hardly seems appropriate. What do you suggest I do? (The same can be said about game states, so whatever the solution...This is the first time I'm trying to make a 2D game, so I'm having quite a few difficulties in getting things right. Right now I'm trying to figure out exactly how the entity state machine should

  • , moving the player between levels in normal game play, and giving the player a preview of a non-trivial projectile they can shoot in the game, which seems to be most accurately done by simulating the world for a few seconds ahead. It looks like I can make a parallel world the "long way" - for each body in the world, copy the body data back into a def and re-create it, then copy the fixtures on it in the same way, then do the same for joints; re-set all the velocities; and if it's a "move" rather than a "copy" delete the original one. I was wondering if someone has already written this code

  • Lately I have been working on a game that i plan to make online. I have used different libraries to make this game as far as i could, but I feel that I should rethink on how Im sertting this game up... with the Physics correctly... So my main question is: What would be a good combination of libraries to make an online game with? Im sure that many people have good combinations of libraries for making a game. The libraries that I would need are ones that fit the criteria of making a simple 3d game(online): 3D Graphics(including a model loader of some sort(if it works with blender that would be even

  • hey so I've decided to Code my own 2D soft-body physics engine in C++ since apparently none exist and I'm starting only with a general idea/understanding on how physics work and could be simulated: by giving points and connections between points properties such as elasticity, density, mass, shape retention, friction, stickiness, etc. What I want is a starting point: resources and helpful... or ideas. finally I was wondering if it was possible to... use the source code of an existing 3D engine such as Bullet and transform it to be 2D based? use the source code of a 2D Rigid body physics

  • I'm creating a component-based game object system. Some tips: GameObject is simply a list of Components. There are GameSubsystems. For example, rendering, physics etc. Each GameSubsystem contains pointers to some of Components. GameSubsystem is a very powerful and flexible abstraction: it represents any slice (or aspect) of the game world. There is a need in a mechanism of registering... GameSubsystems) can implement registerComponent(Component*). pro. Components and GameSubystems know nothing about each other. con. In C++ it would look like ugly and slow typeid-switch

  • I'm looking into building a cross-platform opensource 2D RPG style game engine for ChaiScript. I want to be able to do all of the graphics with SVG and need joystick input. I also need the libraries I use to be opensource and compatible with the BSD license. I'm familiar with allegro, ClanLib, and SDL. As far as I can tell, none of these libraries have built in or obvious integration for SVG... support in a 2D C++ library while minimizing dependencies as much as possible (preferably avoiding Qt altogether)?

  • the objects at a fraction of the distance between their previous and current value positions and rotations. That is yet to be done. Question: Will I also have to do move my collision detection code... collide with a rock. Now I am considering improving it to use interpolation as per all the good articles recommend: http://www.koonsolo.com/news/dewitters-gameloop/ and http://gafferongames.com/game... on as large a Universe as possible. So a physics update solution that is compatible with the networked game that is required. Is the interpolation worth the effort? Right now. I rarely if ever see