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

http://www.koonsolo.com/news/dewitters-gameloop/
  • Перевод
Игровой цикл — это пульс каждой игры. Ни одна игра не будет работать без этого. Однако, к несчастью каждого нового разработчика игр, в сети нет хороших статей, в которых уделено достаточное внимание этой теме. Но не печальтесь, потому как только что вы получили возможность прочитать единственную в своем роде статью, уделяющую вопросу игровых циклов заслуженное внимание. По долгу службы мне часто приходится иметь дело с большим количеством кода мелких мобильных игр. И я каждый раз удивляюсь сколь много существует реализаций игрового цикла. Вы тоже можете удивиться как можно для такой, казалось бы простой, вещи можно придумать множество имплементаций. А ведь можно! И в статье я постараюсь рассказать о достоинствах и недостатках наиболее популярных вариантов игровых циклов. Также я постараюсь описать наилучший на мой взгляд вариант реализации игрового цикла.
(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 — еще одна статья про дискретное время в играх
Поделиться публикацией
Комментарии 61
    +3
    Спасибо за перевод. Очень познавательная статья.
    А есть что-то про игровой цикл, но только с распараллеливанием? Например физику обновлять в одном потоке, ИИ в другом, отрисовка в третьем. Как тут быть с синхронизацией и взаимодействием разных компонентов движка между собой?
      0
      Я об этом думал… Перевод как первый шаг к имплементации через синглтоны и мультитред. По поводу синхоронизации — все зависит от используемого языка. Там есть ньюансы.
        0
        Кажется все-таки синглетоны вообще не причем к возможности распараллеливания. Или я что-то пропустил?
          0
          Синглтон + Мультитред (локи, мьютексы и пр.) = доступный отовсюду в аппликейшене тредсейфти сервис. Как-то так.
            0
            Я это себе так представляю:
            1) Есть поток рендеринга — Low Priority
            2) Есть поток обновления состояния — High Priority
            3) Есть синглтон, хранящий GameState

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

            Концепт такой. Надо попробовать что-то типа танчиков запилить.
              0
              как мне кажется GameState не должен быть в единственном экземпляре. иначе получится как при отключенной вертикальной синхронизации верхняя часть экрана одна картинка, нижняя — вторая.
              только по объектам разделение, одни по предыдущему отсчету, другие по следущему. результат будет такой, что танчики будут дергаться. и двигаться неравномерно.
              его можно разбить на статические данные и динамические. динамические должны иметь по объекту на каждый временной отсчет. которые и будет передаваться от одного треда к другому.

              и не должно быть у потока игросостояния более высокого приоритета. получится, что 1 раз в 40мс он просыпается, что то делает, на это время фпс критически падает. потом он завершается, и фпс взлетает до небес. игра будет пульсирующей.
              имхо правильнее сделать, чтоб поток игросостояния так же не был привязан к тому, что его будут вызывать ровно 25 раз в секунду. лучше если он будет просчитывать следующее состояние из рассчета на то, сколько прошло времени. естественно можно выставить некий таргет, и если выполняется быстрее, чем нужно, то можно стравливать время, а если медленнее, то упрощать вычисления, насколько игромеханика это позволяет.
                0
                > лучше если он будет просчитывать следующее состояние из рассчета на то, сколько прошло времени
                Может я чего то не понял правильно, но в статье про это вроде написано.

                > как мне кажется GameState не должен быть в единственном экземпляре
                «НЕ должен быть» — это опечатка? В синглтоне всегда хранится последний стейт. Там я нехорошо написал про несколько критических секций. Все таки секция должна быть одна.

                Про приоритеты… Мы делаем обновление с фиксированной частотой (10, 25 или сколько то еще раз в сек.), и эта частота должна иметь наивысший приоритет. Фактическая частота рендеринга неважна.
                  0
                  > Фактическая частота рендеринга неважна.
                  Точнее «сколько получится».
                    0
                    1)у автора про отвязку вывода кадров от статических временных промежутков. я имел ввиду, что и просчет игросостояний тоже можно и нужно от них отвязывать.
                    2) не опечатка. следует читать как неприменимость синглтона. как я это вижу. вместо этого некий таймлайн игровых состояний. в виде очереди. стейт(первый) на -5мс, дальше стейт на +35мс(второй), и дальше еще стейт на +75мс. и отображатель рисует интерполированное состояние между первым и вторым. когда второй стейт достигает нулевой отметки времени, первый освобождается, а позади третьего от другого потока должен приехать четвертый стейт еще на 40мс позже.
                    3) частота фпс условно не важна. но важна его стабильность. если брать из рассчета 10 стейтов в секунду, то если обработчик состояния каждые 100мс проснется и с высоким приоритетом будет 50мс что то делать, то за это время не будет ни одного кадра. а в следующие 50 мс он уснет, и отображатель нарисует скажем 5-6 кадров. фпс будет достаточно высокий, 50-60, но он будет дерганый, вплоть до неиграбельности. равномерный фпс 25 кадров лучше выглядит, чем настолько неравномерный 60.
                      0
                      Если рендеринг будет тяжел, то он просто не будет поспевать за обновлением стейта всего навсего. Отрисовывать рендерер всегда будет последнее состояние.
                      При малой производительности просто будут пропускаться некоторые промежуточные состояния: к примеру сначала рендеринг начнет отрисовывать состояние между первым тиком и вторым. Будет делать это два-три тика и в следующий раз отрисует состояние между 3 и 4 тиками или между 4 и 5 тиками.
                      Динамика персонажа не изменится, хоть картинка и будет дерганной. А вот если тяжелый рендеринг будет аффектать обновление стейта, то уже перс начнет вести себя непредсказуемо. Про это в статье и написано.
                      У вас была ситуация в шутерах на слабом железе, когда инерционность поворота камеры увеличивалась из-за тормозов. Теперь представьте, что вместо инерции будет лишь дрожание картинки, а реакция на мышь останется приличной.

                      Про очередь стейтов… Нельзя заранее просчитать несколько стейтов наперед, т.к. они зависят от ввода от юзера.
                        0
                        теряется возможность интерполяции и собственно смысл развязки. чтобы иметь 60фпс нужно и стейт просчитывать 60 раз в секунду и кадр отрисовывать 60 раз в секунду. если стейт просчитывается 10 раз в секунду, то и на экране будет 10. формально счетчик покажет 60, но кажые 6 кадров будут одинаковы и пользователь будет видеть 10фпс.
                        и наоборот, если рендер «тяжелый» и выводит всего 10 фпс, то зачем просчитывать 60 состояний, отображаться будет лишь каждое 6-ое, остальные уйдут в корзину.
                        очередь стейтов решает вот эти проблемы. если рендер не отобразил стейт, то можно увеличивать время между отсчетами. и наоборот, если рендер быстр, то он и будет определять плавность анимации, а не обработчик состояния.

                        А несколько стейтов наперед просчитать можно. вопрос в инпут-лаге.
                        его кстати надо еще уметь просчитывать. это тоже в тему задач гейм-дева.
                        если взять опять же supreme commander. то 10 стейтов в секунду он просчитывает. 100мс между отсчетами. если ввод от игрока придет на 101-ой мс, то отклик на его действие попадет в стейт, который начнет просчитываться на 200-ой мс.
                        допустим стейт просчитывается за 40мс, рендер идет каждые 20мс(50фпс), то получится минимальный инпут лаг в 160мс. если ставить задачу просчитать на один стейт вперед, то инпут лаг становится 260мс. что для реал-тайм стратегий вполне приемлемо.
                        кстати лобби в этой игре красным отмечает пинг выше 500мс, все что ниже считается приемлемым.

                        в случае же шутеров сцена существенно проще, объектов на 2 порядка меньше в такой модели просто нет необходимости. стейт можно просчитывать очень быстро, и не париться интерполяцией, а задавать шаг анимации сразу в стейте.
                          0
                          > теряется возможность интерполяции и собственно смысл развязки
                          По какой причине? Если интерполяцию сделать невозможно даже приближенно (Хмм а почему, собственно? тоже задумывался, но пока в голову не пришел пример), тогда да… лесом идет эта имплементация с интерполяцией и мы откатываемся обратно к двупоточной системе, где нам уже нужно давать достаточный приоритет обоим.

                          > если рендер «тяжелый» и выводит всего 10 фпс, то зачем просчитывать 60 состояний
                          В случае физики, как раз нужно будет. В статье упомянут «взрыв» симуляции.
                            0
                            По поводу прогноза… Я почему-то понял про прогноз стейтов так, что прогноз делается не на два шага, а на 3, 4, 5 и т.д. Но все равно треть секунды задержка мне кажется значительной. Правда не для RTS, конечно, а для шутеров.
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              Сейчас активно CUDA используют в гейм деве (посмотрите шоукейсы на сайте NVidia). Но это для серьезных разработок. Но уже стираются границы между ЦП и ГП.
              А в казуалках 2D акселерация железная, вроде, не так распространена. И тот же XNA ЦП нагружает значительно. Впрочем надо профилировать, чтоб точно сказать что в XNA игрушках (например та же Террария) загружает ЦП.
                0
                Это реальный способ ускорить игру, другие способы, когда разные подсистемы в отдельные потоки складывают просто не работают из-за тесной связи между ними. Анимация связана с физикой, которая связана с триггерами гейплея, которые вообще в скриптах обрабатываются и тесно связаны с ИИ.
              0
              > Фактически мы можем принять как данность, что даже на слабом железе функция update_game() вызывается 25 раз в секунду. Поэтому наша игра будет обрабатывать пользовательский ввод и обновление состояние без особых проблем даже в случае, когда отрисовка выполняется на частоту 15 кадров в секунду.

              Если говорить простыми словами, то я вижу алгоритм таким:

              бесконечный цикл {
                  если (update_game() выполняется не чаще 25 раз в секунду) {
                      update_game();
                  }
                  display_game();
              }

              Ну не могу я представить ситуацию, когда при последовательном вызове функций одна будет выполняться чаще, чем другая, при том, что ее запуск «прореживают». В статье ведь не говорится о многопоточности etc. Что я недопонял?
                +2
                Точно так. И у меня закрались такие же сомнения. От описанного подхода недалеко до мультитреда. Об этом я написал выше. Думаю автор просто не стал усложнять представление концепции для легкого восприятия навичками.
                  +3
                  > навичками
                  Это не «падонкаффский» диалект. Тупо опечатался. Извините.
                  0
                  Запуск update_game не прореживают, а «стабилизируют»: она может запускаться как реже (если, к примеру, display_game уложится в 0.01с), так и чаще (0.1с на отображение). Ваш алгоритм на это не способен, увы.
                    0
                    Ъ. Пока писал самый первый комментарий «где же отличие?», до меня дошло, но я случайно нажал на Alt-Home, и простыня комментария с объяснением стерлась (>_<)

                    Отличие оказалось в том, как алгоритм будет реагировать на задержку. В моем случае — никак (^_^) В случае алгоритма из статьи оный при выявлении задержки будет обновлять мир столько раз, на сколько этот мир «опаздывает».

                    Моя ошибка была в том, что я сделал неверные выводы. Да, update_game() не будет выполняться каждую 1/25 секунды. Обновление может вызываться себе приблизительно с таким интервалом, а потом display_game() напорется на сложную сцену, отрисовка которой займет 1/20 секунды, и следующий update_game() будет вызван уже через 1/5 секунды (5/25 — три интервала, короче), но благодаря такому построению игрового цикла, как в статье, он будет вызван не один, а пять раз, чтобы компенсировать задержку (таким образом, в это время между вызовами update_game() будет проходить 1-2 мс). НО. В среднем (по больнице, есессено, и тем больше по больнице, чем круче скачки FPS) update_game() будет вызываться именно 25 раз в секунду (неважно, с какими промежутками между вызовами), а значит, что можно считать, что между вызовами update_game() в среднем проходит 1/25 секунды.

                    И, наконец, описание своими словами алгоритма из статьи:

                    бесконечный цикл {
                        если (время между вызовами update_game() больше 1/25 секунды) {
                            [время_между_вызовами_update_game_в_секундах / (1/25)] раз сделать { update_game(); }
                        }
                        display_game();
                    }

                    Есессено, что значение времи между вызовами с учетом единиц измерения (секунд) будет дробным, а значит, что после деления на 1/25 (умножения на 25) нужно взять целое число, но это уже нюансы (равно как и переменные, точки отсчета etc).
                      0
                      Вы предлагаете игнорировать изредка возникающую проблему, автор предлагает её решение. Кроме того, в среднем 25 будет как раз у автора; у вас получится меньше (совсем немного), но это может легко привести, к примеру, к рассинхронизации в мультиплеере.

                      Ваш новый алгоритм уже стал сложнее предложенного, и вы забыли про время выполнения самого update_game и MAX_FRAMESKIP. И то и то может иметь значение. А с учётом нюансов, код усложнится ещё сильнее.
                        0
                        Я хотел передать общий смысл моей ошибки и причин моего непонимания (^_^)' Естественно, что чем больше требований (точнейшая синхронизация, многопоточность, мультиплеер, да хоть банально replay-movie), тем больше нюансов и тем сложнее алгоритмы.
                  0
                  Как же хорошо было с контроллерами прерываний… Нажали кнопку или двинули мышкой и сразу прерывание и его обработка, а пока игрок ничего не вводит, только обсчитываем и отрисовываем. :)
                    0
                    Довольно часто этот баг встречается у начинающих разработчиков — начинаешь двигать мышью и игра резко начинает жрать много процессора. Поэтому, если по правильному, положение мыши сохраняют и обрабатывают только в update(). Тогда независимо от кол-ва движений мышью игра потребляет одно и то же кол-во ресурсов.
                      –1
                      Если обработка движения мыши начинает жрать много процессора, выкиньте этот процессор.
                        0
                        Вы плохо себе представляете логику работы игры.
                        Если при каждом событии мыши вы начинаете выполнять относительно непростые действия, то легко получается, что у вас эта обработка фактически вызывается более чем 100 раз в секунду. Для игры это бессмысленно, а нагрузку дает (особенно если это Flash, а если мобильное приложение, то вы бессмысленно «выжигаете» батарею).
                          0
                          Не понимаю, в чем разница? Биос все равно вызывает прерывания по изменению состояния датчиков. Если боитесь слишком часто обрабатывать ввод, то обрабатывайте не каждое изменение, а время проверяйте или в стек записывайте и обрабатывайте уже в самой игре.
                            0
                            Теперь перечитайте мое первое сообщение :)
                              0
                              Вы ответили как противопоставление обработке прерывания при его возникновении. Объявили обработку прерывания багом. И я объяснил, что обработка прерывания это не баг, а вполне рабочий вариант. Возможно, фраза «обработка прерывания» вызвала у Вас ассоциации с работой логической модели игры в зависимости от введенных данных. Это не так. Я про логику игры говорил только, что обсчитываем и отрисовываем, когда игрок ничего не вводит. А Вы?
                                0
                                Если вы при событии MOUSE_MOVE сохраняете координаты мыши, а обрабатываете после, то у вас по-любом вариант с update/draw, а не обработка по событию.

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

                                «обрабатывайте не каждое изменение, а время проверяйте или в стек записывайте и обрабатывайте уже в самой игре» — это update/draw, и ее все используют.
                                  –1
                                  Само появление события mouse_move — это и есть обработка хардверного прерывания от устройства. Прочитайте внимательно первое сообщение. Вы вообще не по теме отвечаете. Логика игры — это уже выше уровнем. Повторюсь, что логику обсчитываем совершенно отдельно.
                    +3
                    Вы издеваетесь (это больше к автору и приверженцам этой тактики), какие циклы, что за 'прошлый век'!

                    Событийный механизм — когда обновление экрана делается по времени по алгоритму XX кадров в YY интервал, когда события в игре выполняются строго когда нужно, когда не объекты сдвигаются на пиксел на game_update(), а их координаты вычисляются в момент их запроса.

                    И не будет тогда ни проблем с тачпадом (когда при меленном выводе невозможно нарисовать гладкую кривую, хотя проблемы могут вытекать еще глубже — из железа и драйверов), ни глюков с разными скоростями, набегающих из-за ошибок вычислений (того же float — ошибки с ним заметнее) и многого другого можно просто не заметить/не встретить, если правильно изначально НЕ ОРГАНИЗОВЫВТЬ цикл.

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

                    p.p.s. FPS и 30 более чем достаточно, проблема чаще возникает не из-за низкого FPS а из-за его неравномерностей, и самое простое — сначала считаем изображение, затем ждем до момента вывода, затем выводим — т.е. должен быть небольшой лаг в 1/30 секунды (бывают алгоритмы, выдающие лаг в 2-3 кадра).
                    Еще неплохим решением со слабым железом может быть вывод недоконца построенного изображения (особенно если есть возможность ухудшить качество без уменьшения информативности) это воспринимается гораздо лучше чем пропуск кадров.
                      +3
                      Напишите похожую статью про событийный механизм в играх, заинтересовался очень даже… Раньше нигде не встречал подобного подхода.
                        0
                        И мне интересно… Я видимо неправильно понял. Перечитаю еще несколько разков. Но пока сдается мне, что это подобие первого решения в данной статье, но с событиями. Наверняка я ошибаюсь.
                          0
                          Одно время уже обсуждали на Хабре события и событийный подход к программированию (кажется, для экономии энергии (читайте — аккумулятора)). Лично я сделал для себя такой вывод: пока не появится удобного (в плане строк кода, подключаемых библиотек, кроссплатформенности и тому подобных шняг) API для аппаратной поддержки событий (прерывания-то есть, но многим работать с ними не очень удобно, да и абстракции вроде API для универсального доступа к устройствам накладывают свои ограничения), события и их обработка в итоге сведутся к тому же бесконечному циклу.
                        • НЛО прилетело и опубликовало эту надпись здесь
                          +1
                          наш рабочий проект создавался еще когда не было операционных систем, точнее они были, но их использование было неоправдано. а «многозадачность» нужна. я то тут не так давно, но вот с опухшими глазами смотрю на это.
                          так вот, там реализован sched вот как раз по этому принципу, только более комплексно. очереди сообщений 2х-милисекундные, 20ти, 100. сам считает таймслайсы, и т.п.
                          сейчас это все, причем существенно эффективнее делает операционная система. хоть линух, хоть винда дает возможности многозадачности другого порядка.
                          собственно тут именно эта задача и стоит. два отдельных процесса — обработки состояния игры и ее отображения должны быть полностью независимы, чего собственно и добивается автор пытаясь абстрагировать механику игры от фпс.

                          как мне кажется проще и правильнее сделать два треда. в одном updateGame, в другом displayGame. и соответственно первый второму через пайп скармливает данные для отображения.
                          чем колхозить вот такую вот «двухзадачность», которая еще и при этом не сможет двухядерник даже напрячь.
                          0
                          кстати про аппроксимацию и интерполяцию. читал про игру Supreme Commander. там обсчет игрового состояния идет 10 раз в секунду всего. при этом фпс 60 рисует абсолютно плавное, и при этом анимированное движение. анимация вся явно в треде отображения. тред игросостояния
                          я так полагаю, что тред отображения при этом всегда должен запаздывать. ибо ракета должна попасть в цель, что может произойти по времени между этими двумя игровыми отсчетами. и тред игросостояния собственно не просто следующее состояние" должен выдавать, а всю достаточную для аппроксимации информацию.
                          и кстати игра утилизирует 2 треда.
                            0
                            хмм… редактирование съело кучу текста… ну ладно…
                              0
                              Я думал о границах применения интерполяции. Если прогнозировать движение объекта, на которое оказывает влияние пользовательский ввод или другие в общем случае случайные факторы, то прогноз и интерполяция с использованием текущих параметров движения объекта будет давать пренебрежимую погрешность лишь на коротких промежутках времени. Видимо 1/10 секунды — достаточно короткий таймсэмпл.
                              Про физику и дифф. ур-ия тут умолчим.
                              0
                              про Unity3d не совсем верно описано.
                              Да, там нет единого цикла, который обновляет игру. Зато каждый объект может обновить свое(ну или если надо, то и другого объекта) состояние.
                              В юнитях в классах, наследующиесях от MonoBehaviour, есть такие методы как Update, FixedUpdate, LateUpdate.
                              Update вызывается при обновлении каждого фрейма. LateUpdate вызывается после выполнения Update(к примеру, на апдейте мы пересчитали данных, а на LateUpdate мы отрисовали с использованием уже обновленных данных).

                              А FixedUpdate — это такой же апдейт, но вызывается раз в определенное время, которое задается в настройках проекта (то есть не зависит от быстродействия девайса).
                                +1
                                А кем все эти эвенты вызываются? В фоне петля должна иметься какая-то. Либо все компоненты — отдельные треды в некотором пуле. Так или иначе петля есть?
                                  0
                                  Ну да, движок вызывает эти методы. Цикл зарыт в самом движке. При этом каждый компонент, назначенный гейм-объекту, является по своей сути объектом. Все компоненты по сути регистрируется у движка и в назначенное время движок дергает эвент у каждого из них.
                                +2
                                Достаточно много работаю в геймдеве и согласен, новички очень часто не понимают этой темы. Теперь будет ссылка, куда их можно послать :)
                                  0
                                  Я тоже не первый год работаю в геймдеве, и мне эта ссылка «не очень». Лучше отправить человека в открытый простой движок, например HGE для 2D, или OGRE если нужно что-то повеселее и пусть он там полазит.
                                  0
                                  Реквестиирую флешеров в тред))
                                  Поделитесь своими размышлениями по сабжу.
                                    0
                                    А собственно что вы хотите услышать? Все приведенные принципы работают для любого языка программирования. Или вы думаете что пульс игры на Actionscript выглядит по другому? :)
                                      0
                                      Ну так то оно так, только даже таймер во флеше от фпс зависит и его обновление не возможно чаще чем раз в кадр. Т.е. 1/25-30 секунды или 1/60 секунды.
                                        0
                                        Насколько я знаю там эту систему привязывают к Enter Frame-у и работает она аналогично — проверяет время, которое было между кадрами, вызывает необходимое количество update_game() после этого вызывает уже display_game()

                                        Но переменного FPS на флеше не получится, потому что там в любом случае ФПС ограничен настройкой флеш плеера.
                                    0
                                    В Box2d вроде как единственный верный путь — использовать постоянный шаг физики с переменным шагом отрисовки. К сожалению, я не программист, поэтому не могу сказать точно. Там даже в комментариях к коду ссылка на статью есть. ;)
                                      0
                                      Не копался в Box2D, но читал/смотрел туториал про то как создается легковесный игровой физический движок. Как раз «проповедовался» подход на основе переменных промежутков времени. Применительно к линейному перемещению — просто вычислялось приращение позиции в зависимости от скорости и пройденного времени. От интегрирования дифф. уравнений настоятельно рекомендуют отказаться.
                                      Поэтому подход с постоянным шагом не является и не заявляется как единственно верный. Но на мой взгляд — это способ получить более реалистичную физику, и такой подход в чем-то сильно упрощает реализацию физики. Конечно, появляются сложности выдерживания этого постоянного шага. Потому я и писал, что тред с обновлением состояния (или только тред физики) должен иметь наивысший приоритет.
                                        0
                                        Ну возможно для разных задач имеет смысл использовать разный подход. Я копался на форумах и основной подход был в воспроизводимости результатов. При использовании переменного шага воспроизводимость не может быть 100%, ибо существуют ошибки округления и прочий квантовый шум. А идея как раз была в 100% воспроизводимости (те же реплеи, но уже с применением реальной физики).

                                        Вот, что я использую в своём прототипе:

                                        -(void) update: (ccTime) dt // Using FIXED timestep
                                        {
                                        static double timeAccumulator = 0;

                                        timeAccumulator += dt;

                                        if (timeAccumulator > (MAX_CYCLES_PER_FRAME * UPDATE_INTERVAL)) {
                                        timeAccumulator = UPDATE_INTERVAL;
                                        }

                                        while (timeAccumulator>=UPDATE_INTERVAL) {

                                        timeAccumulator -= UPDATE_INTERVAL;

                                        world->Step(UPDATE_INTERVAL, velocityIterations, positionIterations);

                                        for (b2Body *b = world->GetBodyList(); b; b=b->GetNext()) {
                                        if (b->GetUserData() != NULL) {
                                        }
                                        }
                                        //
                                        self.hero.jumpTimeout--;
                                        [self.hero update];
                                        //
                                        [self processContacts];
                                        [self addBody];
                                        [self removeBody];
                                        }
                                        }

                                        Не работает разметка что-то…
                                          0
                                          Как я понял в этом коде вычисляется сколько заданных квантов времени укладывается в прошедшем промежутке времени. Однако в аккумуляторе опять будет накапливаться значительная ошибка, т.к. при малом «dt» ошибка округления (особенно при хранении dt во float) будет достаточно велика.
                                            0
                                            Ну фик знает, как я уже сказал, я не программист и скопипастил этот код чуть ли не с приведённого источника. Как-нибудь на досуге покажу знакомым гуру, если вдруг критично станет.
                                      0
                                      Прим. перев.: в движке NeoAxis для физического объекта можно выставлять флаг Continuous Collision Detection; подозреваю, что по нему как раз и выполняется обработка, подобная описанной выше реализации игрового цикла.

                                      CCD используется для детектирования коллизий быстрых объектов. Насколько я помню, есть 2 основных подхода:
                                      1. Увеличить TICKS_PER_SECOND;
                                      2. Быстрый объект растянуть по всему пути его следования.
                                        0
                                        Как я понял в NeoAxis делается интерполяция все-таки — просчитываются два положения между стандартными тиками и вычисляется позиция в промежутке.

                                        >1. Увеличить TICKS_PER_SECOND;
                                        В шутерах будет напряжно.

                                        >2. Быстрый объект растянуть по всему пути его следования.
                                        Сложно реализовать при криволинейных траекториях (особенно при действии силовых полей).
                                        0
                                        Как я понял в NeoAxis делается интерполяция все-таки — просчитываются два положения между стандартными тиками и вычисляется позиция в промежутке.

                                        >1. Увеличить TICKS_PER_SECOND;
                                        В шутерах будет напряжно.

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

                                        >2. Быстрый объект растянуть по всему пути его следования.
                                        Сложно реализовать при криволинейных траекториях (особенно при действии силовых полей).

                                        Да. Но при прямолинейном движении иногда можно получить выигрыш.
                                          0
                                          > Поэтому частота обработки увеличивается только для объекта, для которого CCD включен (для пули). Получается как раз то, о чем вы написали — вычисляются промежуточные позиции.

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

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

                                          Самое читаемое