43
\$\begingroup\$

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?

EDIT: Skip the rest of this post if you don't care about why someone would need such precision. Individuals in comments and answers seem to believe I'm seeking after something I shouldn't, and as such, 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 map, the player has beaten the level. Otherwise, they will have to press stop, alter their machine, and try again.

The reason everything needs to be deterministic is because I plan to produce code that will map every machine (a set of pieces and tools that attempts to solve a level) to an xml or json file by recording each piece's position, size, and rotation. It will then be possible for players to share solves (which are represented by these files) so that they can verify solves, learn from one another, hold competitions, collaborate, etc... Of course, most solves, particularly the simple or quick ones, won't be affected by a lack of determinism. But the slow or complex designs that solve really hard levels might, and those are the ones that will likely be the most interesting and worth sharing.

\$\endgroup\$
45
\$\begingroup\$

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

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 ontop 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

\$\endgroup\$
  • \$\begingroup\$ Comments are not for extended discussion; this conversation has been moved to chat. \$\endgroup\$ – Vaillancourt Aug 4 at 20:01
  • 2
    \$\begingroup\$ Great answer! 2 more points in favour of fixed point: 1. floating point will behave differently closer or further from the origin (if you have the same puzzle in a different place), but fixed point won't; 2. fixed point actually has more precision than floating point for most of its range -- you can gain precision by using fixed point well \$\endgroup\$ – Jibb Smart Aug 5 at 4:07
  • \$\begingroup\$ It is possible to encode binary data in both XML & JSON using base64 elements. It's not an efficient way to represent large amounts of such data, but it is incorrect to imply that they prevent use of binary representations. \$\endgroup\$ – Pikalek Aug 7 at 16:05
  • 1
    \$\begingroup\$ @Pikalek I'm aware, OP asked me about it on comments, I mentioned base64 as one option, among others, including hex, reinterpret cast as int, and using protobuf format since nobody will understand those files anyway, they are not (untrained) human readible. Then - I assume - a mod removed the comments (no, it is not in the chat linked above). Will that happen again? Should I remove that from the answer? Should I make it longer? \$\endgroup\$ – Theraot Aug 7 at 16:28
  • \$\begingroup\$ @Theraot Ah, I can see how I might have interpreted that differently in the context of since deleted comments. (FWIW, I did read through the chats on both this answer & the question). And even if there was a native, efficient way to encode the data, there's still the larger matter of making sure that it means the same thing across platforms. Given the churn, maybe it's best to just leave it as is. Thanks for clarifying! \$\endgroup\$ – Pikalek Aug 7 at 17:29
6
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Unity is indeed working toward a goal of cross-platform determinism with their new Unity Physics system for their Data-Oriented Technology Stack, but as I understand it, it's still a work in progress and not yet complete / ready to use off the shelf. \$\endgroup\$ – DMGregory Aug 5 at 23:06
  • \$\begingroup\$ What is an example of a non-deterministic SIMD instruction? Are you thinking of approximate ones like rsqrtps? \$\endgroup\$ – Ruslan Aug 6 at 10:11
  • \$\begingroup\$ @DMGregory it must be in preview then, as you can use it already - but as you say it may not be finished yet. \$\endgroup\$ – Joe Aug 8 at 13:59
  • \$\begingroup\$ @Ruslan yes rsqrtps/rcpps the results are implementation dependent \$\endgroup\$ – Joe Aug 8 at 14:00
5
\$\begingroup\$

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

\$\endgroup\$
  • 1
    \$\begingroup\$ I completely agree. This is how you guarantee a shared experience with all users. gamedev.stackexchange.com/questions/6645/… sort of discusses a similar topic, comparing the difference between client side vs server side physics. \$\endgroup\$ – Tim Holt Aug 5 at 23:52
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Rounding down won't help, because if the high precision result is non-deterministic then eventually a result is going to round one way on one system and the other way on another system. For example you could always round down to the nearest integer, but then one system computers 1.0 and the other computes 0.9999999999999999999999999999999999999999 and they round off differently. \$\endgroup\$ – yoyo Oct 29 at 22:52
  • 1
    \$\begingroup\$ Yes that is possible, as I already said in the answer. But it will happen extremely seldom, as do other glitches in game physics. So rounding does help. (I wouldn't round down though; round to-nearest to avoid biasing.) \$\endgroup\$ – leftaroundabout Oct 30 at 2:11
0
\$\begingroup\$

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.

\$\endgroup\$
  • 3
    \$\begingroup\$ Rational arithmetic is utterly unpracticable for any sort of numerical integration. Even if each time-step does only * / + - then the denominators will get ever bigger and bigger over time. \$\endgroup\$ – leftaroundabout Aug 5 at 14:48
  • \$\begingroup\$ I would expect that even without considering integration, this wouldn't be a good solution because after only a couple of multiplies or divides, the numbers representing your numerator and denominator would overflow a 64-bit integer. \$\endgroup\$ – jvn91173 Aug 5 at 16:25
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ I'm not seeing any confusion in terminology. The OP wants deterministic behavior from a potentially chaotic system. That's entirely doable. \$\endgroup\$ – Mark Aug 5 at 22:26
  • \$\begingroup\$ Using simpler shapes (such as circles and rectangles) doesn't change the problem at all. You still need lots of trigonometric functions, sqrt, etc... \$\endgroup\$ – jvn91173 Aug 6 at 2:40
-1
\$\begingroup\$

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. You can send a rocket to the moon with double floating point precision, but not single floating point precision.

If you truly need perfect determinism, use fixed point math. This will give you less precision (assuming you use the same number of bits), 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.)

\$\endgroup\$
  • 11
    \$\begingroup\$ The double-precision approach runs afoul of the butterfly effect. In a dynamical system (like a physics sim), even a tiny deviation in initial conditions can amplify through feedback, snowballing up to a perceptible error. All the extra digits do is delay this a little longer - forcing the snowball to roll a bit further before it gets big enough to cause problems. \$\endgroup\$ – DMGregory Aug 4 at 3:41
  • 2
    \$\begingroup\$ Two mistakes at once: 1) Double floating points suffer the same problems and usually only postpone the problem into an ever harder to debug future. 2) There is no rule that states that fixed point must be less precise than floating point. Depending on the scale and the problem at hand, or on the memory you are ready to use per fixed point number, they can be less precise, equally precise or more precise. It does not make sense to say "they are less precise". \$\endgroup\$ – phresnel Aug 5 at 10:05
  • \$\begingroup\$ @phresnel, as an example of fixed-point precision, the IBM 1400 series used arbitrary-precision fixed-point decimal math. Dedicate 624 digits to each number, and you've exceeded the range and precision of double-precision floating point. \$\endgroup\$ – Mark Aug 5 at 22:46
  • \$\begingroup\$ @phresnel (2) Good point. I updated my answer to assume the same number of bits. \$\endgroup\$ – Evorlor Aug 6 at 0:18
-2
\$\begingroup\$

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));
\$\endgroup\$
  • 9
    \$\begingroup\$ I don't think this works for OP's case. Let's say you and I are both playing the game on different systems. Each of us places the puzzle pieces in the same way - a solution that was not predicted in advance by the developer. When you click "start," your PC simulates the physics such that the solution is successful. When I do the same, some small difference in the simulation leads to my (identical) solution not being graded as successful. Here, I don't have the opportunity to consult the memento from your successful run, because it happened on your machine, not at dev time. \$\endgroup\$ – DMGregory Aug 4 at 3:38
  • \$\begingroup\$ @DMGregory That's correct. Thank you. \$\endgroup\$ – jvn91173 Aug 4 at 4:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.