Оптимизация гравитационных расчетов

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

Такое ощущение, что я должен быть в состоянии улучшить производительность. В любой момент времени, вероятно, 99% объектов в системе будут иметь незначительное влияние на объект. Я, конечно, не могу отсортировать объекты по массе и рассматривать только 10 самых крупных объектов или что-то в этом роде, потому что сила изменяется с расстоянием больше, чем с массой (уравнение по направлениям force = mass1 * mass2 / distance^2). Я думаю, что хорошее приближение было бы рассмотреть крупнейшие объекты и самые близкие объекты, не обращая внимания на сотни крошечных фрагментов породы на другой стороне земного шара , что не может повлиять на что - либо , - но для того , чтобы выяснить , какие объекты ближе всего я должен перебрать все объекты, и их позиции постоянно меняютсятак что я не могу сделать это один раз.

В настоящее время я делаю что-то вроде этого:

private void UpdateBodies(List<GravitatingObject> bodies, GameTime gameTime)
{
    for (int i = 0; i < bodies.Count; i++)
    {
        bodies[i].Update(i);
    }
}

//...

public virtual void Update(int systemIndex)
{
    for (int i = systemIndex + 1; i < system.MassiveBodies.Count; i++)
    {
        GravitatingObject body = system.MassiveBodies[i];

        Vector2 force = Gravity.ForceUnderGravity(body, this);
        ForceOfGravity += force;
        body.ForceOfGravity += -force;
    }

    Vector2 acceleration = Motion.Acceleration(ForceOfGravity, Mass);
    ForceOfGravity = Vector2.Zero;

    Velocity += Motion.Velocity(acceleration, elapsedTime);
    Position += Motion.Position(Velocity, elapsedTime);
}

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

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

Функции Gravity.ForceUnderGravity(...)и Motion.Velocity(...), и т. Д. Просто используют немного встроенной векторной математики XNA.

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

Это не должно масштабироваться до невероятных пределов. Мир не безграничен, он содержит границу, которая уничтожает объекты, которые пересекают его - я хотел бы иметь возможность обрабатывать, может быть, тысячу или около того объектов, в настоящее время игра начинает задыхаться около 200.

Любые мысли о том, как я мог бы улучшить это? Какая эвристика, которую я могу использовать, чтобы сократить длину цикла от сотен до нескольких? Какой код я могу выполнять реже, чем каждое обновление? Должен ли я просто многопоточить его, пока он не станет достаточно быстрым, чтобы позволить мир приличного размера? Стоит ли пытаться переложить расчеты скорости на графический процессор? Если так, то как бы я это разработал? Могу ли я хранить статические общие данные на графическом процессоре? Могу ли я создавать функции HLSL на графическом процессоре и вызывать их произвольно (используя XNA), или они должны быть частью процесса отрисовки?

Это звучит как работа для сетки. Разделите игровое пространство на сетку и для каждой ячейки сетки сохраните список объектов, находящихся в ней в данный момент. Когда объекты перемещаются через границу ячейки, обновите список, в котором они находятся. При обновлении объекта и поиске других, с которыми можно взаимодействовать, вы можете посмотреть только текущую ячейку сетки и несколько соседних. Вы можете настроить размер сетки для лучшей производительности (баланс стоимости обновления ячеек сетки - который выше, когда ячейки сетки слишком малы - со стоимостью выполнения поиска, которая выше, когда ячейки сетки слишком велики большой).

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

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

Если игровой мир очень большой, вы можете даже использовать иерархическую сетку, такую ​​как квадри (2D) или октодерево (3D), и применять аналогичные принципы. Более дальние взаимодействия будут соответствовать более высоким уровням иерархии.

Алгоритм Барнса-Хата - путь к этому. Он использовался в симуляторах суперкомпьютера для решения вашей конкретной проблемы. Это не слишком сложно для кодирования, и это очень эффективно. Я на самом деле написал Java-апплет не так давно, чтобы решить эту проблему.

Посетите http://mathandcode.com/programs/javagrav/ и нажмите «Пуск» и «Показать quadtree».

На вкладке параметров вы можете видеть, что количество частиц может доходить до 200 000. На моем компьютере вычисление заканчивается примерно через 2 секунды (рисование 200 000 точек занимает около 1 секунды, но вычисление выполняется в отдельном потоке).

Вот как работает мой апплет:

1. Создайте список случайных частиц со случайными массами, позициями и начальными скоростями.
2. Построить квадродерево из этих частиц. Каждый узел дерева квадрантов содержит центр масс каждого подузла. По сути, для каждого узла у вас есть три значения: масса, масса и масса. Каждый раз, когда вы добавляете частицу к указанному узлу, вы увеличиваете массу и массу на частица. Положение (масса / масса, масса / масса) будет в конечном итоге центром масс узла.
3. Для каждой частицы рассчитайте силы (полностью описано здесь ). Это делается путем запуска на верхнем узле и повторения через каждый подузел квадродерева до тех пор, пока данный подузел не станет достаточно маленьким. Как только вы прекратите повторение, вы можете рассчитать расстояние от частицы до центра масс узла, а затем вы можете рассчитать силу, используя массу узла и массу частицы.

Ваша игра должна легко справляться с тысячами взаимно притягивающих объектов. Если каждый объект «тупой» (как частицы голой кости в моем апплете), вы сможете получить от 8000 до 9000 частиц, а может и больше. И это предполагает однопоточность. В многопоточных или параллельных вычислительных приложениях вы можете получить гораздо больше частиц, чем это обновление в реальном времени.

Смотрите также: http://www.youtube.com/watch?v=XAlzniN6L94 для большого рендеринга этого

У Натана Рида отличный ответ. Короткая версия этого метода - использовать широкофазную технику, которая соответствует топологии вашего моделирования, и выполнять вычисления гравитации только на тех парах объектов, которые будут оказывать заметное влияние друг на друга. Это действительно ничем не отличается от того, что вы сделали бы для обычной широкофазной регистрации столкновений.

Продолжая это, тем не менее, другая возможность состоит в том, чтобы только периодически обновлять объекты. По сути, каждый временной шаг (кадр) обновляет только часть всех объектов и оставляет скорость (или ускорение, в зависимости от ваших предпочтений) одинаковой для других объектов. Пользователь вряд ли заметит какую-либо задержку в обновлениях от этого, если интервалы не слишком велики. Это даст вам линейное ускорение алгоритма, так что определенно посмотрите на методики с широкими фазами, как предложил Натан, которые могут дать гораздо более значительные ускорения, если у вас есть тонна объектов. Хотя совсем не смоделировано то же самое, это похоже на наличие «гравитационных волн». :)

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

Я бы порекомендовал использовать Quad Tree. Они позволяют быстро и эффективно искать все объекты в произвольной прямоугольной области. Вот вики-статья о них: http://en.wikipedia.org/wiki/Quadtree

И бесстыдная ссылка на мой собственный проект XNA Quad Tree на SourceForge: http://sourceforge.net/projects/quadtree/

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

Просто немного (возможно, наивный) вклад. Я не занимаюсь программированием игр, но я чувствую, что ваше основное узкое место - это вычисление гравитации из-за гравитации. Вместо того, чтобы перебирать каждый объект X, а затем находить гравитационный эффект от каждого объекта Y и добавлять его, вы можете взять каждую пару X, Y и найти силу между ними. Это должно сократить количество гравитационных расчетов от O (n ^ 2). Тогда вы будете делать много сложений (O (n ^ 2)), но обычно это дешевле.

Также в этот момент вы можете реализовать такие правила, как «если сила гравитации будет меньше, чем \ epsilon, потому что эти тела слишком малы, установите силу на ноль». Может быть полезно иметь эту структуру и для других целей (включая обнаружение столкновений).

Расширяя ответ seanmiddleditch, я подумал, что мог бы пролить некоторый свет (ирония?) На идею гравитационного поля.

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

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

Но сколько из этих точек вы должны рассчитать, прежде чем они станут более или столь же неэффективными, как раньше? Вероятно, не так много, даже 32x32 - это существенное поле для итерации для каждого объекта. Поэтому разбейте весь процесс на несколько проходов; каждый с различным разрешением (или точностью).

Т.е., первый проход может вычислять гравитацию объектов, представленную в сетке 4x4, причем каждое значение ячейки представляет 2D-координату в пространстве. Предоставление O (n * 4 * 4) промежуточной сложности.

Второй проход может быть более точным, с гравитационным полем с разрешением 64x64, где каждое значение ячейки представляет 2D-координату в пространстве. Однако, поскольку сложность очень высока, вы можете ограничить радиус затрагиваемых окружающих ячеек (возможно, обновляются только окружающие ячейки 5x5).

Дополнительный третий проход может быть использован для высокоточных вычислений с разрешением 1024x1024. Никогда не помните, что вы фактически выполняете отдельные расчеты 1024x1024, но работаете только над частями этого поля (возможно, подразделами 6x6).

Таким образом, ваша общая сложность для обновления составляет O (n * (4 * 4 + 5 * 5 + 6 * 6)).

Чтобы затем рассчитать изменения скорости для каждого из ваших объектов, для каждого гравитационного поля (4x4, 64x64, 1024x1024) вы просто отображаете положение точечных масс в ячейке сетки, применяете вектор гравитационного потенциала этих ячеек сетки к новому вектору; повторите для каждого «слоя» или «прохода»; затем сложите их вместе. Это должно дать вам хороший результирующий вектор гравитационной силы.

Следовательно, общая сложность составляет: O (n * (4 * 4 + 5 * 5 + 6 * 6) + n). Что действительно важно (для сложности), так это то, сколько окружающих ячеек вы обновляете при расчете гравитационного потенциала в проходах, а не общее разрешение гравитационных полей.

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

Я надеюсь, что это имело смысл.

Как насчет другого подхода:

Назначьте область влияния объектам на основе их массы - они просто слишком малы, чтобы иметь измеримый эффект за пределами этого диапазона.

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

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

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

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