Why are computer/game physics engines often non-deterministic?

Question

Developing with various game physics engines over the years, I've noticed that on the same machine I observe widely different results in physics simulations between runs. Most recently, the Unity engine does this, even though physics are calculated at set intervals of time (FixedUpdate) -- as far as I can determine it should be completely independent of frame-rate.

I've asked this question on game forums before, and was told it was due to chaotic motion: see double pendulum. But, even the double pendulum is deterministic if the starting conditions are exactly controlled, right? On the same machine, shouldn't floating point math behave the same way?

I understand that there are problems with floating point math accuracy, but I understand those problems (as outlined here) to not be problems on the same hardware -- isn't floating point inaccuracy still deterministic? What am I missing?

tl;dr: If running a simulation on the same machine, using the same floating point math(?), shouldn't the simulation be deterministic?

Thank you very much for your time.

Muriah

@RyanVincent Floating point numbers are an approximation yes, but they are still deterministic, so the system being chaotic should have no effect. – Snafu

It's worth noting that FixedUpdate() does not run at a consistent frequency (Time.fixedTime). Changing the interval only changes how many times FixedUpdate() gets called prior to Update() (to "catch up"), though the specific number varies based on the elapsed time since the last frame. Here's a little more info on what's actually going on. – Degust

@Degust Found the same source :) Edited my answer accordingly. – Snafu

@RyanVincent From the article: "... so do we have a deterministic result now across all compilers and machines? No." (emphasis mine) Note that on the same computer, the result will be the same. – Snafu

Answer 1

Yes, you are correct. A program executed on the same machine will give identical results each time (at least ideally---there might be cosmic rays or other external things that affect memory and what not, but I would say these are not of our concern). All calculations on a computer are deterministic, and so all algorithms of a computer will necessarily be deterministic (which is the reason it's so hard to make random number generators)!

Most likely the randomness you see is implemented in the program with some random number generator, and the seed for the random numbers varies from run to run. Should you start the simulation with the same seed, you will see the same result.

Edit: I'm not familiar with Unity, but doing some more research seems to indicate that the FixedUpdate routine might be the problem.

Except for the audio thread, everything in unity is done in the main thread if you don't explicitly start a thread of your own. FixedUpdate runs on the very same thread, at the same interval as Update, except it makes up for lost time and simulates a fixed time step.

source

If this is the case, and the function itself looks somewhat like:

void physicsUpdate(double currentTime, double lastTime)
{
    double deltaT = currentTime - lastTime;
    // do physics using `deltaT`
}

Here we will naturally get different behaviour due to deltaT not being same from two different runs. This is determined from what other processes are running in the background, as they could delay the main thread. This function would be called irregularly and you would observe different results from runs. Note that these irregularities will mostly not be due to floating point inprecision, but due to inaccuracies when doing integration. (E.g. velocity is often calculated by v = a*deltaT, which assumes a constant acceleration since last update. This is in general not true).

However, if the function would look like this:

void physicsUpdate(double deltaT)
{
    // do physics using `deltaT`
}

Every time you do simulations using this you will always get the exact same result.

Snafu

I think your Edit is the true answer. Two runs do not nessearally have the same value for Time.deltaTime for every physics update call. Doing math with that value will result in small difrences that will build up over time. – Sandblind

This seems like the best answer to me. I'll keep digging into why every game physics engine I've used is non-deterministic, but just wanted to say thanks for taking the time to provide such a great answer! Perhaps they all suffer from this -- maybe fixed updates are somewhat difficult to achieve? – Muriah

Yeah, I was unable to locate any deliberately random aspect to Unity physics, so it seems more likely to me that variations in deltaT is the problem. – Muriah

@ScottChamberlain Yes, I agree. I wasn't sure originally what 'non-deterministic' things we were talking about. One should note as well that the main discrepancy in this last case is not because of floating point inprecision, but because of error due to linear integration. – Snafu

My impression is that Unity's FixedUpdate routine is called in a routine something like the one sketched out in this post (in which case the variable deltatime shouldn't be a source of indeterminism): kinematicsoup.com/news/2016/8/9/rrypp5tkubynjwxhxjzd42s3o034o8 – Horde

This answer and the edit are incorrect. The engine obviously can't call FixedUpdate/PhysicsUpdate at a perfectly consistent timestep, but each time it does it simply uses the same fixed deltaTime value. If one call happens too slowly then there will be less time before the next call to compensate, but all the internal calculations will get the exact same value. The non-determinism comes from inconsistent floating-point math implementations across different hardware. – Allergist

@Allergist Your argument is incorrect. "The non-determinism comes from inconsistent floating-point math implementations across different hardware." is not true: As OP stated he ran the same simulation on the same hardware. Floating point arithmetic has rounding errors, but it is deterministic on each hardware (everything else is an extremely significant bug). Assuming his physics algorithm is deterministic, which he/she claims (e.g. there are no internal threading errors or similar problems), the difference will stem from the step size deltaT. – Snafu

Try it yourself: create a program doing some weird floating point arithmetic. Run it a million times -- it will give you the exact same result every time. – Snafu

@Snafu I have tried it myself with physics in Unity. It was perfectly consistent on each device individually with the same build but had slight inconsistencies between devices and also sometimes got different results between builds. You can try it yourself as well: call Debug.Log(Time.deltaTime) inside FixedUpdate and you'll see the exact same value in every log message. – Allergist

@Snafu Now that I think about it more, a more likely candidate for the cause of the issue is that I believe Unity uses multiple threads as part of scene loading which can cause objects to be initialised in differing orders and thus give different physics results. Maybe Unity didn't do that back when I made my simulation (back in Unity 4) or maybe it just didn't happen to occur while I was specifically watching for it, but I guarantee that the physics engine is getting the exact same fixed delta time value every frame, otherwise you would practically never get the same results twice. – Allergist

Answer 2

I've not got much experience with Unity or its physics simulations, but I've found the following forum post which also links to an article which seems to indicate it's down to precision with the floating point calculations.

As you've mentioned, a lot of people seem to keep rehashing this question!

The forum also links to this blog post which may shed some light on the issue.

Crowley

Floating point math is deterministic. You should always get the same outputs given the same inputs. – Emeryemesis

Thanks for the answer, but those articles don't mention IEEE floating point math being different on the same hardware... only varying hardware. Floating point math should be deterministic on the same hardware... right? – Muriah

@AaronMeier the blog post I edited the question to link to seems to indicate that there can be runtime factors that affect it, so it may very well be possible! – Crowley

@Crowley - that could be, but the randomascii post doesn't mention identical hardware, but it does reference this post that specifically mentions floating point non-determinism across different hardware. – Muriah