计算大量粒子之间经历的类似重力的最快方法？

Question

给定一组二维空间中的n个粒子,其中每个粒子对集合中所有其他粒子的吸引力,与它们之间的距离的平方成反比,你能想象任何巧妙的计算净力的方法吗？每个粒子,不进行n ^ 2距离计算？

从我的程序的Particle类:

    public void calculateAttractions(List<Particle> entities)
    {
        foreach (Particle p in entities)
        {
            if (!p.Equals(this))
            {
                Vector2 dx = this.Position - p.Position;
                this.ApplyForce(-dx / dx.LengthSquared());
            }
        }
    }

在遇到性能问题之前,暴力方法只能在我的程序中模拟~150个粒子(使用XNA框架和Farseer物理引擎).

如果没有其他方法,这个代码怎么可能被优化,或者我怎么可能作弊？我已经尝试在粒子到粒子的基础上随机调用calculateAttractions(),这样在任何给定的时间内只有大约1/3的粒子被实际更新.这导致性能有所改善,但当然是以准确性为代价.

我要做的是类似于引力计算.有人在这个线程建议用复数工作,并用公式:

(z-z')/abs(z-z')**3

但是,我不知道z指的是什么,我无法在其他任何地方找到这个等式的参考.

编辑:虽然我已经接受了下面的答案,但我最终使用了一个没人提到的解决方案:查找表.基本上,我预先计算所有距离(分辨率为1像素)的另一个粒子在一个粒子上施加的力,在任何方向上最多可达200​​0像素.然后可以在没有任何运行时距离计算的情况下确定力.虽然它不是一个精确的解决方案,但是失真是不可感知的,并且它允许我将模拟粒子的数量增加三倍(到现在数量被物理引擎而不是n体问题限制的程度. )

Answer 1

1. 首先,力是对称的,所以你只需要n平方除以2计算.

2. 第二个上升力随着距离的平方而下降,因此您可以通过设置一个阈值来近似,超过该阈值就无需计算.您只需要在1维中查看此内容.如中,如果x - x'<t和y - y'<t计算,否则不计算.

3. 您可以使用两个占用树将粒子放入小方块或桶中,并且只对一棵树中每个桶中的对进行k平方除以2的距离计算.另一棵树向上和向左平移,以处理相邻方块边界上的任何对.对于第二棵树,不要重复您在第一棵树中所做的距离计算.

4. 在更新之间,某些粒子可能不会改变它们的位置,因此,自上次更新以来,您不需要再次计算任何涉及两个粒子静止的力.

5. 人们可以认为群众也有贡献.进一步的优化是,如果质量太小,那么不计算的阈值t也会缩小.

6. 您可能还希望量化粒子的平移,以便低于最小值的任何移动都不会记录为坐标的更改.

希望这可以帮助!