← All articles

Simulators and determinism

When working with simulators, it is important to understand determinism and why we have trouble with determinism across different platforms and configurations. Simulators that are iterative converge their solution over multiple iterations and can accumulate system-inherited errors and thus can become unstable over time.

Why is determinism important#

Does determinism in simulation systems even matter? The short answer is yes, very important. The long answer is that simulation systems usually base their current world on the previous world. It takes one step at a time (time step) and calculates everything based on the previous step. If you shoot a projectile towards a target, the trajectory of the projectile will travel in a certain curve. If you run the same simulation on a different platform, the projectile might end up somewhere totally different than the first simulation.

Take the following example with a projectile trajectory. They both have the same initial conditions.

Simulation on platform 1:

Simulation on platform 2:

You would expect the results to be the same on both platforms, but they are not.

What can affect determinism#

There are several things that can affect the determinism of a simulation, the order of elements, the rounding of floats, the low level instructions and much more. Here is a list of some examples on what can impact determinism:

  • Sorting

    • Stable vs. unstable sorting
  • float operations

    • Rounding methods
    • Optimizations
  • Hardware instructions

    • Some hardware has higher accuracy than others.

The list is by no means complete, there are hundreds of factors that can affect determinism; the list only contains those we focus on in this post.

Sorting#

In Farseer Physics Engine we sort the contacts (where two shapes touch) by the amount two shapes overlap. This way we can resolve the deepest contacts first and get a more realistic simulation. We used to use Array.Sort() that is based on quick sort, but quick sort is not a stable sorting algorithm. Stable in this case just means that the order of elements is preserved if the keys that are equal are in the same order before and after sorting. If two contacts had the same amount of penetration, they might get shuffled around and the order of IDs will be out of order. We switched to an insertion sort algorithm instead and suddenly the whole simulation acted differently. Not a big problem since it would do that across all platforms, but simulations recorded from previous versions of the physics simulator did not match newer versions anymore.

Floating point operations#

Floats can be tricky to work with. I took the following example from this article on floating points in .net:

C#
static float f;

static void Main(string[] args)
{
    f = Sum(0.1f, 0.2f);
    float g = Sum(0.1f, 0.2f);
    Console.WriteLine(f == g);
}

static float Sum(float f1, float f2)
{
    return f1 + f2;
}

You would guess that the program always returns true - but that is not the case. If compiled under release mode (to enable optimizations) with some older x86 JITs, it can return false. Even though you can represent two values exactly, the result of an operation on the values might not be exact. There is a standard for floating point operations, but it allows different platforms to return different values. This means that even if two systems follow the same standard, they might return different values. Reproducible floating-point results require consistent inputs, evaluation order, precision and rounding behavior.

Let us look at what happens under the hood.

On x87, intermediate results can use 80-bit registers. Storing a result as a float rounds it to 32 bits; storing it as a double rounds it to 64 bits. Some compilers optimize your code in such a way that the value in the register gets compared to the value in memory. Since the memory value has been rounded, it may differ from the value still in the register. This can cause the comparison behavior in the C# example above. To combat this we can do some tricks to disable float optimizations. For approximate equality, compare the difference against a suitable tolerance. Deterministic simulation also requires consistent arithmetic and branching decisions. More on comparison tolerances further down.

Hardware instructions#

Let us take the fused multiply-accumulate instruction as an example. This instruction can be found in IBM PowerPC or Intel Itanium processors that can compute ax±b with a single rounding instead of multiple. This increases accuracy (and performance because of the fewer rounding instructions) and thus a simulation will run with higher accuracy on the PowerPC or Intel Itanium platform compared to the PC platform.

This is just one out of many instructions. Some platforms have lower accuracy some have higher. If you develop a simulation that runs on PC, make sure to test it on other platforms if you officially support them.

What can we do about it#

Now that we know some of the factors that influence the determinism of a simulation we can implement some techniques to increase the determinism.

Use stable sorting with a consistent input order, or break equal-key ties using a consistent unique ID. Anything float related is a little more complicated. There are 3 methods of getting more accuracy:

  • Use doubles
  • Use decimal
  • Epsilon
  • Don’t use floats

double and decimal#

Using doubles simply just shifts the problem. It might not be as visible as before, but it is still there. Floats have a precision of 7 digits while double has 15-16 digits. decimal on the other hand can represent many decimal fractions exactly, but still has finite precision and rounding errors. (They have a precision of 28-29 digits by the way). Take a look at the following example:

C#
static void Main(string[] args)
{
    Console.WriteLine(0.1 + 0.2 == 0.3);
}

The code above will write false for reasons described earlier in this post. The same code using the decimal data type:

C#
static void Main(string[] args)
{
    Console.WriteLine(0.1m + 0.2m == 0.3m);
}

The above example will return true, just like we would expect. Performance of decimals is not as high as with floats or integers because of the added precision. But places where accuracy is paramount, it might be the only solution.

Epsilon#

float.Epsilon is the smallest positive float value greater than zero in .NET. It is not machine epsilon or a useful general comparison tolerance.

C#
static bool Equals(float f1, float f2)
{
    const float tolerance = 1e-6f; // Example absolute tolerance for finite values.
    return Math.Abs(f1 - f2) <= tolerance;
}

Choose the tolerance for the application's scale and acceptable error; this is not a universal equality rule.

Fixed point#

The last thing is to simply not use floats and use integers instead. This is also called fixed point arithmetic. In fixed point math you have a fixed number of digits after the radix point. It is basically an integer that you scale using some scale factor. Take the number 1.595 as an example. That is the same as 1595/1000 – so 1000 is the scale factor here. Not only can this improve accuracy, but it can also improve performance on devices without a FPU.

Conclusion#

Use stable sorting methods if the order of elements is important and make sure to take great care with floats in algorithms that are sensitive to small errors. Use doubles if you simply need more precision or use fixed point math if you need exact values. Floating point values are not evil, they are a trade-off between performance and accuracy, but you might need to do equality checks in places where you do float operations.

More in Game Development

All 26 Game Development articles →