Making physics fully deterministic

[system]

	Attention	Topic was automatically imported from the old Question2Answer platform.
	Asked By	Urben

Hello,
I am just about to start with GoDot. I have quite fleshed out ideas already and I wonder about one aspect: deterministic physics.

To make it short, I want to create a singleplayer 3d parkour game. Two features I want to include are this:

• Reverse, where you can trigger a backwards sequence to get back to any point you want.
• Replay files for high scores that you can “run”, like a ghost car you see in racing games.

I want to do this with making logs of inputs that the game uses to get you to the exact spot in the exact time. Now I wonder if I run into problems with rounding errors, like when 0.0001m difference causes one to fall of the roof instead of jumping from it.

I heard fixed-point numbers limit this problem but they seem to not be a thing in Godot.

Are there resources I can read on this matter?

Replay files for high scores that you can “run”, like a ghost car you see in racing games.

This may not fully answer your question, but saving and loading replays doesn’t require determinism per se. You can save the 3D transforms of all objects in the scene every frame and replay them over time (with interpolation if needed, for slow motion playback). This makes replay files much larger, but they won’t break if you update the game’s physics logic. You can still use compression to make replay files smaller

Calinou | 2019-08-19 19:55

That surely works too and I am sure this is a matter of taste, but I try to get the “elegant” solution done with determinism with your idea being a plan B. So thanks for the submission!

I played a lot of Worms Armageddon back in the days and I was and still am amazed how tiny and accurate the replay files are. It was a locked frame rate (both visual and physics) of 50fps. I know it is a whole different thing with 3d games that use metric systems instead of pixel measurements but I want to try to make something comparable work.

Urben | 2019-08-19 20:12

Calinou is correct, I would say this is the most elegant solution.

To be precise this is not a problem of determinism, most physics engine are deterministic, in the sense that there is no randomness in the calculus. However the problem is that in most cases the game are chaotic, in the sense that very small changes can produce a very different result.

So if you want to stick with your solution, you have to work to reduce chaos in your game. Example: rounding positions where force are applied or rounding the applied forces to avoid floating point imprecision.

BraindeadBZH | 2019-08-19 20:40

Thanks for the comment!
Yes I am aware of the chaotic aspects. What I hope for is to include all factors that generate the same chaos over and over again. Though I yet don’t see how chaos can come up in my ideas, as there is pretty much only the player’s movement in a static world.

Do rounding positions eliminate floating point imprecision or do they “just” reduce them?

Urben | 2019-08-19 20:51

Rounding should totally eliminate imprecision as it only affects the decimal part.

BraindeadBZH | 2019-08-19 20:58

Oh you meant rounding to no digits after the dot? I assumed to like three digits after it. Sounds like that would make me lose alot of precision.

Urben | 2019-08-19 21:05

[system]

	Reply From:	Xrayez

I personally wouldn’t rely on determinism in Godot or being it a thing in the future, even lead developer expressed concerns about this.

There are some libraries which allow you to integrate your own fixed-point math to avoid floating point related errors (the use cases are not limited to physics):

libfixmath (C)
FixedMath.Net (C#)

So in this case you’d have to either provide needed typedef for real_t in the source code directly (if that’s even possible) to utilize fixed point math, or implement your own physics implementation I guess, which is not an option for most people.

Even if determinism (or rather lack of chaos) can be achieved locally, you’d still might encounter issues down the road regarding your solution being cross-platform, with never-ending compiler configurations out there to deal with floating point precision.

So as suggested by others, you’d likely want to come up with ways to efficiently store critical and update states in your game. It’s not really practical to record the states every single frame so you’d want to record only a subset of states and then to apply interpolation when playing those back.

Another approach which I’m considering to try out myself is semi-relying on determinism by actually recording those input actions/events and recording occasional synchronization states at the same time. That way, the most optimal replication can be achieved by simulating game input (see parse_input_event(), action_press() methods) and replicating another bunch of synchronization states which can “catch up” to exact checkpoint state to eliminate any desynchronization at the moment.

Also see an in-depth discussion regarding node replication.

Reverse, where you can trigger a backwards sequence to get back to any point you want.

That’s where mixing inputs with recording states is not a solution because if you do rely on determinism to play those states back, it’s either not really possible or such rewinding won’t be smooth anymore.

P.S. I’m an avid W:A player myself so I can really relate to your concerns.

Xrayez | 2019-08-20 08:41

Thank you for your answer!

The reverse idea is not that critical to waste too much time for now, so I will just put it aside. Still replays will be an important part for the game for me so I will see what I could do.
Generally the idea of mixing both the use of inputs and corrections seem to be the best solution so far.

or implement your own physics implementation I guess, which is not an option for most people.

To which degree? Currently I plan every physics frame for the movement but it will of course include floats and vectors and so on.

Urben | 2019-08-20 17:06

To a degree as if you would integrate some physics engine with native fixed-point math support, see how Bullet physics got integrated into Godot for instance. I haven’t done anything like that though.

Godot has C# support so you could also find external libraries for that perhaps and somehow bypass Godot’s physics and use it for rendering only (still node-based).

Xrayez | 2019-08-20 17:23

That sounds actually like an idea worth considering. Will look into how bullet is integrated and try to understand how it is connected to Godot.
Could you give me a rough direction where to find some kind of documentation of it? I hope it is documented.

Urben | 2019-08-20 18:07

I think you’d need to look at the source code directly. Look how PhysicsServer virtual methods are being overridden to fully support required Godot physics features (to be used in nodes). Ideally you could then switch implementation just by restarting Godot editor. Some folks proposed integrating popular Box2D library but it doesn’t provide some subset of features required by Godot (I think it was a RayShape2D). But you’re not required to implement it all if you personally don’t need something for your project.

Xrayez | 2019-08-20 18:57

Do I understand this correctly that I need to override existing methods globally for this? I was more hoping I could create an own extra bit of physics on top of Bullet so I can still use all it’s features for things that are not affecting my replay files.

Urben | 2019-08-20 20:00

Well then you either have to patch Bullet to make it deterministic yourself or provide your own implementation indeed. As it’s been mentioned, it boils down to using fixed-point math under the hood. I’m not an expert in this, there could be better ways likely. I don’t think it’s that common for the physics engine to be deterministic in the first place so there’s not so much work done on this.

Xrayez | 2019-08-20 20:16

Yeah that doesn’t seem to be a “nice” solution for my current horizon.

What if I find a fixed-point library for one of the other supported languages (like C#) and just not use the physics of Godot/Bullet for my stuff and make it up completely myself within a C# script? I would just put a call of it inside _PhysicsProcess, make it save fixed-point values into my replay file and return a float-version of the values for the immediate use within the engine. It would never be fed with float values but only the inputs so it keeps on using the fixed point numbers stored in itself.

Urben | 2019-08-20 20:33

I think doing it all in C# is a good alternative, but you’d still had to implement your own collision detection and physics, unless you find another compatible C# physics engine. If there’s any interaction with built-in physics, the floating-point error could still accumulate imo.

Xrayez | 2019-08-20 20:44

Right while writing this I already thought about collision detection and that I have zero ideas how to make that up from the scratch. The regular physics are not much of an issue as I only need very few formulas and routines in my case.

Still this seems to be the most promising approach for me. Maybe I can solve the collision problem by determining the coordinates of the next collision with ray-casting. Though this might be a new source of inaccuracies.

Urben | 2019-08-20 21:06