Оптимизация XNA - развертывание цикла?

Question

Я делаю игру XNA и мне интересно, есть ли способ оптимизировать некоторые циклы. Например:

У меня есть класс Map, который содержит коллекцию плиток, поэтому в обновлении карты () я просто вызываю каждую плитку 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. Можете ли вы посоветовать мне другой тип оптимизации?

Спасибо

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) и являются верным признаком потенциальных проблем с производительностью.

Обычно, когда вы работаете с обнаружением столкновений, вы можете оптимизировать код, уменьшив количество объектов, которые могут столкнуться, основываясь на вещах, которые вы уже знаете.

Например, я предполагаю, что плитки не перемещаются и располагаются в единой сетке. Я также могу предположить, что частицы очень маленькие.

Допустим, вы храните данные плитки в двухмерном массиве.

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)). Очевидно, вам также нужно быть осторожным, чтобы не проверять границы массива, и, возможно, вам придется столкнуться с некоторыми другими деталями, если ваши частицы больше одного пикселя, но вы поняли идею.