Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (581)
games submitted by our members
Games in WIP (500)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2] 3
  ignore  |  Print  
  Random thoughts: Extreme speed 2D physics  (Read 8935 times)
0 Members and 1 Guest are viewing this topic.
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #30 - Posted 2012-05-01 15:45:30 »

Except that in nearly all your post you write 'ms', so well, it's a... consistent typo. I'll give you that.

I wish my old teachers were that lenient Smiley

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #31 - Posted 2012-05-01 15:49:28 »

I typically am lenient if its clear what the units are and its clearly a typo except for mock exams (mark does not count). Don't get me wrong... it was wrong and unlike gramma ****s its something that should be pointed out since it can/does change the meaning. But also i want to write ms^{-1}

I have no special talents. I am only passionately curious.--Albert Einstein
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #32 - Posted 2012-05-01 15:52:02 »

Think i fixed all my posts now.

FWIW i said i love physics. That is not really the same as good at it Wink these days its not really my day job anymore.

I have no special talents. I am only passionately curious.--Albert Einstein
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline theagentd
« Reply #33 - Posted 2012-05-01 17:51:58 »

I know how big space is. >_> Like I said I have (had T_T) a simulation running with a few planets placed at their correct distances from the sun + their moons.

Numerical accuracy isn´t going to be good enough even with 64-bit floating point variables, so I plan on using fixed point ints/longs evenly distributed over the simulation area plus floats/doubles for positions relative to the fixed points to get the same numerical accuracy everywhere. I would also use them for velocity. Would that eliminate the need for changing the frame of reference per object? I´m afraid that the numerical accuracy of even doubles will be too low to handle collisions in some cases. For example it´s possible to put something in orbit around the sun (not a planet). That could mean problems if for example two objects collide while in orbits around the sun in the outer parts of the solar system (same distance as Pluto? xd), right? Since the sun is the body with the biggest gravitational pull on the objects they woud use the sun as frame of reference, which is insanely far away. Another problem that fixed precision solves is rendering things with OpenGL. With only 32-bit floats and matrix multiplications things at the same distance as the Earth from the sun cannot be rendered accurately. I think fixed precision for velocity also improves collision detection/handling for objects travelling at very high speeds in almost the same direction.

I suppose this would mean changing the point of reference to the nearest point in an even grid, so maybe we´re even talking about the same thing? =P

Myomyomyo.
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #34 - Posted 2012-05-01 18:25:25 »

We are talking about mostly the same thing. Numerical accuracy is really about cumulative errors. Even a plain old double with 53bits of precision is accurate to microns (about 17 microns) with a baseline from the sun to the earth. The problem with floating point is that the errors depend on the distance from the origin. This is compounded by the use of Cartesian coordinates. Typically spherical coordinates are used. Coordinate transforms then use tensors since these are curvilinear coordinates. That is the basis vectors change depending where you are.

Thing is that these small errors means that your simulated system could eject planets and that sort of thing all the time.

But all of the this is a bit moot for a lot of things. How accurate do you need it to be? What is it for?  Faking it will probably get the job done without instabilities. ie just use parametric equations of motion for the planets. This is what Celestia and other orbital tracking software uses. There are tables that are accurate for the next 1000 years.

Also Celestia is open source and does all its visualization in opengl and they have dealt with the scale problem. You could check out their source.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #35 - Posted 2012-05-01 18:56:12 »

Why not use BigDecimal(MathContext.DECIMAL128) to solve all these accuracy problems.

Yeah, the code verbosity sky rockets and you'll produce quite a bit of garbage, but at least the calculations remain easy to grasp.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline theagentd
« Reply #36 - Posted 2012-05-01 22:16:13 »

Why not use BigDecimal(MathContext.DECIMAL128) to solve all these accuracy problems.

Yeah, the code verbosity sky rockets and you'll produce quite a bit of garbage, but at least the calculations remain easy to grasp.

I want more than one planet... xd It's horribly slow, right? Might have to benchmark that, but I'm not gonna hold my breath... Maybe I can write a less flexible class myself instead?

We are talking about mostly the same thing. Numerical accuracy is really about cumulative errors. Even a plain old double with 53bits of precision is accurate to microns (about 17 microns) with a baseline from the sun to the earth. The problem with floating point is that the errors depend on the distance from the origin. This is compounded by the use of Cartesian coordinates. Typically spherical coordinates are used. Coordinate transforms then use tensors since these are curvilinear coordinates. That is the basis vectors change depending where you are.

Thing is that these small errors means that your simulated system could eject planets and that sort of thing all the time.

But all of the this is a bit moot for a lot of things. How accurate do you need it to be? What is it for?  Faking it will probably get the job done without instabilities. ie just use parametric equations of motion for the planets. This is what Celestia and other orbital tracking software uses. There are tables that are accurate for the next 1000 years.

Also Celestia is open source and does all its visualization in opengl and they have dealt with the scale problem. You could check out their source.

You lost me after you mentioned spherical coordinates...

I agree that using equations for immovable bodies is a good idea, but not for smaller bodies (ships, missiles. asteroids, etc). Let's say they have to be able to remain stable for 100 years in game time (=100 days of running the simulation at 30 "FPS").

Myomyomyo.
Offline pitbuller
« Reply #37 - Posted 2012-05-01 22:23:01 »

Numeric instability could add some nice flavor to game. If you use too much time weird things start happen. The moon escape from the earth and jupiter start slinging deadly moons toward everything and other things that plaey can concider as apocalyptic events.
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #38 - Posted 2012-05-02 10:12:19 »

If the large bodies use parametric equations, this will make pretty much everything quite stable. Space ship etc are only affected by the large bodies and bobs your uncle you have a pretty stable system. Using big int will be very slow, I would just use longs or scaled doubles. For a game its going to be good enough.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline theagentd
« Reply #39 - Posted 2012-05-02 12:01:33 »

I believe that doubles will be insufficient in extreme cases. I also think that using floating precision numbers for something that needs evenly distributed precision (like position and to some extent velocity) is simply bad manners, so allow me to hijack back the thread and instead derail it into even precision variables. I did som math on 64-bit longs and found that a 2D position can represent 2 light years with 1mm precision. Sadly the closest star system to the sun is 4 light years away. >_> Oh, 128-bit ints, where arth thou?

What´s the best way of doing this? I think using integer math is a good idea, but it seems to be really complicated and slow to emulate 128-bit ints. I´m sure that velocity is fine with 64-bit longs and a fixed decimal point since it´ll only be used to accumulate acceleration and I´m fine with limiting the max velocity to a few times the speed of light. xD

One idea is to use a 64-bit long to represent position in meter plus either a 32-bit int or a float as a fraction. This would give a range of 2000 light years with micro or nanometer (10^-9) precision. However, I it seems hard to do basic math with such variables, especially handling overflow and underflow in the fraction variable.

My idea is therefore to store position in >64-bit precision and velocity as a 64-bit decimal long. Acceleration is calculated as doubles since forces benefit from the floating precision.

As an example, here´s gravitational force:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
//SuperDecimal = what position is stored in

//Calculate deltaPosition with fixed precision
SuperDecimal deltaPosition = largestBody.position - smallBody.position;

//Convert values to doubles since from here on precision matters less the higher the value is (=perfect for floats)
double dx = deltaPosition.xToDouble(), dy = deltaPosition.yToDouble();
double distanceSqrd = dx*dx + dy*dy;
double distance = Math.sqrt(distanceSqrd);

double dirX = dx / distance, dirY = dy / distance;
double acceleration = GRAVITATIONAL_CONSTANT * largestBody.mass / distanceSqrd;

//Velocity is also fixed precision, but an acceleration is a double. Round if needed
DecimalLong velocity = smallBody.velocity;
velocity.add(dirX * acceleration, dirY * acceleration);

//Later add velocity to position (add a DecimalLong to a SuperDecimal)
smallBody.position.add(smallBody.velocity);


The only problem is handling the subtraction to calculate deltaPosition and adding velocity. Am I insane? Thoughts?

Myomyomyo.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Roquen
« Reply #40 - Posted 2012-05-02 13:44:44 »

Why not the equivalent of an animation hierarchy at the high level.  The end nodes are where there is some spatial data structure.  The resolution can be very low as exactly where the spatial data structure is attached can be specified by a registration point which can move as needed to give fine grain resolution.  Then all actual objects are simply stored as coordinates inside the local spatial data structure.  If these are still too big, they could be store cell local as the higher levels coordinates are all implicit.  The effect of the spatial data structures on one other could then be a simplified model (or models depending on distance)...for example a point mass for all it's contents if very far away or as a projected line of varying mass, etc. etc.
Offline theagentd
« Reply #41 - Posted 2012-05-02 14:10:57 »

Why not the equivalent of an animation hierarchy at the high level.  The end nodes are where there is some spatial data structure.  The resolution can be very low as exactly where the spatial data structure is attached can be specified by a registration point which can move as needed to give fine grain resolution.  Then all actual objects are simply stored as coordinates inside the local spatial data structure.  If these are still too big, they could be store cell local as the higher levels coordinates are all implicit.  The effect of the spatial data structures on one other could then be a simplified model (or models depending on distance)...for example a point mass for all it's contents if very far away or as a projected line of varying mass, etc. etc.
I hate to admit that I have no idea what you´re saying... (^_^;) Give me some time to process that, but first I need to get some food so my head starts working again...

Myomyomyo.
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #42 - Posted 2012-05-02 17:03:13 »

Roquen has the right idea. When you are looking at different starts you use a different scale, say 1km per count. Then when you "zoom in" you use the 1mm scale for local simulations with coordinates centered on the star, or alternatively everything is 2 numbers a baseline+local delta. Most of the math only needs to use the local delta and can ignore the baseline, while other parts of the simulation can ignore the delta and only work with the baseline.  [edit fixed typo]

The old java3d did something like this with its concepts of baselines.

You still have not really said what this is for? I am intrigued.  And you are aware of http://www.shatters.net/celestia/ right?

I have no special talents. I am only passionately curious.--Albert Einstein
Offline theagentd
« Reply #43 - Posted 2012-05-02 20:21:40 »

Roquen has the right idea. When you are looking at different starts you use a different scale, say 1km per count. Then when you "zoom in" you use the 1mm scale for local simulations with coordinates centered on the star, or alternatively everything is 2 numbers a baseline+local delta. Most of the math only needs to use the local delta and can ignore the baseline, while other parts of the simulation can ignore the delta and only work with the delta. 

The old java3d did something like this with its concepts of baselines.

You still have not really said what this is for? I am intrigued.  And you are aware of http://www.shatters.net/celestia/ right?
So you´re basically approving of what I wrote earlier? Baseline = a long where 1 unit is 1 km or so, and local delta = an int or something. But how do I handle overflows/underflows in the local delta? Overflow = increase baseline, underflow = decrease baseline...

Don´t get too excited about this... Just me pondering over the technical plausability of a 2D space MMORTS...  Wink I liked Ogame except for the fact that it sucked. Since no one wants to make a decent space browser game that...

 - does not depend on how fast you are at pressing F5 to update the browser
 - does not have laughable physics and planets 5 meters away from each other
 - is not ****ing textbased -_-

... I figured I might as well try to make one myself. There you go, add determinism to the list! ^_^ But like I said, don´t get too excited. I have 2 other games to complete first and 2 shadow mapping techniques to test before I can work on this. xD And since I´m completely stalled for around one more week my head is soon going to explode with programming ideas... >_<

Myomyomyo.
Offline sproingie
« Reply #44 - Posted 2012-05-02 21:11:26 »

Here's how a realistic Space MMO would be:

"Set course for Proxima Centauri.  Arrival time in 2387 standard years."

*quit*
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #45 - Posted 2012-05-02 21:14:19 »

Well, only 6.5397 years in his simulation. Don't be such a nay-sayer.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Riven
« League of Dukes »

JGO Overlord


Medals: 605
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #46 - Posted 2012-05-02 22:16:27 »

I just did some benchmarking of verlet integration (2 particles and 1 spring).

double vs BigDecimal(DECIMAL128): over 20000x slower.



A heck of a lot more stable than 64 bit doubles though persecutioncomplex

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #47 - Posted 2012-05-03 00:09:13 »

Local coordinates = good.  Single precision = usually good.

If you really need more than doubles for some things you can always use unevaluated chains (like double-doubles for ~108 bits, etc)...but why bother.
Offline theagentd
« Reply #48 - Posted 2012-05-03 09:18:13 »

Well, only 6.5397 years in his simulation. Don't be such a nay-sayer.
It´s only newtonian physics so we´re not limited by the speed of light at least, and 1 light year takes only 1 day at the spee of light. xD In Ogame it takes weeks or even months to build certain buildings since the cost and time taken to build something increases exponentially.

I just did some benchmarking of verlet integration (2 particles and 1 spring).

double vs BigDecimal(DECIMAL128): over 20000x slower.



A heck of a lot more stable than 64 bit doubles though persecutioncomplex
Thanks for testing that, but that sadly rules out BigDecimal then...

Myomyomyo.
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #49 - Posted 2012-05-03 12:06:25 »

For some kind of MMO game i would stick with 100% parametric for everything. More or less. Run totally different "modes" for between stars vers within systems. Since its parametric it is easy to move any one part of the system to where it should be at any given time. Even approximate orbits for ships etc can work this way, and its probably going to just as accurate as any simulation that would be practical.

Since the transport mode between stars will need to be some kind of FTL to make the game interesting you already have a natural way to separate the scales.

I have no special talents. I am only passionately curious.--Albert Einstein
Offline matheus23

JGO Kernel


Medals: 98
Projects: 3


You think about my Avatar right now!


« Reply #50 - Posted 2012-05-04 14:02:44 »

Well, only 6.5397 years in his simulation. Don't be such a nay-sayer.
It´s only newtonian physics so we´re not limited by the speed of light at least, and 1 light year takes only 1 day at the spee of light. xD In Ogame it takes weeks or even months to build certain buildings since the cost and time taken to build something increases exponentially.

I just did some benchmarking of verlet integration (2 particles and 1 spring).

double vs BigDecimal(DECIMAL128): over 20000x slower.



A heck of a lot more stable than 64 bit doubles though persecutioncomplex
Thanks for testing that, but that sadly rules out BigDecimal then...

So sad... in C++ you could have used long double on 64-bit machines... sad...

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline theagentd
« Reply #51 - Posted 2012-05-04 14:49:33 »

Or rather a long long, if there is such a thing... xD

Myomyomyo.
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #52 - Posted 2012-05-04 14:52:34 »

You can't just throw precession at chaotic systems. Well not really. Errors eventually grow exponentially regardless. The only way to really do it properly is with interval arithmetic. Next best is always be smart with the precision you have. Doubles are seriously pretty good if used properly. rounding errors are about 1mm at 8 light hours. Longs are also good for 1mm error at 2 light years. Add a base line and a galaxy is no problem at all.

And no matter how "good" c++ is or whatever using the longer versions are much slower that the base versions. Its not like its hardware native format. 

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Orangy Tang

JGO Kernel


Medals: 51
Projects: 11


Monkey for a head


« Reply #53 - Posted 2012-05-04 15:00:43 »

Or rather a long long, if there is such a thing... xD

There is, but due to hilarious compatibilities reasons it's usually 64 bits (ie. identical to long).

[ TriangularPixels.com - Play Growth Spurt, Rescue Squad and Snowman Village ] [ Rebirth - game resource library ]
Offline matheus23

JGO Kernel


Medals: 98
Projects: 3


You think about my Avatar right now!


« Reply #54 - Posted 2012-05-04 15:10:24 »

It is MUCH faster (than BigDecimal), if you let the cpu do all that things... btw, I've got an Idea:

theagentd: maybe, you could make something like a Chunk-System (lol.. sorry its minecraft again.), where you have chunks in size, where your double has a good precision (that could be HUGE). Having a chunk system below would make everything acctually really ... yeahh. reeeaaallllly huge: MAX_VAL_LONG * MAX_VAL_LONG  Chunks? I think, thats okey Cheesy. And since you can have really big chunks, you don't have to switch the chunk too often and its not an expensive calculation anyways.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
21  
22  
23  
24  
25  
26  
27  
28  
29  
30  
moveInWorld(double dx, double dy) {
   // dx = Moving on x axis
  // dy = Moving on y axis
  // cx = Current Chunk x
  // cy = Current Chunk y
  // halfChunkSize = your desired/wanted Chunk size /2
  // WARING! UNTESTED CODE:
  if (dx != 0) {
      if (dx > 0) {
         while (x+dx > halfChunkSize) {
            cx++;
         }
      } else {
         while (x+dy < halfChunkSize) {
            cx--;
         }
      }
   }
   if (dy != 0) {
      if (dy > 0) {
         while (y+dy > halfChunkSize) {
            cy++;
         }
      } else {
         while (y+dy < halfChunkSize) {
            cy--;
         }
      }
   }
}


Or rather a long long, if there is such a thing... xD

There is, but due to hilarious compatibilities reasons it's usually 64 bits (ie. identical to long).

Yepp, but on 64-bit machines it works.

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Offline Roquen
« Reply #55 - Posted 2012-05-04 15:13:17 »

delt0r semi beat me.  Over-engineering kids.  Use local coordinate frames.  Example:

Distance sun to earth: 1.509x108 km

A power of two local coordinate frame large enough to cover the sun, the earth's orbit and everything inside, where '1' represents a meter
: 2.748779x108 km

Size of the ULP at the edge of this local coordinate frame:  6.103516x10-5 m

This is kind silly big.
Offline delt0r

JGO Coder


Medals: 22


Computers can do that?


« Reply #56 - Posted 2012-05-04 15:28:36 »

Also lets consider the time resolution. If you want 1mm accuracy that mean the integration steps need to be pretty small. Earth orbital velocity is about 30km/s. So to travel 1mm it takes 33ns. Of course you don't want to use that sort of time step. But you see that you simply don't need all this precision.

Unless you are studying the long term stability of the solar system (really really hard), you just don't need more than properly used longs/doubles. And it will be fast. But not as fast as parametric equations of motion. 

I have no special talents. I am only passionately curious.--Albert Einstein
Offline Roquen
« Reply #57 - Posted 2012-05-04 15:47:00 »

Seems to me that you'd want to maintain rectangle coordinates as well for pretty much everything else.
Offline theagentd
« Reply #58 - Posted 2012-05-04 16:57:18 »

Thanks everyone for your thoughts! I´m glad this sparked so much discussion! So how to store positions is pretty much solved then, but feel free to discuss this further.

Myomyomyo.
Offline matheus23

JGO Kernel


Medals: 98
Projects: 3


You think about my Avatar right now!


« Reply #59 - Posted 2012-05-04 17:04:58 »

So how to store positions is pretty much solved then, ...

huh? YAY Cheesy

See my:
    My development Blog:     | Or look at my RPG | Or simply my coding
http://matheusdev.tumblr.comRuins of Revenge  |      On Github
Pages: 1 [2] 3
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (55 views)
2014-04-15 10:08:23

BurntPizza (53 views)
2014-04-14 19:46:01

UprightPath (66 views)
2014-04-14 09:39:50

UprightPath (49 views)
2014-04-14 09:35:47

Porlus (66 views)
2014-04-14 07:48:38

tom_mai78101 (90 views)
2014-04-09 20:04:31

BurntPizza (151 views)
2014-04-08 15:06:04

tom_mai78101 (247 views)
2014-04-05 05:34:39

trollwarrior1 (204 views)
2014-04-04 04:06:45

CJLetsGame (211 views)
2014-03-31 18:16:10
List of Learning Resources
by SHC
2014-04-17 19:17:39

List of Learning Resources
by Longarmx
2014-04-07 19:14:44

Good Examples
by matheus23
2014-04-05 05:51:37

Good Examples
by Grunnt
2014-04-03 07:48:46

Good Examples
by Grunnt
2014-04-03 07:48:37

Good Examples
by matheus23
2014-04-01 10:40:51

Good Examples
by matheus23
2014-04-01 10:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 07:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!