November 15, 2009

Deterministic Physics

Filed under: Physics applet project — zet @ 20:11

ds-001-physicsshotSo using Box2D in connection with OpenGL showed me that the drawing performance is greatly improved and the CPU has quite a few resources left for doing the physics simulations of JBox2D. However the most important feature for me was the deterministic behavior. I wouldn’t take a nondeterministic engine. But determinism was not among the features that were described. But well, determinism is not such an “important” feature compared with others.

And honestly, it’s a pretty useless feature unless you know exactly what you want and what you need. Anyway, when doing research on the matter, I found a rather interesting forum post. Before I ran into that I was not so sure if it was really possible – if the floating points units of different PCs are really capable of doing deterministic calculations. Most people say no, but that sounded always a bit strange to me after thinking about reproduce able simulation results for scientific calculations, something that is an important constraint when doing research. And this could only be reached through having a floating point unit that is reliable accross different architectures. And as the poster on the box2d forum points out, there’s a standard and it’s working for other games that rely on determinism as well: IEEE754. The next step was to figure out if the Java VM is following this standard. At first I was shocked reading that IEEE754 got dropped with Java 1.2 for performance reasons, but reading on I learned that Sun introduced a new keyword instead: strictfp. Any class or method that is having this keyword is supposed to follow IEEE754. Phew.

Armed with that knowledge, I knew I had to make a test how reliable the data structures of the Box2D Java port are. This means that, given the same order of instructions, the data structures that are being created by the library are deterministic – if object A is compared with object B, it is supposed to be always handled in this order – never comparing B with A instead or anything else. This is extremely important, otherwise the determinism fails. I also already knew that the Box2D demos are running exactly the same way if restarted, but that doesn’t mean that the results would be the same if I would clear all objects in a world and reinserted them in the same order again. There could be still a difference due to memory allocation addresses or different hashes.

So I tested. And luckily, I found out that JBox2D is in deed deterministic. After that I started adding “strictfp” to every class and also “serializeable” since I would need to be able to save and restore certain configurations. I also implemented a small function that calculates a hash for the world’s state only based on the position of all bodies and their rotation. Neglecting the speed and other parameters is actually not so important here. It could improve the reliability of the hashes in means of uniqueness if these information would be included, however speed is more important here. And moreover, if there’s a subtle difference and the simulation goes on, the hash of the next step will be different, that’s pretty sure. And if not … well, another step will follow which will have a different hash then but the likeliness for having a different state that is followed by another state, both having equal hashes as the reference simulation is really pretty low. Physics simulations are usually extremely fragile and even a single bit that is different can cause a totally different outcome of the simulation. Sounds like chaos theory to you? Well, a weather simulation algorithm was actually the cause for Edward Lorenz to come up with the chaos theory.

Anyway, so I have now hashes of the simulation – and I use it to check if my simulation is still as I would expect it to be. This is a quite cheap test, so for a network transmission, the server is supposed to send the current stepcounter of the simulation and the hash and the clients can then figure out if they are in sync with the server. I stole that idea from eemerson, the guy who posted on the Box2D forum.

After I inserted all required serialize codes into the JBox2D engine, I could serialize the state and reload it and in deed, the hashes matched my previous runs! So JBox2D runs pretty much deterministic out of the box, the only missing thing is the strictfp keyword in front of the classes.

The next step requires a bit more creativity – I need to make all actions in this physics environment recordable. That’ll be tricky.

No related posts.

No Comments »

No comments yet.

RSS feed for comments on this post. TrackBack URL

Leave a comment

Copyright Eike Decker 2009