Притяжение частиц

Рейтинг: 0Ответов: 1Опубликовано: 06.02.2015

Делаю игру. В ней должны непрерывно высчитываться координаты частиц, притягивающихся между собой по закону всемирного тяготения. Расчёты у меня производятся по формуле:

F=G*m1*m2/(d*d);

Где G - некоторая константа, m1, m2 - массы частиц, а d - расстояние между частицами.

Расчёты производятся попарно между каждыми двумя частицами. В итоге имеем n! расчётов за один раз, что не есть хорошо. И при n>700 приложение начинает всё больше и больше тормозить.

Теперь вопрос. Как можно упростить/оптимизировать эти вычисления? Может быть, предложите использовать какие-либо библиотеки?

разработка-игр java физика
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

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

Во-вторых, для ускорения поиска частиц, входящих в радиус взаимодействия, можно хранить их не в виде списка, а в BSP-дереве (BSP - Binary Space Partition, двоичное разбиение пространства).

В-третьих (в последнюю очередь!), можно заняться микрооптимизациями. Например, расстояние вы наверняка вычисляете как корень из суммы квадратов разностей координат частиц (sqrt((x1 - x2)^2 + (y1 - y2)^2)). А при вычислении силы вы это же значение возводите в квадрат. Можно избежать вычисления корня и квадрата, если в формулу вычисления силы взаимодействия частиц сразу подставлять сумму квадратов разностей координат.

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