给定二维空间中的一组 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 体问题的程度。 )
最佳答案
首先，力是对称的，因此您只需计算 n 的平方除以 2。
其次，力随着距离的平方而下降，因此您可以通过设置一个阈值来近似计算，超过该阈值就无需计算。您只需要在一维中检查它。如，如果 x - x' < t 和 y - y' < t 计算，否则否。
您可以使用两棵占用树将粒子放入小方 block 或桶中，并且只对一棵树中每个桶中的粒子对进行 k 平方除以 2 的距离计算。另一棵树向上和向左平移，以处理相邻正方形边界上的任何对。对于第二棵树，不要重复您在第一棵树中所做的距离计算。
在更新之间，某些粒子可能不会改变它们的位置，因此您不需要再次计算自上次更新以来涉及两个静止粒子的任何力。
人们可能会认为群众也做出了贡献。进一步的优化是，如果质量太小，则不计算的阈值 t 也可以缩小。
您可能还想量化粒子的平移，这样任何低于最小值的移动都不会被记录为坐标变化。
希望这对您有所帮助!
关于c# - 计算大量粒子之间经历的类似重力的最快方法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14545140/