Implementando un sistema de replay en tu videojuego

En términos de almacenamiento, todo el input de una partida a un videojuego cualquiera (es decir, todos los botones o ejes cuyo estado es modificado y en qué intervalos) es, por lo general, relativamente pequeño. A excepción de los juegos cuyas partidas puedan prolongarse potencialmente durante horas (o días) y en los que almacenar toda la información relevante para una posterior reproducción ocuparía gigas, suele existir un sistema de replay para que podamos revivir, analizar, o enseñar a terceros nuestras hazañas. Me vienen a la mente los replays del Warcraft 3 que ocupaban un puñado de kilobytes, a pesar de ser un juego cuyas partidas podían prolongarse más allá de la media hora y en los que a lo largo del juego se podían generar cientos o miles de unidades que ejecutaban órdenes muy diversas*.

El primer requisito para poder implementar un sistema de replay en el que el tamaño de fichero sea mínimo es que todos los subsistemas relevantes sean deterministas, y especialmente las físicas. Yo ya sospechaba que Box2D lo es**, puesto que al ejecutar varias veces una simulación con los mismos datos iniciales la ejecución siempre terminaba en un estado aparentemente igual, pero el señor Catto lo confirma él mismo, siempre que se utilice, obviamente, el mismo build.

Una opción que consideré inicialmente fue, para cada frame de la partida, almacenar el estado de todos los elementos e ir inyectándolos frame a frame, lógicamente después de haber desactivado la entrada de input. Esto supone almacenar el estado de cientos de elementos por cada frame. Un disparate si no utilizamos algún método de compresión.

Para una partida de, supongamos, cinco minutos, tendríamos unos 18000 frames (5 minutos * 60 segundos por minuto * 60 frames por segundo si tenemos una tasa consistente de frames) con un simple array de 256 booleanos (y aquí conviene recordar que en C/C++ el bool ocupa un byte de memoria, no un bit) ya nos vamos a más de cuatro megas de replay. Y esto solamente para la información de input, sin entrar en otro tipo de información que el juego genere en tiempo de ejecución y sea necesaria para una reproducción fiel.

Una solución más compleja, pero también más económica, pasa por almacenar exclusivamente los cambios de estado que tengan lugar a lo largo de la partida en el input. Por ejemplo, podríamos utilizar un vector que contenga tantos elementos como frames en los que haya habido cambio de estado de algún elemento de input durante la partida, y en cada uno de esos elementos almacenaríamos únicamente el estado de los elementos de input relevantes y no de todos (es decir, si usamos cuatro botones, el estado de esos cuatro botones) en una máscara de bits de dos bytes***, junto con el número de frame en el que hubo cambio. Suponiendo una partida con mil cambios de estado del input, y un entero sin signo de dos bytes para almacenar el frame en el que hay cambio, tendremos 4 bytes * 1000 cambios de input = 4kb. Bastante más asequible. Si te fijas, hemos desacoplado el tamaño de almacenamiento del número de frames. La partida podría durar años, pero sin cambios en el input, el fichero de replay ocuparía 4 bytes^.

Por otro lado, raramente el replay de una partida podrá ser calculado a partir del input solamente. En nuestros juegos nos gusta introducir aleatoriedad. Por ejemplo, en el nivel 3 de la mazmorra a veces querremos que al héroe le aparezca un troll y otras veces una babosa infernal (no, no es el momento adecuado para hacer un chiste sobre tu ex). Esa aleatoriedad puede ser reproducida  en función del algoritmo de generación de números aleatorios que elijamos, pero por lo general va a ser más productivo que simplemente almacenemos el resultado de esa generación y lo reproduzcamos en el replay.

En resumen, necesitamos:

a) Un sistema que almacene todos los datos necesarios para la reproducción fiel de la partida: input y elementos generados aleatoriamente.

b) Un sistema que en el curso de una partida por un lado inyecte el input almacenado en los frames correspondientes y por otro reemplace lo que habitualmente sería generado a partir de un número aleatorio por otra información que sabemos que fue generada en la partida que queremos reproducir.

Por tanto, para realizar la implementación necesitamos:

  1. Definir una estructura sencilla para almacenar estado de los controladores y frame en que se produjo el cambio (frameControllerData):
    typedef struct {
        uint16_t frame;
        uint16_t controllerState;
    } frameControllerData;
  2. Definir una equivalencia entre elemento de controlador y bit que almacenará su estado (por ejemplo, el estado de LEFT_KEY se almacenaría en el bit 0 de controllerState, SPACE_KEY en el bit 1, etc):
  3. Crear un contenedor que almacenará todos los frameControllerData:
    std::vector<framecontrollerdata> m_replayData;
  4. Crear estructuras adicionales que almacenen otros datos necesarios para la reproducción (por ejemplo, si en el frame 78823 de la partida hemos generado aleatoriamente un monstruo, debemos almacenar este suceso y todas sus características – como posición, vida, arma que porta, etc – y luego recrearlo en el replay reemplazando al generador de monstruos). Simplificando mucho, el código sería algo parecido a esto:
    
    if (!replay) {
    
    monsterGenerator->addRandomMonster(world);
    
    } else {
    
    replayManager->addMonster(currentFrame);
    
    }
    
    

    Estas estructuras ya dependen de tu juego en concreto y no tendría sentido definirlas aquí, salvo a modo de ejemplo.

  5. Introducir en el gestor de eventos de input la operación condicional de almacenamiento de cambios de estado (en mi juego irá en los eventos keydown y keyup, pero puede variar en función del tipo de controlador que el juego use). En mi caso uso SDL, y el código queda así:
    void inputStruct::handleEvent(SDL_Event e) {
    switch(e.type) {
    [...]
    case SDL_KEYDOWN:
    
    case SDL_KEYUP:
    {
    // handle key events...
    }
    if (m_replayActive && e.key.repeat == 0)
    {
    
    // store input for replay
    
    replay.storeFrameData(frame, keyState);
    
    }
    
    break;
  6. Almacenar los datos del contenedor en un fichero una vez finalizada la partida. Las clases de stream son las que nos van a ayudar a hacerlo.
  7. Crear dentro de la clase Replay la funcionalidad para inyectar al gestor de input los datos que hemos almacenado en (3). Habitualmente lo que haremos será permitir que el bucle principal gestione el input como siempre y al principio de la actualización inyectemos el estado del input proveniente del replay en la estructura si estamos en el frame correspondiente. De ese modo todas las comprobaciones que se hagan del input se corresponderán con las del replay.
  8. Modificar aquellas partes del código que generen objetos de manera aleatoria para que puedan obtener los datos de la(s) estructura(s) de (4), de un modo similar al de (7).

Hay que tener en cuenta que esta solución está orientada a mi motor e indudablemente va a variar en tu implementación, aunque el razonamiento básico debería ser el mismo.

Para terminar, recomiendo leer este artículo de gamasutra que es un poco más extenso, pues profundiza en aspectos que yo no he tocado como compresión y gestión de deltas, aunque cuando fue escrito los requisitos de memoria eran mucho más restrictivos que en la actualidad.

 

 

*Cierto es que los señores de Blizzard saben muy bien lo que se hacen, pero esto debería servir como ejemplo de hasta qué punto los datos de input, debidamente almacenados, son insignificantes en términos de espacio.

**Si utilizas un motor como Unity o UE, es más que probable que ya traiga o esté disponible desde third parties un componente de replays con lo que este tutorial te serviría sólo en caso de que te decidas a implementarlo tú mismo.

***Podríamos usar un solo byte, pero no tendría sentido. La alineación (padding en inglés) nos obligaría a seguir gastando un byte adicional, y estaríamos tirando a la basura la capacidad de almacenar ocho elementos más de input.

^Puesto que el estado inicial siempre lo vamos a almacenar. Sin embargo, el sistema de ficheros de tu sistema operativo siempre va a obligar al fichero a ocupar típicamente un mínimo de 4kB en disco.

Advertisements
Implementando un sistema de replay en tu videojuego