Serialization breaks determinism?

[snielsen]

I have an interesting problem and I am wondering if it is known issue or if there is something I am missing (I am still pretty new to bullet). I am using bullet in a turn-based multiplayer game I am developing and so determinism is of the upmost importance. I have set things up so that the simulation runs deterministically on every network player's machine and I am not having any problem with that. What I am running into is that from what I can tell the act of serializing and then de-serializing the world (using the standard dynamicsWorld->serialize(serializer)/btBulletWorldImporter(dynamicsWorld) paradigm) is breaking the determinism of the simulation between players.

For example, player A and player B are connected over the network and running the exact same simulation (same processor, same software versions, everything matched up). Player actions that occur are sync'd correctly between them so that they occur in the exact same way at the exact same frame in both simulations (I have verified that this is working correctly). Even though player actions are sync'd to the same frame between them, the player who's turn it is can actually be ahead in the simulation than the other player. So at this point lets suppose it is player A's turn and he is at simulation frame 100 and that player B is at say simulation frame 80 (lets call them 100A and 80B). Now lets cut the network so that the players cannot progress. I have player A serialize 100A and player B serialize 80B and upload them to my server. Subsequently player B downloads from the server serialized state 100A. Player B then de-serializes into memory 80B which it had stored locally. What player B does next is to continue the simulation 80B for 20 more frames (let us suppose that no player actions occurred on player A between frames 80 and 100 and so all that happened was that the simulation just ran for 20 more frames). At this point player B now has 100B and so he de-serializes 100A that he downloaded from the server and compares the two states. I would have expected 100A and 100B to be identical but they are ever so slightly divergent. My metric for determining state equivalence is to compare each body's centerOfMassTransform, linearVelocity, angularVelocity, totalForce and activationState and print out any differences so that I can examine them. I have verified that when I let both simulations run to 100A and 100B and then serialize/de-serialize both that they are functionally identical (as I would have expected).

I have tried a couple of things like making sure that the state of the world is such that every body is !isActive() at the time of serialization but divergence still occurs (although it is much smaller than if serialization occurred during movement). Before using the bullet serializers I had authored my own very simple and non-comprehensive serializer/de-serializer that just covered centerOfMassTransform, linearVelocity, angularVelocity, totalForce and activationState. This was simple enough to just have a save format for structures and was good for setting up the simulation in an initial state that I could kick things off from. Of course my serializer broke the determinism in the above scenario but interestingly the only time when I saw the determinism actually hold in the above scenario was when I was using my own serializers and serialized an "80B" situation in which all moving bodies were not colliding with with any other body (essentially it was a scenario with non-touching blocks falling mid-air after an initial collision) and a "100A" scenario in which the world had settled and all bodies were not activated.

My hope is that there is something that I am doing wrong and that it is expected that a dynamicsWorld after being serialized and then de-serialized back into memory (with the bullet serializers) should be functionally identical to the original version in memory. In the current version of bullet (I am using r2265) do we have this expectation? One thing I noticed is that after de-serialization that body's activationState does not appear to have been preserved. I have run the above scenario with just the bullet serializer (which was extremely divergent when de-serialized because every body started off with an active state) and also with the bullet serializer + my own separate serialization/de-serialization of just activationState (which gets the result pretty close but is still divergent).

One thing that gives me hope that it is me doing something wrong is that when I de-serialize the world state I get "unknown chunk" spit out a fair number of times to the console. I don't know exactly what that means or if it is an indication of failure. I observe that even with "unknown chunk" that the simulation loads to a state that is very similar (but not exact) to the state before serialization (ie there are no obvious failures like missing bodies etc). I hoping that "unknown chunk" indicates an error that would cause the de-serialized state to be divergent from the original. (.bullet file attached for an example state of an "80B")

I have some ideas for workarounds but they are not ideal. I am really hoping that I can preserve determinism across serialization. Any help or insight is much appreciated!

[VicariousEnt]

At this point player B now has 100B and so he de-serializes 100A that he downloaded from the server and compares the two states. I would have expected 100A and 100B to be identical but they are ever so slightly divergent.

I'm not sure I entirely understand your main problem, but in regards to the quote above there you need to keep in mind that no physics intergrators are 100% accurate. I havn't looked into which one Bullet uses yet (read up on Newton Euler 2, Verslet, Runga kata etc if you're not familar with intergrators or what they do), but none of them will produce 100% exactly the same simulation every time, there will always be a little bit of varience, even if done on the same machine.

[snielsen]

I am getting more familiar with the internals of bullet as I work with it but I do not yet know about physics integrators (still just starting out). Thanks for the tip though, I will check those out. From what I understand and have observed however, bullet can actually be configured to run deterministically (http://code.google.com/p/bullet/issues/ ... &start=100) so that a simulation will produce the exact same result every time given the same floating point implementation and bullet version.

For the benefit of anyone who is interested or also encountering this issue, I have done some more experimentation and found a solution that works within the particular parameters of my game. After writing a variety of test harnesses and verifiers within within my game I have identified that there is indeed some state that the dynamicsWorld serializer/de-serializer is not preserving (I don't yet know enough about the internals of bullet to understand what it is though). This is causing the simulation to diverge when compared to the same simulation run without introducing a serialization/de-serialization point. One requirement that I enforce in the game is that I only allow serialization to take place when the entire world is completely settled (all bodies have an activation state of deactivated). My game is turn-based and I have enforced a requirement that the world must be completely settled before people are allowed to pass their turn. That means that these "world settled" conditions occur fairly regularly during gameplay. What I have found is that I can introduce a physics reset by tearing down the dynamicsWorld, bringing it back up again and adding all the bodies back to the new dynamicsWorld every time the world settles. Whatever internal state is not being preserved by serialization is now being reset at identical known points in the simulation on all the networked devices regardless if serialization is actually needed on the device. This has ensured that I can stop and serialize the same simulation at different (settled) points on different networked devices and after replaying the remaining events in the simulations that were stopped at earlier points, the state of all the simulations will be identical. This has turned out to be a solution that works pretty well for my specific situation because the extra performance overhead of destroying the dynamicsWorld, re-creating it and then re-adding all the bodies is somewhat hidden from the user from a perceptibility standpoint because it only happens when nothing is moving.

I have filled a bug (http://code.google.com/p/bullet/issues/detail?id=476) so that at a minimum the base issue can be tracked.

[Kanttori]

Sorry to plug my own code, but in btBulletFileSpawn.cpp (not official code though the naming convention is the same http://www.bulletphysics.org/Bullet/php ... =12&t=5652) I added the code below because I couldn't find them being de-serialized at the time. You can compare 1:1 btRigidBody.h -> btRigidBodyFloatData with this stuff, what's still missing are the "dynamic" parts like m_linearvelocity etc.

Code: Select all

template<typename T> btRigidBody::btRigidBodyConstructionInfo	rigidBodyPrep(
		btScalar mass, const T* data, btCollisionShape* shape,
		const btVector3& localInertia)
{
	btRigidBody::btRigidBodyConstructionInfo
			rbci(mass, 0, shape, localInertia);
	rbci.m_linearDamping =
			data->m_linearDamping;
	rbci.m_angularDamping =
			data->m_angularDamping;
	rbci.m_additionalDampingFactor =
			data->m_additionalDampingFactor;
	rbci.m_additionalLinearDampingThresholdSqr =
			data->m_additionalLinearDampingThresholdSqr;
	rbci.m_additionalAngularDampingThresholdSqr =
			data->m_additionalAngularDampingThresholdSqr;
	rbci.m_additionalAngularDampingFactor =
			data->m_additionalAngularDampingFactor;
	rbci.m_linearSleepingThreshold =
			data->m_linearSleepingThreshold;
	rbci.m_angularSleepingThreshold =
			data->m_angularSleepingThreshold;
	rbci.m_additionalDamping =
			data->m_additionalDamping;

	return rbci;
}

void colObjInit(btCollisionObject* colObj,
		const btCollisionObjectDoubleData& colObjData)
{
	btVector3 temp;
	temp.deSerializeDouble(colObjData.m_anisotropicFriction);
	colObj->setAnisotropicFriction(temp);
	colObj->setContactProcessingThreshold(
			colObjData.m_contactProcessingThreshold);
	colObj->setFriction(colObjData.m_friction);
	colObj->setRestitution(colObjData.m_restitution);
	colObj->setCollisionFlags(colObjData.m_collisionFlags);
	colObj->setHitFraction(colObjData.m_hitFraction);
}

[Gemini]

I am not familiar with the internal workings of bullet but from working with other physics engines it sounds to me like the problem you are getting is due to the order in which collisions/constraints are created.

Typically when two objects overlap (objectA, objectB) some form of encounter is created. The order of the two objects (objectA,objectB) OR (objectB,objectA) often determines the order of contraint setup/creation. Because contraints are solved sequentially you will produce different results depending on the order of your two objects. This will begin to diverge the simulation.
I have not checked the bullet code but I am guessing that the serialise/deserialise code will save the state of individual objects and not the internal structure of the world.

By removing all your objects and recreating your world you are removing the information about "how the objects got where they were". By doing this when you recreate your world on the other computer the deserialise will put the two worlds back into the same state. If you can afford this operation then it may be your only option (Although for large worlds this will be a costly operation).

Take note that by recreating your world on computer A before serialising you will have changed how the simulation "Would" have run on computer A for future simulations.

Again... I am guessing on how bullet is working here from my own previous experience. If I get chance I will have a look through the bullet code and see if this is actually the case. No doubt one of the bullet authours will be able to give the thumbs up/down to my response )

[Erwin Coumans]

I'm currently busy doing research and preparations for Bullet 3.x, so I won't be visiting the forums as regular as usual.

Re-starting after serialization will produce different results due to various issue. This is a feature that I want to include for Bullet 3.x, but if we can make it work in Bullet 2.x that would be great too.

1) The order of overlapping pairs is important, and needs to be the same. This is a broadphase / paircache issue
2) The cached contact points need to be stored in the same order. This is a narrowphase issue.
3) The "warm starting" or cached "applied impulse" needs to be the same. This info is store in the overlapping pairs, but used by the constraint solver

There are likely other areas, but in a nutshell, all this data needs to be serialized as well. I create an issue in the tracked so we can track the progress: http://code.google.com/p/bullet/issues/detail?id=519

Thanks,
Erwin

[snielsen]

Just to follow up, I have found great success in restarting the simulation during those quiet and settled moments when nothing is moving. Because I always reboot the simulation whether serialization is actually wanted or not, this has allowed me to maintain determinism across serialization. It is a somewhat expensive operation but in my scenario it is not too bad and definitely worth the trade-off.

Looking forward to the serialization advancements in Bullet 3.X

Spencer