Algoritmos Basicos de Colisiones para Videojuegos

En el mundo real todas los objetos al ponerse en “contacto” reaccionan: chocan, se deslizan, rebotan, se rompen y todas los otros comportamientos que observamos a diario. En el caso de los videojuegos es muy importante tener un método (o varios) para saber cuando ocurre esto y actuar de manera adecuada, puesto que como se trata de una aplicación en tiempo real, no podemos precalcular en la mayoría de casos dichos eventos. Cuando estemos implementando propiamente un método es importante tener en cuenta los siguientes factores:

  • Uso de recursos: Se refiere a cuanta memoria y uso de procesador requieren las operaciones que estamos realizando para calcular si existe o no la colisión.
  • Colisiones falsas: Cuando utilizamos aproximaciones a las colisiones puede que estas no sean correctas gráficamente, aún cuando el algoritmo reporte una colisión.
  • Colisiones faltantes: El algoritmo fallará al intentar hallar estas colisiones (no las reporta).
  • Escalabilidad: Qué numero de objetos puede llegar a abarcar el algoritmo sin que falle en alguno de los casos anteriores.

Este tutorial muestra algunos de los test geométrico mas sencillos para empezar a trabajar colisiones, los de punto adentro, que tienen como objetivo mostrar si un punto se encuentra dentro de cierta figura geométrica. Para cada caso se muestra la descripción del algoritmo, un código estructurado muy sencillo y un ejemplo en c++ – OpenGL.

Circulo: Este es el test mas sencillo de realizar, basta comprobar si la distancia desde el centro del círculo al punto en cuestión es menor al radio del círculo así:

Punto dentro de circulo

Con ayuda de un poco de matemática milenaria (Pitágoras para ser mas exacto), se encuentra la distancia desde el punto en duda y el centro del círculo, los casos son:

  • La distancia es menor o igual: El punto esta adentro.
  • La distancia es mayor: El punto esta afuera.

Bastante fácil. Hay que observar que este algoritmo es fácilmente extensible al caso de tres dimensiones (punto dentro de una esfera), basta incluir la distancia z dentro de la raíz del calculo de la distancia punto – centro esfera.
Para el caso 2d el algoritmo en c++ sería algo así :

struct Punto2d
{
    float x;
    float y;
};

struct Circulo
{
    Punto2d centro;
    float radio;
};

float distanciaPuntos(Punto2d *puntoA,Punto2d *puntoB)
{
    float distancia_x = puntoB->x - puntoA->x;
    float distancia_y = puntoB->y - puntoA->y;
    return (float) sqrt((distancia_x*distancia_x)+(distancia_y*distancia_y));
}

bool esPuntoAdentro(Circulo *circulo, Punto2d *punto)
{
    if ( distanciaPuntos(&(circulo->centro) , punto) <= circulo->radio)
    {
        return true;
    }
    return false;
}
...

Tip:No es necesario calcular la raíz cuadrada de la distancia, basta con comparar el valor de la distancia al cuadrado (sin la raiz) con el radio al cuadrado. Esto es algo mas óptimo al momento de realizar el test de punto adentro de circulo, claro esta si el radio permanece constante o no varia a un ritmo similar al de la distancia.

download


Descargar:	circulo.zip
Version:	0.1
Actualizado:	December 22, 2009
Tamaño:		175.53 KB

1 2 3

Compartir esta entrada

DiggReddit
  • xuturk

    Muchas gracias por este tutorial, la verdad es que me a ayudado mucho a comprender las colisiones, aun me cuesta pero mañana lo mirare mas detenidamente, pero la del circulo y rectangulo me han quedado bastante claras, si que es cierto que son basicas, pero creo que gracias a esto las podre sacar partido.
    Una anotacion, pregunta:
    en la imagen de la colision del circulo, ¿la segunda operacion de raiz no seria sustituir la a por la letra c?, ya que estamos calculando desde el centro y no desde el otro punto exterior. Aun asi esta bastante claro explicado.
    Muchas gracias una vez mas.
    Saludos!

  • http://soygeek.com.mx Isaac

    Gracias! ha sido de gran ayuda

  • Dark-boy152

    ola  megusto tu projecto  muy bn echo mm puuedes de hjame tu correo para k me explikes algunas cosas k no en tiendo :D… muy buena pgina por sierto