Шаблоны игрового программирования.Очередь событий

Очередь событий (Event Queue)

Оглавление

Событийно-ориентированное программирование ( event-driven programming).

Для того чтобы получать такие послания, где-то глубоко в недрах вашего кода должен находиться цикл событий(event loop). Выглядит он примерно так:


while (running)
{
Event event = getNextEvent();
// Обработка события...
}


Вызов getNextEvent() отправляет порцию необработанного пользовательского ввода в ваше приложение. Вы перенаправляете его в обработчик событий и ваша программа магическим образом оживает. Самое интересное здесь в том, что приложение изымает (pulls) событие когда вам это нужно. Операционная система не сразу перескакивает к определенному коду в вашем приложении, как только пользователь тыкает в периферийное устройство.

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

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

Когда поступает пользовательский ввод, ОС добавляет необработанные события в очередь. Когда вы вызываете getNextEvent(), эта функция вытаскивает самое старое событие из очереди и передает его приложению.

Центральная шина событий

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

Если хотите понять почему не используются - посмотрите в главе Игровой цикл( Game Loop).

Предположим что в вашей игре есть система обучения, показывающая боксы с подсказками после определенных игровых действий. Например, после того как игрок первый раз побеждает глупое чудовище, вы хотите показать ему маленький овал с надписью " Press X to grab the loot!"

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

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

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

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

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

Так о чем мы?

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

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

Несмотря на то что я очень скептически отношусь к шаблону Синглтон( Singleton)GoF, в данном случае он вполне уместен. Но я буду использовать еще более простое решение и просто сделаю метод статичным.

class Audio
{
public:
static void playSound(SoundId id, int volume);
};


Он отвечает за загрузку нужного аудио ресурса, поиск свободного канала для его проигрывания и запуск. Этот раздел не посвящен какому-то реальному API конкретной платформы, так что я буду предполагать что он реализован где-то еще. С его помощью мы напишем собственный метод:


void Audio::playSound(SoundId id, int volume)
{
ResourceId resource = loadSound(id);
int channel = findOpenChannel();
if (channel == -1) return;
startSound(resource, channel, volume);
}


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


class Menu
{
public:
void onSelect(int index)
{
Audio::playSound(SOUND_BLOOP, VOL_MAX);
// Другие вещи...
}
};


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

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

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

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

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

Я столкнулся с этой проблемой когда работал над Henry Hatsworth in the Puzzling Adventure. Тогда я поступил также как пишу дальше.

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

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

Проблема 2: Запросы невозможно обрабатывать в агрегированной форме.

Эта проблема выглядит даже более серьезной, чем та с которой мы познакомимся дальше. Но сейчас у нас по всей кодовой базе в самых разных системах распределено множество вызовов playSound(). При этом наша игра работает на современном многоядерном железе. Чтобы задействовать все ядра, мы распределяем наши системы по разным потокам - рендеринг в один, AI в другой и т.д.

Так как наш API является асинхронным, он запускается в потоке вызывающего кода. Когда мы вызываем его из другой системы игры, мы сталкиваемся с конкуренцией за наш API со стороны нескольких потоков. Посмотрите на код примера. Видите код для потоковой синхронизации? Вот и я нет.

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

Проблема 3: Запросы обрабатываются в неправильном потоке.

Обычно эта проблема связана с тем, что аудио движок интерпретирует вызов playSound() как "Бросить все и проиграть звук прямо сейчас!". Проблема в этой немедленности. Остальные системы игры вызывают playSound() когда им удобно, но не обязательного в тот момент, когда это удобно аудио движку. Чтобы это исправить мы отвяжем получение запроса от его обработки.

Шаблон

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

Запросы могут обрабатываться напрямую или перенаправляются заинтересованным сторонам. Таким образом мы снижаем связность отправителя и получателя, как статически так и во время работы.

Когда использовать

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

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

Я думаю об этом в терминах помещения(pushing) и извлечения(pulling). У вас есть некий код A, который хочет чтобы другой код B выполнил некую работу. Естественным образом для A инициировать это действие будет помещение запроса в B.

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

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

Имейте в виду

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

Центральная очередь событий - это глобальная переменная

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

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

Состояние мира может изменяться

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

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

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

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

Вы рискуете застрять в циклах обратного вызова

Все системы событий и сообщений должны опасаться циклов:

1. A Отсылает событие.
2. B получает его и реагирует, отсылая событие.
3. Это событие принадлежит к тому типу, который интересен A. Поэтому A получает его. В свою очередь A отсылает сообщение...
4. Переходим к пункту 2.

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

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

Пример кода

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

Первая - это блокировка нашего API. Когда фрагмент кода проигрывает звук, он не может ничего сделать пока playSound() не закончит загрузку и начнет издавать звуки через динамик.

Мы хотим отложить эту работу на потом, чтобы playSound() мог возвращать управление сразу. Чтобы это сделать нам нужно овеществить (reify) запрос на проигрывание звука. Нам потребуется маленькая структура, хранящая детали формируемого запроса, которые понадобятся позже.


struct PlayMessage
{
SoundId id;
int volume;
};


Теперь нам нужно добавить в Audio место для отслеживания этих добавляемых сообщений. Профессор по алгоритмам сказал бы вам что нужно использовать структуры данных типа Кучи Фибоначчи( Fibonacci heap) или списка с пропусками(skip list) или черт побери связанный список. Но на практике практически всегда хранить гомогенные структуры данных лучше в старом добром линейном массиве:

Разработчики алгоритмов зарабатывают на публикации анализа новых структур данных. Они точно не заинтересованы в сохранении основ.

• Никакого динамического выделения памяти.


• Никаких накладных расходов на хранение дополнительной информации или указателей.


• Дружелюбное для кеша последовательное использование памяти.

Более подробно о том что такое дружелюбность для кеша написано в главе Локализация данных(Data Locality).

Приступим:


class Audio
{
public:
static void init()
{
numPending_ = 0;
}

// Другие вещи...
private:
static const int MAX_PENDING = 16;

static PlayMessage pending_[MAX_PENDING];
static int numPending_;
};


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


void Audio::playSound(SoundId id, int volume)
{
assert(numPending_ < MAX_PENDING);

pending_[numPending_].id = id;
pending_[numPending_].volume = volume;
numPending_++;
}


В результате playSound() может возвращать управление сразу, но нам конечно все равно придется проигрывать звук. Этот код нужно куда-то перенести и этим куда-то будет метод update():




class Audio
{
public:
static void update()
{
for (int i = 0; i < numPending_; i++)
{
ResourceId resource = loadSound(pending_[i].id);
int channel = findOpenChannel();
if (channel == -1) return;
startSound(resource, channel, pending_[i].volume);
}

numPending_ = 0;
}

// Другие вещи...
};


Теперь нам просто нужно вызвать его из удобного для нас места. Это "удобно" зависит от вашей игры. Это может значить как вызов прямо из Игрового цикла( Game Loop) или из выделенного звукового потока.

Все это хорошо работает, но не подразумевает того что мы можем обработать все звуковые запросы в едином вызове update(). Если вы делаете нечто в духе асинхронной обработки запросов после загрузки нужного звукового ресурса, это не сработает. Чтобы update() обрабатывал запросы по одному, ему нужно иметь возможность извлекать запросы из буфера.

Кольцевой буфер

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

Я знаю что вы подумали. Если мы удаляем элементы из начала очереди, не приходится ли нам сдвигать все оставшиеся элементы? Не будет ли это слишком медленно?

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

• Голова очереди - это откуда считываются запросы. Голова - это самый старый поступивший запрос.


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

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



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


class Audio
{
public:
static void init()
{
head_ = 0;
tail_ = 0;
}

// Методы...
private:
static int head_;
static int tail_;

// Массив...
};


В реализации playSound(), numPending_ заменяется на tail_, но в целом все то же:


void Audio::playSound(SoundId id, int volume)
{
assert(tail_ < MAX_PENDING);

// Добавление в конец списка.
pending_[tail_].id = id;
pending_[tail_].volume = volume;
tail_++;
}


Гораздо интереснее изменения внутри update():


void Audio::update()
{
// Если запросов в очереди нет - ничего не делаем.
if (head_ == tail_) return;

ResourceId resource = loadSound(pending_[head_].id);
int channel = findOpenChannel();
if (channel == -1) return;
startSound(resource, channel, pending_[head_].volume);

head_++;
}


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

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

Теперь, когда у нас есть очередь, мы можем добавлять элементы в конец и удалять их из начала. Здесь есть очевидная проблема. По мере того как мы будем идти по очереди запросов, голова и хвост будут смещаться вправо. В конце концов tail_ достигнет конца массива и вечеринка закончится. И здесь придется подумать.

Мы ведь не хотим чтобы вечеринка закончилась? Нет. Конечно нет.

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



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


void Audio::playSound(SoundId id, int volume)
{
assert((tail_ + 1) % MAX_PENDING != head_);

// Добавление в конец списка.
pending_[tail_].id = id;
pending_[tail_].volume = volume;
tail_ = (tail_ + 1) % MAX_PENDING;
}


tail_++ заменяется на деление инкремента по модулю на размер массива чтобы он переходил в начало. Еще одно изменение - это добавление assert. Нам нужно быть уверенными, что очередь не переполнена. Пока у нас в очереди будет меньше запросов чем MAX_PENDING, у нас будет оставаться промежуток между головой и хвостом. Если очередь будет полной, этот промежуток исчезнет и у нас получится странный Уроборос. Хвост пересечется с головой и начнет ее перезаписывать. assert проверяет чтобы этого не случилось.

Добавляем в update() и перенос головы:


void Audio::update()
{
// Если запросов в очереди нет - ничего не делаем.
if (head_ == tail_) return;

ResourceId resource = loadSound(pending_[head_].id);
int channel = findOpenChannel();
if (channel == -1) return;
startSound(resource, channel, pending_[head_].volume);

head_ = (head_ + 1) % MAX_PENDING;
}


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

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

Агрегация запросов

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


void Audio::playSound(SoundId id, int volume)
{
// Обход ожидающих запросов.
for (int i = head_; i != tail_;
i = (i + 1) % MAX_PENDING)
{
if (pending_[i].id == id)
{
// Использование большего из двух значений.
pending_[i].volume = max(volume, pending_[i].volume);

// Не нужно добавлять.
return;
}
}

// Предыдущий код...
}


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

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

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

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

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

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

Разделение потоков

И наконец самая страшная проблема. В нашем синхронном API в каком потоке вызывалась playSound(), в том же потоке запрос и обрабатывается. А это не всегда то что мы хотим.

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

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

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

Теперь, когда у нас есть три критических элемента, мы к этому готовы:

1. Код для запроса звука отвязывается от кода, который его проигрывает.
2. У нас есть очередь для общения между этими двумя.
3.Очередь инкапсулирована от остальной программы.

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

На самом высоком уровне все, что нам нужно сделать - это убедиться в том, что очередь не изменяется в конкурентном режиме. Так как playSound() делает совсем немного работы - попросту заполняет всего несколько полей - эта функция может выполнять lock, не блокируя обработку надолго. В update() нам понадобится нечто наподобие условной переменной, чтобы мы не тратили впустую процессорные циклы пока не появятся запросы для обработки.

Вторая часть главы