Движок 2D-частиц не может обрабатывать более 450 частиц. Почему? (XNA)

ОБНОВЛЕНИЯ; - изменение j=0 на j=i позволило использовать до 700 частиц с плавной частотой кадров

Я пытаюсь смоделировать 2D-воду с сотнями частиц, у которых есть Vector2, объявляющие их положение, и Vector2 для их скорости.

Когда дело доходит до обнаружения столкновений, моей программе не нравится иметь более 450 частиц, несмотря на то, что она использует только теорему Пифагора.

Вот обнаружение столкновений в основном классе;

        for (int i = 0; i < particleList.Count; i++)
            {
                for (int j = 0; j < particleList.Count; j++)
                {
                    if (distanceBetween(particleList[i].position, particleList[j].position) < reactDistance)
                    {
                        if (particleList[i].position.X > particleList[j].position.X) //x axis
                        {
                            particleList[i].velocity.X += repelSpeed;
                            particleList[j].velocity.X -= repelSpeed;

                            particleList[i].position.X -= attractSpeed;
                            particleList[j].position.X += attractSpeed;
                        }
                        else
                        {
                            particleList[i].velocity.X -= repelSpeed;
                            particleList[j].velocity.X += repelSpeed;

                            particleList[i].position.X += attractSpeed;
                            particleList[j].position.X -= attractSpeed;
                        }

                        if (particleList[i].position.Y > particleList[j].position.Y) //y axis
                        {
                            particleList[i].velocity.Y += repelSpeed;
                            particleList[j].velocity.Y -= repelSpeed;

                            particleList[i].position.Y -= attractSpeed;
                            particleList[j].position.Y += attractSpeed;
                        }
                        else
                        {
                            particleList[i].velocity.Y -= repelSpeed;
                            particleList[j].velocity.Y += repelSpeed;

                            particleList[i].position.Y += attractSpeed;
                            particleList[j].position.Y -= attractSpeed;
                        }
                    }
                }
            }

Вот метод DistanceBetween(v1, v2);

        public float distanceBetween(Vector2 a, Vector2 b)
    {
        float xDist, yDist, distTo;
        if (a.X > b.X) //x axis
        {
            xDist = a.X - b.X;
        }
        else
        {
            xDist = b.X - a.X;
        }

        if (a.Y > b.Y) //y axis
        {
            yDist = a.Y - b.Y;
        }
        else
        {
            yDist = b.Y - a.Y;
        }
        distTo = (float)(Math.Sqrt((xDist * xDist) + (yDist * yDist)));
        return distTo;
    }

Vector2.Distance(v1, v2) не производит видимых изменений производительности.

Если вам интересно, что, черт возьми, делает привлекательность скорости; это моя неудачная попытка сформировать коллекции воды. Я не уверен, как это сделать.

В конечном итоге я хочу что-то вроде этого: http://grantkot.com/MPM/Liquid.html


person ShadowByte    schedule 02.11.2013    source источник
comment
Поскольку частицы первого цикла уже проверены, не может ли второй цикл начаться как j=i, а не как j=0?   -  person Mike B    schedule 02.11.2013
comment
Вау, ты прав. Теперь программа позволяет использовать до 700 частиц с плавной частотой кадров!   -  person ShadowByte    schedule 02.11.2013
comment
Вы также можете попробовать сделать это параллельно. msdn.microsoft.com/en-us/library/   -  person Lasse    schedule 02.11.2013
comment
Кажется неясным, как я могу передать i и j в метод, если они не объявлены в Parallel.For(0, ParticleList.Count, Collision());   -  person ShadowByte    schedule 02.11.2013
comment
См. примеры внизу страницы, на которую я дал ссылку. Лямбда-выражение вполне может сработать для вас.   -  person Lasse    schedule 02.11.2013
comment
'Parallel.For(0, N, i => { // Выполняем работу. });' Что на самом деле здесь происходит? Страница не объясняет по крупицам, что она на самом деле делает.   -  person ShadowByte    schedule 02.11.2013
comment
Parallel.For берет start, end, loop. эквивалентный цикл for будет: for(int i = start; i < N; i++) { loop(i); }. Преимущество в том, что Parallel.For может выполнять loop в нескольких потоках вместо одного, что ускоряет процесс.   -  person Femaref    schedule 02.11.2013
comment
Но как мне на самом деле написать это с помощью i и j?   -  person ShadowByte    schedule 02.11.2013
comment
blogs.msdn.com/b/csharpfaq/archive/2010/06/01/   -  person Lasse    schedule 03.11.2013


Ответы (1)


Хотя есть некоторые аспекты производительности, которые можно улучшить, в конечном счете именно хранение частиц затмит любые усилия.

Ваш алгоритм O(n^2), так как для каждой частицы вы снова перебираете весь список частиц. Для n = 700 это 700*700 = 490000 выполнения цикла. Кроме того, многие частицы проверяются i слишком часто. Если вы начнете внутренний цикл с j=i, вы получите заметное ускорение.

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

Кроме того, вместо вычисления sqrt для каждого расстояния возведите в квадрат расстояние, с которым вы сравниваете:

distTo = (xDist * xDist) + (yDist * yDist);
...

if(distanceBetween(particleList[i].position, particleList[j].position) < reactDistance * reactDistance)

Вы даже можете предварительно вычислить это перед циклами, чтобы у вас не было этих накладных расходов каждый раз.

person Femaref    schedule 02.11.2013
comment
Спасибо. Переход на j=i, как предложил Майк Б., теперь позволяет использовать до 700 частиц с плавной частотой кадров. - person ShadowByte; 02.11.2013
comment
Я посмотрю на Quadtrees, если это всего лишь пластырь. Большое спасибо. - person ShadowByte; 02.11.2013
comment
На YouTube нет удовлетворительных руководств по Quadtree. Я понял идею, и она очень эффективна, но никто не объясняет, как ее запрограммировать настолько хорошо, чтобы я начал к ней приближаться. После многих попыток оптимизации моя программа поддерживает примерно 850 частиц при 50 кадрах в секунду, что вполне удобно. - person ShadowByte; 03.11.2013
comment
В связанной статье в Википедии есть довольно хорошее введение в отношении наиболее важных методов (insert и range), которые подробно описаны в виде псевдокода. Вам придется заполнить остальные. - person Femaref; 03.11.2013