Sign in to follow this  
sofakng

Are physics systems really deterministic? Same inputs equal same outputs? (timestep)

Recommended Posts

I'm having a little trouble understanding something. If you're using a fixed timestep and the exact same inputs, will you get the same exact outputs all the time on every different computer? I'm having a thread conversation over the networking thread and I've thought about this before but it seems like I get different answers but it's probably because I'm not understanding the context of what they're saying. In this article: http://www.gamepoetry.com/blog/2008/04/18/understanding-the-game-loop/ ...the author says that if you use a fixed timestep and the exact same inputs that the results will always be the same and can even be used to record games for replay. However, I've also been told that physics simulators (and basically ALL games that use floats) will have small differences over time thus causing them to be out of sync with other network players. How can this be deterministic if different computers have different results over time? If using a fixed timestep and exact same inputs always produced the same results why would you even need network synchronization? (let's assume the network isn't dropping packets or that we are using TCP and not UDP)

Share this post


Link to post
Share on other sites
Quote:

If you're using a fixed timestep and the exact same inputs, will you get the same exact outputs all the time on every different computer?


No, you're not guaranteed that for arbitrary code. If you use the same computer, and expand 'inputs' to include stuff like the threading choices made by the OS then you could probably guarantee that for certain timesteps (even though you could never practically guarantee the same inputs at that point).

But then again, you often don't need the same exact outputs. If they're off by 0.00001; that's good enough for replays. [edit: And for certain code, you can make effective guarantees. A turn based game for example depends a lot less on timing and has much less opportunity for float drift.]

Share this post


Link to post
Share on other sites
Quote:
Original post by sofakng
If using a fixed timestep and exact same inputs always produced the same results why would you even need network synchronization? (let's assume the network isn't dropping packets or that we are using TCP and not UDP)


You might end up with roundoff errors if registers are saved to the stack for any reason such as taskswitching (registers will have a few extra bits that will be lost when their values are saved to the stack). Over time the accumulation of errors may become significant depending on the application, and you can't really ever trust the code running on someone else's computer because alterations may have been made to it.

Share this post


Link to post
Share on other sites
Thanks for the information.

I'm still a little confused though...

If two physics simulations are running (ODE, Newton, Farseer, etc) on two different machines and I'm using a fixed timestep, will the object positions be "exactly" the same on both machines? (or close enough to not matter?)

What I mean is that if I had these two machines playing a network game together, could each machine run the simulation and have the "correct" object positions?

I know that clients can't be trusted because of cheating, and I know you need a server for disputes (eg. two players moving an object to the same location, etc), but I'm still trying to fully understand determinism and what it means for network gaming, etc.

Share this post


Link to post
Share on other sites
That is perhaps asking the wrong question. It doesn't really involve a fixed timestep. There's inherent latency between the time the input is created and the time that the various simulations get the input. A simulation will always be 'off' because it doesn't know about all of the inputs made in the last 30ms (or however long the network latency is).

If you had two identical machines, under identical load, running the same code, using identical inputs from a script (like a timedemo), they'll produce the same result. Realistically, any two machines with the same code using identical inputs from a script will produce essentially the same result (close enough that it won't matter for the non-psychotic cases).

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn
A simulation will always be 'off' because it doesn't know about all of the inputs made in the last 30ms (or however long the network latency is).

This kind of stuff makes my head hurt so bad, heh.

What you're saying makes sense but I'm a little confused because it seems to be different from the conversation going on in my other thread in the networking forum.

If you'd like to join in (and I would appriciate it), it's located over here: http://www.gamedev.net/community/forums/topic.asp?topic_id=520956

Also, here is the thread where I asked the Farseer physics developers about this same thing: http://www.codeplex.com/FarseerPhysics/Thread/View.aspx?ThreadId=44137&ANCHOR#Post146855

...and they said "This is true. You can never be sure that the same results will be calculated on different systems."

:(

Share this post


Link to post
Share on other sites
The key in that thread is hplus0603's reiteration to you. Every few seconds or so, do some actual state corrections. Things don't deviate too much, but over time that adds up. If you correct the deviances regularly, it never has a chance to add up. And he's had far far more practical experience with these things than I. That thread will probably help you most.

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn
If you had two identical machines, under identical load, running the same code, using identical inputs from a script (like a timedemo), they'll produce the same result. Realistically, any two machines with the same code using identical inputs from a script will produce essentially the same result (close enough that it won't matter for the non-psychotic cases).


Not in my experience. We were developing a replay system with PhysX, there are little rounding errors that can screw up.

Share this post


Link to post
Share on other sites
See, this is what is so confusing :(

It seems like some people say that the output is always deterministic but other people say it's not...

(I'm not trying to criticize or be rude, but I'm just trying to learn...)

Share this post


Link to post
Share on other sites
For example, Havok Physics documentation states:
Quote:
Havok simulation is deterministic, meaning that a simluation will yield exactly identical results if it's run several times from the exact same starting point on the same platorm and configuration.

...

Havok may also yield different results when you run a simulation on different platofrms. Also, simluation on PLAYSTATION®3 may become non-deterministic when we change the default settings and allow the PPU to take SPU tasks related to collision detection and constraint solving.

Share this post


Link to post
Share on other sites
As people have said a physics system is deterministic but there are some factors outside of its control which can affect it. Those errors might be tiny at first but as they accumulate they will grow larger until they are noticable and affect gameplay etc.

One way of fixing this is to allow the physics engines on different machines to play out as they like, and then to synchronise them with the "master" copy.

Or for things like replays we have keyframes that are snapshots of the state of objects and the physics engine. We load up a snapshot, and then just play back the recorded inputs. It works for a while but then gets too different, so we keep loading keyframes at regular intervals during the playback. This essentially forces the replay back to a known good state.

Andy

Share this post


Link to post
Share on other sites
Quote:
Original post by sofakng
See, this is what is so confusing :(

It seems like some people say that the output is always deterministic but other people say it's not...

(I'm not trying to criticize or be rude, but I'm just trying to learn...)


It is. It has to be, modern electronic computers are deterministic.

For a given machine, given the same code and the same inputs you'll get the same result. Period.

The problem comes when that is violated. Different machines may produce different results for the same input (mostly due to differences in floating point processing). And for even the same machine, it's practically impossible to provide the same inputs due to timing issues (what if the OS schedules things differently, what if the hard drive takes .5 ms longer to load something, what if you get a different section of cpu cache that takes a little longer).

As soon as you can provide identical inputs, you'll get identical outputs. But you can't provide that for arbitrary systems.

Share this post


Link to post
Share on other sites
Quote:
Original post by CrimsonSun
You might end up with roundoff errors if registers are saved to the stack for any reason such as taskswitching (registers will have a few extra bits that will be lost when their values are saved to the stack).
Incorrect. The operations used to save the FPU state save all bits, unlike the operations used to pull numbers out of it.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this