Algoritmos Basicos de Colisiones para Videojuegos

Poligono Convexo: Este test algo mas complicado que los anteriores, pero es mas general. Mediante este algoritmo se puede probar cuando un punto se encuentra dentro de un polígono convexo (polígono convexo es aquel que no tiene ángulos internos mayores a 180 grados).

Punto dentro de poligono convexo

Primero es necesario hallar un punto a sobre cada lado (el intermedio puede ser), para de esta manera encontrar el vector ap que va del punto a al punto p (el punto del que se necesita saber si esta adentro del poligono). Se encuentra tambien el vector N normal “interior” del lado y finalmente se hace el producto punto ap.N. Los casos son:

  • ap.N es + o 0 para cada lado: El punto esta adentro.
  • ap.N es – para algun lado: El punto esta afuera.
struct Punto2d
{
    float x;
    float y;
};

struct Poligono
{
    list puntos; //lista de los puntos del poligono
};

bool ladoCorrecto(Punto2d inicial,Punto2d terminal,Punto2d punto)
{
    //se calcula el vector "lado" que va de un punto a otro
    vector2d lado;
    lado.x = inicial.x - terminal.x;
    lado.y =  inicial.y - terminal.y;

    //la perpendicular del vector "lado"
    vector2d perp;
    perp.x = -lado.y; //las perpendiculares son vectores con componentes intercambiadas
    perp.y = lado.x;  // y una componente negativa

    //se saca un punto "muestra" en la mitad del lado
    lado.escalar(0.5f);
    vector2d muestra;
    muestra.x = inicial.x + lado.x ;
    muestra.y = inicial.y + lado.y;

    //se busca el vector entre el punto muestra y el punto supuestamente "adentro"
    vector2d muestraPunto;
    muestraPunto.x = muestra.x - punto.x;
    muestraPunto.y = muestra.y - punto.y;

    //Finalmente se pregunta si el producto punto perp.muestraPunto es negativo
    if(perp.punto(muestraPunto) < 0)
    {
        return false; // si con alguno falla, es que esta afuera
    }
    return true;
}

bool puntoDentroDePoly(Poligono *poly, Punto2d *punto)
{
    list::iterator iterPuntos = poly->puntos.begin();
    bool estaAdentro = true;   //En principio se supone que esta adentro

    if(poly->puntos.size() > 2) //Bueno, es un poligono, no?
    {
        //El primer punto que se lee;
        Punto2d puntoActual;
        Punto2d puntoAnt = *iterPuntos;
        iterPuntos++;

        while(iterPuntos != poly->puntos.end() && estaAdentro)
        {
        puntoActual = *iterPuntos;
        estaAdentro = ladoCorrecto(puntoAnt,puntoActual,*punto);
        puntoAnt = puntoActual;
        iterPuntos++;
    }

    //falta el ultimo con el primero
    if(estaAdentro)// hay que comprobar que todavia se considere adentro
    {
        iterPuntos = poly->puntos.begin();
        puntoActual = *iterPuntos;
        estaAdentro = ladoCorrecto(puntoAnt,puntoActual ,*punto);
    }

    return estaAdentro;
}

return false; //eso no es ni siquiera un triangulo
}

download


Descargar:	poligono-convexo.zip
Version:	0.1
Actualizado:	December 22, 2009
Tamaño:		169.73 KB

Por ahora estos test son útiles por ejemplo para hace seleccion sobre elementos del juego que se puedan encerrar en estas figuras y detectar cuando un cierto elemento del juego entra o sale de una zona demarcada por un circulo, un rectangulo alineado con los ejes o un poligono convexo.

Como nota final es importante ver que estos no son ni los únicos ni los mas eficientes test geométricos (pero con suerte son los mas faciles de entender). Ademas aún no se tiene en cuenta la variable tiempo y las colisiones entre los llamados “bounding”, con lo que se puede realmente empezar a trabajar colisiones.

Informacion de Referencia:

Crashing into New Year, articulo de Gamasutra por Jeff Lander.

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