Deterministic Lock-step in Unity3D(iOS/Android)
Deterministic Lock-step in Unity3D(iOS/Android)
Hello Norbo,
First off, I would just like to thank you for making this amazing engine.
I have played around with it for few months now and basing my upcoming multiplayer app on it.
I am currently developing a game for Android and mobile iOS devices. I am using Unity3D and BEPUphysics .Net 3.5 v1.30.
Initial I used the physics engine to run on my server and had great results syncing players by just sending the transform of the objects. However, the main problem with this model is latency, bandwidth and having to run the physics on my server for each game. Since from playing around with BEPUphysics, I learned it is pretty good at being deterministic, so I decided to program a lock-step version of my network. It turns out that it works out really well and very responsive.
After some initial testing of syncing my PC and Nexus 5 Android, everything seemed to sync really well between my PC and android. Even in midst of chaos where ~150 objects are bouncing around the screen, the transforms matched exactly on both platforms!
Here is a video where everything is 100% synced between my Nexus 5 Android and PC by only sending the player's input state: http://youtu.be/RhseAgPSWUA
After seeing how well it worked out, I decided to try another simulation, this time having a stack of rectangles on top of each other and shooting a sphere at it. Anddddd....... that's where it starts... After setting up the stacked up rectangles, I did a quick simulation to see how it syncs on my network. The results did not match on both platforms =( This seemed strange to me as in my other simulations with about 150 objects bouncing and colliding, both simulation were 100% synced between both platform. But... having little bunch of stacked up rectangles results in different simulation in each platform :s
So I did bunch of tests, I played around with _controlfp_s to try to match Android's Java floating point precision but no luck there since as of right now I have no idea how Java rounds floating numbers. I wrote a script to make sure that objects in Unity are created in the same order every time, but that doesn't seem to be the problem - though, I feel that I may of missed something and maybe objects are not being created in same order.. O ensured all multi-threading is disabled..
However, the simulation always matches on all my Android phones. My PC always produces the same simulation each time, but the simulations are different on each platform. Unfortunately, it seems to be the floating point precision problem that many developers run into =(
My main concern is maintaining deterministic across Android and iOS devices. I am hoping there is a work around this.. Is there certain things I should avoid to maintain determinism? for example, avoid physics that rely on transcendental functions(sin , cos, etc..)?? Also is there any hope if I switch to BEPU double version? - will that help? What about fixed-floating number?? - my game is not a physics game, so I am not concerned about the quality of the physics.. Is there any suggests that you can give me that could point me to the right direction????
Once again, thanks for this great engine, I will surely donate if my app does well in app market.
First off, I would just like to thank you for making this amazing engine.
I have played around with it for few months now and basing my upcoming multiplayer app on it.
I am currently developing a game for Android and mobile iOS devices. I am using Unity3D and BEPUphysics .Net 3.5 v1.30.
Initial I used the physics engine to run on my server and had great results syncing players by just sending the transform of the objects. However, the main problem with this model is latency, bandwidth and having to run the physics on my server for each game. Since from playing around with BEPUphysics, I learned it is pretty good at being deterministic, so I decided to program a lock-step version of my network. It turns out that it works out really well and very responsive.
After some initial testing of syncing my PC and Nexus 5 Android, everything seemed to sync really well between my PC and android. Even in midst of chaos where ~150 objects are bouncing around the screen, the transforms matched exactly on both platforms!
Here is a video where everything is 100% synced between my Nexus 5 Android and PC by only sending the player's input state: http://youtu.be/RhseAgPSWUA
After seeing how well it worked out, I decided to try another simulation, this time having a stack of rectangles on top of each other and shooting a sphere at it. Anddddd....... that's where it starts... After setting up the stacked up rectangles, I did a quick simulation to see how it syncs on my network. The results did not match on both platforms =( This seemed strange to me as in my other simulations with about 150 objects bouncing and colliding, both simulation were 100% synced between both platform. But... having little bunch of stacked up rectangles results in different simulation in each platform :s
So I did bunch of tests, I played around with _controlfp_s to try to match Android's Java floating point precision but no luck there since as of right now I have no idea how Java rounds floating numbers. I wrote a script to make sure that objects in Unity are created in the same order every time, but that doesn't seem to be the problem - though, I feel that I may of missed something and maybe objects are not being created in same order.. O ensured all multi-threading is disabled..
However, the simulation always matches on all my Android phones. My PC always produces the same simulation each time, but the simulations are different on each platform. Unfortunately, it seems to be the floating point precision problem that many developers run into =(
My main concern is maintaining deterministic across Android and iOS devices. I am hoping there is a work around this.. Is there certain things I should avoid to maintain determinism? for example, avoid physics that rely on transcendental functions(sin , cos, etc..)?? Also is there any hope if I switch to BEPU double version? - will that help? What about fixed-floating number?? - my game is not a physics game, so I am not concerned about the quality of the physics.. Is there any suggests that you can give me that could point me to the right direction????
Once again, thanks for this great engine, I will surely donate if my app does well in app market.
Last edited by test44x on Tue Mar 24, 2015 6:34 pm, edited 1 time in total.
Re: Deterministic Lock-step in Unity3D(iOS/Andriod)
Unfortunately, when dealing with two completely different pieces of hardware and thick runtimes, I'm not sure how to force floating point compatibility consistently. I would not be surprised to hear that a particular platform combination just could not be made compatible (barring extreme hackery).
That said... the fact that you had a full chaotic simulation running deterministically implies that it's possible, at least for those platforms. There may be some part of the engine which produces subtly different behavior, but which is avoidable. Trying different subsets of the simulation to narrow down possible diverging elements could reveal something of interest- maybe, say, some collision pair handler generates different numerical behavior on one platform, but that pair type could then be avoided or even adjusted.
It may be worth playing around with different JIT compilers. For example, the old x86 and x64 compilers produced significantly different results for all sorts of math (x87 vs SSE instructions), and RyuJIT is different still. It may be possible to might be able to pick a compiler (or otherwise tune the compiler) that matches better for whatever corner case is being hit. This is a very brittle approach that assumes a lot of things which really shouldn't be assumed, though, and I don't have much hope for it working at all.
I doubt that using doubles would help. It might do something to the generated assembly, similar to the above, but if it worked it would be just as brittle.
The only sure fire way I'm aware of to ensure cross platform determinism is to reimplement all the math as fixed point with all its associated developmental work and runtime cost.
That said... the fact that you had a full chaotic simulation running deterministically implies that it's possible, at least for those platforms. There may be some part of the engine which produces subtly different behavior, but which is avoidable. Trying different subsets of the simulation to narrow down possible diverging elements could reveal something of interest- maybe, say, some collision pair handler generates different numerical behavior on one platform, but that pair type could then be avoided or even adjusted.
It may be worth playing around with different JIT compilers. For example, the old x86 and x64 compilers produced significantly different results for all sorts of math (x87 vs SSE instructions), and RyuJIT is different still. It may be possible to might be able to pick a compiler (or otherwise tune the compiler) that matches better for whatever corner case is being hit. This is a very brittle approach that assumes a lot of things which really shouldn't be assumed, though, and I don't have much hope for it working at all.
I doubt that using doubles would help. It might do something to the generated assembly, similar to the above, but if it worked it would be just as brittle.
The only sure fire way I'm aware of to ensure cross platform determinism is to reimplement all the math as fixed point with all its associated developmental work and runtime cost.
Re: Deterministic Lock-step in Unity3D(iOS/Andriod)
I figure that fixed math struct is the only way to go so I am in the process of implementing a fixed math type in bepu.
However, I ran into a problem. The Fixed Math library I am using currently doesn't support Acos function, but it does have Sin, Cos, Tan, and Atan2. You used Acos functions in few places, is there any way I can derive Acos from the supported functions or is there a way around the math you used Acos for?
Only alternative I have right now is using Math.Acos library and then casting the result back to my fixed floating type.. I feel that this defeats the purpose of using fixed floating point... Any suggestions?
However, I ran into a problem. The Fixed Math library I am using currently doesn't support Acos function, but it does have Sin, Cos, Tan, and Atan2. You used Acos functions in few places, is there any way I can derive Acos from the supported functions or is there a way around the math you used Acos for?
Only alternative I have right now is using Math.Acos library and then casting the result back to my fixed floating type.. I feel that this defeats the purpose of using fixed floating point... Any suggestions?
Re: Deterministic Lock-step in Unity3D(iOS/Andriod)
A few options: compute acos from atan, compute an approximation (e.g. taylor series), or use a lookup table.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
After setting up my Fixed struct type and testing it out, it turns out that the Collision detection behaves strangely.
I started debugging and it seems that BEPU produces insane precision that's beyond my fixed struct. For exmaple, some of the contact points produces floating 1e-40!!! there is no practical way of achieving fixed math with that much precision.
My lowest precision is about 1e-8f, anything lower than that will equate to 0. I see that throughout the code there are numbers such as 1e-9f, 1e-12f, 1e-14f that are being used for comparison. The code below from PhysicsChecker.cs throws exception due to contact.Normal having insane numbers like 1e-6 * 1e-6f
Are precisions that high really needed? Would it harm the engine if I were to set anything higher than 1e-8f to 1e-8f?? Do you have any suggestions on how to handle these insane precisions? Any way of scaling them?
As for my Collision detection, objects some times collide and sometimes do not. At first, none of my objects would collide with each other, but after correctly implementing IsInfinity check for my struct, some of the objects started colliding. All the objects are of Box type.. but only some collide. This seems to be an issue with static objects, it collides with some object but not all..
Do you know by any chance what would be causing objects to pass through each other? Could it because of precision?
Thanks in advance!
I started debugging and it seems that BEPU produces insane precision that's beyond my fixed struct. For exmaple, some of the contact points produces floating 1e-40!!! there is no practical way of achieving fixed math with that much precision.
My lowest precision is about 1e-8f, anything lower than that will equate to 0. I see that throughout the code there are numbers such as 1e-9f, 1e-12f, 1e-14f that are being used for comparison. The code below from PhysicsChecker.cs throws exception due to contact.Normal having insane numbers like 1e-6 * 1e-6f
Code: Select all
public static void Validate(this Contact contact)
{
contact.Normal.Validate();
if (contact.Normal.LengthSquared() < 0.9f)
throw new ArithmeticException("Invalid contact normal.");
contact.Position.Validate();
contact.PenetrationDepth.Validate();
}
As for my Collision detection, objects some times collide and sometimes do not. At first, none of my objects would collide with each other, but after correctly implementing IsInfinity check for my struct, some of the objects started colliding. All the objects are of Box type.. but only some collide. This seems to be an issue with static objects, it collides with some object but not all..
Do you know by any chance what would be causing objects to pass through each other? Could it because of precision?
Thanks in advance!
Re: Deterministic Lock-step in Unity3D(iOS/Andriod)
1e-40 is definitely way beyond the level of importance needed by anything in the engine. Such values are just numerical accidents without any real meaning at the scales of a regular simulation.I started debugging and it seems that BEPU produces insane precision that's beyond my fixed struct. For exmaple, some of the contact points produces floating 1e-40!!!
The 1e-12 and 1e-14 in the Quaternion can be easily pushed to larger values. The two functions in which they are used actually benefit from that level of precision (hence the use of doubles in one of them), but it will only marginally harm corner case behavior if you move it out to something like 1e-7 or 1e-8.I see that throughout the code there are numbers such as 1e-9f, 1e-12f, 1e-14f that are being used for comparison.
Things like the MPRToolbox.RayCastSurfaceEpsilon and others using 1e-9 can be bumped up without a huge impact in most cases, too. These are all matters of quality as opposed to absolute binary correctness.
Some of them can be handled by arbitrarily scaling everything up, though this can then run into upper limits. Others, like the quaternions, work in a fixed space- scaling and reinterpreting could work, but it would be slightly gross. (A specialized fixed point value that operated in the smaller range required by the quaternion might be useful.)Are precisions that high really needed? Would it harm the engine if I were to set anything higher than 1e-8f to 1e-8f?? Do you have any suggestions on how to handle these insane precisions? Any way of scaling them?
Another option is to just use 64 bit fixed point math. That would give you a resolution of 1e-14 in a range of ~185000 units. It'll take a small performance hit from extra cache pressure, but it should be irrelevant relative to the cost of using fixed point math in general assuming this is running on a CPU that can natively handle 64 bit integer math.
That doesn't sound much like a precision issue.As for my Collision detection, objects some times collide and sometimes do not. At first, none of my objects would collide with each other, but after correctly implementing IsInfinity check for my struct, some of the objects started colliding. All the objects are of Box type.. but only some collide. This seems to be an issue with static objects, it collides with some object but not all..
Do you know by any chance what would be causing objects to pass through each other? Could it because of precision?
If the objects are totally passing through each other without interacting at all, it may be a bug introduced in the broad phase somewhere. The broad phase is responsible for finding pairs of objects to collide; if it got broken, then it would fail to generate pairs correctly and stuff would just pass through.
If the objects 'sort of' collide but incorrectly, then the bug is probably in the relevant narrow phase algorithm. For example, if two boxes fail to collide properly, it's probably within the execution of the BoxPairHandler and its children.
If you visualize contact points and see that they are being generated reasonably (i.e. similar to the non-fixed point math version), it may be a bug introduced in the solver.
Re: Deterministic Lock-step in Unity3D(iOS/Andriod)
Here is a video of what I mean: https://www.youtube.com/watch?v=9bY2J9Ct1j4 Please use 720P quality to see the bounding boxes clearly.
Notice how the bounding box is acting weird with the boxes? Notice how when the board rotates to a certain direction the bounding box gets smaller and smaller, but when when it gets passed a certain angle it behaves properly.... Hmmmm I am not confident about my Abs, Sign or -( e.g -2.5f) math functions...I am going to look into to them more.
Spheres and mesh objects seem to be fine, but other than those two, the bounding boxes are acting strangely in a linear way
Any idea what could be causing the bounding box to behave like that?
Thanks for your help!
Notice how the bounding box is acting weird with the boxes? Notice how when the board rotates to a certain direction the bounding box gets smaller and smaller, but when when it gets passed a certain angle it behaves properly.... Hmmmm I am not confident about my Abs, Sign or -( e.g -2.5f) math functions...I am going to look into to them more.
Spheres and mesh objects seem to be fine, but other than those two, the bounding boxes are acting strangely in a linear way
Any idea what could be causing the bounding box to behave like that?
Thanks for your help!
Re: Deterministic Lock-step in Unity3D(iOS/Andriod)
It appears to be a bug introduced in bounding box calculation, so BoxShape.GetBoundingBox is the most likely spot as you seem to have guessed.
The bounding box is modified by the EntityCollidable.ExpandBoundingBox function too, but I suspect that isn't the problem.
The bounding box is modified by the EntityCollidable.ExpandBoundingBox function too, but I suspect that isn't the problem.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Yes, you are completely right! The Issue was within GetBoundingBox, there was a bug with my Math.Sign function which was causing the calculation errors. Now I am getting much better collision detection and proper boundingBox.
I will need your help on two more bugs that I am seeing. Sometimes, objects go through each other and bounce back.. Here is video of what I mean:
https://www.youtube.com/embed/dRytfj1k5lw
Notice how the sphere ball sinks into the ground then jumps back up. I hope it's not due to precision then I have to shift my bits in a way that gives me 1e-14f precision. I am using 64bit long, I think it's doable, but might screw up my other calculations. I have not yet changed any floating point numbers in the engine. 1e-14f and the rest are unchanged.
Another bug is that I am getting ArithmeticException("Invalid contact normal."); from the code below in PhysicsChecker.cs
This mostly happens when boxes are stacked on top of each other. I think it's due to my fixed math not catching all the possible IsNaN and IsInfinity. I have Sqrt(<0), division by zero, infinity * infinity covered.. I can't think of any other way that would cause IsNaN or IsInfinity, do you know by any chance what causes those?
Once, again thanks for your help!
I will need your help on two more bugs that I am seeing. Sometimes, objects go through each other and bounce back.. Here is video of what I mean:
https://www.youtube.com/embed/dRytfj1k5lw
Notice how the sphere ball sinks into the ground then jumps back up. I hope it's not due to precision then I have to shift my bits in a way that gives me 1e-14f precision. I am using 64bit long, I think it's doable, but might screw up my other calculations. I have not yet changed any floating point numbers in the engine. 1e-14f and the rest are unchanged.
Another bug is that I am getting ArithmeticException("Invalid contact normal."); from the code below in PhysicsChecker.cs
Code: Select all
[Conditional("CHECKMATH")]
public static void Validate(this Contact contact)
{
contact.Normal.Validate();
if (contact.Normal.LengthSquared() < 0.9f)
{
Console.WriteLine("Invalid contact normal." + contact.Normal);
//throw new ArithmeticException("Invalid contact normal.");
}
contact.Position.Validate();
contact.PenetrationDepth.Validate();
}
Once, again thanks for your help!
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Sphere-mesh collision:
Appears to be a lack of penetration correction. The contact visualizer seems to imply it has a reasonable detected penetration, but the constraint isn't pushing it out. (The "pop" appears to be correct behavior; angular momentum of the ball gets transformed into linear momentum by the impact with an obstacle.)
I'd check the ContactPenetrationConstraint.Update to make sure the bias field is being set correctly (line ~193). When the contact's penetration is deeper than the allowed penetration threshold, the bias should be nonzero. Make sure the contact penetration data is also reasonable.
Precision is most likely not related.
Compound falling halfway through the ground, ragdolls falling partly through the ground:
I'm not sure these two things are related, but they may be. The collision pair count seems to be correct in either case, but it seems to fail to generate contacts sometimes.
Assuming they aren't related, I would recommend checking the CompoundConvexPairHandler.UpdateContainedPairs function when the compound should be detecting contacts but isn't. My guess is that the detected overlaps will be empty because something is wrong with the compoundInfo.hierarchy.Tree. Judging by the video, the tree may be built with the bounding boxes all centered on the compound's center of mass, or maybe with zero extent.
If the two problems are related, that compound midphase should work fine and something else will be the culprit. In this case I'd expect the BoxPairHandler (which the CompoundConvexPairHandler will create as a subpair) to have some kind of bug, since all the issues seem to involve box-box collisions. The somewhat random working/broken state reminds me of problems caused by the order of objects in a pair; keep an eye out for anything that looks like it might depend on which collidable is object 'a' versus 'b'.
This may require walking through the box-box pair handler to see if you notice anything weird.
Precision is probably not related.
Fancy shapes bouncing around:
Given that boxes and spheres do not seem to bounce, this is probably something specific to these shape types. I can't quite tell from the video, but it may be bounding box related again. If the bounding box does not fully contain the shape, contacts will only be created after there is already a deep penetration. Unfortunately, I suspect it may not be this simple- ConvexHullShape has a unique implementation of GetBoundingBox and it is behaving the same way as the MinkowskiSumShape and TransformableShape.
The one thing all those shapes share is a reliance on MPR/GJK-based contact generation. They use the GeneralConvexContactManifold, which is one of the more complicated collision detection algorithms in the engine. I can't pinpoint the most likely source of the problem; it may require walking through it and looking for anything clearly out of the ordinary (possibly comparing against the working floating point version).
This is one area where precision may be a problem. MPR and GJK both rely heavily on thresholds, and it's conceivable that they would not play well with things getting clamped or zeroed out.
But I wouldn't expect the lack of catching such error conditions to be the cause of general case behavior problems. The engine goes out of its way to avoid generating invalid values. If the conditions arise where such values could show up, something already went wrong.
Instead, if this happens with box-box collision specifically, it may be a hint about the nature of the box-box bug above. Trace how that bad normal is getting generated.
Appears to be a lack of penetration correction. The contact visualizer seems to imply it has a reasonable detected penetration, but the constraint isn't pushing it out. (The "pop" appears to be correct behavior; angular momentum of the ball gets transformed into linear momentum by the impact with an obstacle.)
I'd check the ContactPenetrationConstraint.Update to make sure the bias field is being set correctly (line ~193). When the contact's penetration is deeper than the allowed penetration threshold, the bias should be nonzero. Make sure the contact penetration data is also reasonable.
Precision is most likely not related.
Compound falling halfway through the ground, ragdolls falling partly through the ground:
I'm not sure these two things are related, but they may be. The collision pair count seems to be correct in either case, but it seems to fail to generate contacts sometimes.
Assuming they aren't related, I would recommend checking the CompoundConvexPairHandler.UpdateContainedPairs function when the compound should be detecting contacts but isn't. My guess is that the detected overlaps will be empty because something is wrong with the compoundInfo.hierarchy.Tree. Judging by the video, the tree may be built with the bounding boxes all centered on the compound's center of mass, or maybe with zero extent.
If the two problems are related, that compound midphase should work fine and something else will be the culprit. In this case I'd expect the BoxPairHandler (which the CompoundConvexPairHandler will create as a subpair) to have some kind of bug, since all the issues seem to involve box-box collisions. The somewhat random working/broken state reminds me of problems caused by the order of objects in a pair; keep an eye out for anything that looks like it might depend on which collidable is object 'a' versus 'b'.
This may require walking through the box-box pair handler to see if you notice anything weird.
Precision is probably not related.
Fancy shapes bouncing around:
Given that boxes and spheres do not seem to bounce, this is probably something specific to these shape types. I can't quite tell from the video, but it may be bounding box related again. If the bounding box does not fully contain the shape, contacts will only be created after there is already a deep penetration. Unfortunately, I suspect it may not be this simple- ConvexHullShape has a unique implementation of GetBoundingBox and it is behaving the same way as the MinkowskiSumShape and TransformableShape.
The one thing all those shapes share is a reliance on MPR/GJK-based contact generation. They use the GeneralConvexContactManifold, which is one of the more complicated collision detection algorithms in the engine. I can't pinpoint the most likely source of the problem; it may require walking through it and looking for anything clearly out of the ordinary (possibly comparing against the working floating point version).
This is one area where precision may be a problem. MPR and GJK both rely heavily on thresholds, and it's conceivable that they would not play well with things getting clamped or zeroed out.
There are some other cases like log(0), pow(0,0), acos/asin out of range, just about anything with NaN as a parameter, 0 * infinity, and so on that could return NaN. I'm not sure off the top of my head which ones IEEE754 and C# require.This mostly happens when boxes are stacked on top of each other. I think it's due to my fixed math not catching all the possible IsNaN and IsInfinity. I have Sqrt(<0), division by zero, infinity * infinity covered.. I can't think of any other way that would cause IsNaN or IsInfinity, do you know by any chance what causes those?
But I wouldn't expect the lack of catching such error conditions to be the cause of general case behavior problems. The engine goes out of its way to avoid generating invalid values. If the conditions arise where such values could show up, something already went wrong.
Instead, if this happens with box-box collision specifically, it may be a hint about the nature of the box-box bug above. Trace how that bad normal is getting generated.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Unfortunately, it seems that I will need to change my fixed math struct...
The main issue right now is performance.. compare to float, my struct is 20+x slower. I assumed that it was due to the huge amount of casting back and forth during run time, but it turns out that doing 100,000 casts between types takes only about 3000 ticks.
It appears that just dividing long is much faster rather than dividing by bit shifting , I am not sure if it is because of my CPU, but the difference is significant.
Long is about 3 times slower than float on my PC it, but int is almost same speed as float. So.... I am thinking to use long without any struct and just scale everything say by 1e9?? DOES THAT SOUND CRAZY TO YOU lol?... I don't see why it will not work... For functions such as sin, cos, tan etc I will use a lookup table and write special functions.
Can you think of any reason why it won't work out other than doing the tedious task of scaling every number?
EDIT:
Actually, scratch that idea. I found a Fixed math library that written for embedded devices without FPU. It's written in C, I ported one of the 64bit class to C# and it looks actually promising . It only about 3.5x slower than floating, which is pretty fast. There is a even faster version which I am going to port as well and try to increase it's precision.
The main issue right now is performance.. compare to float, my struct is 20+x slower. I assumed that it was due to the huge amount of casting back and forth during run time, but it turns out that doing 100,000 casts between types takes only about 3000 ticks.
It appears that just dividing long is much faster rather than dividing by bit shifting , I am not sure if it is because of my CPU, but the difference is significant.
Long is about 3 times slower than float on my PC it, but int is almost same speed as float. So.... I am thinking to use long without any struct and just scale everything say by 1e9?? DOES THAT SOUND CRAZY TO YOU lol?... I don't see why it will not work... For functions such as sin, cos, tan etc I will use a lookup table and write special functions.
Can you think of any reason why it won't work out other than doing the tedious task of scaling every number?
EDIT:
Actually, scratch that idea. I found a Fixed math library that written for embedded devices without FPU. It's written in C, I ported one of the 64bit class to C# and it looks actually promising . It only about 3.5x slower than floating, which is pretty fast. There is a even faster version which I am going to port as well and try to increase it's precision.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Make sure the application is being compiled for 64 bit (if the platforms support it); targeting 32 bit will introduce a lot of unnecessary work for a 64 bit cpu.Long is about 3 times slower than float on my PC it, but int is almost same speed as float.
That would technically work, yesSo.... I am thinking to use long without any struct and just scale everything say by 1e9?? DOES THAT SOUND CRAZY TO YOU lol?... I don't see why it will not work... For functions such as sin, cos, tan etc I will use a lookup table and write special functions.
![Razz :P](./images/smilies/icon_razz.gif)
Avoiding that with the other library would be nice, though.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Well... after a long journey I finally did it.
This was a lot harder than I thought. Turning a physics engine to use a fixed math library was pretty easy, but having the physics to run close to non-fixed math speed WAS THE HARDEST part. It turns out, using struct and operator overloading is very expensive for math calculations. A simple statement like a.M11 * b.M11 + a.M12 * b.M21 + a.M13 * b.M31 when using a operator overloading has too many method calls which makes it 15 times slower than floating point!
The only way I figured to match hardware floating speed is to inline the calculation. Here is a prime example:
A easy statement like this:
had to be converted to this in order to match floating point speed:
This was the only way to match floating point speed. So I end up inclining about 70% of the physic's calculations, especially performance case sensitive areas. As a result, I finally got the fixed math version to perform same speed as floating point and I am pretty happy about it.
Sure enough everything is deterministic between my android and PC. All the simulation that were not deterministic before are completely deterministic. As far as I know I don't think there is any physics engine that is deterministic across all platform, so this is a big accomplishment especially since it performs very close to the original floating point speed.
Buttt unfortunately... this only holds true for 64 bit CPUs. Since I am using long for all the calculations, a 32 bit CPU doesn't work well with Int64 calculations.
Here is a rough benchmark so far: On a 64 bit CPU(and 64bit release), fixed math is only about 5% slower than floating point. On 32bit CPU, it's about 2.5 times slower than floating point.
Since I am targeting mobiles phones, unity only compiles 32bit for mobiles. In order to match the floating point speed on 32bit builds, I would have to use int instead of long. However, that's not really possible because of precision problems and overflows. So only way I can think of improving speed is to use int in areas where I know for sure that there wont any be large numbers to calculate since it will cause overflow.
For example, I believe Quaternion and Matrix3x3 won't store numbers above 360(if there is no invalid calculation) so with that, I can patch the calculation there to use int instead of long to get some speed boost. This is where I will need your help, do you know any areas of calculation where the numbers are always between certain range?
Another thing I am hoping you can help me with is to ensure I did not mess up any calculations. Unfortunately, in the process of inclining the math, I have introduced few bugs here and there. I was wondering if you have any Test unit or something that you used to ensure the math calculations are right. So far, I have tested it against the demos, but that relies on visually seeing if the physics is correct or not. Using breakpoints is hard too since the physics jumps all over the place with hard to track abstract calls.
Thanks for reading this and your help in advance.
This was a lot harder than I thought. Turning a physics engine to use a fixed math library was pretty easy, but having the physics to run close to non-fixed math speed WAS THE HARDEST part. It turns out, using struct and operator overloading is very expensive for math calculations. A simple statement like a.M11 * b.M11 + a.M12 * b.M21 + a.M13 * b.M31 when using a operator overloading has too many method calls which makes it 15 times slower than floating point!
The only way I figured to match hardware floating speed is to inline the calculation. Here is a prime example:
A easy statement like this:
Code: Select all
float resultM11 = a.M11 * b.M11 + a.M12 * b.M21 + a.M13 * b.M31;
float resultM12 = a.M11 * b.M12 + a.M12 * b.M22 + a.M13 * b.M32;
float resultM13 = a.M11 * b.M13 + a.M12 * b.M23 + a.M13 * b.M33;
float resultM21 = a.M21 * b.M11 + a.M22 * b.M21 + a.M23 * b.M31;
float resultM22 = a.M21 * b.M12 + a.M22 * b.M22 + a.M23 * b.M32;
float resultM23 = a.M21 * b.M13 + a.M22 * b.M23 + a.M23 * b.M33;
float resultM31 = a.M31 * b.M11 + a.M32 * b.M21 + a.M33 * b.M31;
float resultM32 = a.M31 * b.M12 + a.M32 * b.M22 + a.M33 * b.M32;
float resultM33 = a.M31 * b.M13 + a.M32 * b.M23 + a.M33 * b.M33;
Code: Select all
Matrix3x3 tmp;
tmp.M11.rawVal = ((a.M11.rawVal * b.M11.rawVal) >> Fast64.Q) + ((a.M12.rawVal * b.M21.rawVal) >> Fast64.Q) + ((a.M13.rawVal * b.M31.rawVal) >> Fast64.Q);
tmp.M12.rawVal = ((a.M11.rawVal * b.M12.rawVal) >> Fast64.Q) + ((a.M12.rawVal * b.M22.rawVal) >> Fast64.Q) + ((a.M13.rawVal * b.M32.rawVal) >> Fast64.Q);
tmp.M13.rawVal = ((a.M11.rawVal * b.M13.rawVal) >> Fast64.Q) + ((a.M12.rawVal * b.M23.rawVal) >> Fast64.Q) + ((a.M13.rawVal * b.M33.rawVal) >> Fast64.Q);
tmp.M21.rawVal = ((a.M21.rawVal * b.M11.rawVal) >> Fast64.Q) + ((a.M22.rawVal * b.M21.rawVal) >> Fast64.Q) + ((a.M23.rawVal * b.M31.rawVal) >> Fast64.Q);
tmp.M22.rawVal = ((a.M21.rawVal * b.M12.rawVal) >> Fast64.Q) + ((a.M22.rawVal * b.M22.rawVal) >> Fast64.Q) + ((a.M23.rawVal * b.M32.rawVal) >> Fast64.Q);
tmp.M23.rawVal = ((a.M21.rawVal * b.M13.rawVal) >> Fast64.Q) + ((a.M22.rawVal * b.M23.rawVal) >> Fast64.Q) + ((a.M23.rawVal * b.M33.rawVal) >> Fast64.Q);
tmp.M31.rawVal = ((a.M31.rawVal * b.M11.rawVal) >> Fast64.Q) + ((a.M32.rawVal * b.M21.rawVal) >> Fast64.Q) + ((a.M33.rawVal * b.M31.rawVal) >> Fast64.Q);
tmp.M32.rawVal = ((a.M31.rawVal * b.M12.rawVal) >> Fast64.Q) + ((a.M32.rawVal * b.M22.rawVal) >> Fast64.Q) + ((a.M33.rawVal * b.M32.rawVal) >> Fast64.Q);
tmp.M33.rawVal = ((a.M31.rawVal * b.M13.rawVal) >> Fast64.Q) + ((a.M32.rawVal * b.M23.rawVal) >> Fast64.Q) + ((a.M33.rawVal * b.M33.rawVal) >> Fast64.Q);
Sure enough everything is deterministic between my android and PC. All the simulation that were not deterministic before are completely deterministic. As far as I know I don't think there is any physics engine that is deterministic across all platform, so this is a big accomplishment especially since it performs very close to the original floating point speed.
Buttt unfortunately... this only holds true for 64 bit CPUs. Since I am using long for all the calculations, a 32 bit CPU doesn't work well with Int64 calculations.
Here is a rough benchmark so far: On a 64 bit CPU(and 64bit release), fixed math is only about 5% slower than floating point. On 32bit CPU, it's about 2.5 times slower than floating point.
Since I am targeting mobiles phones, unity only compiles 32bit for mobiles. In order to match the floating point speed on 32bit builds, I would have to use int instead of long. However, that's not really possible because of precision problems and overflows. So only way I can think of improving speed is to use int in areas where I know for sure that there wont any be large numbers to calculate since it will cause overflow.
For example, I believe Quaternion and Matrix3x3 won't store numbers above 360(if there is no invalid calculation) so with that, I can patch the calculation there to use int instead of long to get some speed boost. This is where I will need your help, do you know any areas of calculation where the numbers are always between certain range?
Another thing I am hoping you can help me with is to ensure I did not mess up any calculations. Unfortunately, in the process of inclining the math, I have introduced few bugs here and there. I was wondering if you have any Test unit or something that you used to ensure the math calculations are right. So far, I have tested it against the demos, but that relies on visually seeing if the physics is correct or not. Using breakpoints is hard too since the physics jumps all over the place with hard to track abstract calls.
Thanks for reading this and your help in advance.
Last edited by test44x on Wed Apr 15, 2015 3:12 pm, edited 1 time in total.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Well done!Sure enough everything is deterministic between my android and PC. All the simulation that were not deterministic before are completely deterministic. As far as I know I don't think there is any physics engine that is deterministic across all platform, so this is a big accomplishment especially since it preforms very close to the original floating point speed.
While it's a little bit late for this now, you may be able to avoid some of the pain with [MethodImpl(MethodImplOptions.AggressiveInlining)] on the relevant functions if your targets support it. Unfortunately, I've noticed it producing worse assembly than manual inlining in some cases.It turns out, using struct and operator overloading is very expensive for math calculations. A simple statement like a.M11 * b.M11 + a.M12 * b.M21 + a.M13 * b.M31 when using a operator overloading has too many method calls which makes it 15 times slower than floating point
The primary range limited functions tend to be in:For example, I believe Quaternion and Matrix3x3 won't store numbers above 360(if there is no invalid calculation) so with that, I can patch the calculation there to use int instead of long to get some speed boost. This is where I will need your help, do you know any areas of calculation where the numbers are always between certain range?
1) Quaternions,
2) Areas involving trigonometry,
3) Rotation/orthonormal matrices (Both Matrix3x3 and Matrix)
But unfortunately, even these areas do not spend much time range limited, so there isn't a huge amount of optimization potential. Even the Quaternion will end up having to do full precision math when transforming positions, for example. Off the top of my head, I can't remember any notable chunks (using the above or otherwise) that spend a lot of cycles range limited.
There probably should be some low level tests like that, but I don't have any. The BEPUphysicsDemos.Demos.Extras.Tests contains a few specialized demos to test chunks of the engine which may help narrow down bugs, though they often require familiarity with the system in question to judge. Stuff like BooleanConvexTestDemo, MPRCastingDemo, MPRTestDemo, BoxBoxTestDemo, JointLimitTestDemo and so on.Another thing I am hoping you can help me with is to ensure I did not mess up any calculations. Unfortunately, in the process of inclining the math, I have introduced few bugs here and there. I was wondering if you have any Test unit or something that you used to ensure the math calculations are right. So far, I have tested it against the demos, but that relies on visually seeing if the physics is correct or not. Using breakpoints is hard too since the physics jumps all over the place with hard to track abstract calls.
Re: Deterministic Lock-step in Unity3D(iOS/Android)
Can you please contribute your code ? Having a BEPU fork with Fixed Point Math would be a massive help.