数以万计的粒子的快速嵌套循环

Question

我正在Unity环境中进行一些视觉艺术研究。我正在尝试实现与差异线增长as explained here非常相似的目标但我主要担心的是，在算法中的某个位置，每个节点都应检查每个其他节点以了解其接近程度，并从所有这些邻近粒子构造斥力阵列。

这是我的代码的片段：

   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);
        } 

这是我的RepulsionForce（）函数在DifferentialLineNode类中

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

您应考虑将for而不是foreach用于列表，例如， here当您为性能编码时。不过，我认为您的问题更多是结构性问题，而不是与此类细节相关的问题。

[我建议您查看Quadtrees，例如按this implementation，将您的总面积分成多个部分，并将每个粒子与一个部分相关联。要找到邻居，您只需遍历树。

Answer 2

计算最近点为O（n ^ 2），因此如果粒子数量很大，性能会下降也就不足为奇了。但这可以很容易地得到改善。可以使用几种搜索结构选项：

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

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

鉴于您的问题，我建议从一个简单的3D网格开始。如果这还不够，我会考虑使用kd树。除非有特定原因，否则我将避免合并数据结构。八叉树和kdtrees应该足够好扩展。

我建议尝试一些profiling tools来检查实际花费的时间。我还建议您设置一些受控环境，以便在已知数据集上运行算法并测量时间。 Benchmark.Net是黄金标准，但是在测量大的变化时，简单的秒表应该是相当不错的。

也应该有一些进行微优化的机会。避免在紧密循环中创建列表，如果需要，请创建可重复使用的列表。避免重复操作。避免昂贵的操作。比其他集合更喜欢数组和列表，因为运行时对它们进行了特殊的优化。首选for而不是foreach，因为前者可以避免创建迭代器对象。