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

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

Вступление

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

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

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

Отличие "природного" времени от времени "компьютерного".

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

Дискретность (Квантование)

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

Неоднородность

В один момент «природного» времени ядро процессора выполняет только одну операцию. Это и придает «компьютерному» времени свойство, отличающее его от «природного» времени – это свойство неоднородности его течения. То есть, для всех наших игровых объектов время течет не одновременно.

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

Высокопроизводительный таймер

Для измерения временных отрезков в программах целесообразно использовать функции, дающие сравнительно высокую точность. В ОС Windows используется QueryPerfomanceCounter, в Linux gettimeofday. Точность может отличаться на различных процессорах, но они почти всегда дают точность лучше, чем 1 миллисекунда.

Типичный main loop

float dt = 0.0f;
while (is_run) {
    if (active == false) WaitMessage();
    timer.start();
    doUpdate(dt);
    doRender();
    dt = timer.elapsed();
}

Виды синхронизации

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

Интегрирование

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

void onUpdate(float dt) {
    value += dt;
}

Это пример простейшего интегрирования.

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

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

vec3 pos;
vec3 velocity;
vec3 force;

void onUpdate(float dt) {
    pos += velocity * dt + (force * dt * dt) / 2;
    velocity += force * dt;
}

Здесь мы видим известную школьную формулу:

S = v0*t + (a * t^2) / 2

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

Теперь поговорим о недостатках этого метода. Дело в том, что формула для интегрирования не всегда такая простая, как это могло бы казаться. Могу привести в пример игру S.T.A.L.K.E.R, в которую я так и не смог нормально поиграть на своем слабеньком компьютере – но не из-за того, что fps был совсем уж неприемлемым, а как раз по причине того, что разработчики использовали для сглаживания вращения камеры нечто вот такое:

vec3 camera_angles;
void onUpdate(float dt) {
    vec3 new_camera_angles = input.getMouseDelta();
    float k = 0.5f; // k = 0.0f..1.0f
    camera_angles = new_camera_angles * k + camera_angles * (1.0f - k);
}

Из-за этого камера была слишком инертной при низких значениях fps. Казалось бы, простое и очевидное сглаживание, но неправильно реализованное, оно создает дискомфорт для игрока при низких значениях fps, не позволяя наслаждаться всеми прелестями зоны отчуждения. Как результат — в S.T.A.L.K.E.R я так и не играл.

Fixed time step

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

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

Естественно, метод тоже содержит подводные камни:

• Обновление логики больше не связано с кадрами, поэтому движения могут выглядеть не такими плавными, как при интегрировании. При этом не имеет смысла показывать игроку больше кадров в секунду, чем частота обновления логики. Поэтому частоту обновления логики лучше сделать равной частоте кадровой развертки – скажем, 60, 85, или 120. Если игра слишком динамичная, лучше сделать 120, многие современные игровые мониторы умеют показывать столько кадров.
• Существует проблема, которую я называю «временной коллапс», ну или можно называть это «черной дырой времени». Проблема возникает, когда время выполнения функции onUpdate() довольно велико (допустим, там рассчитывается вся физика, и было добавлено огромное количество объектов). При этом за игровой цикл onUpdate() начинает вызываться все большее количество раз, и программа просто зависает. Мы тратим много времени на onUpdate(), а значит нам нужно компенсировать прошедшее время уже двумя onUpdate(), два onUpdate() – это уже четыре onUpdate() в следующем цикле – и так далее. Поэтому необходимо контролировать время просчета логики, и если оно слишком велико, нужно его ограничивать. Естественно, после этого уже никакой синхронности ожидать не приходится, но это спасет от зависания. При этом пользователю можно сообщить о том, что его компьютер не справляется с расчетами, и предложить приобрести более быстрый компьютер :)

Периодические события

Перейдем к более конкретным примерам. Периодическим событием я называю событие, которое происходит через фиксированный временной промежуток. Примером такого события является реализация вызова onUpdate() с заданной частотой при реализации fixed time step.

void onUpdate() { }

float freq = 10.0f;
float time_to_event = 0.0f;

void doUpdate(float dt) {

    float ifreq = 1 / freq;
    time_to_event -= dt;

    while (time_to_event <= 0.0f) {
        event();
        time_to_event += ifreq;
    }
}

В данном примере событие onUpdate() будет вызываться с частотой freq раз в секунду. Мы видим, что если ifreq будет меньше dt (то есть заданная частота вызова будет больше fps — частоты вызова doUpdate()), то onUpdate() вызовется несколько раз в пределах одного doUpdate(). Вроде бы все правильно, но что если представить, что onUpdate() создает объект, который тоже имеет переменное во времени состояние?

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

Давайте посмотрим, как этого избежать:

class Bullet {
    void update(float dt) { }
};

float fire_rate = 10.0f;
float time_to_shoot = 0.0f;
vector <Bullet *> bullets;

void onUpdate(float dt) {
    for (int i=0; i<bullets.size(); i++) {
        bullets[i]->update(dt);
    }
    float ifire = 1 / freq;
    time_to_shoot -= dt;
    while (time_to_shoot <= 0.0f) {
        Bullet *bullet = new Bullet();
        bullet->update(-time_to_shoot);
        bullets.push_back(bullet);
        time_to_shoot += ifreq;
    }
}

В данном примере мы компенсируем пуле время, которое прошло с момента ее запуска до следующего вызова onUpdate(), где Bullet::update() будет вызван уже в штатном порядке.

А что будет, если при стрельбе игрок будет двигаться, или направление выстрела будет меняться? Это тоже нужно учитывать:

class Bullet {
    void update(float dt) { … }
    void setTransform(const Transform &tf) { … }
};

float fire_rate = 10.0f;
float time_to_shoot = 0.0f;
vector <Bullet *> bullets;
Transform old_tf;
bool first_update = true;

void onUpdate(float dt) {
    for (int i=0; i<bullets.size(); i++) {
        bullets[i]->update(dt);
    }

    Transform tf = getBarrelTransform();
    if (first_update) {
        old_tf = tf;
        first_update = false;
    }

    float ifire = 1 / freq;
    float k = time_to_shoot / dt;
    float delta_k = ifire / dt;
    time_to_shoot -= dt;

    while (time_to_shoot <= 0.0f) {
        float k = 1.0f - (-time_to_shoot / dt);
        Bullet *bullet = new Bullet();
        bullet->setTransform(lerp(old_tf, tf, k));
        bullet->update(-time_to_shoot);
        bullets.push_back(bullet);
        time_to_shoot += ifreq;
    }
    old_tf = tf;
}

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

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