2

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

我有一个 Map 类，其中包含一组图块，因此，在 Map Update() 中，我只调用每个图块 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. 您能建议我进行任何其他类型的优化吗？

谢谢

4

1 回答 1

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) 复杂度，并且是潜在性能问题的明确标志。

通常，当您使用碰撞检测时，您可以通过减少基于已知事物可能发生碰撞的对象的数量来优化代码。

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

假设您将平铺数据存储在二维数组中。

var tiles = new int[32,32];

值 0 表示没有图块，值 1（或 > 0）表示图块是实心的。您还知道，当在屏幕上渲染图块时，它们是 64x64 像素。

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

    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) 复杂度）。显然，您还需要注意不要检查数组边界之外的内容，如果您的粒子大于单个像素，则可能还有其他一些细节需要处理，但您明白了。

于 2013-12-18T04:14:13.637 回答