   More efficent way to do this?
  hello everyone, i'm attempting to create a mutual gravity particle system, however i'm having a few issues, mostly with the following code:void gParticle::CalculatePull(gParticle *b){    float d = sqrtf(powf(b->GetX()-m_x,2)+powf(b->GetY()-m_y,2));    if(d>b->GetRadius()+m_Radius){ float f = (m_Mass*b->GetMass())/d*G; m_xVel+=(b->GetX()-m_x)/d*f; m_yVel+=(b->GetY()-m_y)/d*f; b->SetXVel(b->GetXVel()+(m_x-b->GetX())/d*f); b->SetYVel(b->GetYVel()+(m_y-b->GetY())/d*f);   }}void gParticleManager::Update(unsigned char Flag, float G){   if(Flag&PARTICLEMAN_PULL){ for(int i=0;i<m_NbrParticles;i++){    for(int d=i+1;d<m_NbrParticles;d++){  m_Particles.CalculatePull(m_Particles+d);    } }   }}without it, i can generate ~600 particles before even noticing a slowdown, and that slow down is only a few FPS loss, but with it, i can only get upto ~150 particles before a slowdown becomes very noticable(dropping the frame rate in half)i'd appreciate any ideas on optimizing the code to run faster, i can't think of any(note this is being built on the psp, not the pc, so if 600 seems small that'd be why(although i feel 600 is small even on the psp))[Edited by - slicer4ever on May 19, 2010 3:06:20 AM]
  Hi Slicer,In case you do atm, don't update drag evey frame.Integrate (e.g 2 times a second), and interpolate positions for rendering.Partition your space into cells. For each Particle P.Calculate particle <--> particle drag only for particles in the same or neighbouring cells. Then add particle <--> cell drag for all remaining cells.Just my 2 cents.Best Jochen   ;  You have an O(N^2) problem here - the complexity rises on the square of the number of elements.You need to turn your problem into a smaller one.An easy way of doing this for an application such as this is to grid up your universe into 3D cubes. You then put each particle into the cube which contains it. You can then easily find all the neighbours to a particle because they're in one of the 3x3x3 cube of cubes surrounding the cube it's in.Problems involve -- the fact you're discarding more distant influences. You may not care about this, or it might be really important. Depends on your application.You might want to detect that *some* particles are very large and have very large influences and apply them separately. That would let you model (for example) an asteroid belt around a star better.Another option is to build a hierarchy of objects, based on their relative gravitational influences. For example, the earth-sun-moon system could be done in two parts -- the earth/sun interaction and the earth-moon system. Likewise, the moon-apollo11 system could be modelled independently of the others. Add them all together when they're done.You might find that layers are important -- you might want to do sun/earth/jupiter as a system, but then do earth/moon and jupiter/moons separately on the basis that while jupiter influences the earth, its moons really don't much.;  You might gain a ton of caching improvements (read: performance) when switching from Array-of-struct to Struct-of-array.   ;  I always wanted to ask one thing:is pow(x,2) faster than x*x? Or it's used to avoid float overflow / precision errors?Sorry for the stupid question.   ;  Search for "n body simulation" and read this paper from Barnes&Hut:http://www.nature.com/nature/journal/v324/n6096/abs/324446a0.htmlThis should give you some ideas how to speed up calculation.   ;  thanks for the input guys, i'll take a look at the article nmi, although i'm not certain i can implement an grouping system, as has been suggested, since the particles are too close together, the time to go through and make grouped objects seems like it'd slow down the program, more than speed it up, but i'll see what happens when i do, thanks for the input thus far=-)   ;  I would suggest:void gParticle::CalculatePull(gParticle *b){    float dx = b->GetX()-m_x;    float dy = b->GetY()-m_y;    float d2 = dx*dx + dy*dy;    float r = b->GetRadius()+m_Radius;    if(d2 > r * r)    { float f = (m_Mass*b->GetMass()) / d2 * G; float vx = (b->GetX()-m_x) * f; float vy = (b->GetY()-m_y) * f; m_xVel += vx; m_yVel += vy; b->SetXVel(b->GetXVel() - vx); b->SetYVel(b->GetYVel() - vy);   }}Notes:- Square roots are slow.- Divides are slow.- Compilers generally won't rearrange floating point maths very much (depending somewhat on settings).I've not even tried to compile or test this myself. However, as long as I've not made any silly mistakes this should be significantly quicker, and still give similar results.   ;Quote:Original post by KatieAnother option is to build a hierarchy of objects, based on their relative gravitational influences. For example, the earth-sun-moon system could be done in two parts -- the earth/sun interaction and the earth-moon system. Likewise, the moon-apollo11 system could be modelled independently of the others. Add them all together when they're done.For the moon you need both sun and earth interactions. The sun's interaction is WAY bigger to the moon then earth's interaction. The sun is giving the moon the yearly 'circle' around the sun, the earth only gives it a slight wobble.</offtopic>   