Serialization breaks determinism?
Posted: Sat Jan 15, 2011 7:40 pm
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!
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!