Doble/Triple buffering y Page flipping

2007/10/10

Hoy toca hablar de los métodos de buffering al pintar en pantalla en Allegro (Bueno, en cualquier programa, pero implementado en Allegro xD)

Cuando se hace un juego, siempre hay que ir pintando los gráficos en pantalla, y si se hace sin ningún tipo de buffer, se pinta a la vez que el monitor se refresca, provocando los molestos efectos que hacen que parece que la pantalla parpadea. Esto es, en resumidas cuentas, porque cuando estamos pintando el frame N, también hay restos del N-1, y el monitor pinta partes de cada uno.

Para evitar esto, se usa un buffer donde se pinta todo lo necesario del frame y después se vuelca a la memoria de video para que el monitor lo actualice. Hay varias técnicas.

Page Flipping:

Consiste en tener el doble de memoria (dos páginas de memoria) de lo que la pantalla usa. Es decir, si tenemos una resolución de 800×600 a 16bpp, se usa casi 1 Mbyte de memoria de video. Pues en este caso usaríamos casi 2, para que mientras se dibuja en una página, se muestra la otra.

Por ejemplo, inicializamos el sistema gráfico de la siguiente manera:

BITMAP *pantalla_buffer[2];
int pantalla_actual;
BITMAP *pantalla;

pantalla_buffer[0] = create_video_bitmap(SCREEN_W, SCREEN_H);
pantalla_buffer[1] = create_video_bitmap(SCREEN_W, SCREEN_H);
pantalla_actual = 0;
pantalla = pantalla_buffer[pantalla_actual];
Con esto estamos reservando dos páginas (pantalla_buffer) e indicando que la actual es la 0. Además tenemos la variable pantalla, que será a la que nos refiramos siempre por comodidad, para no tener que estar poniendo pantalla_buffer[pantalla_actual] siempre, y además la haremos accesible al resto de paquetes.

Y para actualizar la pantalla, se llamaría en cada proceso de renderizado (en cada frame) a:

show_video_bitmap(pantalla);
pantalla_actual = (pantalla_actual+1)%2;
pantalla = pantalla_buffer[pantalla_actual];

Con la primera linea lo que hacemos es pedir que se pinte el bitmap pantalla (la página donde hemos pintado). Con las dos siguientes lineas actualizamos la página actual, para que en el siguiente frame, al pintar sobre el bitmap pantalla, pintemos en la otra página a la que se está mostrando.

En algunos sistemas hay que especificar la memoria de video concreta que hay que reservar, así que, antes de nada habría que poner:


#ifdef ALLEGRO_VRAM_SINGLE_SURFACE
error_init = set_gfx_mode(GFX_AUTODETECT_WINDOWED, w, h, w*2, h);
#else
error_init = set_gfx_mode(GFX_AUTODETECT_WINDOWED, w, h, 0, 0);
#endif

Doble Buffer:

Es una técnica bastante parecida, pero en vez de tener dos páginas de memoria de video, tenemos un buffer de memoria principal, que volcaremos sobre la pantalla en cada frame.

Para inicializar el sistema gráfico lo haríamos con:


BITMAP *pantalla = create_bitmap(SCREEN_W, SCREEN_H);

En este caso la variable pantalla actuaría de buffer. Y para actualizar la pantalla copiaríamos el buffer en la memoria de video con:


blit(pantalla, screen, 0, 0, 0, 0, SCREEN_W, SCREEN_H);

Triple Buffer:

Aunque por su nombre parezca que es como el doble buffer, la verdad es que su implementación se parece más a la del page flipping, pero con tres páginas.

Además, esta técnica no la soportan todos los sistemas, y por ello se debería de dar opcional a las otras técnicas, por si no funciona. Para comprobar si se puede o no, se usa:


gfx_capabilities & GFX_CAN_TRIPLE_BUFFER

Si el flag comprobado no está activado, puede intentar activarse de todas maneras con la funcion enable_triple_buffer()

Una vez se haya comprobado que se puede, se inicializa igual que el page_flipping, pero en vez de ser un array de 2 páginas, es de 3:


BITMAP *pantalla_buffer[3];
int pantalla_actual;
BITMAP *pantalla;

pantalla_buffer[0] = create_video_bitmap(SCREEN_W, SCREEN_H);
pantalla_buffer[1] = create_video_bitmap(SCREEN_W, SCREEN_H);
pantalla_buffer[2] = create_video_bitmap(SCREEN_W, SCREEN_H);
pantalla_actual = 0;
pantalla = pantalla_buffer[pantalla_actual];
Y se actualiza cada frame de la siguiente manera:


while(poll_scroll());
request_video_bitmap(pantalla);
pantalla_actual = (pantalla_actual+1)%3
pantalla = pantalla_buffer[pantalla_actual];

Lo que hacemos con la primera linea es comprobar el estado del hardware para ver si está listo o no. Con la segunda pide una página de la memoria de video, pero no espera para un repintado. Y con las dos últimas lineas, se actualiza la página actual, de igual manera que en el page flipping.

Ya que disponemos del código para cada tipo de renderizado, y no es muy complicado, lo suyo sería encapsularlo en funciones y hacer posible que el usuario seleccionase cual quiere, por si alguna le va mejor que otras en su sistema (por ejemplo, en mis pruebas, con page_flipping me va muy rápido en Linux, pero lento en Windows…)


Detector de colisiones en 2D

2007/08/13

Voy a abrir la sección de Allegro & C con algo que existe en otras librerías o lenguajes para programar juegos, pero no en Allegro: Las colisiones 2D.

Yo al principio empecé a programar con lenguajes que te proporcionaban funciones como image_collides, image_overlaps y cosillas de esas, así que nunca me preocupé en este aspecto. Ahora Allegro te proporciona muchísimas funciones muy útiles, pero no estas xD.

Se que hay algunas otras librerias como ppcol o algunas así, que ya lo tienen implementado, pero bueno, si programo juegos no es para hacerlo todo perfecto, sino entre otras cosas, para aprender cositas, así que, para variar, me voy a hacer yo mismo mis propias funciones. Además el verlas aquí paso a paso servirá para muchos otros que intenten hacerlas por si mismo.

En primer lugar, debemos preguntarnos que tipo de colisiones queremos comprobar. Por ejemplo, en un programa de tipo Final Fantasy 6 (RPG Maker), pues no hace falta la gestión de colisiones, ya que se hace todo por tiles o bien por lógica, es decir, no hay que comprobar en tiempo real que los objetos estén colisionando fisicamente. Otro caso distinto es un juego de carreras, plataformas, un shooter en los que la precisión es importante. (Cuantas veces me habre sulfurado cuando en una carrera me chocaba contra una pared rozándola cuando en realidad no la había tocado…?)

Tipos de colisiones

Una vez sabemos que necesitamos comprobar las colisiones, ¿de qué manera la comprobaremos? Porque si lo que queremos es ver si dos pelotas están chocando, tipo pang, matematicamente nos basta, pero si tenemos una nave espacial y queremos ver si un disparo le da o no, habría que hacerlo, dependiendo de la forma de la nave, con precisión a nivel de pixel.

Detección de solapamiento de rectángulos:

Cuando la precisión no es lo más importante, podemos utilizar este método, que consiste en saber si un rectángulo está dentro del otro:

/** Verdadero si una caja se solapa con la otra
** x1, y1: coordenadas del 1er rectangulo
** w1, h1: tamaño del 1er rectangulo
** x2, y2: coordenadas del 2º rectangulo
** w2, h2: tamaño del 2º rectangulo
*/

int rect_overlaps(const int x1, const int y1, const int w1, const int h1, const int x2, const int y2, const int w2, const int h2) {

return ((x1 < x2+w2) && (x2 < x1+w1) && (y1 < y2+h2) && (y2 < y1+h1));

}

Detección de solapamiento de círculos:

Del mismo estilo que el anterior, pero para formas circulares. Aquí se calcula viendo si la distancia entre los dos círculos es menor que la suma de sus radios.

/** Verdadero si un circulo solapa a otro, comprobado con precision (lento)
** x1, y1, r1: coordenadas y radio del 1er circulo
** x2, y2, r2: coordenadas y radio del 2º circulo
**/

int circle_overlaps_precision(const int x1, const int y1, const int r1, const int x2, const int y2, const int r2) {

return (r1+r2 < sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)));

}

Aquí existe un problema, ya que, la fórmula implica el uso de multiplicaciones y raices cuadradas para el cálculo de una distancia, con lo que, en el uso continuado de esta función, como es normal en un juego, el rendimiento no es su fuerte.

Para ello se usa otra implementación, que aunque sacrifica un poco de precisión, gana mucho en velocidad. Se basa en la serie de Maclaurin:

/** Verdadero si un circulo solapa a otro (rapido)
** x1, y1, r1: coordenadas y radio del 1er circulo
** x2, y2, r2: coordenadas y radio del 2º circulo
**/
int circle_overlaps(const int x1, const int y1, const int r1, const int x2, const int y2, const int r2) {
int x,y,m; x = abs(x2 - x1);
y = abs(y2 - y1);
m = min(x,y);

return (abs(x + y – (m >> 1) – (m >> 2) + (m >> 4)));
}
Por cierto, para los más despistados, recordar que el operador >> es el desplazamiento a la derecha (división entre 2), así que (m >> 1) es m/2 así como (m >> 4) es m/16.

Detección de colisiones pixel-pixel:

Lo anterior es relativamente rápido ya que son matemáticas, pero cuando queremos hacer una comprobación realmente precisa, necesitamos comprobarlo a nivel de pixel, y esto ya es una operación mucho más lenta.

Os voy a mostrar la base del proceso, porque después se le pueden hacer varias optimizaciones para que vaya más rapido, pero engorronaría el código un poco y sería más dificil de comprender.

/** Verdadero si una imagen colisiona con otra (pixel-pixel)
** a, b: las dos imagenes a comprobar
** x1, y1: posición de la imagen a
** x2, y2: posición de la imagen b
**/

int image_collision(BITMAP *a, BITMAP *b, const int x1, const int y1, const int x2, const int y2) {
int x,y, w,h;
int n2, n4;
int i,j;
int nulo;
int (*gp)(BITMAP*,int,int);

Como podreis imaginar, en vez de comprobar todos los píxeles de ambas imagenes, se comprobaran solo aquellos que estén solapados, así que necesitamos saber cual es ese área:

/* se limita el area a comprobar segun la zona de la colision */
x = max(x1, x2);
n2 = min(x1+a->w, x2+b->w);
y = max(y1, y2);
n4 = min(y1+a->h, y2+b->h);
/* hay solapamiento */
if(n2 >= x && n4 >= y) {
/* tenemos la region de la interseccion en x,y,w,h */
w = n2-x;
h = n4-y;

Ya tenemos el cuadro solapado, en coordenadas de pantalla, en las variables x,y,w,h. Otro aspecto, es que si no hay solapamiento no se hace ninguna comprobación, por lo que mientras las imágenes no se solapen, no hay diferencia de rendimiento.

Un aspecto a considerar es la profundidad de pantalla. Ya que se no se usará la funcion getpixel, sino la optimizada para aumentar el rendimiento _getpixel## siendo ## la profundidad de colores, hay que comprobarlo:

/* depende de la profundidad de pantalla */
switch(bitmap_color_depth(screen)) {
case 24:
nulo = MASK_COLOR_24;
gp = _getpixel24;
break;
case 32:
nulo = MASK_COLOR_32;
gp = _getpixel32;
break;
default:
nulo = MASK_COLOR_16;
gp = _getpixel16;
}

Y ahora ya si, se comprueban los pixeles solapados. Diremos que habrá una colisión cuando, mirando por pares, los píxeles de la imagen a que solapa con el de la b, no sean transparentes:

/* se comprueba dentro del area, pixel a pixel */
for(i=x; i<x+w; i++) {
for(j=y; j<y+h; j++) {
if((gp(a, i-x1, j-y1) != nulo) && (gp(b, i-x2, j-y2) != nulo)) {
return 1;
}
}
}

Y cerramos las llaves de los if abiertos anteriormente:

}
return 0;
}

¿Posibles optimizaciones? Unas cuantas, como por ejemplo utilizar una máscara binaria con un preprocesado de la imagen en su carga, para que no haya que utilizar las funciones de getpixel, sino que se pueda hacer todo con operaciones lógicas entre bits, que son mucho más rápidas.