计算大量粒子之间类似引力的力最快的方法是什么？

Question

计算大量粒子之间类似引力的力最快的方法是什么？

5

假设有一组在二维空间中的 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());
            }
        }
    }

在我的程序中（使用XNA框架和Farseer物理引擎），暴力方法只能模拟大约150个粒子，就会遇到性能问题。

如果没有其他方法，这段代码该如何优化，或者该如何作弊？我已经尝试了按照每个粒子的基础上随机调用calculateAttractions()函数，以便在任何给定时间内只有大约1/3的粒子实际上正在更新。这导致了一些性能上的改进，但当然牺牲了精度。

我的目标类似于重力计算。在这个线程中，有人建议使用复数并使用以下公式：

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

然而，我不知道z指的是什么，也找不到这个方程在其他地方的参考资料。

编辑：虽然我已经接受了下面一个回答，但我最终使用了没有人提到的解决方案：查找表。基本上，我预先计算了所有距离（以1像素为分辨率）内任何方向上2000像素之外的另一粒子对一个粒子施加的力。因此，可以在没有任何运行时距离计算的情况下确定力。虽然这不是一个精确的解决方案，但失真是不可感知的，并且它使我能够将模拟粒子的数量增加三倍（现在数量受物理引擎而不是n-体问题限制）。

- Madison Brown

8

这被称为N体问题。对于这个问题有几种近似的模拟方法。搜索“N体模拟”，你会找到很多结果。 - Khaled Alshaya

谢谢，这很有帮助。您对使用复数进行计算有什么想法吗？ - Madison Brown

大多数大规模天体物理模拟使用四叉树/八叉树。近距离粒子之间的力被精确计算。远距离单元格之间的力则使用快速多极分解进行近似评估。 - Hristo Iliev

3个回答

2

要精确计算所有 N 粒子之间的力，必须确定 O(N^2) 粒子-粒子距离。没有比 O(N^2) 更好的方法，但是你可以通过注意对称性（即 dist(i,j) == dist(j,i)）实现 (1/2)N^2。

通过欺骗，你可以做到几乎相同的事情，而只计算“附近”的粒子相互作用（这些粒子的幅度最大），并利用空间索引结构。

其中一个想法是利用四叉树（3D中的八叉树），以使您能够有效地确定一小组与特定粒子“接近”的M粒子。在计算粒子力时，您只考虑这个缩小的集合。您需要尝试不同的阈值来确定集合M是否足够大--显然，小集合将非常快但不准确，大集合将准确但慢。

随着粒子移动，空间索引也需要更新。使用四叉树的一种方法是设置每个叶子的上限和下限粒子数，并在违反这些约束时细化树。

总体而言，根据相当均匀分布的粒子集，树的高度将为O(log(N))，您应该从基于树的方法中期待O(N*log(N))的性能。

- Darren Engwirda

1

既然你提到作弊是可以的，那么通过计算单个粒子与整个组（包括粒子本身）的质心之间的吸引力，可能会伪造事物。这将是一个O(2N)问题（N代表质心，加上每个粒子经历的力量另外一个N）。对于某些粒子排列方式，这可能会与实际运动定律显著偏离，但对于大多数（随机）初始排列，这可能是一个合理的近似。

- Randall Cook

1

我之前尝试过这个方法。不幸的是，当你有多个粒子分组时，这种方法就会失败。 - Madison Brown

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cris Stringfellow · Accepted Answer

首先，力是对称的，因此只需要进行n平方除以2次计算。
其次，力随着距离的平方衰减，因此您可以通过设置阈值来近似计算。在一维中只需要检查这个阈值。也就是说，如果x - x' < t且y - y' < t，则进行计算，否则不进行计算。
您可以使用两个占用树将粒子放入小正方形或桶中，并且仅针对每个桶中的成对粒子执行k平方除以2次距离计算。另一个树向上和向左移动，以处理相邻正方形边界上的任何成对。对于第二棵树，不要重复第一棵树中进行的距离计算。
更新之间，可能会有一些粒子不改变位置，因此您不需要重新计算涉及自上次更新以来保持静止的两个粒子的任何力。
可以假设质量也会产生影响。进一步的优化是，如果质量太小，则不计算的阈值t也会缩小。
您还可以量化粒子的平移，以便任何低于最小值的移动不会被视为坐标的更改。

希望这可以帮助您！