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

Question

给定二维空间中的一组 n 个粒子，其中每个粒子都对集合中的所有其他粒子产生吸引力，吸引力与它们之间距离的平方反比成正比，你能想象出任何巧妙的方法来计算每个粒子所受的合力，无需执行 n^2 距离计算？

来 self 程序的 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 的粒子被更新。这导致性能有所提高，但当然是以准确性为代价的。

我正在尝试做的类似于重力计算。有人在 this thread建议使用复数并使用等式:

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

但是，我不知道 z 指的是什么，也无法在其他任何地方找到对这个等式的引用。

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

Answer 1

1. 首先，力是对称的，因此您只需计算 n 的平方除以 2。

2. 其次，力随着距离的平方而下降，因此您可以通过设置一个阈值来近似计算，超过该阈值就无需计算。您只需要在一维中检查它。如，如果 x - x' < t 和 y - y' < t 计算，否则否。

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

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

5. 人们可能会认为群众也做出了贡献。进一步的优化是，如果质量太小，则不计算的阈值 t 也可以缩小。

6. 您可能还想量化粒子的平移，这样任何低于最小值的移动都不会被记录为坐标变化。

希望这对您有所帮助!