How does Spring make Deterministic Physics?

How does Spring make Deterministic Physics?

Discuss game development here, from a distinct game project to an accessible third-party mutator, down to the interaction and design of individual units if you like.

Moderator: Moderators

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

How does Spring make Deterministic Physics?

Post by jpthek9 » 07 Feb 2015, 23:36

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.
0 x

abma
Spring Developer
Posts: 3560
Joined: 01 Jun 2009, 00:08

Re: How does Spring make Deterministic Physics?

Post by abma » 08 Feb 2015, 00:15

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.
0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 08 Feb 2015, 01:45

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?
0 x

abma
Spring Developer
Posts: 3560
Joined: 01 Jun 2009, 00:08

Re: How does Spring make Deterministic Physics?

Post by abma » 08 Feb 2015, 01:47

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
0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 08 Feb 2015, 02:18

Thanks a bunch :)
0 x

User avatar
PicassoCT
Journeywar Developer & Mapper
Posts: 10239
Joined: 24 Jan 2006, 21:12

Re: How does Spring make Deterministic Physics?

Post by PicassoCT » 08 Feb 2015, 09:28

There are plans, to one day add bullet for additional unitphysics via opencl.
0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 08 Feb 2015, 19:19

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.
0 x

User avatar
smoth
Posts: 22300
Joined: 13 Jan 2005, 00:46

Re: How does Spring make Deterministic Physics?

Post by smoth » 08 Feb 2015, 19:37

What is deterministic physics? What is deterministic in an rts game?
0 x

User avatar
Silentwings
Moderator
Posts: 3597
Joined: 25 Oct 2008, 00:23

Re: How does Spring make Deterministic Physics?

Post by Silentwings » 08 Feb 2015, 19:41

I guess he means synced.
0 x

User avatar
smoth
Posts: 22300
Joined: 13 Jan 2005, 00:46

Re: How does Spring make Deterministic Physics?

Post by smoth » 08 Feb 2015, 19:47

Dunno, that is why I asked better to ask and look ignorant, than assume I know
0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 08 Feb 2015, 20:05

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.
0 x

User avatar
jK
Spring Developer
Posts: 2299
Joined: 28 Jun 2007, 07:30

Re: How does Spring make Deterministic Physics?

Post by jK » 08 Feb 2015, 20:24

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).
0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 08 Feb 2015, 20:34

Oh, interesting. I think I'll look into using STREFLOP as well. Do you know of any libraries in C#?
0 x

abma
Spring Developer
Posts: 3560
Joined: 01 Jun 2009, 00:08

Re: How does Spring make Deterministic Physics?

Post by abma » 08 Feb 2015, 21:19

0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 08 Feb 2015, 21:42

That's alright. I did more research into doubles and conducted some tests. For my uses, it's accurate enough.
0 x

User avatar
PicassoCT
Journeywar Developer & Mapper
Posts: 10239
Joined: 24 Jan 2006, 21:12

Re: How does Spring make Deterministic Physics?

Post by PicassoCT » 09 Feb 2015, 09:09

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/
Last edited by PicassoCT on 09 Feb 2015, 09:58, edited 1 time in total.
0 x

jpthek9
Posts: 18
Joined: 07 Feb 2015, 23:30

Re: How does Spring make Deterministic Physics?

Post by jpthek9 » 09 Feb 2015, 09:13

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,
0 x

User avatar
PicassoCT
Journeywar Developer & Mapper
Posts: 10239
Joined: 24 Jan 2006, 21:12

Re: How does Spring make Deterministic Physics?

Post by PicassoCT » 09 Feb 2015, 10:04

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.
0 x

hokomoko
Spring Developer
Posts: 585
Joined: 02 Jun 2014, 00:46

Re: How does Spring make Deterministic Physics?

Post by hokomoko » 09 Feb 2015, 12:46

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.
0 x

Kloot
Spring Developer
Posts: 1865
Joined: 08 Oct 2006, 16:58

Re: How does Spring make Deterministic Physics?

Post by Kloot » 09 Feb 2015, 13:22

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.
0 x

Post Reply

Return to “Game Development”