c# - XNA 优化 - 循环展开？

Question

我正在制作 XNA 游戏，我想知道是否有优化某些循环的方法。例如:

我有一个 Map 类，它包含一个图 block 集合，因此，在 Map Update() 中我只调用每个图 block Update()

    // Update method in Map Class
    public void Update()
    {
        for (int index = 0; index < tiles.Count; index++)
        {
            tiles[index].Update();
        }
    }

这很好用，但是，对于一些较大的填充对象，它可能会变得最糟糕，例如 Particle 类，其中每个粒子都由 ParticleManager 类(包含粒子集合)管理，因此:

    // Update method in ParticleManager class
    public void Update()
    {
        for (int index = 0; index < particle.Count; index++)
        {
            particle[index].Update();
        }
    }

    //Update Method in Particle class
    public void Update()
    {
        for (int index = 0; index < Map.tiles.Count; index++)
        {
             CheckCollitions(Map.tile[index], this);
        }
    }

ParticleManager 为每个粒子循环，每个粒子检查每个 Tile 的碰撞。因此，如果您有 20 个粒子和 100 个 Tiles，它将进行大量计算:

20 loops cycles * 100 loops cycles

这就是为什么我在考虑一些优化，比如循环展开但是，我不知道它是否适用于(我认为不是)未定义长度的循环(因为编译器在编译时不知道这些循环长度)

总结:

1. 可以使用循环展开来优化这些循环吗？
2. 你能给我一些其他优化类型的建议吗？

谢谢

Answer 1

首先，循环展开是一种微观优化，不会带来很多好处。在绝对需要之前不要打扰。

更重要的是，优化代码的方法更多地是关于所使用的数据结构和算法，而不是迭代集合的速度。

在您的特定示例中，您正在有效地执行此操作..

    for (int p = 0; p < particle.Count; p++)
    {
        for (int t = 0; t < Map.tiles.Count; t++)
        {
                 CheckCollitions(Map.tile[t], particle[p]);
        }
    }

像这样的嵌套循环表示复杂度为 O(n^2)，是潜在性能问题的明确标志。

通常，当您使用碰撞检测时，您可以根据已知信息减少可能发生碰撞的对象数量，从而优化代码。

例如，我假设图 block 不会四处移动，而是以统一的网格布局。我也可以假设颗粒非常小。

假设您将图 block 数据存储在二维数组中。

var tiles = new int[32,32];

值为 0 表示没有瓷砖，值为 1(或 > 0)表示瓷砖是实心的。您还知道，当图 block 在屏幕上呈现时，它们是 64x64 像素。

这意味着，您可以使用简单的数学运算非常快速地对任何图 block 进行基本碰撞测试。

    for (int p = 0; p < particle.Count; p++)
    {
        var tileWidth = 64;
        var tileHeight = 64;
        var particlePosition = particle[p].Position;
        var tx = particlePosition.X / tileWidth; 
        var ty = particlePosition.Y / tileHeight;

        var tile = tiles[tx, ty];

        if(tile == 0)
        {
            // no collision
        }
        else
        {
            // collision detected
        }
    }

在这一点上，您确切地知道粒子位置落在数组中的哪个瓦片中并删除了内部循环(有效地将其降低到 O(n) 复杂度)。显然，您还需要注意不要检查数组的边界之外，如果您的粒子大于单个像素，可能还有一些其他细节需要处理，但您明白了。