I'm making a space exploration type game, it will have many planets and other objects that will all have realistic gravity. I currently have a system in place that works, but if the number of planets goes above 70, the FPS decreases an practically exponential rates. I'm making it in C# and XNA.

My guess is that I should be able to do gravity calculations between 100 objects without this kind of strain, so clearly my method is not as efficient as it should be.

I have two files, Gravity.cs and EntityEngine.cs. Gravity manages JUST the gravity calculations, EntityEngine creates an instance of Gravity and runs it, along with other entity related methods.

EntityEngine.cs

        public void Update()
        {
            foreach (KeyValuePair<string, Entity> e in Entities)
            {
                e.Value.Update();
            }

            gravity.Update();
        }

(Only relevant piece of code from EntityEngine, self explanatory. When an instance of Gravity is made in entityEngine, it passes itself (this) into it, so that gravity can have access to entityEngine.Entities (a dictionary of all planet objects))

Gravity.cs

namespace ExplorationEngine
{
    public class Gravity
    {
        private EntityEngine entityEngine;
        private Vector2 Force;
        private Vector2 VecForce;
        private float distance;
        private float mult;

        public Gravity(EntityEngine e)
        {
            entityEngine = e;
        }


        public void Update()
        {
            //First loop
            foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
            {
            //Reset the force vector
            Force = new Vector2();

                //Second loop
                foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
                {
                    //Make sure the second value is not the current value from the first loop
                    if (e2.Value != e.Value )
                    {
                        //Find the distance between the two objects. Because Fg = G * ((M1 * M2) / r^2), using Vector2.Distance() and then squaring it
                        //is pointless and inefficient because distance uses a sqrt, squaring the result simple cancels that sqrt.
                        distance = Vector2.DistanceSquared(e2.Value.Position, e.Value.Position);

                        //This makes sure that two planets do not attract eachother if they are touching, completely unnecessary when I add collision,
                        //For now it just makes it so that the planets are not glitchy, performance is not significantly improved by removing this IF
                        if (Math.Sqrt(distance) > (e.Value.Texture.Width / 2 + e2.Value.Texture.Width / 2))
                        {
                            //Calculate the magnitude of Fg (I'm using my own gravitational constant (G) for the sake of time (I know it's 1 at the moment, but I've been changing it)
                            mult = 1.0f * ((e.Value.Mass * e2.Value.Mass) / distance);

                            //Calculate the direction of the force, simply subtracting the positions and normalizing works, this fixes diagonal vectors
                            //from having a larger value, and basically makes VecForce a direction.
                            VecForce = e2.Value.Position - e.Value.Position;
                            VecForce.Normalize();

                            //Add the vector for each planet in the second loop to a force var.
                            Force = Vector2.Add(Force, VecForce * mult);
                            //I have tried Force += VecForce * mult, and have not noticed much of an increase in speed.
                        }
                    }
                }

                //Add that force to the first loop's planet's position (later on I'll instead add to acceleration, to account for inertia)
                e.Value.Position += Force;
            }

        }

    }
}

I have used various tips (about gravity optimizing, not threading) from THIS question (that I made yesterday). I've made this gravity method (Gravity.Update) as efficient as I know how to make it. This O(N^2) algorithm still seems to be eating up all of my CPU power though.

Here is a LINK (google drive, go to File > download, keep .Exe with the content folder, you will need XNA Framework 4.0 Redist. if you don't already have it) to the current version of my game. Left click makes a planet, right click removes the last planet. Mouse moves the camera, scroll wheel zooms in and out. Watch the FPS and Planet Count to see what I mean about performance issues past 70 planets. (ALL 70 planets must be moving, I've had 100 stationary planets and only 5 or so moving ones while still having 300 fps, the issue arises when 70+ are moving around)

After 70 planets are made, performance tanks exponentially. With < 70 planets, I get 330 fps (I have it capped at 300). At 90 planets, the FPS is about 2, more than that and it sticks around at 0 FPS. Strangely enough, when all planets are stationary, the FPS climbs back up to around 300, but as soon as something moves, it goes right back down to what it was, I have no systems in place to make this happen, it just does.

I considered multithreading, but that previous question I asked taught me a thing or two, and I see now that that's not a viable option.

I've also thought maybe I could do the calculations on my GPU instead, though I don't think it should be necessary. I also do not know how to do this, it is not a simple concept and I want to avoid it unless someone knows a really noob friendly simple way to do it that will work for an n-body gravity calculation. (I have an NVidia gtx 660)

Lastly I've considered using a quadtree type system. (Barnes Hut simulation) I've been told (in the previous question) that this is a good method that is commonly used, and it seems logical and straightforward, however the implementation is way over my head and I haven't found a good tutorial for C# yet that explains it in a way I can understand, or uses code I can eventually figure out.

So my question is this: How can I make my gravity method more efficient, allowing me to use more than 100 objects (I can render 1000 planets with constant 300+ FPS without gravity calculations), and if I can't do much to improve performance (including some kind of quadtree system), could I use my GPU to do the calculations?