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:
And how they are problematic:
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:
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:
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