How does Spring make Deterministic Physics?
Moderator: Moderators
How does Spring make Deterministic Physics?
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.
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?
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.
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?
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?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.
Re: How does Spring make Deterministic Physics?
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: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?
https://github.com/spring/spring/tree/d ... s/Sim/Misc
Re: How does Spring make Deterministic Physics?
Thanks a bunch :)
Re: How does Spring make Deterministic Physics?
There are plans, to one day add bullet for additional unitphysics via opencl.
Re: How does Spring make Deterministic Physics?
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.
For my game, I'm making it deterministic by using double math.
Re: How does Spring make Deterministic Physics?
What is deterministic physics? What is deterministic in an rts game?
- Silentwings
- Posts: 3720
- Joined: 25 Oct 2008, 00:23
Re: How does Spring make Deterministic Physics?
I guess he means synced.
Re: How does Spring make Deterministic Physics?
Dunno, that is why I asked better to ask and look ignorant, than assume I know
Re: How does Spring make Deterministic Physics?
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?
That's not deterministic. It just gives similar results as long as the _math_ is stable.jpthek9 wrote:For my game, I'm making it deterministic by using double math.
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?
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?
no: https://springrts.com/wiki/About#Development (Spring doesn't use C#)
Re: How does Spring make Deterministic Physics?
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?
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.
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
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/
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.
Meaning, if you forget to cull ones operations errors, it will grow, and invest your whole determinstic simulation.1.0001*1.0001=1.00020001
1.0001^1000=1.1051653926032326972401842401091
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)
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.
Re: How does Spring make Deterministic Physics?
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?
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.
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?
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.
That should be syncable with no problem, but rounding errors may be.
Re: How does Spring make Deterministic Physics?
It won't.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.
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.