10 января 2012 в 14:48

Моделирование большого количества взаимодействующих друг с другом частиц из песочницы tutorial

Рассмотрим ситуацию, когда необходимо обрабатывать столкновения между объектами. Как вы в этом случае поступите? Вероятно, самым простым решением будет проверить каждый объект с каждым другим объектом. И это правильное решение, и все будет замечательно до тех пор пока объектов не много. Как только их станет порядка нескольких тысяч, вы заметите, что все стало как-то медленно работать. А если частиц несколько десятков тысяч или сотен? Тогда все замрет. Вот здесь уже интересно, на какие хитрости и оптимизации вы пойдете, чтобы решить такую проблему.

Для простоты, будем рассматривать 2D случай, частицы круглые, радиус частиц у всех одинаковый.

Содержание


1. Обзор алгоритмов
1.1. Полный перебор
1.2. Sweep & Prune
1.3. Регулярная сеть
2. Некоторые оптимизации
2.1. Sweep & Prune
2.2. Регулярная сеть
3. Сравнение скорости выполнения
4. Приложение (программа и исходный код)
5. Заключение



1. Обзор алгоритмов


1.1. Полный перебор

Это самый простой и в то же время самый медленный из всех возможных способов. Идет проверка между всеми возможными парами частиц.

    void Update()
    {
        for (int i = 0; i < NUM_P; ++i) {
            for (int j = i + 1; j < NUM_P; ++j) {
                Collision(&_particles[i], &_particles[j]);
            }
        }
    }

Сложность: O(n ^ 2)

Плюсы:
* Очень прост в понимании и реализации
* Не чувствителен к разным размерам частиц
Минусы:
* Самый медленный из всех

1.2. Sweep & Prune

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

Попробую описать работу алгоритма в картинках.
Начальное состояние:

Как видим, частицы не упорядочены.
После сортировки по левой границе частицы(позиция по X минус радиус частицы), получаем следующую картину:

Теперь можно приступать к перебору. Проверяем каждую частицу с каждой другой частицей до тех пор пока правая граница первой частицы больше левой границы второй частицы.

Рассмотрим на примере.
0 частица проверит столкновение с 1 и 2:

1 со 2 и 3.
2 только с 3.
3 проверит столкновение с 4, 5 и 6:

Думаю, что суть ясна.

Моя реализация данного алгоритма:

    void Update()
    {
        qsort(_sap_particles, NUM_P, sizeof(Particle *), CompareParticles);

        for (int i = 0; i < NUM_P; ++i) {
            for (int j = i + 1; j < NUM_P && _sap_particles[i]->pos.x + RADIUS_P > _sap_particles[j]->pos.x - RADIUS_P; ++j) {
                Collision(_sap_particles[i], _sap_particles[j]);
            }
        }
    }

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

Так же этот алгоритм можно применить для более сложных объектов, в этом случае следует использовать их AABB(Axis-Aligned Bounding Box, минимальный ограничивающий прямоугольник).

Сложность: O(n ^ 2) — в худшем случае, O(n * log(n)) — в среднем случае

Плюсы:
* Прост в реализации
* Не чувствителен к разным размерам частиц
* Хорошая производительность
Минусы:
* Требуется немного времени, чтобы понять алгоритм

1.3. Регулярная сеть

Как вы, вероятно, уже догадались из названия, суть алгоритма сводится к тому, что все пространство делится на равномерную сеть из маленьких квадратиков, размер которых равен диаметру частицы. Каждый такой квадратик(ячейка) этой сети представляет собой массив.
Выглядеть это может, например, так:
    const int _GRID_WIDTH = (int)(WIDTH / (RADIUS_P * 2.0f));
    const int _GRID_HEIGHT = (int)(HEIGHT / (RADIUS_P * 2.0f));

    std::vector<Particle *> _grid[_GRID_WIDTH][_GRID_HEIGHT];

На каждой итерации главного цикла эта сеть очищается и заново заполняется. Алгоритм заполнения предельно прост: индекс ячейки частицы вычисляется путем деления обеих координат на диаметр частицы и отбрасыванием дробной части. Пример:
    int x = (int)(_particles[i].pos.x / (RADIUS_P * 2.0f));
    int y = (int)(_particles[i].pos.y / (RADIUS_P * 2.0f));

Таким образом, для каждой частицы необходимо вычислить индекс и внести ее в ячейку с этим индексом(добавить элемент в массив).
Теперь остается только пройтись по каждой ячейке и проверить все ее частицы со всеми частицами соседних, окружающих ее 8 ячеек, при этом не забыв проверить с самой собой.

Это можно сделать так:
    void Update()
    {
        for (int i = 0; i < _GRID_WIDTH; ++i) {
            for (int j = 0; j < _GRID_HEIGHT; ++j) {
                _grid[i][j].clear();
            }
        }

        for (int i = 0; i < MAX_P; ++i) {
            int x = (int)(_particles[i].pos.x / (RADIUS_P * 2.0f));
            int y = (int)(_particles[i].pos.y / (RADIUS_P * 2.0f));

            _grid[x][y].push_back(&_particles[i]);
        }
    
        // далее много циклов проверки с соседними ячейками
    }

Сложность: O(n)

Плюсы:
* Самый быстрый из всех
* Прост в реализации
Минусы:
* Требуется дополнительная память
* Чувствителен к разным размерам частиц(требуется модификация)

2. Некоторые оптимизации


2.1. Sweep & Prune

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

Оптимальная ось OX:



2.2. Регулярная сеть

Оптимизация №1:
Используем более эффективное представление сети:
    const int _MAX_CELL_SIZE = 4;
    const int _GRID_WIDTH = (int)(WIDTH / (RADIUS_P * 2.0f));
    const int _GRID_HEIGHT = (int)(HEIGHT / (RADIUS_P * 2.0f));

    int _cell_size[_GRID_WIDTH * _GRID_HEIGHT];
    Particle *_grid[_GRID_WIDTH * _GRID_HEIGHT * _MAX_CELL_SIZE];

Думаю, не стоит говорить о том, что одномерный массив быстрее двумерного, а так же, что статический массив константной длины быстрее динамического std::vector, не говоря уже о том, что все это мы объединили. Так же пришлось завести еще один массив, который будет говорить о том сколько частиц находится в каждой из ячеек.
И да, мы ввели ограничение на количество частиц в ячейке, и это не совсем хорошо, т.к. грозит тем, что при сильном сдавливании, в ячейку потребуется записать значительно большее количество частиц, а т.к. это невозможно, некоторые столкновения не обработаются. Однако, при хорошем разрешении столкновений данной проблемы можно избежать.

Оптимизация №2
Вместо того, чтобы на каждой итерации главного цикла полностью очищать массив сетки, мы будем лишь вносить в нее те изменения, которые произошли.
Пробегаем по всем частицам каждой ячейки сети, вычисляем новый индекс частицы, и если он не равен текущему, то удаляем частицу из текущей ячейки и добавляем на свободное место в новую ячейку.
Удаление происходит путем записи на ее место последней частицы из этой же ячейки.
Вот мой код, который это реализует:
    for (int i = 0; i < _GRID_WIDTH * _GRID_HEIGHT; ++i) {
        for (int j = 0; j < _cell_size[i]; ++j) {
            int x = (int)(_grid[i * _MAX_CELL_SIZE + j]->pos.x / (RADIUS_P * 2.0));
            int y = (int)(_grid[i * _MAX_CELL_SIZE + j]->pos.y / (RADIUS_P * 2.0));
            
            if (x < 0) {
                x = 0;
            }
            if (y < 0) {
                y = 0;
            }
            if (x >= _GRID_WIDTH) {
                x = _GRID_WIDTH - 1;
            }
            if (y >= _GRID_HEIGHT) {
                y = _GRID_HEIGHT - 1;
            }

            // если индекс частицы изменился и в новой ячейке есть свободные места
            if (x * _GRID_HEIGHT + y != i && _cell_size[x * _GRID_HEIGHT + y] < _MAX_CELL_SIZE) {
                _grid[(x * _GRID_HEIGHT + y) * _MAX_CELL_SIZE + _cell_size[x * _GRID_HEIGHT + y]++] = _grid[i * _MAX_CELL_SIZE + j];
                // на место старой частицы записываем последнюю из этой же ячейки
                _grid[i * _MAX_CELL_SIZE + j] = _grid[i * _MAX_CELL_SIZE + --_cell_size[i]];
            }
        }
    }

Оптимизация №3
Мы используем проверку с соседними 8 ячейками. Это избыточно, достаточно проверять лишь 4 соседних ячейки.
Например, так:

С остальными ячейками проверка пройдет либо раньше, либо позже:


Оптимизация №4
Можно немного ускорить работу алгоритма увеличив локальность данных в памяти. Это позволит чаще читать данные из кеша процессора, и меньше обращаться к оперативной памяти. Но не стоит это делать на каждой итерации главного цикла, т.к. это убьет всю производительность, однако, можно проводить данную операцию, например, раз в секунду, или раз в несколько секунд, если сцена изменяется незначительно.
Увеличить локальность можно изменив порядок частиц в главном массиве, в соответствии с их расположением в сети.
Т.е. первые 4 частицы будут из 0 ячейки, следующие 4 из 1 и так далее.

3. Сравнение скорости выполнения


Количество частиц Bruteforce (мс) Sweep & Prune (мс) Регулярная сеть (мс)
1000 4 1 1
2000 14 1 1
5000 89 4 2
10000 355 10 4
20000 1438 28 7
30000 3200 55 11
100000 12737 140 23

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

4. Приложение (программа и исходный код)


http://rghost.ru/35826275

В архиве находится проект написанный в CodeBlocks, а так же бинарники под Linux, но т.к. для создания окна и вывода графики я использовал библиотеку ClanLib, то проект должен без проблем скомпилироваться и под Windows.

Управление в программе:
цифра 1 — Bruteforce
цифра 2 — Sweep & Prune
цифра 3 — Регуляная сеть
левая кнопка мышки — перемещение «расталкивалки».

5. Заключение


В данной статье приведен краткий обзор наиболее распространенных алгоритмов, использующихся для обработки столкновений. Однако, это не ограничивает область применения этих алгоритмов, ничто не мешает использовать их для любого другого взаимодействия. Основная задача, которую они на себя берут — это более удобное представление данных, для возможности быстрого отсеивания заранее неинтересных нам пар.
+143
11388
639
Elsedar 25,2

Комментарии (44)

+4
IgorMats, #
Просто шикарно! Огромное спасибо. Недавно как раз была задача ускорить работу самого тормознутого алгоритма из вышеприведенных. Сделал что-то похожее на Sweep & Prune, а теперь все стало на свои места! Пошел переписывать правильно. Спасибо!
+5
Elsedar, #
Рад, что вам понравилось).
+1
Pavelius, #
Я так понимаю это навеяно вот этим^
www.gamedev.net/blog/1350/entry-2253939-intelligent-2d-collision-and-pixel-perfect-precision/
или просто совпадение, но в любом случае почитать было интересно и познавательно.
Только и тут (и в той статье к слову тоже), лично мне не понравилось, что не хватает самого интересного: как использовать KD-tree для таких задач.
+1
Elsedar, #
Эту статью вижу первый раз.
KD-tree далеко не самый лучший вариант для collision detection, у них немного другая область применения. Их хорошо использовать, например, для поиска в пространстве или при рендеринге.
+2
Mrrl, #
Зависит от масштаба. Если размер частиц большой и клеток регулярной сетки получается немного, то сетка лучше. Если же частицы маленькие, распределены неравномерно, а область пространства большая — то я бы строил дерево. Конечно, алгоритмы там будут посложнее (рекурсивно спускаться, отслеживая 4 соседних ветки, а когда дошли до размера одной из частиц — полностью просматривать все оставшиеся ветки). И перемещать частицу из одной ячейки в другую совсем непросто. Но при малой плотности может быть выигрыш — и по времени, и по памяти.
+2
Elsedar, #
Мне кажется наоборот будет проигрыш, как по памяти, так и по времени работы алгоритма, причем на большем количестве частиц это будет сильнее заметно. Ведь это можно легко проверить опираясь на сложность алгоритмов.
+1
Mrrl, #
Сложность работы по сетке — не меньше O(N+M), где N — число частиц, а M — число ячеек сетки. Ведь их надо просмотреть… Конечно, можно просматривать только частицы, а ячейки вычислять по ним — тогда скорость будет O(N), но память все равно O(N+M). В случае дерева сложность будет порядка O(N*log(M)), где log(M) — глубина дерева, а память — O(N), если мы будем останавливать рост дерева когда в ветке останется одна точка. Если M много больше N, то дерево предпочтительнее.
+3
Pavelius, #
На сколько я знаю (хотя возможно ошибаюсь), большинство физических движков для поиска столкновений (особенно со статик геометрией) используют деревья.
Например farseer: farseerphysics.codeplex.com/SourceControl/changeset/view/94324#1436486
+1
Ravager, #
Думаю для Collision detection частиц регулярная сеть будет быстрее чем проверка пересечения с узлами Kd-tree. Но это скорее связано именно с частицами и 2d. В 3d для поиска коллизий между полигональными объектами подойдет KD-tree для быстрого отсечения потенциально невозможных объектов взаимодействия
+1
xander_unlim, #
спасибо, интересно было почитать, алгоритмами надо заниматься!
+4
Ogoun, #
Делал на основе регулярной сети, только со своими оптимизациями, сторона ячейки сети имеет размер 2^n, где n можно регулировать. При поиске столкновений координаты объектов преобразовывал из реальных в координаты сети по следующей формуле:
Xs=x>>n
Ys=y>>n, простым побитовым сдвигом, при совпадающих ячейках проверял столкновение. Способ работает очень быстро. Не требуется деление при переводе координат.
+1
Elsedar, #
Точно, раньше я тоже до этого доходил, но когда писал статью совсем забыл. Это действительно очень эффективно.
+1
limon_spb, #
А можно, пожалуйста, по-подробнее?
Не до конца понял про сторону = 2^n.

в описанном в статье алгоритме сторона ячейки равна диаметру частицы. А у вас сторона ячейки = 2^n чего? даже не знаю… пикселей?.. метров? :-)
+2
Elsedar, #
Имелось ввиду размерность сетки, на сколько частей каждую из сторон нужно поделить.
+1
limon_spb, #
ааа, т.е. все поле делится на 2^n по горизонтали и по вертикали?
Спасибо, теперь понял!
+1
Elsedar, #
Да, именно так.
+1
HomoLuden, #
Еще забыли диаграммы Вороного. Перекликается со «Sweep and Prune».
0
EvilGen, #
Диаграммы Вороного используют как один из методов построения sweepline algorithm. Sweepline это их единственное перекликание. В остальном там все гораздо сложнее и в этой статье не нужно…
+1
HomoLuden, #
> В остальном там все гораздо сложнее и в этой статье не нужно…
Сложнее для понимания или вычислительная нагрузка выше. Этот метод за «n*logn» построит граф, из которого для каждого узла известны соседние. Как минимум упоминания достоен, пусть и понять снаскока Fortune's Sweepline не всякому под силу.
0
HomoLuden, #
К тому же после первого построения этот подход упрощает обработку ситуации добавления еще одного узла и перемещения уже имеющихся.
0
EvilGen, #
Я конечно извиняюсь, но использовать Вороного для Моделирования большого количества взаимодействующих друг с другом частиц в рамках данной статьи — это как использовать 4-х физиков для забивания 3-х гвоздей — можно, но к чему это вообще?
0
HomoLuden, #
> Сложность: O(n ^ 2) — в худшем случае, O(n * log(n)) — в среднем случае
Я тоже извиняюсь, если ошибаюсь, но Fortune's Sweepline дает в худшем случае n*logn. Даже если я ошибаюсь, то в худшем случае будет все таже сложность n^2. Так что мне кажется очень даже уместно.
В представленном выше методе также используется сортировка. Алгоритм Фортуна, также ускоряется при выполнении операций над уже обработанным набором. Так что все то же с точки зрения нагрузки. А при имеющейся реализации сложность восприятия неактуальна.
–1
stab, #
> К тому же после первого построения этот подход упрощает обработку ситуации добавления еще одного узла и перемещения уже имеющихся.

> Алгоритм Фортуна, также ускоряется при выполнении операций над уже обработанным набором.

В смысле, у вас есть инкрементальный вариант алгоритма Фортуна? В студию!
0
HomoLuden, #
Думаю там все нативно имеется. Во всяком случае мое понимание таково: 2 кейса
1) Если нового узла не добавляется, то просто обновляем позиции и опять же проверяем расстояния с «соседями в логическом графе». Исключения в случаях когда должно произойти схлопывание одного из полигонов. Но не вижу проблемы чекать два положения узла — прошлое и новое.
2) Если добавляется узел — есть альтернативный Фортуновскому алгоритм разбиения области на полигоны вороного. Забыл как называется — что-то типа «половинного деления площади». Может найду попозже. Эта альтернатива позволяет вообще с нуля строить диаграмму. В нашем же случае нужно просто по графу найти узел в чью зону попадаем и построить новые границы полигона, обойдя по часовой стрелке или против границы полигона в который новый узел угодил.

Принципиальных сложностей не вижу.
0
stab, #
У меня мысли такие же, но мои попытки ускоренной реализации для движущихся точек, при готовом графе, ни к чему ускоренному не превели. Если много точек появляется-исчезает в небольшом «объёме», то одни и те же куски графа перестариваются много раз, при некоторый «плотности» обновлений, выгоднее просто пускать полное перестроение.

Вся прелесть Фортуна в том, что однажды обработав некоторую область, второй раз он ей не занимается. Поэтому и заинтересовал ваш опыт в этом вопросе, вот если бы был какой-то «локальный Фортун», который, при готовом графе и заданном списке удалённых-добавленных точек, умел интегрировать изменения в граф «за один проход», это было бы да.
+1
EvilGen, #
Удивительно доходчиво написанная статья на интересующую меня тему, спасибо!
+2
Deranged, #
Интересно, какой алгоритм пересчета используется в CortextCommand.
+1
EvilGen, #
Если действительно интересно можно начать копать здесь: habrahabr.ru/blogs/gdev/135794/
+1
Pand5461, #
А списки Верле плюс списки ячеек в этом случае можно использовать? Там тоже, вроде бы, сложность O(n*log(n)), и проблемы с разными размерами не должно быть.
+1
limon_spb, #
Очень интересно! Решал похожую задачку, решение нашел в книге по созданию игр, но там все было не так систематично. А тут все четко! Спасибо!
–7
egorinsk, #
Во-первых, не понимаю, зачем писать статью про 3 алгоритма, если не читая ее, понятно, что рабочий из них только один. Вы бы могли сократить объем и потраченное читателями время в 3 раза, если бы написали только про 1 алгоритм!

Во-вторых, у вас есть if () с комментарием // если индекс частицы изменился и в новой ячейке есть свободные места. А где else? А если свободных мест нет?

Не лучше ли (да конечно лучше, это же очевидно) сделать массив хеш-таблиц? В хеш-таблие хранятся ид всех частиц в данной клетке. В Си это вроде бы std::set или std::map, не знаю, что лучше для этой цели. Хотя, конечно, лучше или нет, можно проверить только бенчмарком. Наверно, если у нас в клетке несколько частиц, тупо перебирать массив может оказаться быстрее.

Вот код на явакрипте (так компактнее и понятнее) для этой задачи.

var clusters = new Array(xCellsCount * yCellsCount);

for (var i in particles) {
var particle = particles[i];
var oldClusterNumber = particle.cluster;
var newNumber = Math.floor(particle.x / xCellSize) + Math.floor(particle.y / yCellSize);
if (oldClusterNumber != newNumber) {
// переместим частицу
delete clusters[oldClusterNumber][particle.id];
clusters[newNumber] || (clusters[newNumber] = {});
clusters[newNumber][particle.id] = true;
}
}

Проверка на столкновение делается так:

for (var i in particles) {
var particle = particles[i];
var cluster = clusters[particle.cluster];
cluster || (throwError('Empty cluster! Thats impossible'));
for (var j in cluster) {
var other = particles[cluster[j]];
if (other.id >= particle.id) { continue; };
checkCollision(particle, other);
}
}

+2
limon_spb, #
На сколько я понял, алгоритм с сеткой работает для частиц одинакового диаметра. Остальные — со всеми частицами. Так что иногда нужен, я полагаю, не только последний описанный алгоритм.
Ну а самый первый, наверное, нужен для того, чтобы задать основу, или базис. Типа того :-) Иногда ведь сгодится и он, если частиц не так много
+3
Elsedar, #
Что ж, отвечу по порядку.

Рабочие все 3 алгоритма, выбрать можно любой, нужно исходить из исходных данных, если частиц мало, не долго думая выбираем 1 алгоритм, потратив на его написание 10 секунд и не паримся. 2 алгоритм очень популярен, особенно, когда хочется и производительность и не очень хочется копаться в более сложных вещах, тратим на его понимание несколько минут и меньше минуты на кодирование.
Так же мне хотелось сравнивать все алгоритмы по времени работы.

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

По сути, эта сеть и является хеш таблицей, которая хранит указатели на частицы.

Извините, но ваш код я не читал.
+2
HomoLuden, #
Даже если был бы лишь один рабочий, рассмотреть стоило бы хотябы для понимания.
Вот пример:
The «Double-Checked Locking is Broken» Declaration
Обратите на подразделы: «A fix that doesn't work», «More fixes that don't work» и пр.
+2
PapaBubaDiop, #
Для метода частиц в ячейках используется стандартный алгоритм, для которого надо завести дополнительный целочисленный массив частиц. В массиве ячеек хранится индекс первой частицы попавшей в ячейку. В массиве частиц хранится номер следующей частицы попавшей в эту же ячейку. В этом случае не нужны ограничения на глубину массивов и прочие бяки. Пользуюсь этим для алгоритма SPH.
+1
dmitrygusev, #
По вашим результатам времена работы второго и третьего алгоритмов растут одинаково линейно (с небольшим различием линейного коэффициента).

Можете привести сравнение скорости выполнения не в миллисекундах (тем более про железо ничего не сказано), а в количестве операций?

Еще было бы интересно посмотреть как изменится производительность алгоритмов от плотности распределения частиц?

Кстати, сложность алгоритма поиска соседей не может быть O(n), потому что количество пар соседей — это даже не линейная функция от n. То есть, чтобы найти все пары соседей среди n точек не достаточно n операций. Например, для четырех близко расположенных точек, количество пар соседей будет равно шести.

FYI:
Во втором или третьем номере журнала «Программные продукты и системы» (2012) выйдет статья «Алгоритм поиска ближайших соседей» применительно к SPH. Там будет алгоритм со сложностью O(N^2/k), где k > 2 зависит от распределения частиц в пространстве.

Там, например, есть такой эксперимент, где показано, что для поиска очередной пары соседей требуется в среднем 1,3 операции (точки равномерно распределены в квадрате при плотности частиц от 40 до 98 процентов, сторона квадрата от 50 до 100 точек, то есть n было в диапазоне от 2500 до 10000, радиус взаимодействия равен 5, k получилось в диапазоне от 10 до 20). Интересно было бы посмотреть на ваши цифры.
+1
Elsedar, #
Каюсь, время работы алгоритмов, по факту является временем работы всего Solver-а, а он включает в себя еще и расталкивание частиц, которое занимает значительное время. Т.е. это не совсем время работы именно алгоритма.
Рост времени 2 алгоритма не такой, какой ожидается, из-за того, что частицы на каждом шаге уже практически отсортированы.
Если выключить расталкивание частиц и на каждой итерации все частицы перемешивать, то рост времени у 2 алгоритма будет совсем другой, ближе в ожидаемому. На таких же условиях проверил 3 алгоритм, линейность во всей своей красе:
10000 — 1 мс
20000 — 2 мс
30000 — 3 мс
100000 — 10-11 мс
Можете убедиться в этом сами, в методе Collision, первой строкой сделать return, и на каждой итерации вызывать InitParticles.

Как измерить скорость работы в количестве операций я не совсем понимаю.
+2
dmitrygusev, #
Фактическое количество операций можно посчитать, если делать counter++ на каждой итерации самого глубокого цикла (циклов, если их несколько на одном уровне). Например,

counter = 0;

for (int i...) {
for (int j...) {

if (...) {

for (k...) {
counter++;
}

} else {


counter++;
}
}
}

Сделайте эту штуку только для части, где ведется поиск соседей. Если у вас моделируется поведение частиц в итераций — 1) найти соседей, 2) применить физику, 3) отрисовать, и опять сначала с шага 1) — то нужно сделать только замер первого прохода шага 1, т.е. когда частицы еще находятся в перемешанном состоянии. Можно, конечно, привести и замеры для второго и следующих проходах, но они будут не так показательны.

Еще, третий алгоритм зависит не только от количества частиц, но и от площади распределения частиц и от плотности распределения. Можете эти цифры тоже привести?
0
dmitrygusev, #
FYI

Вышла статья: swsys.ru/index.php?page=article&id=3249
–1
Ember, #
Всегда хотел замоделировать процесс формирования солнца и планет из частиц, но сложность моделирования взаимодействия всех частиц со всеми останавливала.
+2
Pand5461, #
С гравитацией по-любому придется считать или каждую частицу с каждой, или использовать particle-mesh методы. Быстрые и простые алгоритмы есть только для короткодействующих сил.
0
PapaBubaDiop, #
нет ничего сложного — smothe particle hydrodynamics (SPH) решит вашу задачу на десктопе за пару дней с приемлемой точностью.
0
chupvl, #
Броуновское движение — Броуновская динамика — примера программных решений довольно много (понимаю, что для вас это была просто алгоритмическая игра, но...)
www.ifr.ac.uk/materials/fractures/brownian.html
mccammon.ucsd.edu/uhbd.html
0
B_Sadovskiy, #
Извиняюсь, вопрос не по теме. А в какой программе Вы рисовали эти графики?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.