5

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

从我的程序的粒子类：

    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 指的是什么，我在其他任何地方都找不到这个方程的参考。

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

4

3 回答 3

8

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

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

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

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

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

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

希望这可以帮助！

于 2013-01-27T07:07:35.557 回答
2

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

要通过作弊来做几乎相同的事情，您可以只计算“附近的”粒子相互作用（无论如何这些都是最大幅度的）并利用空间索引结构。

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

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

总体而言，基于合理分布的粒子集，树的高度将是O(log(N))并且您应该期望O(N*log(N))基于树的方法的性能。

于 2013-01-27T07:07:53.357 回答
1

既然你提到作弊是可以的，那么通过计算单个粒子与整个群体（包括粒子本身）的质心之间的吸引力，就有可能造假。这将是一个 O(2N) 问题（N 代表质心，加上另一个 N 代表每个粒子的受力）。对于某些粒子排列，这可能会显着偏离实际的运动定律，但对于大多数（随机）初始排列来说，它可能是一个合理的近似值。

于 2013-01-27T07:07:45.897 回答