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

Скачать статью и посетить домашнюю страницу Colony

Скачать статью Threaded Crowd Simulation with Collision Avoidance [Eng., PDF 714KB]
Домашняя страница Colony (исходный код, исполняемые файлы, видео)


Рис. 1: Демонстрация Colony

OЗадача, стоящая на пути полной реализаций всех амбиций современных игр-стратегий, состоит в том, чтобы организовать взаимодействие сотен игровых персонажей без столкновений. Как мы можем увеличить количество юнитов и при этом продолжать работу в реальном времени?? Стратегии и аркады задействуют лишь небольшое количество юнитов из-за повышения издержек на их обработку. На примере игры Colony мы покажем, как минимизировать издержки с помощью многопоточной обработки на CPU. Мы также покажем как организовать многопоточную систему избегания столкновений. В своей конечной версии Colony смогла смогла смоделировать несколько тысяч персонажей при установленном уровне производительности 30 фреймов в секунду.


Введение

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


Colony: Игра, которая играет сама с собой

По сути это даже и не игра, поскольку она минимально взаимодействует с пользователем и не имеет игровой цели, но в плане программирования она очень похожа на игру. Логика и структура данных очень похожи на то, что можно найти в любой современной игре. Работа Colony начинается со сцены леса в солнечный день. Если приблизить картинку, то можно увидеть снующих туда-сюда роботов. Задачей роботов является замостить бетоном весь лес. Вначале они строят в разных местах бетонные заводы, затем они начинают систематически уничтожать лес, делая бетон, заливая площадку и возвращаясь за новой порцией бетона. Процесс идёт таким образом, пока весь лес не исчезнет, затем игра начинается с начала.


Архитектура Colony

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

Данные симуляции хранятся в объекте Game наряду с характеристиками уровня – размерами карты и другими данными. Основной функцией объекта Game является процедура обновления модели. Процедура избегания столкновений выполняется на стадии обновления с применением пространственной структуры, используемой для сортировки персонажей. Для их хранения в Colony используется модифицированное kd-Tree, что позволяет производить быстрый поиск ближайших соседей каждого персонажа. Рассматривалось также использование алгоритма sweep and prune (SAP) широкой фазы. Проблема с алгоритмом SAP заключается в том, что вставки и удаления данных являются затратными операциями, а число игровых единиц постоянно меняется. Обычно персонажи равномерно распределены по карте, и для оптимизации вставки и удаления мы провели бининга (binning), который позволил исключить удалённых персонажей из рассмотрения.

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

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

Рис. 2: Двумерная проекция клеток на карте Colony

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

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


Моделирование: вызов функции обновления состояния

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


Биннинг

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

Рис. 3: Выделены клетки с ближайшими соседями

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


Обновление состояния игровых объектов

Алгоритм рассчитывает направление движения персонажа, испуская из текущего положения вперёд по направлению движения два луча, отступающих друг от друга на ширину персонажа.

На своём пути лучи могут сталкиваться с другими агрегатами в соседних клетках – в этом случае агрегат поворачивается в направлении точки, соответствующей точке пересечения на соседнем луче (на рис. 4 отмечено жёлтой стрелкой). При этом аппарат делает резкий или плавный поворот – в зависимости от расстояния.

Рис. 4. Пример прохождения лучей


Параллелизация узких мест

В идеальном случае эмуляция Colony может выполнять все операции по обновлению состояний параллельно. К сожалению, последовательный режим обработки часто бывает необходим, поскольку результаты многих вычислений служат входными данными для последующих операций. В Колонии работа распределяется в виде задач. Для этого используется диспетчер задач, работающий на основе Intel® Threading Building Blocks (TBB), который составляет простой интерфейс к механизму заимствования задач TBB. С помощью диспетчера задач на каждом шаге симуляции создаётся свой набор задач, при этом все условия необходимые для его выполнения передаются через систему зависимостей. Зависимости набора задач – это те наборы задач, которые должны завершиться до того, как данный набор задач сможет начать свое выполнение. Работа по процессу симуляции распределена таким образом, что наборы задач не требуют данных, которые рассчитываются в других задачах данной операции. Поэтому обрабатываемые данные легко разбиваются на части. Функция обновления состояния, работая с массивами, в которых начальный и конечный индексы обозначают группу задач, выполняющихся параллельно на всех ядрах процессора, параллельно выполняет следующие действия:
  1. Записывает юниты в соответствующие клетки
  2. Определяет новые направления для юнитов (в зависимости от пункта 1)
  3. Обновляет состояния юнитов при их движении в новом направлении и отрабатывает их логику поведения (в зависимости от пункта 2)
Эффект от параллелизации можно наблюдать с помощью Intel® VTune Amplifier XE 2011, который в данном случае отображает параллельность выполнения метода CalculateDirection при работе на четырёхядерном процессоре Intel® Core™ с HDG 3000.


Рис. 5. Уровень параллелизма выполнения функции CalculateDirectionTask


Intel VTune Amplifier XE 2011 также показывает общий уровень параллелизма. Основная работа симудяции распределена между аппаратными потоками, и остаётся лишь небольшая часть последовательного кода, который отвечает, в основном, за рендеринг:

Рис. 6. Общий график параллелизма

Ниже приведено распределение задач во фрейме, по данным Platform View Intel® Graphics Performance Analyzers (Intel® GPA). Дан расширенный вид одного аппаратного потока. Как уже показал Intel VTune Amplifier XE 2011, расчёт направлений движения отнимает основную часть времени:

Рис. 7. Работа в тестовой системе распределена на 8 потоков


Производительность

Рис. 8. Количество юнитов при скорости работы 30 фреймов в секунду


Рис. 9. Уменьшение времени генерации фреймов при увеличении количества
ядер и с подключением технологии Intel® Hyper-Threading


С включённой технологией Intel® Hyper-Threading при переходе от 2 ядер к 4 наблюдается рост производительности в 1,79 раза. Анализ произведён в системе с 4-ядерным процессором Intel® Core™ второго поколения с графикой HDG 3000, все ядра имеют частоту 2,30 ГГц.

Перспективы проекта

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


Заключение

Поскольку количество процессорных ядер в новых процессорах непрерывно возрастает, возможность использовать все эти вычислительные мощности является ключевым фактором для увеличения количества персонажей в современных игровых стратегиях реального времени. Colony демонстрирует возможность использования одного из многих методов эмуляции большого количества игровых персонажей с системой избежания столкновений. Можно также рассмотреть и более развитые технологии, наравне с реализацией более сложного ИИ. Как было показано, ключом к простому параллелизму является определение последовательных участков кода с помощью таких средств, как Intel® Parallel Studio, и хранение данных в таком формате, который позволит легко разбивать их на части и обрабатывать раздельно – всё это возможно при помощи Intel® Threading Building Blocks.


Материалы


Об авторах

Кайл Вайхт (Kyle Weicht) работает программистом в Intel Software and Services Group, в отделе Visual Computing Software Division, где занимается поддержкой графических решений Интел. Кайл имеет степень бакалавра в области разработки игр университета Full Sail University.

Omar Омар Родригес (Omar A Rodriguez) работает программистом в Intel® Software and Services Group, занимается поддержкой графических решений Интел в Visual Computing Software Division. Имеет степень бакалавра компьютерных наук Университета штата Аризоны. Омар не является ведущим гитаристом группы Mars Volta.

Джеф Фриман (Jeff Freeman) является программистом в Intel Software and Services Group, занимается поддержкой графических решений Intel в отделе Visual Computing Software Division. Имеет степень бакалавра компьютерных наук политехнического института Rensselaer.

Omar A. Rodriguez
Kyle Weicht
Jeff Freeman
12-15-2010
12-15-2010
Tech Articles
Intel® GPA
Intel® TBB
no
We introduce Colony, a real-time simulation of a large number of units with AI and collision avoidance. Colony harnesses increasing CPU core count to parallelize serial portions of simulation update code identified by Intel® Parallel Studio. The optimized task-based version of Colony can simulate many thousands of AI-controlled units at 30 frames per second.
Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.