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 はすべてのパーティクルに対してループし、各パーティクルはすべてのタイルの衝突をチェックします。したがって、20 個のパーティクルと 100 個のタイルがある場合、多くの計算が行われます。

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) の複雑さを示しており、潜在的なパフォーマンスの問題の確実な兆候です。

通常、衝突検出を使用する場合、既知の情報に基づいて衝突する可能性のあるオブジェクトの数を減らすことで、コードを最適化できます。

たとえば、タイルが動き回らず、均一なグリッドに配置されているとします。また、粒子が非常に小さいと仮定することもできます。

タイル データを 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 に答える