Page 1 of 3

How does Spring make Deterministic Physics?

Posted: 07 Feb 2015, 23:36
by jpthek9
Hi, I'm developing an RTS and I'd like to find out how to make simulations deterministic, specifically the physics of it. I noticed that Spring has a really nifty engine so I'd like to learn from it.

Does it use an open source collision detection library like Box2D? How does it deal with floating point imprecisions? Also, is it deterministic in the first place or do units have to be synced? Thanks in advance for the help.

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 00:15
by abma
basicly it uses streflop to make all float operations the same on all computers.

units don't have to be synced only (user-)commands are transfered between the computers.

afaik it doesn't use a collision detection library.

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 01:45
by jpthek9
abma wrote:basicly it uses streflop to make all float operations the same on all computers.

units don't have to be synced only (user-)commands are transfered between the computers.

afaik it doesn't use a collision detection library.
Thanks for the info! I'll look into streflop and see if I can do something with it. Just wondering, how does Spring keep units apart without collision detection?

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 01:47
by abma
jpthek9 wrote:Thanks for the info! I'll look into streflop and see if I can do something with it. Just wondering, how does Spring keep units apart without collision detection?
ah, sorry that was unclear: spring doesn't use an external lib for collision detection it has its own thing implemented. I guess the related files are Collision* here:

https://github.com/spring/spring/tree/d ... s/Sim/Misc

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 02:18
by jpthek9
Thanks a bunch :)

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 09:28
by PicassoCT
There are plans, to one day add bullet for additional unitphysics via opencl.

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 19:19
by jpthek9
Oh, I've heard of bullet. Would you use the same technique (streflop) to make it deterministic?

For my game, I'm making it deterministic by using double math.

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 19:37
by smoth
What is deterministic physics? What is deterministic in an rts game?

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 19:41
by Silentwings
I guess he means synced.

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 19:47
by smoth
Dunno, that is why I asked better to ask and look ignorant, than assume I know

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 20:05
by jpthek9
Determinism is if the same input is replayed, the same result comes out so the command can be sent instead of positions, as abma suggested.

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 20:24
by jK
jpthek9 wrote:For my game, I'm making it deterministic by using double math.
That's not deterministic. It just gives similar results as long as the _math_ is stable.
But math doesn't have to be stable, minimal difference in the input numbers can give totally different output (-> chaos theory).
Spring needs bit-level equalism across all OS & CPUs.
For that we need streflop, which sets FPU-flags & gives sync-able/deterministic versions of many math functions (sin, cos, tan, exp, log, ...) cause the std:: ones don't have to do so (they are coded for speed).

So yes, when we include bullet we have to compile ourself with streflop modifications (same as we do with lua & assimp already).

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 20:34
by jpthek9
Oh, interesting. I think I'll look into using STREFLOP as well. Do you know of any libraries in C#?

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 21:19
by abma

Re: How does Spring make Deterministic Physics?

Posted: 08 Feb 2015, 21:42
by jpthek9
That's alright. I did more research into doubles and conducted some tests. For my uses, it's accurate enough.

Re: How does Spring make Deterministic Physics?

Posted: 09 Feb 2015, 09:09
by PicassoCT
I do not understand that last sentence.
Are you using a deterministic simulation or not?
Cause if you do (most multiplayer games do it now-adays, its the only way to really avoid transfering all the games data <<BulletPositions/etc.>>)
you either go with the deterministic float approach. Why? Because:
http://stackoverflow.com/questions/2100 ... y-examples
Tl,DR : Floating Points on a PC are not only of finite precision, but also prone to plattform dependent (FPU) diffrent calculation methods and numeric errors.

STREFLOP handles this stuff by deactivating all the fancy, fast gimicks every CPU creator brings along, and bringing them all to behave according to the standard when rounding numbers, dividing, etc..

Now the alternative, if you decide to use Vanilla doubles (which are diffrent on diffrent hardware) would be to cut all digits out that are erroprone. Which means you have to find out which digits are errorprone - and there is a whole sience dedicated to that.

Means you have to calculate the condition of every operation you do:
http://en.wikipedia.org/wiki/Condition_number

Translates into Noobish:
If you have a unit, who gets a damage buff, every millisecond, with a little error in it. This errors mutliply up.
1.0001*1.0001=1.00020001
1.0001^1000=1.1051653926032326972401842401091
Meaning, if you forget to cull ones operations errors, it will grow, and invest your whole determinstic simulation.
Meaning, what starts out as a soldier walking just slightly out of line on one machine, means on that machine, he is not hit by an arrow, he survives the war, and returns home to his wife, only to find out that on all other deterministic-simulations, she was a widdow, married another guy called Schroedinger, and the have a child called Desync Bug!

Now if you have a badly conditioned operation, it will with certain numbers produce tremendous errors.
http://en.wikipedia.org/wiki/Floating_p ... y_problems

And again desync Bug dangers. Machines are just machines, and engineering is realizing, that the default handed to you as user is faulty to, and carefully working around it. Even the windows calculator produces errors if take a number, multiply it long enough with 0.9 and then divide it again with 0.9 back to its original value. Try it yourself, copy paste this code into :
http://www.tutorialspoint.com/execute_lua_online.php

Code: Select all

numberDiv=1
startNumber=1
itterator=1
divisor=0.9
while math.abs(numberDiv-startNumber) == 0 do
    for i=1,itterator do
    numberDiv=numberDiv*divisor    
     print(numberDiv)
    end
    
    
    for i=1,itterator do
    numberDiv=numberDiv/divisor 
     print(numberDiv)
    end
    print("number divided "..numberDiv .. " should be "..startNumber .. " imprecission of" .. math.abs(numberDiv-startNumber))
    
    itterator=itterator+1
    
    
end

print(itterator)
To be honest, the whole process with doubles will be only managable, if you automatize finding, calculating and eliminating the errors. And even then ... Getting Spring to sync was a hard fight. You will have to fight the same fight. Good luck, and if you have any questions, contact us in IRC #sy.

Many starters take the warnings, and horror-tales of engineering as a personal assault, or a attempt at discouraging them from making theire game. We dont. Quite to the contrary! Do it! But to succeed, you will have to go through the same stuff- and that is why we warn you. Its our way of cheering you on!

http://gafferongames.com/networking-for ... terminism/

Re: How does Spring make Deterministic Physics?

Posted: 09 Feb 2015, 09:13
by jpthek9
I was thinking of doing something simple like rounding every calculation to the 4th decimal place. Doubles have up to 16 digits of precision across multiple platforms so (I hope) this will work. Thanks for the wishes and I hope Spring good development as well,

Re: How does Spring make Deterministic Physics?

Posted: 09 Feb 2015, 10:04
by PicassoCT
It will work.. 99.999 % of the time.
Meaning as your machine throws dice all the time, at a horrendous rate. you will have desync bugs every second second.
Those errors, if you have a calculation with bad condition, can even overcome this culling of digits.

Re: How does Spring make Deterministic Physics?

Posted: 09 Feb 2015, 12:46
by hokomoko
If you only want numbers to the 4th decimal place, you can use an implementation of fixed point numbers, or even regular integers with some adaptation.
That should be syncable with no problem, but rounding errors may be.

Re: How does Spring make Deterministic Physics?

Posted: 09 Feb 2015, 13:22
by Kloot
jpthek9 wrote:I was thinking of doing something simple like rounding every calculation to the 4th decimal place. Doubles have up to 16 digits of precision across multiple platforms so (I hope) this will work.
It won't.

Precision (how many bits are used for a number's representation) does not equal accuracy (how many digits of a finite-precision calculation match its "true" value), 3.1234567890123456789 has 20 decimal digits of precision but is a highly inaccurate approximation of pi. Errors that occur in floating-point arithmetic like digit cancellation or truncation are sensitive to every operand digit, not just the last 16 - 4 (or whatever arbitrary cutoff you pick), and the only sync-safe way to handle them with a lockstep simulation model is by controlling the FPU's (as well as the compiler and system libs...) of all machines involved.