Управляйте большим количеством независимых актеров в режиме реального времени

8

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

Slubb
источник
1
хотя ваш вопрос может показаться немного другим, вы можете использовать тот же алгоритм, что и здесь . в этом алгоритме нет необходимости использовать обработку parralel, и только с одним вы получите повышение производительности.
Ali1S232
Распараллеливание обновления не поможет, если, скажем, у вас есть два ядра, а обновление половины из них уже занимает слишком много времени, но если у вас есть несколько доступных ядер и вы их еще не используете, это должно помочь. В идеале вам понадобится решение, не требующее обновления каждого отдельного блока за каждый шаг по времени, или способ упростить обновление, чтобы вы могли это сделать. Насколько велик этот шаг по времени? Это не зависит от рисования кадров, верно?
Блецки
4
Первое, что вы можете сделать, это признать, что ваша скорость не имеет ничего общего с количеством независимых актеров. Это связано с тем, что делают эти актеры . У меня может быть сто тысяч независимых актеров, обновляющих> 60fps, если все, что они делают, if not dead position += 1или один актер, обновляющих <1fps, если он входит в бесконечный цикл. Некоторые из ваших алгоритмов - некоторые части того, что делают эти модули - просто слишком дороги, как вы делаете их, и все. Вероятно, есть много разных возможных причин и множество разных стратегий для каждого.
двойник

Ответы:

4

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

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

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

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

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

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

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

Ларс Виклунд
источник
+1. Мои мысли, в частности, сводят логику к управляемым группам, которые обрабатываются только каждые несколько циклов, причем все такие группы потенциально находятся в шахматном порядке для равномерной обработки.
инженер
1

Насколько я помню, у вас всегда будет менее 10000 единиц игры. я не могу вспомнить ни одной игры с таким числом, хотя земля империи может пройти до 14000 за хак, но никто никогда не достигнет этой точки. так что просто наличие статического массива из 10 000 объектов кажется более чем необходимым.

как вы знаете, итерация более 10000 объектов не представляет особой проблемы, но она может занять много времени, если ваш алгоритм работает медленнее, чем O (n). например, если вы попытаетесь проверить каждый два объекта на предмет обнаружения столкновения, это займет O (n ^ 2) времени, что означает много времени. поэтому вы должны как-то сломать свои алгоритмы. давайте рассмотрим пример алгоритма для каждой вещи, о которой я могу думать прямо сейчас:

  1. обнаружение столкновений: для каждого алгоритма обнаружения столкновений вы должны проверять каждые два объекта, но вы можете отменить некоторые проверки, начиная циклы. как я предположил в комментариях, вы можете использовать тот же алгоритм, что и для этого вопроса . нет необходимости использовать несколько потоков или что-либо еще, даже с одним потоком и четырьмя регионами вы уменьшите количество проверок с n * (n-1) до 4 * (n / 4) ((n-1) / 4), и оптимизируя количество регионов, вы можете получить еще лучшие результаты. Я думаю, что используя регионы с наилучшими номерами, вы даже можете получить O (n log (n)).

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

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

  4. для выбора единиц вы также можете использовать те же регионы.

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

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

Ali1S232
источник
Я помню, что в Empires Dawn of Modern World было более 40 000 человек :). Позор, что рендерер мог держать только 1000 на экране, хотя до того, как они начали исчезать, но остальная часть игры работала хорошо :).
замедленная
@daniel: в этом нет ничего страшного, у генералов не было никаких ограничений на количество юнитов. Я просто давал примерное количество единиц, на которых основывались мои математические расчеты. 40000 и 10000 не сильно отличаются друг от друга.
Ali1S232