Ensuring deterministic / repeatable simulation

[NetSavant]

Hi -

I'm working on a physics-based puzzle game that involves destructible objects - I'm having trouble getting the simulation to be repeatable though - it's important to this game, as some levels will have a rube-goldbergness where small variations can mess up the final result, so the user would have to run the level many times with the same solution to finally pass it.

I've narrowed down and eliminated a lot of variables that interfere with determinism (multithreadedness, etc.) - on the first run after game launch I can get it to produce the exact same simulation reliably - but reloading the level (which disposes & recreates the Space with the exact same settings) and running it again produces subtly different results.

So what I'm wondering is - is there any way to ensure repeatable simulation for multiple physics "runs" without stopping and restarting the whole executable? Are there maybe static resources BEPUphysics is holding onto outside the space itself that I can manually reset for each run? Does allocated heap space from other objects matter to the simulation in any way?

Thanks in advance!

-Luke

[NetSavant]

One other note, related to memory allocation - I made a very bare-bones "determinism testing build" to try and eliminate anything that my game engine might be doing to interfere - I noticed in CLR profiler that disposing & nulling the Space and triggering garbage colleciton didn't free up the vast majority of the allocated heap:

m_Space = new Space();

// ... run some physics simulations (about 1.1 MB allocated during run)

m_Space.Dispose();
m_Space = null;
GC.Collect()

// ...still about 1.0 MB of heap space allocated to BEPUphysics namespace types

Is this due to BEPU's static resource pooling? If so is it possible to manually free up / reset the resource pool? I'm thinking maybe that affects how the simulation runs when future spaces are created - not sure if that's relevant or not.

Best,

-Luke

[Norbo]

Is this due to BEPU's static resource pooling?

Yes, though it shouldn't harm determinism unless there are bugs.

If so is it possible to manually free up / reset the resource pool?

Not in the 'stable' version, but I added it to the development version:
http://bepuphysics.codeplex.com/SourceC ... evelopment
There are other resource pools not in the shared "Resources" section, though.

My own tests indicate that resetting does not eliminate the problem. There appears to be another problem lurking somewhere. Even with multithreading completely disabled, I'm still seeing a lack of determinism. My current guess is that there's something like sorting on hash codes somewhere, though I don't remember doing that anywhere except in the multithreaded solver (which is nondeterministic for other reasons).

[Norbo]

It appears the problem (or at least the problem with the single threaded failures) lies somewhere in the broad phase. Replacing the DBVH with a simple brute force system 'fixes' the issue. I'll see if I can find anything.

[NetSavant]

Interesting, thanks - was brainstorming some weird workarounds like reloading the BEPU assembly each simulation run, but will wait to hear back (sounds like that might not tackle it if it were due to hashCode sorting etc., and I'm sure it'd be fun to get working on the xbox

-Luke

[Norbo]

Well that was a goose chase- it appears to be related to something in pair handlers that isn't getting cleaned up when they are returned to their factory. Getting close now.

[NetSavant]

You're right - did a little digging, I was able to get an exact repeatable simulation on a level with just box entities by reinitializing the box-box pair handler factory when I reinitialized the space:

Code: Select all

TypePair boxPair = new TypePair(typeof(ConvexCollidable<BoxShape>), 
    typeof(ConvexCollidable<BoxShape>));
 NarrowPhaseHelper.CollisionManagers[ boxPair ] = new BoxPairFactory();

So that could serve as a workaround for my purposes - just basically re-run the code in NarrowPhaseHelper's static initializer. Not sure the garbage ramifications there but I can probably hack around that too.

[NetSavant]

Somewhat sneaky but this works:

Code: Select all

typeof( NarrowPhaseHelper ).TypeInitializer.Invoke( null, null );

[Norbo]

That would indeed do it

I've tracked down the primary offenders now. Some update orders in contact constraints had dependencies on pooled data order, and a couple of other things used data which, while valid, was from a previous usage of the instance and caused differences in the simulation.

You can grab the latest development version here: http://bepuphysics.codeplex.com/SourceC ... evelopment

While I did scan every probable location of similar errors, I may not have caught every single one (though the pieces I tested did succeed). The "nuclear bomb" approach of resetting the entire NarrowPhaseHelper will still work in those cases; though, with luck, you shouldn't have to do it anymore.

I also updated the multithreading documentation to reflect the fact that the broad phase, solver, and narrowphase all have to be single threaded for determinism (it only mentioned broad phase and solver before).

[NetSavant]

Excellent, that did the trick - getting repeatable results now without employing the "nuclear option"

[NetSavant]

And thanks in general - brilliant piece of software.