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

C#: detectando cuando una ventana WPF es minimizada

Tanto si utilizamos un form como si utilizamos una ventana WPF la propiedad que tenemos que comprobar es WindowState. La diferencia viene en que un form el evento que se dispara al minimizar es _Resize y en una ventana WPF es _StateChanged.

En mi código quiero minimizar el form que contiene la barra de herramientas si minimizo la ventana principal, e igualmente quiero devolverla a su posición si maximizo o devuelvo a su posición a la principal.

Capture

Fuente: StackOverflow

C#: detectando cuando una ventana WPF es minimizada

Visual C#: obtener resolución del escritorio

La clase System.Windows.Forms.Screen nos ofrece la propiedad Screen.AllScreens que nos da acceso a una colección de todas las pantallas detectadas por el sistema. La propiedad Screen.PrimaryScreen nos da acceso a la pantalla principal.

La resolución la obtenemos de la propiedad Bounds del objeto:

Rectangle resolution = Screen.PrimaryScreen.Bounds;

La propiedad Screen.PrimaryScreen.WorkingArea nos ofrece el tamaño del área de trabajo.

Obtenido de stack overflow.

Visual C#: obtener resolución del escritorio

¿Cuándo usar el registro de Windows en vez de ficheros?

A la hora de crear una aplicación, a menudo nos vamos a encontrar que necesitamos reutilizar datos de una sesión anterior, una característica que dentro del mundo de la informática se conoce como persistencia. Lo más habitual es trabajar con ficheros, ya que al fin y al cabo el disco duro nos ofrece exactamente eso, la capacidad de almacenar datos que sobrevivan no sólo al ciclo de vida de la aplicación sino al apagado del ordenador.

Debemos tener en cuenta, sin embargo, que Windows nos ofrece una base de datos integrada en el sistema que también nos permite almacenar información pero con algunas ventajas:

  • Cada usuario tiene su propio registro. Esto implica que si queremos almacenar datos por usuario, no tenemos que crear nosotros mismos un sistema de usuarios, de permisos ni de absolutamente nada.
  • Ofrece una interfaz de clave/registro que no necesita ser parseada. Podemos almacenar datos arbitrarios en el registro sin tener que andar insertando separadores.
  • El sistema operativo nos ofrece una interfaz gráfica de gestión. Utilizando regedit podemos crear claves, modificarlas y borrarlas.
  • El registro es gestionado por el kernel. Si tu aplicación se cuelga o tiene cualquier problema, los cambios que hayas hecho en el registro seguirán estando ahí. Si el sistema entero se cuelga, es responsabilidad de Windows asegurarse de que el registro es válido.
  • El registro es seguro para hilos. Varios hilos o procesos pueden estar accediendo a la misma clave y podremos asegurar que las modificaciones son atómicas.

Por supuesto, el registro presenta también desventajas:

  • No vale para una gran cantidad de datos. El registro no está diseñado para guardar ese nivel de dos gigas que has creado, sino para almacenar unos pocos parámetros de configuración.
  • Dificultad de manejo. Al ser un enorme bloque de bytes, es difícil de gestionar y de crear backups.
  • Escasa portabilidad. Si me quiero llevar mi aplicación a otro escritorio, no me queda otro remedio que andar exportando claves, frente a la opción de tener un fichero de configuración que pertenezca a los ficheros de la propia aplicación.

Si utilizamos C#, la clase Registry (que podemos encontrar en el namespace Microsoft.Win32) nos facilita operaciones para trabajar con él.

Sacado de éste enlace.

¿Cuándo usar el registro de Windows en vez de ficheros?

Configure NetBeans / SDL 2.0.3 / MinGW

I will reproduce here the steps to configure SDL2.0.3 library for Netbeans with MinGW in an intel i7 (x86_64 architecture) and Windows 7 64 bit SP1. I will assume you have downloaded already the neccesary packages (netbeans, mingw x86_64 and SDL 2.0.3) and know how to configure environment variables. If you don’t just google “windows 7 set environment variables” and follow instructions; it’s an easy and straightforward process.

  1. Install Netbeans (C/C++ version) from scratch. I installed stable version 7.4
  2. Install MinGW x86_64 version. The path where it was installed will be henceforth called %MINGWPATH%”
  3. Uncompress SDL tar file to %SDLPATH%
  4. Add “%MINGWPATH%/msys/1.0/bin” and “%MINGWPATH%/bin” to the PATH environment variable.
  5. Start netbeans; it should automatically detect your mingw tool collection. If it doesn’t, go to tools -> Options -> c/c++ -> build tools tab and click on add collection. Select the /bin folder of the %MINGWPATH% as the base directory, and %MINGWPATH%/msys/1.0/bin for the make.exe if it’s not automatically selected.
  6. Now create a new project and create a c++ application.
  7. In Project properties -> c++ compiler -> include directories and headers -> add folder %SDLPATH%/x86_64-w64-mingw32/bin
  8. Do not close the window; on the Linker section add %SDLPATH%/x86_64-w64-mingw32/lib to “additional library directories”.
  9. Finally, add these libraries in this order: mingw32.a, SDL2main.a, SDL2.a. The first file can be found on the %MINGWPATH%/x86_64-w64-mingw32/lib and the other two in the %SDLPATH%/x86_64-w64-mingw32/lib.
Now you should be able to succesfully compile an application that can make use of the SDL API. To create SDL applications, google a bit more. 🙂
Configure NetBeans / SDL 2.0.3 / MinGW

Aprender C: desarrollando un juego de ajedrez (II)

En el anterior post comenté que el tablero es un array de punteros a una variable de tipo pieza. En un principio pensé en crear una variable para cada pieza del juego, pero enseguida deseché la idea. ¿Qué valor me aporta una pieza por sí sola, sin estar situada en una casilla de un tablero? Un array de punteros me facilita la vida; si el puntero apunta a NULL entonces puedo considerar que la casilla está vacía. De lo contrario, si apunta a una variable de tipo pieza, sé que una pieza de ese tipo ocupa esa casilla, que es al final de cuentas lo que a mí me interesa. Además, de esta forma sólo necesito crear una variable por cada tipo de pieza y color; un único peón blanco, un único peón negro, un caballo blanco, etc. La declaración de variables e inicialización es como sigue:

tPiece  pb, pn, tb, tn, cb, cn, ab, an, rb, rn, reyb, reyn;

void initPieces() {
    
    pb.color = tb.color = cb.color= ab.color= rb.color= reyb.color=WHITE;
    pn.color= tn.color = cn.color= an.color= rn.color= reyn.color=BLACK;
    pb.rol= pn.rol=PAWN;
    tb.rol= tn.rol = ROOK;
    cb.rol= cn.rol=KNIGHT;
    ab.rol= an.rol=BISHOP;
    rb.rol= rn.rol=QUEEN;
    reyn.rol= reyb.rol= KING;
    
}

Estas variables y procedimiento yo los he incluído en ficheros aparte llamado pieces.h y pieces.c.

Las piezas están declaradas como variables globales; esto no es especialmente elegante, pero sí efectivo.

El tablero también debe ser iniciado al principio de la ejecución del programa, puesto que un puntero declarado pero no inicializado apunta a direcciones aleatorias de memoria – y aunque probablemente el sistema operativo no nos permitiría andar modificando contenido aleatorio de nuestra memoria, es una buena práctica inicializar los punteros.

void initBoard(tPiece* t[][8], int alto, int ancho) {

    int i,j;
    for( i = 0; i < ancho; i++ ) {
        for( j = 0; j < alto; j++ ) {
            t[i][j] = NULL;
        }
    }
    
}

Bien, pues con esto ya tenemos nuestro tablero y piezas listos para ser usados.

Aprender C: desarrollando un juego de ajedrez (II)

Aprendiendo C: desarrollando un juego de ajedrez

Como he decidido finalmente orientar mi carrera profesional a la industria del entretenimiento digital, y salí de la universidad con conocimientos de C muy bajos, he tomado la determinación de programar un juego de ajedrez en C para aprender (parte de) ese lenguaje.

Sin más dilación, hoy explicaré los tipos y estructuras de datos usadas.

Una pieza de ajedrez es un elemento del que (por el momento) nos interesa abstraer dos características: color y papel que juega. Mi declaración es la siguiente:

typedef struct {
   tColor color;
   tRol rol;
 } tPiece;

Tanto tColor como tRol son enumeraciones. En C una enumeración es un conjunto de elementos nombrados por el programador a los que el compilador asigna un valor en función de su orden. De esta manera,

typedef enum {WHITE, BLACK} tColor;
typedef enum {PAWN,ROOK, KNIGHT, BISHOP, QUEEN, KING} tRol;

A la hora de compilar, WHITE será sustituido por el valor 0, BLACK por 1. De igual modo, PAWN 0, ROOK 1, KNIGHT 2, etc.

Finalmente, el tablero es un array de 8×8. Ojo, es un array DE PUNTEROS a una variable de tipo tPiece:

tPiece* t[8][8];

Al por qué considero que debe ser un array de punteros, daré explicación en el siguiente post.

Aprendiendo C: desarrollando un juego de ajedrez