Структуры данных для интерполяции и многопоточности?

В последнее время я сталкиваюсь с некоторыми проблемами, связанными с дрожанием кадров, и кажется, что лучшим решением было бы то, что было предложено Гленном Фидлером (Gaffer on Games) в классической программе Fix Your Timestep! статья.

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

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

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

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

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

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

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

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

Для каждого класса объекта создайте сопутствующий класс, который сможет содержать объект Visual State. Этот объект будет создан при моделировании и использован для рендеринга. Интерполяция легко подключается между ними. Если состояние является неизменным и передается по значению, у вас не возникнет проблем с потоками.

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

пример

Традиционный дизайн

class Actor
{
  Matrix4x3 position;
  float fuel;
  float armor;
  float stamina;
  float age;

  void Simulate(float deltaT)
  {
    age += deltaT;
    armor -= HitByAWeapon();
  }
}

Использование визуального состояния

class IVisualState
{
  public:
  virtual void Interpolate(const IVisualState &newVS, float f) {}
};
class Actor
{
  struct VisualState: public IVisualState
  {
    Matrix4x3 position;
    float fuel;
    float armor;
    float stamina;
    float age;

    virtual auto_ptr<IVisualState> Interpolate(const IVisualState &newVS, float f)
    {
      const VisualState &newState = static_cast<const VisualState &>(newVS);
      IVisualState *ret = new VisualState;
      ret->age = lerp(this->age,newState.age);
      // ... interpolate other properties as well, using any suitable interpolation method
      // liner, spline, slerp, whatever works best for the given property
      return ret;
    };
  };

  auto_ptr<VisualState> state_;

  void Simulate(float deltaT)
  {
    state_->age += deltaT;
    state_->armor -= HitByAWeapon();
  }
}

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

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

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

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

Когда я писал материал для интерполяции, я работал с графикой на частоте 60 Гц и физикой на частоте 30 Гц. Оказывается, что Box2D гораздо стабильнее, когда он работает на частоте 120 Гц. Из-за этого мой интерполяционный код получает очень мало пользы. При удвоении целевой частоты кадров физика в среднем обновляется дважды за кадр. С джиттером это тоже может быть в 1 или 3 раза, но почти никогда не бывает 0 или 4+. Более высокий уровень физики как бы решает проблему интерполяции. При работе с физикой и частотой кадров при 60 Гц вы можете получать 0-2 обновления за кадр. Визуальная разница между 0 и 2 огромна по сравнению с 1 и 3.

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

Как правило, это требует больше усилий, чем система с переменным временным шагом (при разумном диапазоне частот кадров, в диапазоне 25–100 Гц).

Я попробовал метод фиксированного временного шага + интерполяции один раз для очень маленького прототипа - без многопоточности, но с обновлением логики с фиксированным временным шагом и как можно более быстрым рендерингом, когда он не обновляется. Мой подход заключался в том, чтобы иметь несколько классов, таких как CInterpolatedVector и CInterpolatedMatrix, которые хранят предыдущие / текущие значения и используют аксессор из кода рендеринга для извлечения значения для текущего времени рендеринга (которое всегда будет между предыдущим и текущее время)

Каждый игровой объект в конце своего обновления устанавливает свое текущее состояние в набор этих интерполируемых векторов / матриц. Такого рода вещи могут быть расширены для поддержки многопоточности, вам потребуется как минимум 3 набора значений - одно, которое обновлялось, и как минимум 2 предыдущих значения для интерполяции между ...

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

ИМХО, лучше всего идти с переменным временным шагом - если вы не делаете RTS или другую игру, в которой у вас огромное количество объектов, и вам нужно синхронизировать 2 независимых моделирования для сетевых игр (отправка только команд / команд по сеть, а не объектные позиции). В этой ситуации фиксированный временной интервал является единственным вариантом.

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

Да, к счастью, ключ здесь "имеет отношение к моему рендереру". Это может быть не более, чем добавление старой позиции и временной метки для нее в микс. Имея 2 позиции, вы можете интерполировать их между собой, и, если у вас есть система 3D-анимации, вы все равно можете просто запросить позу в тот или иной момент времени.

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

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

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

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

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

Трудно создать неизменный объект, поскольку все его дочерние элементы также должны быть неизменными, и вам нужно быть очень осторожным, чтобы все действительно было неизменным. Но если вы действительно осторожны, вы можете создать суперкласс, GameStateкоторый будет содержать все данные (и субданные и т. Д.) В вашей игре; «Модель» часть организационного стиля Модель-Представление-Контроллер.

Затем, как говорит Джеффри , экземпляры вашего объекта GameState быстры, эффективны с точки зрения памяти и поточно-ориентированы. Большим недостатком является то, что для того, чтобы что-то изменить в модели, вам необходимо пересоздать модель, поэтому вам нужно быть очень осторожным, чтобы ваш код не превратился в огромный беспорядок. Установка переменной внутри объекта GameState в новое значение более сложна, чем просто var = val;, с точки зрения строк кода.

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

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

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

В моей настройке у каждого RenderCommand есть 3d геометрия / материалы, матрица преобразования и список источников света, которые на нее влияют (все еще выполняется рендеринг вперед).

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