Algoritmos para colisiones de boundings

Este tutorial presenta algunos algoritmos para determinar la intersección de figuras geométricas conocidas como “bounding” o delimitantes, usadas en la detección de colisiones en videojuegos, teniendo en cuenta que son aplicables a los casos donde la velocidad del objeto es menor al tamaño del bounding, ya que de no ser así, es necesario usar los llamados “bounding de tiempo”, que no se explican en este tutorial. Se presentaran los algoritmos de circulo-circulo, rectangulo-rectangulo y circulo-rectángulo.

Debido a que generalmente los videojuegos bien sean 2d o 3d manejan objetos de gran complejidad gráfica, desde una personaje de un plataforma 2d hasta un sofisticado modelo de un shooter 3d, es necesario hacer aproximaciones para evitar un uso de recursos exorbitantes al tener que comprobar cada píxel o polígono del modelo contra los otros objetos (píxeles o polígonos) contra los que pueda colisionar. Dentro de estas aproximaciones está la de “encerrar” al objeto en uno o varios objetos geométricos de simplicidad menor y que por lo tanto requieren un uso menor de recursos para detectar una colisión.

Para los algoritmos de colisión presentados mas adelante es necesario saber donde está el objeto y donde estará en el siguiente instante discreto de tiempo, para que nuestro algoritmo pueda reaccionar antes de que la colisión ocurra y no cuando esta ya haya ocurrido.

Entre los más sencillos tenemos:

Colisión Circulo-Circulo (Bounding circle)

Este algoritmo esta basado en “encerrar” el objeto en círculo.Es uno de los casos más triviales tanto en 2d como en 3d. Los datos que debemos tener presentes sobre el bounding son:

o Centro del círculo.
o Radio del círculo.
o Vectores desplazamiento del objeto.

La prueba para determinar si un círculo esta en contacto con otro es bastante sencilla, basta determinar si la distancia entre ambos círculos es menor o igual a la suma de sus radios, de ser así, los círculos se están tocando. La imagen muestra la forma en que se calcula la colisión, en esta se asume que C1 y C2 son los puntos transformados por el vector de desplazamiento del objeto (es decir los puntos en el tiempo t+1 sobre el que se desea detectar la colision).

Pare el caso de la distancia, la operación de distancia entre los centros de los círculos es una operación costosa. Esta se puede reescribir como:

Por lo que la desigualdad para el caso de la colisión queda:

Dado que es probable que r1 y r2 no cambien de valor, el lado izquierdo de la desigualdad se puede pre calcular para todas las parejas de círculos en la escena.

Hay que notar que este algoritmo para detectar la colisión es usado cuando la suma de los magnitudes de los vectores de desplazamiento es menor a los radios de los círculos, de otra manera se pueden dejar de detectar colisiones como la de la figura.

Este mismo problema se presenta para todos los algoritmos de colisión de este tutorial y para resolverlo es necesario usar bounding volumes bien sea por aproximación o continuos, tema para otro tutorial. Igualmente para cantidades altas de boundings es necesario utilizar optimizaciones espaciales para disminuir el problema de las comparaciones N-N de boundings.

El código en c++ se vería algo así:

[cpp]
struct Punto2d
{
float x;
float y;
};

struct Circulo2d
{
Punto2d centro;
float radio;
};

//Calcula la distancia en el eje x entre dos puntos
float distanciaX(Punto2d *puntoA,Punto2d *puntoB)
{
float distancia_x = puntoB->x – puntoA->x;
if(distancia_x < 0)
{
return -distancia_x;
}
return distancia_x;
}

//Calcula la distancia en el eje y entre dos puntos
float distanciaY(Punto2d *puntoA,Punto2d *puntoB)
{
float distancia_y = puntoB->y – puntoA->y;
if(distancia_y < 0)
{
return -distancia_y;
}
return distancia_y;
}

//Calcula la distancia entre dos puntos
float distancia(Punto2d *puntoA,Punto2d *puntoB)
{
float distancia = sqrt( pow(distanciaX(puntoA,puntoB),2) + pow(distanciaY(puntoA,puntoB),2));
return distancia;
}

//Calcula la distancia al cuadrado entre dos puntos
float distanciaCuadrada(Punto2d *puntoA,Punto2d *puntoB)
{
float distanciaC = pow(distanciaX(puntoA,puntoB),2) + pow(distanciaY(puntoA,puntoB),2);
return distanciaC;
}

//Evalua el contacto entre dos circulos usando la distancia regular
bool evaluarContacto(Circulo2d *circ1, Circulo2d *circ2)
{
if(distancia( &((*circ1).centro),&((*circ2).centro)) <= (*circ1).radio + (*circ2).radio)
return true;
return false;
}

//Evalua el contacto entre dos circulos usando la distancia cuadrada
bool evaluarContactoCuad(Circulo2d *circ1, Circulo2d *circ2)
{
if(distanciaCuadrada( &((*circ1).centro),&((*circ2).centro)) <= radiosCuadrados)
return true;
return false;
}
[/cpp]

El código del ejemplo está en c++ para Visual Studio 2010, aunque no debería ser problema compilarlo en Visual Studio 2008. El código se ejecutó en Windows 7 y Xp.

[drain file 21 show template]

1 2 3 4

Compartir esta entrada

DiggReddit

7 Responses to Algoritmos para colisiones de boundings

  1. Hola, interesante mu00e9todo, lo voy a probar. En la primer figura me parece que hay un error en la expresiu00f3n de d(c1-c2), ya que aparecen dos tu00e9rminos que corresponden a variables de X , pero no de Y [ d(c1-c2)=( (c1x-c2x)’1/2 + (c1x-c2x)’1/2) ‘ 1/2]. Saludos

  2. Efectivamente se me habu00eda pasado el error, corregido.nnGracias.

  3. Hola los links no me funcionan

  4. Click derecho y guardar como, ya los probe.

  5. es dificil entender esto pero quien me puede explicar ke es esto solo keria buscar diferentes formas de multiplicar

  6. u00bfcomo descargo los archivos?

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *