19 de Junio, 2020

Usando listas en 8-bits

Escribo muy poco por aquí, y llevo bastante tiempo que lo que escribo es más bien una bitácora de novedades en lo que voy haciendo en temas gamedev (hacer juegos).

Tengo un rato libre, así que a ver si consigo explicar cómo uso listas en mis juegos de 8-bits.

Las listas son la base del sistema de entidades que uso en mis juegos, que es además el corazón del bucle principal:

mientras el juego no acabe:
   leer entrada teclado/joystick
   actualizar entidades <- ¡recorrer la lista!
   dibujar entidades <- ¡recorrer la lista otra vez!
   esperar si es necesario, para velocidad constante

Que en realidad es probablemente como lo haría en C en cualquier otro entorno, solo que con algunas características especiales:

  • Usando variables globales. Esto es por temas de rendimiento, porque variables locales o parámetros requerirá trabajar con la pila y malgastaremos valiosos ciclos de CPU.
  • Nada de memoria dinámica. En realidad son dos listas, una con la memoria libre y otra con la memoria en uso. Como curiosidad, la idea original la tomé de cómo MINIX gestionaba la memoria en una de sus primeras versiones.
  • Opcionalmente, escrito en ensamblador, por temas velocidad.

Lo primero es definir la estructura que define el tipo de dato que usamos en la lista, con una estructura tal que:

struct st_entity
{
    uint8_t type;
    uint8_t x;
    uint8_t y;
    void (*update)();
    void (*draw)();
    struct st_entity *n;
};

Muy simplificado solo tenemos lo necesario, más dos propiedades de ejemplo (x e y).

Con esta estructura ya podemos declarar algunas variables globales:

// sp_used es el principio de nuestra lista de "en uso"
// sp_new siempre apunta a la última entidad creada
struct sp_entity *sp_used, *sp_new;
// sp_free es la lista de memoria libre
struct sp_entity *sp_free;
// entities es donde realmente reservamos memoria estática, con límite
struct sp_entity entities[MAX_ENTITIES];
// sp_collect indica cuando hay memoria para liberar
// de sp_used a sp_free
uint8_t sp_collect;

He puesto comentarios en el código, así que espero que esté claro.

Lo siguiente es inicializar la memoria. En los 8-bits el compilador de C es bastante posible que soporte una sección para inicializar variables, pero sueles ser menos eficiente en temas espacio.

void init_entities()
{
    uint8_t i;

    // todo a 0
    memset(entities, 0, sizeof(struct st_entity) * MAX_ENTITIES);

    // podemos el puntero "siguiente" apuntando al siguiente en la lista
    for (i = 0; i < MAX_ENTITIES - 1; ++i)
        entities[i].n = entities + i + 1;

    // nada en uso, todo libre, nada que liberar
    sp_used = NULL;
    sp_free = entities;
    sp_collect = 0;
}

Hasta ahora es bastante simple, ¿verdad? Lo único es el tema de las variables globales (que no he usado en la variable del bucle porque esto se ejecuta una vez, no hay problemas de rendimiento; y es posible que en un trozo de código tan sencillo el compilador haga un buen trabajo usando un registro en lugar de la pila).

¿Cómo obtendríamos una nueva entidad?

uint8_t new_entity()
{
    if (!sp_free)
    	return 0;

    sp_new = sp_free;
    sp_free = sp_free->n;
    sp_new->n = sp_used;
    sp_used = sp_new;

    return 1;
}

Si reservamos memoria con éxito, la función devuelve 1; y tendremos la entidad en sp_new. Sino es 0 y, bueno... hemos intentado manejar más entidades de lo que habíamos planeado y habrá que reaccionar en consecuencia.

Una vez que tenemos una nueva entidad, hay que inicializar los campos de la estructura:

if (!new_entity())
    panic();

// aquí usaría un enum; asumamos 0 es libre y 1 en uso
sp_new->type = 1;
sp_new->draw = my_draw;
sp_new->update = my_update;

// x, y son cero, para el ejemplo nos vale

De esta forma draw y update que son punteros a funciones, apuntarán al código que tiene que dibujar y actualizar esta entidad (en realidad este tipo de entidad).

Solo nos quedan dos cosas: recorrer la lista y destruir (liberar) entidades.

Recorrer la lista es muy simple. La función que llamamos para dibujar o actualizar el estado tendrá en sp_it un puntero a los datos de la entidad (en este ejemplo tiene x e y).

// este es nuestro "iterador", y mejor global y con cuidado
// de no usarlo en dos sitios a la vez
struct sp_entity *sp_it;

// recorremos la lista de usados llamando a nuestra función de dibujado
// de cada entidad
for (sp_it = sp_used; sp_it; sp_it = sp_it->n)
    sp_it->draw();

En este caso asumimos que todas las entidades en nuestra lista tienen que ser dibujadas, porque en la rutina de dibujado tiene una regla: no se pueden destruir entidades.

Para actualizad entidades hacemos algo similar, solo teniendo en cuenta que al final vamos a liberar memoria (estoy haciendo un esfuerzo para no llamar a esto garbage collector porque se parece, pero no es :D).

// este es nuestro "iterador", y mejor global y con cuidado
// de no usarlo en dos sitios a la vez
struct sp_entity *sp_it;

// recorremos la lista de usados llamando a nuestra función de dibujado
// de cada entidad
for (sp_it = sp_used; sp_it; sp_it = sp_it->n)
    sp_it->update();

// si hay memoria a liberar, lo hacemos
if (sp_collect)
    free_entities();

La diferencia es que en update podemos marcar una entidad para ser destruida; y lo hacemos con:

// 0 para no en uso
sp_it->type = 0;
// avisamos que hay una entidad a liberar
sp_collect++;

Como sp_it apunta a la entidad que estamos procesando, podemos hacer el cambio desde nuestra my_update.

Liberar memoria, que simplemente es manipular la lista de forma que la entidad que estaba en uso pasa a libre, es la parte más complicada y costosa (por eso liberamos todas las entidades de una vez):

void free_entities()
{
    // si no hay nada que liberar...
    if (!sp_used)
        return;

    // dos iteradores: actual, anterior
    for (sp_it = sp_it2 = sp_used; sp_it && sp_collect;)
    {
        // 0 era libre
        if (sp_it->type == 0)
        {
            sp_collect--;

            if (sp_it == sp_used)
            {
                sp_it2 = sp_free;
                sp_free = sp_used;
                sp_used = sp_used->n;
                sp_free->n = sp_it2;
                sp_it = sp_it2 = sp_used;
                continue;
            }
            else
            {
                sp_it2->n = sp_it->n;
                sp_it->n = sp_free;
                sp_free = sp_it;
                sp_it = sp_it2->n;
                continue;
            }
        }
        sp_it2 = sp_it;
        sp_it = sp_it->n;
    }
}

Básicamente es recorrer la lista moviendo entidades marcadas como libre de la lista de entidades en uso a entidades libres, además contando cuántas entidades nos quedan por liberar, para poder abandonar la lista cuanto antes y ahorrar tiempo.

Y esto es todo. Se puede ver un ejemplo con Z88DK, que incluye uno de mis juegos para ZX Spectrum.

Espero no haber metido la pata con ninguno de los ejemplos (aunque puede ser útil, así es más importante entender que copiar código). Igual si tu juego no tiene que crear/destruir entidades, o no te preocupa que crear una entidad pueda ser más lento (en este caso es O(1)), con un array ya lo tienes (al final tampoco manejamos tantas entidades a la vez).

He tardado un poco más de la cuenta en escribir todo esto, pero no ha estado mal. Intentaré repetir, ¿una vez a la semana? Veremos :D.

Anotación por Juan J. Martínez, clasificada en: programming, gamedev, c.

Hay 2 comentarios

Gravatar

Gran aporte… y en C… y con ejemplos. Me vendrá muy bien. Muchas gracias. Ya te seguía en Twitter y te has ganado un seguidor de blog… Un abrazo
PD: lástima que estos blogs no estén en libro.. Tengo uno muy bueno Fusión-C pero con pocos ejemplos y le faltan explicaciones como esta.

por un visitante, en 2020-06-19 16:37:54

Gravatar

Muy interesante! Se agradece que alguien con tu experiencia comparta sus técnicas y conocimientos.

Uno a la semana igual va a ser mucho trabajo, ojo, yo encantado :-). Pero una entrada de vez en cuando así más técnica seria un puntazo.

por un visitante, en 2020-06-20 08:36:45

Los comentarios están cerrados: los comentarios se cierran automáticamente una vez pasados 30 días. Si quieres comentar algo acerca de la anotación, puedes hacerlo por e-mail.

Algunas anotaciones relacionadas: