поведение частиц

From

Maxim Gusev (2:5083/39.30)

To

Alexey N Konoplyov

Date

2002-09-04T21:17:40Z

Area

RU.ALGORITHMS

Как поживаете, Alexey ?

 AK>     Задача: моделируется поведение частиц на 2d плоскости. Частцы
 AK> обладают массой и притягиваются друг к другу исходя из общеизвестных
 AK> соотношений F=G*m1*m2/R^2, F=m*a.
Круто.
 AK> Сейчас это реализовано так: на каждом шаге просчета для каждой из
 AK> частиц высчитывается вектор ускорения, и исходя из этого ускорения
 AK> корректируется скорость движения частицы и ее положение на плоскости.
Первое, что приходит в голову: откажись от умножения на G. Все равно у тебя
модельное пространство со своими "постоянными". Лишнее умножение ни к чему.

Сила и ускорение - это вектора. Ты не привел подробностей, но возможно, при
обработке векторов у тебя вычисляется куча лишней тригонометрии.

 AK>     Основная проблема: нужно промоделировать большое (порядка
 AK> десятков тысяч) число частиц, причем очень желательно - в реальном
 AK> времени.
Хотелось бы знать, какую задачу ты решаешь, создавая эту модель.

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

 AK>     Вопрос - можно ли как-нибудь снизить степень сложности алгоритма?
Можно увеличить скорость в 2-4 раза путем увеличения ;) сложности алгоритма.

Например, обрати внимание, что у тебя величина притяжения между объектами,
скажем, 1 и n вычисляется дважды - при обработке номера 1, а затем - при
обработке номера n. Можно сделать так, что сила взаимодействия между этими
объектами вычисляется один раз (меняется только ее знак).

Попробуй нарисовать на бумаге 4 объекта, взаимодействующих по принципу "каждый
с каждым" и все станет ясно.

 AK> В данной реализации потолок - полторы тысячи объектов, один кадр в
 AK> секунду. Объектов необходимо на порядок или два поболее.
Способов преодолеть квадратичный закон пока не вижу.

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

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

Полагаю, эти моменты полностью оправдают переход к приближенным вычислениям .

                C уважением, Maxim Gusev.

--- УТВЕРЖДАЮ. MSG-редактор капитан 2.5 ранга Голд Дедович фор ДОС
 * Origin: ФИДО, вино и либидо! (2:5083/39.30)