Box2D Forums

It is currently Sat Apr 19, 2014 10:50 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2, 3  Next
Author Message
PostPosted: Tue Nov 18, 2008 3:37 pm 
Offline

Joined: Tue Nov 18, 2008 1:28 pm
Posts: 10
I've seen a lot of discussion in various threads about the why and possible 'heres how I might try to do it', but nothing stating specific changes that could be made. The program I'm developing runs a simulation in 8 second intervals and the cost to the users system that might be associated with guaranteeing values is worth the hit for what I'm doing. In order to reduce the insane strain on a server that would be caused by running large numbers of Box2D worlds, I would basically calculate a CRC for each user of each world. If/when this were to fall out of sync (due to attempts at altering data for example) the server would step in and evaluate the previous 8 seconds, otherwise it would simply fetch the data from one of the users. Also important for storing entire replays of the simulation.

Long story short, has anyone actually gone ahead and found a way to at least increase if not completely stabilize box2D and its non-deterministic nature. If so, how? Any suggestions are appreciated.


Top
 Profile  
 
PostPosted: Tue Nov 18, 2008 9:08 pm 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
The problem has nothing to do with Box2d, it is a fundamental limitation of the way floating point math is specified - there's no guarantee of determinism in the spec, so different systems are allowed to make different rounding assumptions. There's just about nothing we could do to the floating point engine to make this better.

If you use the fixed point version of the engine you'll probably have an easier time getting consistency since integer math carries more guarantees.


Top
 Profile  
 
PostPosted: Tue Nov 18, 2008 9:38 pm 
Offline

Joined: Tue Nov 18, 2008 1:28 pm
Posts: 10
I guess after all the reading I've done in the past few hours I'm not expecting it to be perfect but I would like to increase the stability. Fixed point is one thing I'll look into testing, is there anything else?

The problem I see is right that already at this point I'm falling out of sync fairly quickly running two copies on the same system. I fear that as things are right now there will be no way to maintain any reasonable degree of tolerance for the required time (currently only need 8 seconds at a time) when its on various systems.

Just to clarify, two instances of the application run, and send data to a server at the end of every 8 second interval. Each instance of the application has objects defined in the same order and no new objects are added after the initial start. Is there any reasonable measure of how much worse this will get on other systems because as is, its just barely acceptable locally.

Thanks for taking the time to reply.


Top
 Profile  
 
PostPosted: Wed Nov 19, 2008 2:46 am 
Offline

Joined: Wed Sep 10, 2008 8:03 am
Posts: 138
Are you using dynamic or static time steps? I kinda would expect the same result each time with the same starting conditions and the same CPU.


Top
 Profile  
 
PostPosted: Wed Nov 19, 2008 3:10 am 
Offline

Joined: Sun Sep 23, 2007 2:35 pm
Posts: 803
I agree with Daid, I've always seen runs on the same system go exactly the same way (the testbed demonstrates this nicely).

By going out of sync within 8 seconds, do you mean that over 480 frames the results or different, or that it's taking different amounts of time to calculate the 480 frames in two separate processes? That would be another problem altogether, which has little to do with Box2d.


Top
 Profile  
 
PostPosted: Wed Nov 19, 2008 11:41 am 
Offline

Joined: Tue Nov 18, 2008 1:28 pm
Posts: 10
Fixed timestep, I have it set as #define TIMESTEP 0.016666668f at the moment working out to roughly 60 frames per second. Not worried about it running slower than that, and I skip draw calls when it needs to catch up anyway.

Tested it on my laptop (Core 2 Duo T8300 [2.4GHz]) and ran another instance on a P4 3.0GHz, with the same commands sent from the server. When the commands are executed (various forces applied to the scene) the results are sent back to the server and compared. Within 480 frames (just to be clear) at the fixed time step and things are off by more than 1.0f for positions which is fairly significant for what I'm doing. On the same machine this was less though the commands I was issuing were different so it may be a coincidence.


If I build the fixed point version of box2d, how would I need to alter my code thats used in the implementation currently? I haven't been able to find much info about that on the forums right now. Also, using visual studio to build, enabling the fixed point version causes a warning treated as error conversion from '__int64' to 'int'. Any ideas about that?

Thanks again for taking the time to reply guys.


Top
 Profile  
 
PostPosted: Tue Nov 25, 2008 10:55 am 
Offline

Joined: Tue Nov 04, 2008 3:05 am
Posts: 60
Quote:
...with the same commands sent from the server.


How are you guaranteeing that you're executing these commands on the same frame on each machine?


Top
 Profile  
 
PostPosted: Tue Nov 25, 2008 11:40 am 
Offline

Joined: Tue Nov 18, 2008 1:28 pm
Posts: 10
Each command is given a frame at which it is meant to execute. Since I have a fixed time step for box2D and I only skip draw calls, never logic calls it should always be the same. Worst case scenario the simulation should slow down visually but still run the same.
As for fixed step, I just learned I would need to go back to version 1.6 in order to know it is a tested version but I'm assuming that would come at the cost of some stability in other areas.


Top
 Profile  
 
PostPosted: Tue Jun 23, 2009 12:43 am 
Offline

Joined: Mon Jun 22, 2009 11:27 pm
Posts: 4
I'd like to chime in on this topic.

I just started looking at Box2D to play with at home and one of the first questions i have about it.. is it deterministic?

I work at Gas Powered Games and i can tell you first hand that floating point math is deterministic. You just need the same instruction set and compiler and of course the user's processor adhears to the IEEE754 standard, which includes all of our PC and 360 customers. The engine that runs DemiGod, Supreme Commander 1 and 2 rely upon the IEEE754 standard. Not to mention probably all other RTS peer to peer games in the market. As soon as you have a peer to peer network game where each client broadcasts what command they are doing on what 'tick' number and rely on the client computer to figure out the simulation/physical details your going to rely on the determinism of the floating point processor.

Heres a quick break down of what we do..

Our time step is fixed at 0.1f second, we use this timestep for all our math on the simulation thread. Each client simulates their own world/physics/steering/pathing etc etc. and theres TONS of float based math going on. Hash all position/rotations and CRC check them across clients and if the CRC check fails we pause the game with a big flashing DESYNC error.

When the CRC check fails we know that on Tick x client y had a 'desync'. As devs we turn on desync logging to try and hunt down why a single unit (out of a thousand units) would have a single pos bit off from another machine. Usually it's because theres a uninitialized variable ( which would result in random memory on each machine ). Or because something isn't done in the right order or tick.

In DemiGod the smaller grunts use full steering (ie repulse/attract accumulation to determine facing direction and movement like you see with steering boids) All of that craziness, completely deterministic.

The Ageia PhysX guys came in and showed us their technology and hardware, wanted us to use it in Supreme Commander to do its physics but we couldn't do it.. and thats because their software is not deterministic. You have to actually go through the code and actively care about determinism.

In short, we had to implement our own (more basic) physics code to ensure we had determinism.

Getting to the point of all this. We should not blame the floating point processor for not having this feature. The IEEE standard is a standard that our shipped games rely on for our games to stay in sync across PCs over the Internet for both PC and 360 hardware. For a game like supreme commander its nice to have the clients do all the work and yet still be in sync across different machine speeds.. have you seen Supreme Commander? its insane. And because we made our code base deterministic we have replays you can load/save etc.

I'm driving this point home for encouragement. I would love to see Box2D be completely deterministic, as there really isn't a good 2D physics solution or 3D solution out there that I know of that has the deterministic love poured into it.

Imagine Box2D with gameplay mechanics like Braid or speed up, slow down like in the Matrix and have the simulation completely in sync across all machines. that would freakin rock!

Ok so whats the solution? Well for starters we have to stop pointing the finger at the floating point processor and start pointing it at our lack of ninja strength. Then suck down some moutain dew, wrap a black t-shirt around our face ( leave a slit for the eyes ) then, while staring hard at the flat light, slam those plastic squares!


You'll want to build some way of recording sync data... we use a sync file log for each TICK containing the end CRC (of all positions/orientations etc) as well as all kinds of positional / ordering logging information. I use macros throughout our codebase, like this:

gpDesyncLog("gpnav: tick[%d] got pos[%f,%f,%f]", tick, pos.x,pos.y,pos.z");

When desync logging #define is enabled, that macro will printf spew that text to a log file (one per tick)... the files build up over time and when a desync is detected ( by CRCs not matching across machines ) we pause the game, run a diff tool on the log directory of all the tick log files and retrace where the desync happened and fix it.

Once you fix all the desyncs, your physics will work great over the network where each client is doing all of its own work and everything is in sync perfectly across ticks.

Its work.. and that's why you gotta get ninja on it. But I believe its worth it. It would kick serious rear if Box2D had this feature.

Unless theres a random function called or if you cant make the order of operations deterministic, or unless theres something im missing entirely, i don't see why Box2D couldn't become deterministic given some serious ninja action. Much like how continuous physics was added, someone just needs to kick serious a**, thats all there is to it.

I wish good physics libraries had this feature.. I believe in the future they will have it.

Anyway theres my 4 cents.. if its in your heart and its strong for this feature.. you gotta go after it!

- Elijah


Top
 Profile  
 
PostPosted: Tue Jun 23, 2009 1:08 am 
Offline

Joined: Mon Jun 22, 2009 11:27 pm
Posts: 4
desync related things that we deal with to keep things deterministic

1 ensure everything works off of a fixed time step

2 never use uninitalized memory

3 collections can sometimes be in a different order on different machines in this case, sort the collection

4 computations that are spread across ticks must start and finish on the same predetermined tick number even if it means waiting a while for client x. We must have it done on that tick.

theres probably lots more.. but these 4 come to mind

ok off to bed, i hope i've helped stirr up some hope and excitement for this feature.

Networked, record able, physics based Braid anyone?


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 22 posts ]  Go to page 1, 2, 3  Next

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: Exabot [Bot] and 2 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Powered by phpBB® Forum Software © phpBB Group