How can I perform a deterministic physics simulation?

Question

I'm creating a physics game involving rigid bodies in which players move pieces and parts to solve a puzzle/map. 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?

Answer 1

---

On handling floating point numbers in a deterministic way

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.

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

The compiler 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 together and write them with SIMD, or some other optimization I cannot think of right now. And remember that if we want the same operations to happen in the same order, 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.

Arguably, 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) for the C++ MSVC compiler.

---

The case for fixed point numbers

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 undo the scaling.

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 whatever value you got after the cast. So, before the cast scale to get one bit more than you need, and truncate it afterwards.

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.

---

To be clear, if you can use a compiler that lets you specify how floating points works, and that is enough for you, then you can do that. That is not always an option. Besides, we are doing this for determinism. Fixed point numbers does not mean there are no errors, after all they have limited precision.

I do not think that "fixed point number are hard" is a good reason to not use them. And if you want a good reason to use them, it is determinism, in particular determinism across platforms.

---

See also:

• 3D Graphics on Mobile Devices - Part 2: Fixed Point Math
• The neglected art of Fixed Point arithmetic
• CORDIC Algorithm Simulation Code

---

Addendum: I am suggesting to keep the size of the world small. With that said, Both OP ans Jibb Smart bring up the point that moving away from the origin floats have less precision. That will have an effect on physics, one that will be seen far earlier than the edge of the world. Fixed point numbers, well, have fixed precision, they will be equally good (or bad, if you prefer) everywhere. Which is good if we want determinism. I also want to mention that the way we usually do physics has the property of amplifying small variations. See The Butterfly Effect - Deterministic Physics in The Incredible Machine and Contraption Maker.

---

Another way to do physics

I have been thinking, the reason why the small error in precision in floating point numbers amplify is because we are doing iterations on those numbers. Each simulation step we take the results of the last simulation step and do stuff on them. Accumulating errors on top of errors. That is your butterfly effect.

I do not think we will see a single build using a single thread on the same machine yield different output by the same input. Yet, on another machine it could, or a different build could.

There is an argument for testing there. If we decide exactly how things should work, and we can test on target hardware, we should not put out builds that has a different behavior.

---

However, there is also an argument for not working in away that accumulates so much errors. Perhaps this is an opportunity to do physics in a different way.

As you might know, there is continuous and discrete physics, both work on how much each object would advance on the timestep. However, continuous physics has the means to figure out the instant of collision instead of probing different possible instants to see if a collision happened.

Thus, I am proposing the following: use the techniques of continuous physics to figure out when the next collision of each object will happen, with a large timestep, much larger that the one of a single simulation step. Then you take the nearest collision instant and figure out where everything will be at that instant.

Yes, that is a lot of work of a single simulation step. That means that simulation will not start instantly...

... However, you can simulate the next few simulation steps without checking collision each time, because you already know when the next collision will happen (or that no collision happens in the large timestep). Furthermore, the errors accumulated in that simulation are irrelevant because once the simulation reaches the large timestep, we just place the positions we computed beforehand.

Now, we can use the time budget that we would have used to check for collisions each simulation step to compute the next collision after the one we found. That is we can simulate ahead by using the large timestep. Assuming a world limited in scope (this will not work for huge games), there should be a queue of future states for the simulation, and then each frame you just interpolate from the last state to the next one.

---

I would argue for interpolation. However, given that there are accelerations, we cannot simply interpolate everything the same way. Instead we need to interpolate taking into account the acceleration of each object. For that matter we could just update position the same way we do for the large timestep (which also means it is less error prone because we would not be using two different implementations for the same movement).

---

Note: If we are doing this floating point numbers, this approach does not solve the problem of objects behaving differently the further away from the origin they are. However, while it is true that precision is lost the further away you go from the origin, that is still deterministic. In fact, that is why did not even bring that up originally.

---

Addendum

From OP in comment:

The idea is that players will be able to save their machines in some format (such as xml or json), so that each piece's position and rotation is recorded. That xml or json file will then be used to reproduce the machine on another player's computer.

So, no binary format, right? That means we also need to worry whatever or not the floating point numbers recovered match the original. See: Float Precision Revisited: Nine Digit Float Portability

Answer 2

I work for a company which makes a certain well known real-time strategy game, and I can tell you that floating point determinism is possible.

Using different compilers, or the same compiler with different settings, or even different versions of the same compiler, can all break determinism.

If you need crossplay between platforms or game versions then I think you'll need to go fixed point - the only possible crossplay which I'm aware of with floating point, is between PC and XBox1, but that's pretty crazy.

You'll need to either find a physics engine which is fully deterministic, or take an open source engine and make it deterministic, or roll your own engine. Off the top of my head, I have a feeling that Unity of all things added a deterministic physics engine, but I'm not sure if it's just deterministic on the same machine or deterministic across all machines.

If you are going to try to roll your own stuff, a few things that can help:

• IEE754 floats are deterministic if you're not doing anything too fruity (google "IEE754 determinism" for more info on what is or isn't covered)
• You need to make sure every client has their rounding mode and precision set identically (use controlfp to set it)
• rounding mode and precision can be changed by certain maths libraries, so if you're using any closed libs they you might want to check these after making calls (again using controlfp to check)
• some SIMD instructions are deterministic, a lot aren't, be careful
• as mentioned above, to ensure determinism you also need the same platform, the same exact version of the same compiler, compiling the same configuration, with the same compiler settings
• build some tooling in to detect state desyncs, and help diagnose them - e.g. CRC the game state every frame to detect when a desync occurs, then have a verbose logging mode you can enable where modifications to the game state are laboriously logged to a file, then take 2 files from simulations which desynced from eachother, and compare in a diff tool to see where it's gone wrong
• initialise all your variables in the game state, major source of desyncs
• the entire game simulation needs to happen in exactly the same order every time to avoid desyncs, it's incredibly easy to get this wrong, it's advisable to structure your game simulation in such a way that minimises this. I'm really not a software design pattern guy, but for this case it is probably a good idea - you might consider some kind of pattern where the game simulation is like a secure box, and the only way to mutate game state is to insert "messages" or "commands", with only const access provided to anything outside of the game state (e.g. rendering, networking, etc). So networking the simulation for a multiplayer game is a case of sending these commands over the network, or replaying the same simulation is a case of recording the stream of commands the first time around, and then replaying them each time the replay is viewed.

Answer 3

I'm not sure if this is the type of answer you're looking for, but an alternative might be to run the calculations on a central server. Have the clients send the configuration to your server, let it perform the simulation (or retrieve a cached one) and send back the results, which are then interpreted by the client and processed into graphics.

Of course, this shuts off any plans you might have to run the client in offline mode, and depending on how computationally intensive the simulations are you might need a very powerful server. Or multiple ones, but then at least you have the option to make sure they have the same hard- and software configuration. A real-time simulation might be hard but not impossible (think of live video streams - they work, but with a slight delay).

Answer 4

I'm going to give a counter-intuitive suggestion that, while not 100% reliable, should work fine most of the time and is very easy to implement.

Reduce precision.

Use a pre-determined constant time-step size, perform the physics over each time-step in standard double-precision float, but then quantise down the resolution of all variables to single-precision (or something even worse) after each step. Then most of the possible deviations that floating-point reordering could possibly introduce (compared to a reference run of the same program) will be clipped away because those deviations happen in digits that don't even exist in the reduced precision. Thus the deviation don't get the chance of a Lyapunov buildup (Butterfly Effect) that would eventually become notable.

Of course, the simulation will be slightly less accurate than it could be (compared to real physics), but that's not really notable as long as all of your program runs are inaccurate in the same way.

Now, technically speaking it is of course possible that a reordering will cause a deviation that reaches into a higher-significance digit, but if the deviations are really only float-caused and your values represent continuous physical quantities, this is exceedingly unlikely. Note that there are half a billion double values between any two single ones, so the vast majority of time-steps in most simulations can be expected to be exactly the same between simulation runs. The few cases where a deviation does make it through quantisation will hopefully be in simulations that don't run so long (at least not with chaotic dynamics).

---

I would also recommend you consider the complete opposite approach to what you're asking about: embrace the uncertainty! If the behaviour is slightly nondeterministic, then this is actually closer to actual physics experiments. So, why not deliberately randomise the starting parameters for each simulation run, and make it a requirement that the simulation succeeds consistently over multiple trials? That'll teach a lot more about physics, and about how to engineer the machines to be robust/linear enough, rather than super-fragile ones that are only realistic in a simulation.

Answer 5

Create your own class for storing numbers!

You can force a deterministic behavior if you know precisely how the computations will be performed. For example, if the only operations you deal with are multiplication, division, addition and subtraction, then it would be sufficient to represent all numbers as just a rational number. To do this, a simple Rational class would do just fine.

But if you want to deal with more complicated computations (possibly trigonometric functions for example), then you will have to write such functions yourself. If you wanted to be able to take the sine of a number, you would have to be able to write a function that approximates the sine of a number while only using the operations mentioned above. This is all doable, and in my opinion circumvents much of the hairy details in other answers. The tradeoff is that you instead will have to deal with some math.

Answer 6

There is some confusion of terminology here. A physical system can be completely deterministic, but impossible to model for a useful time period because its behaviour is extremely sensitive to the initial conditions, and an infinitesimally small change in the initial conditions will produce completely different behaviours.

Here's a video of a real device whose behaviour is intentionally unpredictable, except in a statistical sense:

https://www.youtube.com/watch?v=EvHiee7gs9Y

It is easy to construct simple mathematical systems (using only addition and multiplication) where the result after N steps depends on the N'th decimal place of the starting conditions. Writing software to model such a system consistently, on any computer hardware and software the user might have, is close to impossible - even if you have a budget big enough the test the application on every likely combination of hardware and software.

The best way to fix this is to attack the problem at its source: make the physics of your game as deterministic as it needs to be to get reproducible results.

The alternative is to try to make it deterministic by tweaking the computer software to model something which is not what the physics specified. The problem is that you have introduced several more layers of complexity into the system, compared with explicitly changing the physics.

As a specific example, suppose your game involves collisions of the rigid bodies. Even if you ignore friction, the exact modelling of collisions between arbitrary-shaped objects which may be spinning as they move is in practice impossible. But if you change the situation so that the only objects are non-rotating rectangular bricks, life gets very much simpler. If the objects in your game don't look like bricks, then hide that fact with some "non-physical" graphics - for example literally hide the instant of collision behind some smoke or flames, or a cartoon-text-bubble "Ouch" or whatever.

The player has to discover the game physics by playing the game. It doesn't matter if it is not "totally realistic" so long as it is self consistent, and similar enough to common-sense experience to be plausible.

If you make the physics itself behave in a stable manner, a computer model of it can also produce stable results, at least in the sense that rounding errors will be irrelevant.