# f(x) < O(n^2) to compute gravitational attraction between all object in a space sim..

Discussion in 'OT Technology' started by CodeX, Sep 25, 2007.

1. ### CodeXGuest

So, I know this might not be the best place to ask this, but w/e Ill give OT's programming crew the benefit of the doubt.

I have a 3D space simulation (OpenGL if you were wondering) where I have about 5000 spheres that represent various heavenly bodies (varied sizes and masses) and I want to add gravity to the simulation, obviously. Well, rendering spheres is not the fastest thing in the world and with 5000 on the screen at a time I'm already running at about 30fps. So I need to find the most efficient way to calculate the forces of gravity between all of these objects.

First, I am sure you all know that gravity acts over an unlimited distance, so all objects must be considered to all other objects for this to be accurate. However I am willing to do something like set a max distance where anything farther away from the object is not considered. The formula for gravitational attraction is (G*m1*m2)/r^2 where G is the gravitational constant, the two m's are the masses of the two objects and r is the distance between the centers of mass of the two objects. Since r is squared in the denominator the force of gravity diminishes at an exponential rate as the distance increases, which is why I am willing to make that sacrifice.

Now, I am not an expert on algorithms, and all I have been able to come up with a polynomial time algorithm, basically loop through every object, and for each object loop through every other object and determine their distance apart, then calculate the force of gravity, and finally apply that force to each of their movement vectors. With 5000 objects this is essentially 25 million comparisons... which is not going to happen.

So, help me think of a better way to do this.

Joined:
Jun 11, 2003
Messages:
5,104
0
Location:
STL
3. ### johanActive Member

Joined:
Nov 4, 2003
Messages:
5,123
0
Location:
Sahasrara; magnetic violet infinite
dont compute it. transform it into a lookup table.

4. ### CodeXGuest

thanks for those tutorials I will check them out

Joined:
Jan 27, 2005
Messages:
19,712