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.