Deterministic physics engine?

[xananax]

I am looking at Phaser, but not sure what to go with yet; As I say in the title, I'm looking for a deterministic physics engine, and I find it difficult to obtain information on that subject.

In other terms, the same rigid body with the same parameters, subject to the same conditions, should always react in the exact same way. It seems to me that most physics engine are not concerned with guaranteeing that, which makes sense in most cases, but not in mine.

I am not overly concerned with performance, as long as the simulation is accurate and predictable. Any suggestion?

[permith]

You can make your game tick faster.    The faster your game tick is the smaller the jumps are when stuff is moving(for the same apparent speed to a human).

Minimize multiplications/divisions/trig and other things that rely on floating point math. 

You can minimize things that are actually moving around.

Have speed caps.

Have systems that ensure everything is always processed in the same order(IE: SIM always loads things in the same order, and processes them in the same order).

Avoid random numbers

Minimize the time that the simulation runs.   Or tricks that bring you close to this(IE brief empty areas in a platformer)

when you're using floating point numbers minimize the number of digits on the left side of the decimal(since you'll decrease the number of digits on the right side).

____________

These aren't phaser specific, but the whole goal of the above is to minimize the speed of objects at the simulation level and hopefully make them to only be moving less than couple pixels for each actual game tick.   You can do some pretty accurate things without going very deep down the rabbit hole.   Most game physics rely more on "it's not important", "the player won't notice", "high performance", and "humans can't see that many significant digits".  It shouldn't be difficult to get something very reliable up and running(it's just that when you say utmost/perfect accuracy that stuff breaks apart).

Since you don't care about performance you can very easily pump your game tick up to something like 1000 FPS, sure graphically it'll only run at a couple FPS but it's an easy/lazy way to achieve at least some of your goal. 

[JazzAceman]

I think most of the engines are "deterministic". I think the problem is the timing: Using a time based stepping instead of a frame based stepping leads to many "random" effects mostly because the floating point inaccuracy, or because of fluctuating frame rates, which can cause (perhaps invisible) "jump" effects, and therefore collision errors. When I've implemented my physics system I've decided to implement it frame based instead of  time based: This way you will have much less (if any) floating point errors, and a fluctuating frame rate doesn't cause any collision errors. The downside is, that slowing down the frame rate will also slowing down the movement of your objects. You can handle this error by implementing a physics loop which operates independently of the main game loop (setTimeout()), so that a frame rate slowdown doesn't affect your physics calculations. You can also set this timeout to a lower value than 60fps, so your physics calculations will consume less cpu time, so that the movement will be more regular (less variations). There is no optimal solution, but for most of the games, this will work.

[AhmedElyamani]

I'd strongly recommend you program your simulation in c++. When physics engines are made in javascript they usually rely heavily on many approximations rather than absolute calculations (because the browser has too little RAM).

[xananax]

Thanks everyone for the suggestions. I will mull this over.

I think my best option is to go with JazzAceman's solution, if he is correct that the delta time is the culprit. Permith's solution might also work, but in involves a degree of control over all objects that I'm not sure I am comfortable with. I might hit a bug and have no idea why. Also, cranking up the timestep that much is not really an option; I'm not overly concerned by performance, as I won't have a lot of bodies, but I still want things to run sorta smooth.

As for programming in c++, it's impossible, I insist on being able to run my game in browser.

 

[Antriel]

Most of what permith said makes sense, but I don't see how timestep has anything to do with it.
C++ simulation also doesn't make sense much, unless the physics library you use in js actually does any approximations.

As far as my experience goes, physics engines are deterministic. Any randomness comes from testing on different CPU which can solve floating point operation slightly differently.
Unless the engine purposefully adds some randomness factor, if you execute the code exactly the same, the result should be exactly the same, on the same CPU.

[JazzAceman]

2 hours ago, Antriel said:

Most of what permith said makes sense, but I don't see how timestep has anything to do with it.

The errors caused by the differences in CPU floating point calculations are insignificant, compared with the errors caused by variable time steppings:

The delta time of your game loop is irregular (especially in JS), so your calculations will cause different interim results, and so different end results every time, because of additional floating point errors. Also especially in JS, and even more on mobile devices, it can happen that your browser skips multiple frames, and so your delta time jumps up from your >average< 16,666667 ms to, for example, 166,6666667 ms. So your object's velocity will be 10 times higher than normal. If a bullet is moving 10 times faster than expected, it can easily overleap small colliders, or a bouncing ball can (depending on implementation) suddenly bounce right into space. Sometimes the  effects are even worse. You can prevent your objects from moving too fast by capping the velocity, or even the delta time, but if you do that: Each end result will be totally different, which would be not very "deterministic". :-)

By the way, this is also the reason why many multiplayer shooters have a fixed frame rate.

There are multiple solutions to avoid this problem, and I don't say that my solution is the "best" of them, but using a frame based, instead of a time based physics system, is perhaps the easiest solution to implement. 

Here is an interesting article about the timestep problem:

http://gafferongames.com/game-physics/fix-your-timestep/

 

 

[Antriel]

Right, well I thought it was given that the physics need fixed time step

I don't agree that errors differences in floating point calculations are insignificant though. All it takes is the calculation landing on edge case and the rounding error can make all the difference -> chaos theory.
And just so I am not saying it without any proof:

That's fixed time step difference between running on the same PC in Flash Player vs HTML5 in Chrome

[JazzAceman]

3 hours ago, Antriel said:

That's fixed time step difference between running on the same PC in Flash Player vs HTML5 in Chrome

Yeah, but I didn't say that floating point calculation differences are insignificant per se (quite the opposite), I've said that calculation differences between different CPUs are insignificant compared with timing caused errors. And by the way, to compare HTML5 and Flash simulations doesn't proof CPU-inaccuracy, but  it proofs differences between the Adobe Flash and the JavaScript implementation in Google Chrome, especially if they are tested on the same PC. The differences in the simulation could be caused by different data type implementations (more or less precision for example) or one of the many other aspects in the different platform implementations. If you want to proof that different CPU's will result in different simulations, because of different floating point implementations, you have to write your Physics Engine in C++ and run it on different CPU's. 

[permith]

A fixed time step can be really really important. 

		Acceleration				
		50 pix per sec				
						
		5 MS step			15 MS step	
Step		Speed	Position		speed	position
1		0	0			0	0
2		0.25	0.25			
3		0.5	0.75			
4		0.75	1.5			0.75	0.75
5		1	2.5			
6		1.25	3.75			
7		1.5	5.25			1.5	2.25
8		1.75	7			
9		2	9			
10		2.25	11.25			2.25	4.5
11		2.5	13.75			
12		2.75	16.5			
13		3	19.5			3	7.5
14		3.25	22.75			
15		3.5	26.25			
16		3.75	30			3.75	11.25
17		4	34			
18		4.25	38.25			
19		4.5	42.75			4.5	15.75

Speed = Acceleration Rate * (Step rate/1000) + previous speed
Position = last position + speed

This is the simplest possible physics demo, taking one of the the simplest problem(s) of acceleration, and chosen as pretty much the "worse case"/"most obnoxious" scenario.   Even a more complex engine that properly integrates and derives out, the physics engine will start to run into problems with different step times when you start to see things collide with each other(IE in the 15MS something would happen at step 10 instead of step 8 and compound out from there).

Basically if you were to have a variable tick rate, everything might as well be semi-random instead of determined.   If you don't have a fixed tick rate you can't even count on your game running the same on every computer, since with a variable tick rate will probably be determined by the system.

_____________

Really it comes down to taking the assumptions that you "need", and adjusting your other requirements to suit the engine.    IE:  in the 15MS example to get the same final speed you're going to choose a higher acceleration rate to account for the missed steps.    To account for inaccuracies in not having a .001MS step time you're going to have some logic to get get objects out of the inside of each other, choose some max speeds, and take actions to minimize/account for objects with race conditions(IE: 3 objects inside of each other)(which should be handled by the engine itself).

_____________

There are in the end A LOT of things you can do if you want to race down the rabbit hole.   But to get there you're going to need to go deeper down it than most people ever need to to make something fun.    Especially when the same thing can be achieved with a little bit of understanding, kludging numbers, and focusing on a few actual requirements.  

Even the most popular games like candy crush or solitaire don't care if they give a winnable game at the start of the game.   And people still return to those.

[xananax]

13 hours ago, permith said:

Even the most popular games like candy crush or solitaire don't care if they give a winnable game at the start of the game.   And people still return to those.

Thank you for this, it made me review my requirements and get a more down-to-earth view of what I need.