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. CodeX

    CodeX Guest

    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.
     
  2. EvilSS

    EvilSS New Member

    Joined:
    Jun 11, 2003
    Messages:
    5,104
    Likes Received:
    0
    Location:
    STL
  3. johan

    johan Active Member

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

    CodeX Guest

    thanks for those tutorials I will check them out
     
  5. deusexaethera

    deusexaethera OT Supporter

    Joined:
    Jan 27, 2005
    Messages:
    19,712
    Likes Received:
    0
    There is no better way to do it. This is why gravitational models of the solar system (with roughly 5000 objects of any meaningful mass) are only performed by the most badass supercomputers on Earth. Your machine will melt.

    You could store an array of previously-calculated relationships for each tick of the simulation, which would reduce the number of calculations by half. But 12.5M is still not gonna happen.
     

Share This Page