Автор: Джефф Эндрюс (Jeff Andrews)

Опубликовано: 18.01.2013

Изменено: 18.01.2013

Постоянная ссылка

Комментарии [0]

Проектирование архитектуры параллельного игрового движка


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



Страницы: 1 2 3 4

1. Введение
1.1. Обзор
1.2. Допущения
2. Режим параллельного выполнения
2.1. Режимы выполнения
2.1.1. Свободный пошаговый режим
2.1.2. Жесткий пошаговый режим
2.2. Синхронизация данных
3. Движок
3.1. Фреймворк
3.1.1. Планировщик
3.1.2. Универсальная сцена и объекты
3.2. Менеджеры
3.2.1. Менеджер задач
3.2.2. Менеджер состояний
3.2.3. Менеджер служб
3.2.4. Менеджер среды
3.2.5. Менеджер платформы
4. Интерфейсы
4.1. Интерфейсы субъекта и наблюдателя
4.2. Интерфейсы менеджеров
4.3. Системные интерфейсы
4.4. Интерфейсы изменений
5. Системы
5.1. Типы
5.2. Системные компоненты
5.2.1. Система
5.2.2. Сцена
5.2.3. Объект
5.2.4. Задача
6. Связываем всё вместе
6.1. Инициализация
6.2. Загрузка сцены
6.3. Игровой цикл
6.3.1. Исполнение задач
6.3.2. Раздача изменений
6.3.3. Проверка выполнения и выход
7. Заключительные соображения
8. Об авторе
Приложение А. Схема примерного движка
Приложение Б. Схема связи движка и систем
Приложение В. Модель наблюдателя
Приложение Г. Советы по реализации задач
Список рисунков
Литература


1. Введение


С появлением нескольких ядер внутри одного процессора, необходимость создания параллельного игрового движка становится всё более и более важной. Всё ещё возможно фокусироваться в основном только на GPU (графическом процессоре) и иметь однопотоковый игровой движок, но преимущество использования всех процессоров в системе (не важно CPU или GPU), может дать намного более богатые возможности для пользователя. Например, при использовании нескольких ядер CPU, игра может увеличить количество физических объектов (твёрдых тел) на экране для лучших эффектов, или можно разработать более "умный" искусственный интеллект, который позволит воплотить более человеческое поведение.

1.1. Обзор


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

1.2. Допущения


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


2. Режим параллельного выполнения


Режим параллельного выполнения является краеугольным камнем эффективной многопоточной игровой среды. Чтобы добиться по-настоящему параллельной работы игрового движка, с минимальными затратами на синхронизацию, необходимо сделать так, чтобы каждая система работала в своем собственном режиме выполнения, как можно меньше взаимодействуя с другими системами движка. Конечно, при этом не обойтись без совместного доступа к данным. Однако, вместо того, чтобы каждая система обращалась к общим данным, например, за координатами положения или ориентации объекта, каждой системе следует предоставить свою копию данных. Это устранит взаимную зависимость разных частей движка от данных. Уведомления об изменениях, внесенных какой-либо частью в общие данные, передаются Менеджеру состояний (State Manager), который помещает все изменения в очередь – это называется режимом обмена сообщениями (messaging). После того, как разные системы завершили свой очередной цикл выполнения, они обрабатывают сообщения от Менеджера состояний, в соответствие с которыми обновляют свои внутренние структуры данных. Использование подобного механизма позволяет значительно сократить накладные затраты на синхронизацию, обеспечивая независимую работу систем.

2.1. Режимы выполнения


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

На рисунке 1 показано, как разные системы работают в «свободном режиме» пошагового выполнения (free step mode), при этом необязательно, чтобы все они завершали выполнение операции за один и тот же такт. Также возможен и жесткий режим пошагового выполнения (lock step mode, рисунок 2), когда выполнение всех систем завершаются за один такт.

2.1.1. Свободный пошаговый режим


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

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

Выполнение в свободном пошаговом режиме
Рисунок 1. Выполнение в свободном пошаговом режиме



2.1.2. Жесткий пошаговый режим


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

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

Выполнение в жестком пошаговом режиме
Рисунок 2. Выполнение в жестком пошаговом режиме



2.2. Синхронизация данных


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

Существуют два подхода:
1) Время – правильное значение хранится в подсистеме, сделавшей последнее изменение.
2) Приоритет – правильное значение принадлежит системе, имеющей наибольший приоритет. Этот механизм может сочетаться с временным механизмом (для обработки изменений, внесенных подсистемами с одинаковым приоритетом).

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

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


3. Движок


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

Следующая схема иллюстрирует разные части игрового движка:

Высокоуровневая архитектура движка
Рисунок 3. Высокоуровневая архитектура движка


Заметим, что функциональные блоки, относящиеся непосредственно к игре, рассматриваются как отдельный от движка элемент. Это и обеспечивают необходимую гибкость, обеспечиваемую тем, что сам движок играет роль «клея», соединяющего функциональные части. Модульность также позволяет загружать или выгружать системы по мере необходимости.

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

Общее представление о такой блочной организации можно получить из Приложения А "Схема примерного движка".

Как указывалось в разделе 2, по своей сути системы являются дискретными элементами. Благодаря этому они могут работать параллельно без вмешательства в работу других систем. В то же время, это порождает определенные проблемы в тех случаях, когда системам необходимо обмениваться информацией, ведь данные необязательно находятся в стабильном состоянии. Обмен информацией между системами может потребоваться по следующим двум причинам:
1) Чтобы сообщить другой системе об изменении, внесенном в общие данные (например, координаты положения или ориентации объектов);
2) Чтобы запросить некоторые функции, недоступные в рамках конкретной системы (например, система расчета ИИ обращается к системе расчета геометрии/физики для проверки пересечения лучей).

Первая проблема коммуникации между системами решается путем реализации Менеджера состояний, как было описано в предыдущем разделе. Более подробно работа Менеджера состояний рассматривается в разделе 3.2.2 «Менеджер состояний».

Для решения второй проблемы в системе предусматривается механизм для предоставления служб, которые могут потребоваться другой системе. Более подробное описание этого механизма содержится в разделе 3.2.3 «Менеджер служб».

3.1. Фреймворк


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

Цикл игры также выполняется во фреймворке и имеет следующий порядок:

Основной цикл игры
Рисунок 4. Основной цикл игры


На первом этапе цикла игры происходит обработка всех ожидающих сообщений окон операционной системы, так как движок, как правило, выполняется в оконной среде. Без этого движок не реагировал бы на вызовы операционной системы. На следующем этапе планировщик назначает задачи систем с помощью Менеджера задач. Более подробно данный этап рассматривается ниже в разделе 3.1.1. На последующем этапе все изменения, обработанные Менеджером состояний (подробное описание в разделе 3.2.2) передаются требуемым элементам движка. На заключительном этапе интегрированная среда проверяет статус выполнения, определяя, следует ли завершить работу движка либо продолжить выполнение каких-либо операций, например, для перехода к следующей сцене. Статус выполнения движка хранится в Менеджере среды, описание которого приводится в разделе 3.2.4.

3.1.1. Планировщик


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

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

3.1.2. Универсальная сцена и объекты


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

На приведенной ниже схеме показано расширение универсальной сцены и объекта:

Расширение универсальной сцены и объекта
Рисунок 5. Расширение универсальной сцены и объекта


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

Более подробная схема взаимодействия движка с системами приводится в Приложении Б "Схема связи движка и систем".

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

Дополнительная информация о компонентах системы приводится в Разделе 5.2 «Системные компоненты".




Страницы: 1 2 3 4