数万个粒子上的更快嵌套循环

Question

我正在 Unity 环境中进行一些视觉艺术研究。我正在尝试实现与此处解释的差分线增长非常相似的东西， 但我主要担心的是，在算法中的某个地方，每个节点都应该检查每个其他节点以查看它的接近程度，并根据所有这些构建排斥力阵列附近的粒子。

这是我的代码片段：

   public void Differentiate()
    {
        int c = nodes.Count;                                 
        Vector3[] repulsionForces = new Vector3[c];

        for (int i = 0; i < c ; i++)
        {

            // Construct nearbies
            List<DifferentialNode> nearby = new List<DifferentialNode>();
            foreach(DifferentialNode n in nodes)
            {
                float d = Vector3.Distance(n.position, nodes[i].position);
                if (d < 5)
                {
                    nearby.Add(n);
                }
            }
            // Get Forces
            Vector3 repulsionForce = nodes[i].RepulsionForce(nearby);

            // Limit Forces
            repulsionForce = Vector3.ClampMagnitude(repulsionForce, maxForce);

            // Apply Multipliers
            repulsionForce *= Repulsion;

            // Put Forces into Array
            repulsionForces[i] = repulsionForce;
        }

        for (int i = 0; i < c; i++)
        {
            nodes[i].applyForce(repulsionForces[i]);
            nodes[i].update();
            nodes[i].velocity = new Vector3(0, 0, 0);
        } 

这是我在 DifferentialLineNode 类中的 RepulsionForce() 函数

public Vector3 RepulsionForce(List<DifferentialNode> nearby)
{
    Vector3 repulsionForce = new Vector3();

    foreach (DifferentialNode n in nearby)
    {
        // calculate distance between both
        float d = Vector3.Distance(n.position, this.position);
        // calculate difference and divide by exp(d) to get less influence when far
        Vector3 diff = ( this.position - n.position ) / (Mathf.Exp(d)); 
        repulsionForce += diff;
    }
    repulsionForce /= (float)nearby.Count;
    repulsionForce.Normalize();

    return repulsionForce;
}

一旦我开始游戏，一切都会下降到 1fps 以下，我认为嵌套循环是它的来源，因为 n^n 的复杂性。我一直在研究 Octree / KdTree 实现，但找不到任何解释的代码。还有其他路线吗？超过一个 ？可以任意组合吗？非常感谢

Answer 1

每个点计算距离内的点都是O(n^2)，所以如果粒子数量大，性能下降也就不足为奇了。但这可以很容易地改进。可以使用多种搜索结构选项：

• 3D 网格。这应该很容易实现，只需创建一个 3D 列表数组。选择合适的 bin 大小，以便您有固定数量的 bin 进行迭代。这样做的主要缺点是内存使用量，如果模拟中存在大的空洞且没有粒子，这一点将更加显着。
• 稀疏八叉树。如果点的间距不均匀，则与网格相比的主要优势是更好的内存使用。如果您需要搜索任意距离，它也会更好地扩展。缺点是实现更复杂。
• 树。这是一个非常好的数据结构，因为它使用相当少的内存，可以用连续内存实现，并且可以很好地扩展。一个缺点是很难处理位置的变化。实现也比网格更复杂。

对于网格或八叉树，可以在 bin 之间移动点。对于 kd 树，重建树可能会更好。任何选项都应将搜索时间从 O(N^2) 减少到 O(n log n)。

Given the context of your question I would recommend starting with a simple 3D grid. If this is not sufficient I would consider using a kd tree. I would avoid combining datastructures unless there is some specific reason to do this. Octrees and kdtrees should scale well enough.

I would recommend trying some profiling tools to check what actually takes time. I would also recommend setting up some controlled environment to run the algorithm on a known dataset and measure the time. Benchmark.Net is the gold standard, but a simple stopwatch should be fairly good when measuring large changes.

There should also be some opportunity for micro-optimizations. Avoid creating lists in a tight loop, if needed, create a list that is reused. Avoid repeated operations. Avoid expensive operations. Prefer arrays and lists over other collections since the runtime has special optimizations for these. Prefer for instead of foreach since the former may avoid the creation of an iterator object.