Rounding simulation

Topics: Developer Forum, User Forum
Mar 29, 2012 at 8:56 PM

Hey guys,

I'm building a realtime multiplayer game using farseer for physics with client side prediction. My goal is to avoid sending state as much as possible, sending only input data when possible. My idea is to make farseer a little bit more deterministic by rounding all values to 2 decimals. My thought for this is that it avoids the problem of small differences slowly growing bigger.

Do you think this is a good idea? I'm not sure where I should implement this yet, I was thinking the simplest solution is to just set Position and Rotation on all objects to their rounded off values. I'm still struggling a bit with joints, they don't seem to enjoy forcefully setting Position very much. Any input on this would also be greatly appreciated. I know it's not what farseer is built for, but I really like farseer and there really is no opensource .net physics engine as mature as this that _does_ carry networked physics in mind.

Please note that I am fully prepared to make changes in farseer's deepest innards, I have already read through most of its codebase.

(I have already read this thread and I think this is sort of a continuation on it http://farseerphysics.codeplex.com/discussions/346714?ProjectName=farseerphysics)

Apr 1, 2012 at 12:03 PM

Hi,

I don't think rounding will give you much. You would be just introducing an error now instead of potentially having an error over time. Also floating point math is just one part of the problem. The other is the solver itself - it loops over all objects and is iterative. This means that the order in which the objects are added to the containers and the order in which the solver processes the islands and collision pairs is very important. On different machines the order might (will) be different and produce different results.

To say it in another way the solver does not find an exact solution to the equations of motion within the system. Even further an exact solution might not be even possible to find. It does find an approximate solution, possibly one of many, that is good enough (relatively stable - the more it iterates over during a small time step the more stable). 

There are several posts on the Box2D forums (also on the Bullet forums) that deal with a "replay" feature in games which needs determinism and where these problems are discussed. AFAIR the only correct solution is to record a movie of the game to replay afterwards...

All in all depending on how accurate you want your worlds to behave you would have to synchronize them at some point which is not really so bad if the rest of your simulation is more or less well predicted.

Apr 1, 2012 at 2:07 PM
Edited Apr 1, 2012 at 2:42 PM

Hey Jerrysb,

Thanks alot for your answer! I will look for posts about replays on the box2d forums.

I don't understand what you mean by introducing an error now. When I perform the rounding on both sides wouldn't the results be closer together because they drop some precision which has uncertainty? i.e. only the most certain part of the number remains? Ofcourse it leaves an edgecase where the error is actually increased, but depending on the accuracy of the calculation this chance should be quite small. In my mind it should even be able to compensate the iterative solvers problem as long as the solvers are only slightly different.

My needs are not as precise as a replay would be, I just want the predictions to hold for a second or two, drastically reducing the amount of state having to be communicated.

http://www.box2d.org/forum/viewtopic.php?f=3&t=4614 is encouraging, with only bodies he only has an error of 5 * e-8 after 1000 steps. Granted that is Java and I don't know if Java enforces stricter floating point. But if the errors are always that small cutting to e-2 precision will maybe fix this.

Apr 1, 2012 at 8:37 PM

Hi,

I can give a simple example :

Consider dividing 1 by 20.

Case 1: you use a float (1/20=0.05f).

Case 2: you decide to round and keep only one decimal. 1/20=0.05f becomes 0.1f or even 0f depending on the rules for rounding you use. Quite different when you use it afterwards for multiplication to a velocity for example. 

Whatever you do to your floats to alter precision you cannot improve the accuracy which depends on the engine so I can't see it of being much help.

http://en.wikipedia.org/wiki/Accuracy_and_precision

As for the thread linked well obviously simulation disagreement is mostly affected by collisions so depending on the actual scenario if the collisions are not frequent the error won't be much. And the guy still synchronized his worlds with an authoritative server every x seconds which is a good way to go.

Honestly in my opinion the fact that the engine is not deterministic is not such a big issue if appropriate steps are undertaken. It only means it can't (shouldn't) be used for scientific experiments like projecting a bridge or building an airplane.  :)

Apr 7, 2012 at 1:43 AM

I understand your example. I don't need accurate calculation, I need accurate synchronicity.

To use your example:

Case 1: I use a full precision float. For simplicity lets assume 1/20= 0.501 on machine one, 1/20 = 0.504 on machine two. The delta step comes and the machines multiply it by a velocity and a deltatime and 16 * 0.501 = 8.016, and 16 * 0.504= 8.064. The small difference became a factor 10 bigger and every step the machines diverge further.

Case 2: I use a rounded float. 1/20 = 0.501 becomes 0.50, and 1/20 = 0.504 becomes 0.50 too. The next calculation will now only have insignificant divergance which will be cut off by rounding again, 0.80 might not be entirely accurate, but the machines will be much closer to eachother. If the precision is chosen well this might lead to the simulations never diverging, unless there are freaky big floating point inaccuracies.

In my case, the longer the simulations are in sync, the more efficient my network protocol is, the more players can interact with eachother, the more epic the game will be!

Apr 7, 2012 at 11:17 AM

Well I get your point, even though I disagree. For a game developer the problems with diverging calculations due to floating point differences only come in some particular edge cases - like division/miltiplication by 0 when it's not 0 (or in general scaling), some trigonometry (like tg), collisions that don't happen even though bodies are "touching", lines that seem parallel but are not - stuff like that. These edge cases might not be such a big deal really - for example a bullet just grazing a target instead of hitting it is not a big deal. Some tunneling could be ok...

However there is still a problem with the integrator which is iterative and also run in multiples over time and it already has issues since it is just an approximation. See for example http://en.wikipedia.org/wiki/Flying_ice_cube

In our case joints might be the issue rather than bodies. I think by loosing precision you might get your simulations to agree more but you risk them becoming inaccurate and that can have consequences like bodies getting stuck into each other or joints becoming unstable. In other words you might reach situations from which the engine cannot recover and that worries me.

Since you have to synchronize anyway sooner or later (like every 5s maximum) why do all that work for little benefit. If your model is very complex then even on one machine and without networking semi-implicit Euler might already be quite innacurate let alone you tamper with it or "adjust" it with brute force post-time step. If your model is simple - then the integrator is already quite accurate anyways regardless of precision if the latter is within sensible limits. In other words even if you used a perfect integrator (or at least a fourth-order one like RK4) you would gain no benefits losing speed. Consequently the error in floating pont math between machine with different architectures would not influence anything that much.

If, instead, your model is in-between in terms of complexity then you can certainly try out some adjustments but corner cases might rear their ugly heads at the most unfortunate moments.

At the end of the day we should really ask what is that makes it so difficult to synchronize across a network. I would argue that *by far* this is the inconsistencies of roundtrip transmission times that far outweigh anything else in scale. The simple fact that you can lose a whole packet of information (and TCP is just a band-aid) can have a huge impact. Furthermore since we have no control over the Internet you would have to deal with that problem anyways in some manner...

Apr 7, 2012 at 12:03 PM

Hey thanks for the continued feedback, I really appreciate it a lot. The game I'm building is a multiplayer racing game. Two cars touching in one simulation and not touching in another is actually my worst case scenario. I've built quite an elaborate network protocol, so if it does happen it will quickly be detected and corrected. I have also planned some strategies for dealing with lost/late packets and such so I hope to be well prepared for the horrors of the internet :P

Even without lowering precision I'm already having problems with unstable joints, probably because of my calls to SetPosition. My next todo item is building a testbed to find out what the best way of setting the position/rotation of an object with joints is. The wheels of my cars go into a slight oscillation after a few state frames. But I'll leave that for a next thread :)

I will keep your advice in mind and delay the weird optimizations until I'm certain that they would solve the biggest problems, I guess that's the correct way to do it anyway.

Apr 7, 2012 at 12:37 PM
Edited Apr 8, 2012 at 12:11 PM

I don't know if you've already stumbled accross gafferongames but here's a link for a more in-depth discussion (the comments section is very much worth it):

http://gafferongames.com/networking-for-game-programmers/floating-point-determinism/

 

[EDIT] PS: joint instability when manually setting position is almost certainly due to "warm starting" which by definition uses previous values in the initial step iteration to quickly approach the solution.  In our case previous values are invalid or worse harmful since we've teleported. I'm not an expert here as in my simulations I always use forces for movement but I suppose if you read on that on the Box2D forums you might gain significant insight.