Многопоточность 2D гравитационных расчетов

Я создаю игру по исследованию космоса, и в настоящее время я начал работать над гравитацией (в C # с XNA).

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

При этом используется 100 объектов, обычно при рендеринге 1000 из них без физических вычислений получается более 300 FPS (что является моим пределом FPS), но более 10 объектов приводят игру (и единственный поток, на котором она выполняется) к ее колени при выполнении физических расчетов.

Я проверил использование своего потока, и первый поток убивал себя от всей работы, поэтому я решил, что мне просто нужно сделать физический расчет в другом потоке. Однако, когда я пытаюсь запустить метод Update класса Gravity.cs в другом потоке, даже если в методе Gravity Update ничего нет, игра все равно проигрывает 2 FPS.

Gravity.cs

public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in entityEngine.Entities)
        {
            Vector2 Force = new Vector2();

            foreach (KeyValuePair<string, Entity> e2 in entityEngine.Entities)
            {
                if (e2.Key != e.Key)
                {
                    float distance = Vector2.Distance(entityEngine.Entities[e.Key].Position, entityEngine.Entities[e2.Key].Position);
                    if (distance > (entityEngine.Entities[e.Key].Texture.Width / 2 + entityEngine.Entities[e2.Key].Texture.Width / 2))
                    {
                        double angle = Math.Atan2(entityEngine.Entities[e2.Key].Position.Y - entityEngine.Entities[e.Key].Position.Y, entityEngine.Entities[e2.Key].Position.X - entityEngine.Entities[e.Key].Position.X);

                        float mult = 0.1f *
                            (entityEngine.Entities[e.Key].Mass * entityEngine.Entities[e2.Key].Mass) / distance * distance;

                        Vector2 VecForce = new Vector2((float)Math.Cos(angle), (float)Math.Sin(angle));
                        VecForce.Normalize();

                        Force = Vector2.Add(Force, VecForce * mult);
                    }
                }
            }

            entityEngine.Entities[e.Key].Position += Force;
        }

    }

Да, знаю. Это вложенный цикл foreach, но я не знаю, как еще сделать расчет гравитации, и, похоже, это работает, он настолько интенсивен, что ему нужен собственный поток. (Даже если кто-то знает супер эффективный способ выполнения этих вычислений, я все равно хотел бы знать, как я МОЖЕТ сделать это на нескольких потоках)

EntityEngine.cs (управляет экземпляром Gravity.cs)

public class EntityEngine
{
    public Dictionary<string, Entity> Entities = new Dictionary<string, Entity>();
    public Gravity gravity;
    private Thread T;


    public EntityEngine()
    {
        gravity = new Gravity(this);
    }


    public void Update()
    {
        foreach (KeyValuePair<string, Entity> e in Entities)
        {
            Entities[e.Key].Update();
        }

        T = new Thread(new ThreadStart(gravity.Update));
        T.IsBackground = true;
        T.Start();
    }

}

EntityEngine создается в Game1.cs, а его метод Update () вызывается в Game1.cs.

Мне нужно, чтобы мои физические расчеты в Gravity.cs запускались каждый раз, когда игра обновляется, в отдельном потоке, чтобы вычисления не замедляли игру до ужасно низкого (0-2) FPS.

Как мне сделать так, чтобы этот поток работал? (любые предложения по улучшению системы Planetary Gravity приветствуются, если у кого-то они есть)

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

Спасибо вам за помощь!

РЕДАКТИРОВАТЬ : После прочтения ответов, которые я получил, я вижу, что вы, ребята, на самом деле все равно, и не просто пытаться высказать ответ, который может сработать. Я хотел убить двух зайцев одним ударом (улучшить производительность и изучить некоторые основы многопоточности), но, похоже, большая часть проблемы заключается в моих вычислениях, и что многопоточность доставляет больше хлопот, чем стоит увеличения производительности. Спасибо всем, я прочитаю ваши ответы еще раз и опробую ваши решения, когда я закончу со школой, еще раз спасибо!

У вас есть классический алгоритм O (n²) . Основная причина вашей проблемы не имеет ничего общего с многопоточностью и имеет отношение к тому, что ваш алгоритм имеет высокую сложность.

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

В разработке игр вы, как правило, хотите избегать алгоритмов O (n²) , если у вас нет небольшого (и предпочтительно фиксированного или ограниченного) объема данных и очень быстрого алгоритма.

Если бы каждая сущность влияла на каждую другую сущность, вам по необходимости потребовался бы алгоритм O (n²). Но похоже, что только несколько сущностей фактически взаимодействуют (из-за if (distance < ...)) - так что вы можете значительно сократить количество операций, используя то, что называется « Пространственное разбиение ».

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

Одна из основных проблем с производительностью вашего кода довольно проста. Это чертовски медленно :

foreach (KeyValuePair<string, Entity> e in Entities)
{
    Entities[e.Key].Update();
}

Вы выполняете поиск в словаре по строке, каждую итерацию (несколько раз в других циклах) для объекта, который у вас уже есть!

Вы могли бы сделать это:

foreach (KeyValuePair<string, Entity> e in Entities)
{
    e.Value.Update();
}

Или вы могли бы сделать это: (лично мне это нравится больше, оба должны быть примерно одинаковой скорости)

foreach (Entity e in Entities.Values)
{
    e.Update();
}

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

Хотя, как часто вы на самом деле нужно искать предметы по имени? По сравнению с тем, как часто вы должны проходить их все? Если вы редко выполняете поиск по именам, рассмотрите возможность сохранения ваших сущностей в List(дайте им Nameчлен).

Код, который у вас есть, относительно тривиален. Я не описал это, но могу поспорить, что большая часть вашего времени исполнения уходит на повторный поиск в словаре . Ваш код вполне может быть "достаточно быстрым", просто решив эту проблему.

РЕДАКТИРОВАТЬ: Следующая самая большая проблема, вероятно, вызов Atan2и затем немедленно преобразовать его в вектор с Sinи Cos! Просто используйте вектор напрямую.

Наконец, давайте рассмотрим многопоточность и основные проблемы в вашем коде:

Первое и самое очевидное: не создавайте новую тему каждый кадр! Объекты нити довольно "тяжелые". Самое простое решение этого было бы просто использовать ThreadPoolвместо этого.

Конечно, не все так просто. Давайте перейдем к проблеме номер два: не трогайте данные сразу в двух потоках! (Без добавления соответствующей инфраструктуры безопасности потоков.)

Вы в основном топаете память здесь самым ужасным образом. Здесь нет нити безопасности. Любой из нескольких " gravity.Update" потоков, которые вы запускаете, может неожиданно перезаписывать данные, используемые в другом потоке. Тем временем ваш основной поток, несомненно, будет касаться и всех этих структур данных. Я не был бы удивлен, если бы этот код приводил к трудно воспроизводимым нарушениям доступа к памяти.

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

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

Обычно я бы порекомендовал начать с практики чего-то простого, где ваша тема в основном "запустить и забыть". Воспроизведение аудио, запись чего-либо на диск и т. Д. Ситуация усложняется, когда вам нужно передать результат обратно в основной поток.

Есть три основных подхода к вашей проблеме:

1) Поставьте блокировки вокруг всех данных, которые вы используете в потоках. В C # это делается довольно просто с помощью lockутверждения.

Как правило, вы создаете (и сохраняете!) new objectСпециально для блокировки, чтобы защитить некоторый набор данных (это из соображений безопасности, как правило, возникает только при написании общедоступных API - но все же в хорошем стиле). Затем вы должны заблокировать объект блокировки везде, где вы получаете доступ к данным, которые он защищает!

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

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

2) Скопируйте данные в поток, дайте ему обработать и затем извлеките результат снова, когда он закончится.

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

И, конечно же, вам все равно придется выполнять какую-то другую работу в фоновом режиме, иначе ваш основной поток будет просто сидеть и ждать окончания работы вашего другого потока, чтобы он мог скопировать данные обратно!

3) Используйте поточно-ориентированные структуры данных.

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

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

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

Потоки не будут волшебным образом ускорять код, который у вас там есть, а просто позволят вам сделать что-то еще одновременно!

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

Что касается вашего потока: старайтесь не создавать поток каждый ход обновления. Эти накладные расходы могут замедлить ваше движение больше, чем ускорение. Вместо этого попробуйте создать один поток столкновений, и пусть он сделает всю работу за вас. У меня нет конкретного подхода « копировать-вставить-этот код» , но есть статьи о синхронизации потоков и фоновом работнике для C #.

Другой момент заключается в том, что в цикле foreach вам не нужно это делать, entityEngine.Entities[e.Key].Textureпотому что вы уже получили доступ к dict в заголовке foreach. Вместо этого вы можете просто написать e.Texture. Я действительно не знаю о влиянии этого, просто хотел, чтобы вы знали;)

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

Пример с 2 сущностями A и B:

pick A in first foreach loop
   pick A in second foreach loop
      skip A because keys are the same
   pick B in second foreach loop
      collision stuff
pick B in first foreach loop
   pick A in second foreach loop
      collision stuff
   pick B in second foreach loop
      skip B because keys are the same

Хотя это и возможный подход, возможно, вы справитесь с А и В за один ход, пропустив половину проверок на столкновение

Надеюсь, это поможет вам начать =)

PS: Даже если вы сказали, что не хотите это слышать: попробуйте сохранить обнаружение столкновений в одном потоке и просто ускорить его. Потоки, кажется, хорошая идея, но с этим возникает необходимость синхронизироваться как в аду. Если вы проверяете столкновение медленнее, чем ваше обновление (причина его создания), вы получите ошибки и сбои, потому что столкновение сработает после того, как корабли уже перемещены, и наоборот. Я не хочу вас расстраивать, это всего лишь личный опыт.

EDIT1: Ссылки с учебником по QuadTree (Java): http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

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

Распараллеливание вашей симуляции может, даже в лучшем случае, ускорить ее только с коэффициентом, равным количеству процессоров × ядер на процессор × потоков на ядро, доступных в вашей системе, то есть где-то между 4 и 16 для современного ПК. (Перемещение вашего кода в графический процессор может привести к гораздо более впечатляющим факторам распараллеливания за счет дополнительной сложности разработки и более низкой скорости вычисления базовых показателей для каждого потока.) С алгоритмом O (n²), как и в примере кода, это позволит вам используйте от 2 до 4 раз больше частиц, чем у вас есть.

И наоборот, переключение на более эффективный алгоритм может легко ускорить вашу симуляцию, скажем, в 100-10000 раз (цифры просто угаданы). Временная сложность хороших алгоритмов моделирования n-тела, использующих пространственное подразделение, масштабируется примерно как O (n log n), что является «почти линейным», так что вы можете ожидать почти тот же коэффициент увеличения числа частиц, с которыми вы можете работать. Кроме того , что будет по- прежнему использовать только один поток, так что все еще будет место для распараллеливания на вершине , что .

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

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

Еще один ответ по оптимизации, который не имеет ничего общего с потоками. Прости за это.

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

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

РЕДАКТИРОВАТЬ : Эта оптимизация в основном для тех случаев, когда вы тестируете столкновения, что, как я сейчас заметил, на самом деле не то, что вы делаете (хотя в определенный момент вы обязательно это сделаете) Тем не менее, это может быть применимо к вашей ситуации, если все частицы имеют одинаковый размер / массу.

Я не очень разбираюсь в многопоточности, но кажется, что ваши циклы отнимают много времени, поэтому, возможно, изменится с этого

i = 0; i < count; i++
  j = 0; j < count; j++

  object_i += force(object_j);

к этому

i = 0; i < count-1; i++
  j = i+1; j < count; j++

  object_i += force(object_j);
  object_j += force(object_i);

мог бы помочь

Если у вас уже есть такие огромные проблемы с 10 симулируемыми объектами, вам нужно оптимизировать код! Ваш вложенный цикл будет вызывать только 10 * 10 итераций, из которых 10 итераций пропускаются (один и тот же объект), что приводит к 90 итерациям внутреннего цикла. Если вы достигнете только 2 FPS, это будет означать, что ваша производительность настолько плоха, что вы достигнете только 180 итераций внутреннего цикла в секунду.

Я предлагаю вам сделать следующее:

1. ПОДГОТОВКА / СРАВНЕНИЕ: Чтобы точно знать, что эта подпрограмма является проблемой, напишите небольшую подпрограмму. Он должен выполнить Update()метод Gravity несколько раз, например, 1000 раз, и измерить его время. Если вы хотите достичь 30 кадров в секунду с 100 объектами, вы должны смоделировать 100 объектов и измерить время для 30 выполнений. Это должно быть менее 1 секунды. Использование такого теста необходимо для разумной оптимизации. В противном случае вы, вероятно, достигнете противоположного и сделаете код медленнее, потому что вы просто думаете, что он должен быть быстрее ... Поэтому я действительно призываю вас сделать это!

2. ОПТИМИЗАЦИЯ: Несмотря на то, что вы не можете многое сделать с проблемой усилий O (N²) (то есть: время вычисления увеличивается квадратично с количеством моделируемых объектов N), вы можете улучшить сам код.

   а) Вы используете много поисков «ассоциативный массив» (словарь) в вашем коде. Это медленно! Например entityEngine.Entities[e.Key].Position. Вы не можете просто использовать e.Value.Position? Это сохраняет один поиск. Вы делаете это везде во всем внутреннем цикле, чтобы получить доступ к свойствам объектов, на которые ссылаются e и e2 ... Измените это! б) Вы создаете новый вектор внутри цикла new Vector2( .... ). Все «новые» вызовы предполагают некоторое выделение памяти (и позже: освобождение). Это даже намного медленнее, чем поиск по словарям. Если вам нужен только этот Вектор временно, разместите его вне циклов И-повторно используйте его путем повторной инициализации его значений новыми значениями вместо создания нового объекта. в) Вы используете много тригонометрических функций (например, atan2иcos) в цикле. Если ваша точность не обязательно должна быть действительно точной, вы можете вместо этого использовать таблицу поиска. Для этого вы масштабируете свое значение до определенного диапазона, округляете его до целочисленного значения и ищите его в таблице предварительно рассчитанных результатов. Если вам нужна помощь с этим, просто спросите. г) Вы часто используете .Texture.Width / 2. Вы можете предварительно рассчитать это и сохранить результат как .Texture.HalfWidthили - если это всегда четное положительное целое значение - вы можете использовать битовую операцию сдвига >> 1для деления на два.

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

Я думаю, что эти оптимизации будут намного лучше, чем попытка достичь более высокой производительности при использовании нескольких потоков! У вас будет много проблем с координацией потоков, поэтому они не будут перезаписывать другие значения. Также они будут конфликтовать при доступе к аналогичным областям памяти. Если для этой работы вы используете 4 процессора / потока, вы можете ожидать только частоту кадров от 2 до 3.

Вы можете переработать его без линий создания объекта?

Vector2 Force = new Vector2 ();

Vector2 VecForce = new Vector2 ((с плавающей точкой) Math.Cos (угол), (с плавающей точкой) Math.Sin (угол));

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