2D particle engine can't handle over 450 particles. Why? (XNA)

Question

UPDATES; -changing j=0 to j=i allowed up to 700 particles with a smooth frame rate

I am trying to simulate 2D water with hundreds of particles that have Vector2s declaring their position and a Vector2 for their velocity.

When it comes to collision detection, my program dislikes having more than 450 particles despite only using Pythagoras' theorem.

Here's the collision detection in the main class;

        for (int i = 0; i < particleList.Count; i++)
            {
                for (int j = 0; j < particleList.Count; j++)
                {
                    if (distanceBetween(particleList[i].position, particleList[j].position) < reactDistance)
                    {
                        if (particleList[i].position.X > particleList[j].position.X) //x axis
                        {
                            particleList[i].velocity.X += repelSpeed;
                            particleList[j].velocity.X -= repelSpeed;

                            particleList[i].position.X -= attractSpeed;
                            particleList[j].position.X += attractSpeed;
                        }
                        else
                        {
                            particleList[i].velocity.X -= repelSpeed;
                            particleList[j].velocity.X += repelSpeed;

                            particleList[i].position.X += attractSpeed;
                            particleList[j].position.X -= attractSpeed;
                        }

                        if (particleList[i].position.Y > particleList[j].position.Y) //y axis
                        {
                            particleList[i].velocity.Y += repelSpeed;
                            particleList[j].velocity.Y -= repelSpeed;

                            particleList[i].position.Y -= attractSpeed;
                            particleList[j].position.Y += attractSpeed;
                        }
                        else
                        {
                            particleList[i].velocity.Y -= repelSpeed;
                            particleList[j].velocity.Y += repelSpeed;

                            particleList[i].position.Y += attractSpeed;
                            particleList[j].position.Y -= attractSpeed;
                        }
                    }
                }
            }

Here's the distanceBetween(v1, v2) method;

        public float distanceBetween(Vector2 a, Vector2 b)
    {
        float xDist, yDist, distTo;
        if (a.X > b.X) //x axis
        {
            xDist = a.X - b.X;
        }
        else
        {
            xDist = b.X - a.X;
        }

        if (a.Y > b.Y) //y axis
        {
            yDist = a.Y - b.Y;
        }
        else
        {
            yDist = b.Y - a.Y;
        }
        distTo = (float)(Math.Sqrt((xDist * xDist) + (yDist * yDist)));
        return distTo;
    }

Vector2.Distance(v1, v2) produces no visible performance changes.

If you're wondering what on Earth attractSpeed does; it's my poor attempt at trying to form collections of water. I'm not sure how to do it.

Ultimately I want something like this: http://grantkot.com/MPM/Liquid.html

Answer 1

While there are some performance aspects that can be improved, ultimately, it's the storage of the particles that will dwarf any efforts.

Your algorithm is O(n^2), as for each particle, you iterate over the whole particle list again. For n = 700, that's 700*700 = 490000 executions of the loop. Also, many particles are checked i too often. If you start the inner loop at j=i, you'll gain a noticeable speed up.

However, this will only be a bandaid in my opinion. You should look into a more efficient storage of your particles, namely the Quadtree.

Also, instead of calculating a sqrt for each distance, square the distance you compare against:

distTo = (xDist * xDist) + (yDist * yDist);
...

if(distanceBetween(particleList[i].position, particleList[j].position) < reactDistance * reactDistance)

You can even precalculate that before the loops so you don't have that overhead every time.