Game development
27 January 2012

Игровые циклы или ЭлектроКардиоГама

Original author: Koen Witters
Translation
Игровой цикл — это пульс каждой игры. Ни одна игра не будет работать без этого. Однако, к несчастью каждого нового разработчика игр, в сети нет хороших статей, в которых уделено достаточное внимание этой теме. Но не печальтесь, потому как только что вы получили возможность прочитать единственную в своем роде статью, уделяющую вопросу игровых циклов заслуженное внимание. По долгу службы мне часто приходится иметь дело с большим количеством кода мелких мобильных игр. И я каждый раз удивляюсь сколь много существует реализаций игрового цикла. Вы тоже можете удивиться как можно для такой, казалось бы простой, вещи можно придумать множество имплементаций. А ведь можно! И в статье я постараюсь рассказать о достоинствах и недостатках наиболее популярных вариантов игровых циклов. Также я постараюсь описать наилучший на мой взгляд вариант реализации игрового цикла.
(Thanks to Kao Cardoso Félix this article is also available in Brazilian Portuguese) (Thanks for me, in Russian also, прим. перев.)

Игровой цикл


Каждая игра содержит последовательность вызовов чтения пользовательского ввода, обновления состояния игры, обработки ИИ, проигрывания музыки и звуковых эффектов, отрисовки графики. Эта последовательность вызовов выполняется внутри игрового цикла. Т.е., как и было сказано в тизере, игровой цикл — это пульс каждой игры. В статье я не буду углубляться в детали реализации упомянутых выше тасков, а сконцентрируюсь исключительно на проблеме игрового цикла. По той же причине я упрощу список тасков до двух функций: обновление состояния и отрисовка. Ниже представлен пример кода для наиболее простой реализации игрового цикла.
 bool game_is_running = true;
    while( game_is_running ) {
        update_game();
        display_game();
    }


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

FPS
FPS — это аббревиатура от «Frames Per Second» (Кадров В Секунду, прим. перев.). В контексте представленной выше реализации игрового цикла это количество вызовов display_game() за одну секунду.

Скорость игры
Скорость игры — это количество обновлений состояния игры за одну секунду. Иными словами, количество вызовов update_game() в секунду времени.

FPS, зависящий от постоянной скорости игры


Реализация

Самое простое решение проблемы тайминга — просто выполнять вызовы с фиксированной частотой 25 раз/сек. Код, реализующий этот подход ниже.
const int FRAMES_PER_SECOND = 25;
    const int SKIP_TICKS = 1000 / FRAMES_PER_SECOND;

    DWORD next_game_tick = GetTickCount();
    // GetTickCount() returns the current number of milliseconds
    // that have elapsed since the system was started

    int sleep_time = 0;

    bool game_is_running = true;

    while( game_is_running ) {
        update_game();
        display_game();

        next_game_tick += SKIP_TICKS;
        sleep_time = next_game_tick - GetTickCount();
        if( sleep_time >= 0 ) {
            Sleep( sleep_time );
        }
        else {
            // Shit, we are running behind!
        }
    }


Это реализация с одним большим плюсом: ПРОСТОТА! Коль скоро вы знаете, что update_game() вызывается 25 раз в секунду, написание остального кода становится проще пареной репы. К примеру, реализация функционала реплея становится тривиальной задачей. Если в игре не используются случайные величины, то вы просто можете логгировать пользовательский ввод и воспроизводить его позже. На своей тестовой машине вы можете подобрать некое компромиссное значение для FRAMES_PER_SECOND, но что произойдет на более быстром или более медленном железе? Давайте выясним это.

Слабое железо

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

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

На мощном железе проблем не будет, но компьютер будет простаивать, тратя впустую «драгоценное» (видимо это ирония? — прим. перев.) процессорное время. Постыдились бы запускать игру с 25..30 FPS, когда она могла бы выдавать из за 300! Ваша игра потеряет в привлекательности по сравнению с тем, что она могла бы показать при использовании процессора на всю катушку. С другой стороны на мобильных платформах оно может быть и к лучшему — позволит сэкономить энергию.

Вывод

Завязывание FPS на фиксированную скорость игры — решение простое, позволяющее сохранить простоту кода. Но есть проблемы: задав слишком большое значение для FPS мы породим проблемы на слабом железе; задав слишком низкое значение мы неэффективно будем использовать мощное железо.

Скорость игры, зависящая от переменного FPS


Реализация

Другое решение проблемы — дать игре работать как можно быстрее и сделать скорость игры зависящей от текущего FPS. Игра будет обновляться с использованием промежутка времени, потраченного на отрисовку предыдущего кадра.
DWORD prev_frame_tick;
    DWORD curr_frame_tick = GetTickCount();

    bool game_is_running = true;
    while( game_is_running ) {
        prev_frame_tick = curr_frame_tick;
        curr_frame_tick = GetTickCount();

        update_game( curr_frame_tick - prev_frame_tick );
        display_game();
    }

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

Слабое железо

Слабое железо может иногда породить задержки в местах, где игра становится «тяжеловата». Это определенно будет иметь место в 3D играх, когда слишком много полигонов отрисовывается. В результате провал в FPS приведет к замедлению обработки пользовательского ввода. Обновление игры будет реагировать на провалы FPS, в результате состояние игры будет изменяться с заметными лагами. В результате время реакции игрока, ровно как и ИИ, замедлится, что может сделать даже простой маневр невозможным. К примеру, препятствие, которое можно преодолеть при нормальном FPS, будет невозможно преодолеть при низком FPS. Еще более серьезные проблемы на слабом железе будут при использовании физики. Симуляция физики может "взорваться".

Мощное железо

Вы можете удивиться тому, что представленная выше реализация игрового цикла может работать неправильно на быстром железе. К сожалению может. И прежде чем показать почему, позвольте немного разъяснить некоторые моменты математики на компьютере. В виду конечной разрядности представления числа в форме с плавающей точкой, некоторые значения не могут быть представлены. Так, значение 0.1 не может быть представлено в двоичном виде и будет округлено при хранении в переменной типа double. Продемонстрирую это с использованием консоли python:
>>> 0.1
0.10000000000000001

Само по себе это нестрашно, но в последовательных вычислениях приводит к проблемам. Пусть у вас есть машина, скорость которой равна 0.001 в попугаях (вольный перевод, прим. перев.). Через 10 секунд машина переместится на расстояние 10.0 попугаев. Если разобьем это вычисление по кадрам, то получим следующую функцию с FPS в качестве параметра:
>>> def get_distance( fps ):
... skip_ticks = 1000 / fps
... total_ticks = 0
... distance = 0.0
... speed_per_tick = 0.001
... while total_ticks < 10000:
... distance += speed_per_tick * skip_ticks
... total_ticks += skip_ticks
... return distance


А нука попробуем посчитать пройденный путь для 40 FPS.
>>> get_distance( 40 )
10.000000000000075


Постойте ка! Это не 10.0 попугаев! Что произошло? Все просто… Т.к. мы разбили вычисление пути на 400 кадров, то при суммировании накопилась значительная ошибка. Представляете что будет при 100 FPS?
>>> get_distance( 100 )
9.9999999999998312


Вот это да! Ошибка стала еще больше!!! Это потому, что мы делаем еще больше сложений при 100 FPS. Стало быть и ошибка накапливается больше. Таким образом, игра будет работать по-разному при 40 FPS и 100 FPS.
>>> get_distance( 40 ) - get_distance( 100 )
2.4336088699783431e-13

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

Вывод

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

Постоянная скорость игры и максимальное FPS


Реализация

Наша первая реализация, «FPS, зависящее от постоянной скорости игры», имеет проблемы на слабом железе. Она порождает лаги как FPS так и обновления состояния игры. Возможное решение этой проблемы — выполнять обновление состояния с фиксированной частотой, но снижать частоту отрисовки. Ниже код реализации такого подхода:
const int TICKS_PER_SECOND = 50;
    const int SKIP_TICKS = 1000 / TICKS_PER_SECOND;
    const int MAX_FRAMESKIP = 10;

    DWORD next_game_tick = GetTickCount();
    int loops;

    bool game_is_running = true;
    while( game_is_running ) {

        loops = 0;
        while( GetTickCount() > next_game_tick && loops < MAX_FRAMESKIP) {
            update_game();

            next_game_tick += SKIP_TICKS;
            loops++;
        }

        display_game();
    }


Игра будет обновляться с фиксированной частотой 50 раз в секунду, а отрисовка будет выполняться с максимально возможной частотой. Заметьте, если отрисовка будет выполняться чаще чем обновление состояние, то некоторые соседние кадрый будут одинаковыми, так что в действительности максимальное значение FPS будет ограничено частотой обновления состояния игры. На слабом железе FPS будет снижаться до тех пор, пока цикл обновления состояния не будет достигать значения MAX_FRAMESKIP. На практике это означает, что игра действительно начнет тормозить, только когда FPS отрисовки проседает ниже значения 5 (= FRAMES_PER_SECOND / MAX_FRAMESKIP).

Слабое железо

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

Мощное железо

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

Вывод

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

Постоянная скорость игры, независящая от переменного FPS


Реализация

Возможно ли улучшить предыдущую реализацию, чтобы она работала быстрее на слабом железе и была бы визуально привлекательнее на мощном? Ну, к счастью для нас, да, это возможно! Состояние игры не нужно обновлять 60 раз в секунду. Пользовательский ввод, ИИ, а также обновление состояния игры, достаточно обновлять 25 раз в секунду (я с этим не согласен, не всегда, прим. перев.). Так что давайте вызывать update_game() 25 раз в секунду, не чаще, не реже. А вот отрисовка пусть выполняется так часто, как железо потянет. Но медленная отрисовка не должна сказываться на частоте обновления состояния. Как добиться этого показано в следующем коде.
const int TICKS_PER_SECOND = 25;
    const int SKIP_TICKS = 1000 / TICKS_PER_SECOND;
    const int MAX_FRAMESKIP = 5;

    DWORD next_game_tick = GetTickCount();
    int loops;
    float interpolation;

    bool game_is_running = true;
    while( game_is_running ) {

        loops = 0;
        while( GetTickCount() > next_game_tick && loops < MAX_FRAMESKIP) {
            update_game();

            next_game_tick += SKIP_TICKS;
            loops++;
        }

        interpolation = float( GetTickCount() + SKIP_TICKS - next_game_tick )
                        / float( SKIP_TICKS );
        display_game( interpolation );
    }


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

Зачем нужна интерполяция


Состояние игры обновляется 25 раз в секунду. Поэтому, если не используется интерполяция, то и кадры будут отображаться с той же максимальной частотой. Тут нужно заметить, что 25 кадров в секунду это не так медленно, как кому-то может показаться. К примеру, в фильмах кадры сменяются с частотой 24 кадра в секунду. Так что 25 кадров в секунду кажется достаточным, но не для быстро движущихся объектов. Для таких объектов следует увеличить частоту обновления состояния, чтобы получить более плавную анимацию. Альтернативой увеличенной частоте обновления как раз и служит связка интерполяции и предсказания.
* Прим. перев.: в движке NeoAxis для физического объекта можно выставлять флаг Continuous Collision Detection; подозреваю, что по нему как раз и выполняется обработка, подобная описанной выше реализации игрового цикла.

Интерполяция и предсказание


Как было написано выше, состояние обновляется на своей, независимой, частоте. Поэтому возможна ситуация, когда отрисовка начинается между двумя последовательными тиками. Пусть вы обновили состояние в 10 раз. Затем вызывается отрисовка и выполняется она где-то между 10 и 11 тиками. Пусть это будет дискретное время 10.3. В результате «interpolation» будет иметь значение 0.3. В качестве примера, представьте машину, движущуююся следующим образом:
position = position + speed;
Если на 10 шаге цикла обновления состояния позиция будет 500, скорость будет 100, тогда на 11 шаге позиция будет 600. Так какова же будет позиция машины во время отрисовки? Можно просто взять позицию на последнем шаге, т.е. 500. Но куда лучше предсказать позицию на следующем шаге и произвести интерполяцию для времени 10.3. Получим код вида:
view_position = position + (speed * interpolation)
Таким образом машина будет отрисована в позиции 530. Переменная «interpolation» в общем случае содержит значение от 0 до 1 относительной позиции во времени между текущим и следующим кадрами (переделано для лучшего понимания, прим. перев.). Нет нужды делать предсказание слижком сложным, чтобы обеспечить плавность анимации. Конечно, возможна ситуация когда один объект частично пересечется с другим непосредственно перед детектированием коллизии. Но, как мы увидели ранее, состояние игры обновляется 25 раз в секунду, поэтому артефакт рендеринга будет виден лишь долю секунды (а что если плотность объектов велика и коллизий много? — прим. перев.) и с малой вероятностью он будет замечен пользователем.

Слабое железо

В большинстве случаев update_game() будет выполняться намного быстрее, чем display_game(). Фактически мы можем принять как данность, что даже на слабом железе функция update_game() вызывается 25 раз в секунду. Поэтому наша игра будет обрабатывать пользовательский ввод и обновление состояние без особых проблем даже в случае, когда отрисовка выполняется на частоту 15 кадров в секунду.

Мощное железо

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

Вывод

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

Заключение


Игровой цикл не такая уж и простая вещь, как вам может показаться. Мы рассмотрели 4 возможные реализации. И среди них есть по крайней мере одна (где обновление состояния жестко завязано на FPS), которую вы определенно должны избегать. Постоянная частота кадров может быть приемлемой на мобильных устройствах. Однако, если вы хотите портировать игру на разные платформы, то придется развязывать частоту обновления и частоту отрисовки, реализовывать интерполяцию и предсказание. Если не хотите заморачиваться с предсказанием и интерполяцией, то можете использовать большую частоту обновления состояния, но найти оптимальное ее значение для слабого и мощного железа может оказаться сложной задачей.

А теперь марш кодить вашу <%place_your_game_title_here%>!

Попутные статьи (от переводчика)


  1. habrahabr.ru/blogs/silverlight/125037 — Игровой цикл в SL
  2. habrahabr.ru/blogs/gdev/112444 — там есть упоминание о том, что в Unity3D нет игрового цикла как такового (видимо он запрятан?)
  3. habrahabr.ru/blogs/gdev/102930 — про создание игрового движка
  4. habrahabr.ru/blogs/android_development/136968 — пример игры на кокосе
  5. gafferongames.com/game-physics/fix-your-timestep — еще одна статья про дискретное время в играх

+55
43.2k 490
Comments 62