Mdthbs

I'm creating a physics game involving rigid bodies in which players move pieces and parts to solve a puzzle. A hugely important aspect of the game is that when players start a simulation, it runs the same everywhere, regardless of their operating system, processor, etc...

There is room for a lot of complexity and simulations may run for a long time, so it's important that the physics engine is completely deterministic with regards to its floating point operations, otherwise a solution may appear to "solve" on one player's machine and "fail" on another.

How can I acieve this determinism in my game? I am willing to use a variety of frameworks and languages, including Javascript, C++, Java, Python, and C#.

I have been tempted by Box2D (C++) as well as its equivalents in other languages, as it seems to meet my needs, but it lacks floating point determinism, particularly with trigonometric functions.

The best option I've seen thus far has been Box2D's Java equivalent (JBox2D). It appears to make an attempt at floating point determinism by using StrictMath rather than Math for many operations, but it's unclear whether this engine will guarantee everything I need as I haven't built the game yet.

Is it possible to use or modify an existing engine to suit my needs? Or will I need to build an engine on my own?

EDIT: I'll further explain how the game is supposed to work. The player is given a puzzle or level, which contains obstacles and a goal. Initially, a simulation is not running. They can then use pieces or tools provided to them to build a machine. Once they press start, the simulation begins and they can no longer edit their machine. If the machine solves the puzzle, the player has beaten the level. Otherwise, they will have to press stop, alter their machine, and try again.

I will end up saying to use fixed point number. However, this is a ride I am taking you on.

Floating point is deterministic. Well, it should be. It is complicated.

There is plenty of literature on floating point numbers:

• What Every Computer Scientist Should Know About Floating-Point Arithmetic


• THE NEW IEEE-754 STANDARD FOR FLOATING POINT ARITHMETIC


• IEEE 754-2008 revision

And how they are problematic:

• 
  Consistency of Floating Point Results or Why doesn’t my application always give the same answer?.


• 
  Cross-Platform Issues With Floating-Point Arithmetics in C++.


• 
  The pitfalls of verifying floating-point computations.


• 
  Is floating point math deterministic?.


• 
  What could cause a deterministic process to generate floating point errors.


• 
  Consistency: how to defeat the purpose of IEEE floating point.

For abstract. At least, on a single thread, the same operations, with the same data, happening in the same order, should be deterministic. Thus, we can start by worrying about inputs, and reordering.

One such input that causes problems is time.

Firat of all, you should always compute the same timestep. I am not saying to not measure time, I am saying that you will not pass time to the physics simulation, because variations in time are a source of noise in the simulation.

Why do you measure time if you are not passing it to the physics simulation? You want to measure the elapsed time to know when a simulation step should be called, and - assuming you are using sleep - how much time to sleep.

Thus:

• Measure time: Yes


• Use time in simulation: No

Now, instruction reordering. There are two sources of reordering: 1) the CPU...

It is possible to ensure that instructions happen in the same order in each CPU core, up until the point where they need to interact. The problem is as follows: if a CPU core needs to do an instruction that requires a value that has to be retrieved from the cache of another core, it is likely that it will pospone that instruction to one that uses values that are in its own cache, while it waits for the value from the other core.

Physics has plenty of opportunities for parallelism. However, if you want to avoid these problems - and keep the code easy to follow anyway - have your physics be single threaded.

Addendum: This reminds me, you want to miminize trips to RAM. They have a similar effect on the instruction order and a bigger effect on performance.

Thus:

• Single threaded: Yes


• Optimize for CPU cache: Yes

... and 2) the compiler.

It could decide that f * a + b is the same as b + f * a, however that may have a different result. It could also compile to fmadd, or it could decide take multiple lines like that that happen togheter and write them with SIMD, or some other optimization I cannot think of right now. And remember we want the same operations to happen on the same order, it comes to reason that we want to control what operations happen.

And no, using double will not save you.

You need to worry about the compiler and its configuration, in particular to synchronize floating point numbers across the network. You need to get the builds to agree to do the same thing.

Arguebly, writing assembly would be ideal. That way you decide what operation to do. However, that could be a problem for supporting multiple platforms.

Thus:

• Ern... Hmm... Use a compiler that let you configure how they deal with floating point numbers. For example see /fp (Specify floating-point behavior)
  .

That brings me to different idea: keep your values small and truncate the results.

Due to the way floats are represented in memory, large values are going to lose precision. It comes to reason that keeping your values small (clamp) mitigates the problem. Thus, no huge speeds and no large rooms. Which also means you can use discrete physics because you have less risk of tunneling.

On the other hand, small errors will accumulate. So, truncate. I mean, scale and cast to an integer type. That way you know nothing is building up. There will be operations you can do staying with the integer type. When you need to go back to floating point you cast and unscale.

Note I say scale. The idea is that 1 unit will actually be represented as a power of two (16384 for example). Whatever it is, make it a constant and use it. You are basically using it as fixed point number. In fact, if you can use proper fixed point numbers from some reliable library much better.

I am saying truncate. About the rounding problem, it means you cannot trust the last bit of whaever value you got after the cast. So, before the cast scale to get one bit more than you need, and truncate it afterwads.

Thus:

• Keep values small: Yes


• Careful rounding: Yes


• Fixed point numbers when possible: Yes

Wait, why do you need floating point? Could you not work only with an integer type? Oh, right. Trigonometry and radication. You can compute tables for trigonometry and radication and have them baked in your source. Or you can implement the algorithms used to compute them with floating point number, except using fixed point numbers instead. Yes, you need to balance memory, performance and precision. Yet, you could stay out of floating point numbers, and stay deterministic.

Did you know they did stuff like that for the original PlayStation? Please Meet My Dog, Patches.

By the way, I am not saying to not use floating point for graphics. Just for the physics. I mean, sure, the positions will depend on the physics. However, as you know a collider does not have to match a model. We do not want to see the results of truncation of the models.

Thus: USE FIXED POINT NUMBERS.

See also:

• 3D Graphics on Mobile Devices - Part 2: Fixed Point Math


• The neglected art of Fixed Point arithmetic


• CORDIC Algorithm Simulation Code

Use double floating point precision, instead of single floating point precision. Although not perfect, it is accurate enough to be deemed deterministic in your physics.

If you truly need perfect determinism, use fixed point math. This will give you less precision, but deterministic results. I am not aware of any physics engines that use fixed point math, so you may need to write your own if you wanted to go this route. (Something I would advise against.)

Use the Memento Pattern.

In your initial run, save off the positional data each frame, or whatever benchmarks you need. If that is too unperformance, only do it every n frames.

Then when you reproduce the simulation, follow the arbitrary physics, but update the positional data every n frames.

Overly simplified pseudo-code:

function Update():

    if(firstRun) then (SaveData(frame, position));

    else if(reproducedRun) then (this.position = GetData(frame));