Simulating Pseudo-Newtonian Motion on a 2D Plane

[SkyMarshal]

Sorry if this is the wrong place to ask a question like this, but I am at wits end trying to make this system function properly while remaining computationally efficient.

A summary of what I have so far:

• An iterative simulator that computes gravitational attration of objects on a cartesian co-ordinate plane, which computes the delta-V and then linearly adjusts the position based on this. (It is accurate enough for my needs with the timeframes being used, while being faster than more precise methods.)
• Simulated objects containing a position, velocity, and any acceleration it is applying as well as a bearing. These are approximated as spheres with the radius derived from mass and density moving on the plane of the simulation.
• A means to add velocities in a manner respecting relativistic equations. 0.5c + 0.6c results in ~0.86c, not the expected 1.1c if using a direct addition method.

The problem I am having is that when the number of simulated masses increases, both the number of calculations for gravitational attraction and for Collision detection increase exponentially, with n² calculations being required for n bodies, for both collision and gravitation. As such, various types of Binary Space Partitioning trees (In the case of this 2D space, quadtrees are the ones that should be used) can be used to significantly reduce the number of calculations needed as the number of objects increases. For collisions, a data structure like so allows you to only check for collisions within either nearby nodes or the same node you are in, based on implementation. For gravitation, the Barnes-Hut simulation technique can be used to more rapidly and efficiently approximate gravitational attraction.

Now, you may think I just revealed the solution to my own problem, but that is where you in correct. A Quadtree only segments the contents of a finite space into smaller spaces, but the simulation I am working with has a working space of (theoretically) 10⁴⁷ meters per side, when the size of the simulated space is on the order of 10¹³ meters... as such, subdividing that massive space into a small enough amount to gracefully handle the needed calculations on the scales we are working with would be likely both memory and computationally inefficient.

Thus, I pose to you: How should I go about partitioning this massive space into manageable chunks, without being pants on head retarded about it?

 

[mfb]

You have (10^47 m)^2 simulated area and details within 10^13 meters? How many objects do you have in your simulation?
Is this supposed to run on a supercomputer? ;)

10^20 times the diameter of the observable universe down to planetary systems...

 

[SkyMarshal]

The number objects will likely be on the order of a hundred or so at most, objects that will not be near the player will either be abstracted away or just simply offloaded until they are flown near again.
The real problem is not the number of objects being simulated (I assure you, steps will be taken to keep the numbers down like no other) but the scale of the simulation, since I highly HIGHLY expect players to do their damnedest to try to fly out of the simulation. (While the simulation is enormous, there will be a form of FTL, so the hurdle of lightspeed will not bother them too much...)

Also, to clarify, not all of that volume need even be used in the simulation, it's just the maximum limit to the size that can be handled with the precision of the positioning variables. (Single precision floating point, where an in increase of one in one of the position variables will move you 10⁹ meters. Since single precision floating point can reach a maximum of around 10³⁸, the maximum length per axis is 10⁴⁷m) The actual content is almost entirely randomly generated or assembled by preexisting data, so that is not an issue.

(Sorry if this is not very coherent, I just woke up.)

 

[Muphrid]

If you know something about the total mass of all objects in the simulation, it might be reasonable to say that, beyond a certain distance, no amount of mass could have an appreciable effect on the motions of objects in our vicinity. Perhaps this could give you a way to keep the quadtree from having to partition the whole simulation domain.

 

[SkyMarshal]

I already have a function set aside to preform a cutoff on gravitation when the exerted force drops below one Newton, but that does not solve the issue with computing collisions if they are past whatever arbitrary cutoff to the quadtree we devise. In addition, it is currently planned to have more than one solar system... and two large concentrations of objects separated by a much larger distance would be merry hell with the topography of a quadtree. (The solar systems would not be simulated unless a player ship was within them, essentially... but there can be more than one ship. Throw in two simulated solar systems into the quadtree and you got a problem.)

 

[mfb]

Ok... so you want to simulate some planetary systems (or maybe just 1) and a lot of empty space around?

I think I would try something like that:
- simulate the area around stars in a regular way (quadtrees and whatever)
- add a region around this where you simplify gravity to "main star attracts stuff only". Things in this region do not influence the main area or anything else, so you can store them in a separate way. If you still want that spaceships can interact with each other, divide the volume by angle (as seen from the star) in several chunks. Alternatively, make really big chunks.
- everything else is free space. If you still want spaceships approaching each other there, an n^2-scaling might be fine.Edit: Other things:
- for everything moving with relativistic velocity, but not very close to stars, you can neglect gravity completely
- you can make "velocity chunks", as different objects with relativistic relative motion won't couple to each other anyway

 

[SkyMarshal]

Hah! Brilliant! I'll probably steal that and cackle like a madman, and probably use a much much bigger quadtree for checking collisions between ships in deep space, since the leaves could be enormous based on how many ships are in deep space.