¿Estructuras de datos para interpolación y subprocesamiento?

¡He estado lidiando con algunos problemas de fluctuación de velocidad de fotogramas con mi juego últimamente, y parece que la mejor solución sería la sugerida por Glenn Fiedler (Gaffer en juegos) en el clásico Fix Your Timestep! artículo.

Ahora, ya estoy usando un intervalo de tiempo fijo para mi actualización. El problema es que no estoy haciendo la interpolación sugerida para renderizar. El resultado es que obtengo marcos duplicados u omitidos si mi velocidad de renderizado no coincide con mi velocidad de actualización. Estos pueden ser visualmente notables.

Por lo tanto, me gustaría agregar interpolación a mi juego, y estoy interesado en saber cómo otros han estructurado sus datos y códigos para respaldar esto.

Obviamente tendré que almacenar (¿dónde? / ¿Cómo?) Dos copias de la información del estado del juego relevante para mi renderizador, para que pueda interpolarse entre ellas.

Además, este parece ser un buen lugar para agregar subprocesos. Me imagino que un hilo de actualización podría funcionar en un tercera copia del estado del juego, dejando las otras dos copias como de solo lectura para el hilo de renderizado. (¿Es esta una buena idea?)

Parece que tener dos o tres versiones del estado del juego podría introducir rendimiento y, hasta ahora más importante, de confiabilidad y productividad del desarrollador, en comparación con tener una sola versión. Así que estoy particularmente interesado en métodos para mitigar esos problemas.

De particular interés, creo, es el problema de cómo manejar agregar y eliminar objetos del estado del juego.

Finalmente, parece que algún estado no es directamente necesario para renderizar, o sería demasiado difícil rastrear diferentes versiones de (por ejemplo: un motor de física de terceros que almacena un solo estado), por lo que me interesaría saber cómo las personas han manejado ese tipo de datos dentro de dicho sistema.

No intentes replicar todo el estado del juego. Interpolarlo sería una pesadilla. Simplemente aísle las partes que son variables y necesarias renderizando (llamémosle un "Estado Visual").

Para cada clase de objeto, cree una clase acompañante que pueda contener el objeto Visual State. Este objeto será producido por la simulación y consumido por el renderizado. La interpolación se conectará fácilmente en el medio. Si el estado es inmutable y se pasa por valor, no tendrá problemas de subprocesos.

El renderizado generalmente no necesita saber nada sobre las relaciones lógicas entre los objetos, por lo tanto, la estructura utilizada para el renderizado será un vector simple o, como máximo, un árbol simple.

Ejemplo

Diseño tradicional

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

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

Usando estado visual

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();
  }
}

Mi solución es mucho menos elegante / complicada que la mayoría. Estoy usando Box2D como mi motor de física, por lo que mantener más de una copia del estado del sistema no es manejable (clonar el sistema de física y luego tratar de mantenerlos sincronizados, podría haber una mejor manera, pero no pude encontrar uno).

En cambio, mantengo un contador de la generación de física. . Cada actualización incrementa la generación de física, cuando el sistema de física se duplica, el contador de generación también se actualiza.

El sistema de renderización realiza un seguimiento de la última generación renderizada y el delta desde esa generación. Al renderizar objetos que desean interpolar su posición, puede usar estos valores junto con su posición y velocidad para adivinar dónde se debe renderizar el objeto.

No mencioné qué hacer si el motor de física era demasiado rápido. Casi diría que no debes interpolar para un movimiento rápido. Si hiciste ambas cosas, deberías tener cuidado de no hacer que los sprites salten adivinando demasiado lento y luego demasiado rápido.

Cuando escribí el material de interpolación, estaba ejecutando los gráficos a 60Hz y la física a 30Hz. Resulta que Box2D es mucho más estable cuando se ejecuta a 120Hz. Debido a esto, mi código de interpolación tiene muy poco uso. Al duplicar la velocidad de fotogramas objetivo, la física en promedio se actualiza dos veces por fotograma. Con jitter que podría ser 1 o 3 veces también, pero casi nunca 0 o 4+. La tasa de física más alta soluciona un poco el problema de interpolación por sí mismo. Al ejecutar tanto la física como la velocidad de fotogramas a 60 hz, puede obtener 0-2 actualizaciones por fotograma. La diferencia visual entre 0 y 2 es enorme en comparación con 1 y 3.

Escuché que este enfoque de los pasos temporales sugería con bastante frecuencia, pero en 10 años en los juegos, nunca he trabajado en un proyecto del mundo real que se basara en un paso temporal fijo y una interpolación.

En general, parece más esfuerzo que un sistema de paso de tiempo variable (suponiendo un rango sensible de framerates, en el rango de 25Hz-100Hz).

Intenté una vez el enfoque de interpolación de tiempo fijo + fijo para un prototipo muy pequeño: sin subprocesos, pero con actualización lógica de paso de tiempo fijo y renderizado lo más rápido posible cuando no se actualiza. Mi enfoque allí era tener algunas clases como CInterpolatedVector y CInterpolatedMatrix, que almacenaban valores anteriores / actuales, y utilizaban un descriptor de acceso del código de representación, para recuperar el valor para el tiempo de representación actual (que siempre estaría entre el anterior y tiempos actuales)

Cada objeto del juego, al final de su actualización, establecería su estado actual en un conjunto de estos vectores / matrices interpolables. Este tipo de cosas podría extenderse para admitir subprocesos, necesitaría al menos 3 conjuntos de valores, uno que se estaba actualizando y al menos 2 valores anteriores para interpolar entre ...

Tenga en cuenta que algunos valores no se pueden interpolar trivialmente (por ejemplo, 'marco de animación de sprite', 'efecto especial activo'). Es posible que pueda omitir la interpolación por completo, o puede causar problemas, dependiendo de las necesidades de su juego.

En mi humilde opinión, es mejor seguir un paso de tiempo variable, a menos que esté haciendo un RTS u otro juego donde tenga una gran cantidad de objetos, y tenga que mantener 2 simulaciones independientes sincronizadas para juegos de red (enviando solo órdenes / comandos a través del red, en lugar de posiciones de objeto). En esa situación, el tiempo fijo es la única opción.

Obviamente tendré que almacenar (¿dónde? / ¿Cómo?) Dos copias de la información del estado del juego relevante para mi renderizador, para que pueda interpolarse entre ellas.

Sí, afortunadamente la clave aquí es "relevante para mi renderizador". Esto podría no ser más que agregar una posición anterior y una marca de tiempo para la mezcla. Dadas 2 posiciones, puede interpolar a una posición entre ellas, y si tiene un sistema de animación 3D, puede solicitar la pose en ese punto preciso de todos modos.

Realmente es bastante simple: imagina que tu procesador debe ser capaz de representar tu objeto de juego. Solía ​​preguntarle al objeto qué aspecto tenía, pero ahora tiene que preguntarle qué aspecto tenía en un momento determinado. Solo necesita almacenar la información necesaria para responder a esa pregunta.

Además, este parece ser un buen lugar para agregar subprocesos. Me imagino que un hilo de actualización podría funcionar en una tercera copia del estado del juego, dejando las otras dos copias como solo lectura para el hilo de renderizado. (¿Es esta una buena idea?)

Simplemente suena como una receta para el dolor adicional en este momento. No he pensado en todas las implicaciones, pero supongo que puede obtener un poco de rendimiento adicional a costa de una mayor latencia. Ah, y puede obtener algunos beneficios de poder usar otro núcleo, pero no sé.

Tenga en cuenta que en realidad no estoy investigando la interpolación, por lo que esta respuesta no la aborda; Solo me preocupa tener una copia del estado del juego para el hilo de renderizado y otra para el hilo de actualización. Por lo tanto, no puedo comentar sobre el tema de la interpolación, aunque podría modificar la siguiente solución para interpolar.

Me he estado preguntando sobre esto ya que he estado diseñando y pensando en un motor multiproceso. Entonces hice una pregunta sobre Stack Overflow, sobre cómo implementar algún tipo de patrón de diseño de "diario" o "transacciones" . Obtuve algunas buenas respuestas, y la respuesta aceptada realmente me hizo pensar.

Es difícil crear un objeto inmutable, ya que todos sus hijos también deben ser inmutables, y debe tener mucho cuidado de que todo sea realmente inmutable. Pero si tienes cuidado, podrías crear una superclaseGameState que contenga todos los datos (y subdatos, etc.) en tu juego; la parte "Modelo" del estilo organizativo Modelo-Vista-Controlador.

Luego, como dice Jeffrey , las instancias de su objeto GameState son rápidas, eficientes en memoria y seguras para subprocesos. El gran inconveniente es que para cambiar cualquier cosa sobre el modelo, es necesario volver a crear el modelo, por lo que debe tener mucho cuidado de que su código no se convierta en un gran desastre. Establecer una variable dentro del objeto GameState en un nuevo valor es más complicado que solovar = val; , en términos de líneas de código.

Sin embargo, estoy terriblemente intrigado por eso. No necesita copiar toda su estructura de datos en cada cuadro; simplemente copie un puntero a la estructura inmutable. Eso en sí mismo es muy impresionante, ¿no estás de acuerdo?

Comencé teniendo tres copias del estado del juego de cada nodo en mi gráfico de escena. Uno está siendo escrito por el hilo del gráfico de la escena, uno está siendo leído por el renderizador y un tercero está disponible para leer / escribir tan pronto como uno de esos necesite intercambiarse. Esto funcionó bien, pero fue demasiado complicado.

Entonces me di cuenta de que solo necesitaba mantener tres estados de lo que se iba a representar. Mi hilo de actualización ahora llena uno de los tres búferes mucho más pequeños de "RenderCommands", y el Renderer lee del búfer más nuevo en el que no se está escribiendo actualmente, lo que evita que los hilos se esperen uno al otro.

En mi configuración, cada RenderCommand tiene la geometría / materiales en 3D, una matriz de transformación y una lista de luces que lo afectan (aún haciendo renderizado hacia adelante).

Mi hilo de render ya no tiene que hacer ningún cálculo de eliminación o distancia ligera, y esto aceleró considerablemente las escenas grandes.