Introducción

Como es costumbre lo mejor es empezar con un resumen de todas las posibilidades existentes y después centrarme en explicar como se hace en XNA.

Una la detección típica de dos objetos en juegos se divide en dos pasos:

1. Fase general (Broad Phase): Determinar si dos pares de figuras necesitan ser probadas para colisión  y
   surge como necesidad de reducir los cálculos innecesarios.
2. Fase  especifica (Narrow Phase):  Determinar para cada par de figuras el resultado de la colisión.  Es la fase donde se calcula si existe una colisión y la respuestas a esta.

En la fase general, se distinguen los dos siguientes métodos (entre muchos otros):

1. Dividir el espacio Celdas o Grillas (Grid). El mas simple pero no es nativo a XNA.
2. Trazar una rayo en dirección de movimiento del objeto  (Raycasting),  para probar si se encuentra en camino de colisión hacia otros objetos, que si es Nativo a XNA.

Se combinan dos métodos o mas.

Para la segunda fase podemos distinguir entre mucho otros métodos:

1. Volúmenes de limitación (Bounding Volume), que consiste en cubrir al objeto con una superficie como Cajas y las Esferas. Facil implementación en XNA
2. Teorema de Separación de Ejes, que debido a su complejidad no se expondrá, pero puedes descargar el ejemplo SAT XNA del espacio de proyectos de XNARecursos en ThreeSixBox

Además de estos hablaremos de los vectores 3D y planos 3D en nuestros juegos 2D. Ttambién puede servir para los que trabajan 3D.

VOLÚMENES DE LIMITACIÓN EN XNA USADOS EN 2D
Fase  especifica

Son el método mas popular y simple se trabajan trabajan en coordenadas del 3D, pero podemos aprovecharlos para nuestros juegos 2D.

Vector 3D es una estructura que contiene 3 puntos en coordenadas espaciales (X,Y,Z), de este no son  útiles 2 constructores: 

• Vector3 (float x, float y, float z) Construirlo a partir de sus componentes.
•  Vector3 (Vector2 VectorXY, float z) Construirlo a partir de un Vector2D (x,y)  y el componente Z

BoundingBox  o OBJETO CAJA
Se define por medio de  dos puntos, menor y mayor.  En el caso 2D el menor siempre es el que se encuentra en la esquina superior izquierda (posición del observador de la pantalla) y el mayor la esquina inferior derecha.

Solo existe un constructor BoundingBox (Vector3 min,Vector3 max)

COMO EJEMPLO

Queremos construir una superficie de limitación tipo caja que represente un  Aeroplano en pantalla. Con coordenadas (x,y)  y  textura  Texture2D.

Primero declaramos las variables objeto

BoundingBox Avion_Caja;
Texture2D Textura_Avion;
float x,y;

Una vez cargada la textura y en el método Update de un objeto o juego (es mejor si se hace al finalizar el úpate):

Avion_Caja = new BoundingBox (new Vector3(x,y,0),new Vector3(x+Textura_Avion.Width,y+Textura_Avion.Width,0));

Si la posición es un Vector2  en lugar de los componentes:

Vector2 posicion;

Nuestro Caja seria asignada así:

Avion_Caja = new BoundingBox(new Vector3(posicion, 0), new Vector3(x + Textura_Avion.Width, y + Textura_Avion.Width, 0));

El secreto para trabajar en 2D es asignar siempre la coordenada Z = 0.

BoundingSphere o Esfera

Representa una esfera que ocupa un espacio 3D, se construye por medio de un Vector3 y un radio determinado. Representa el método mas rápido  eficiente por la simpleza de los cálculos involucrados.

COMO EJEMPLO
Queremos construir una superficie de limitación tipo esfera que represente un objeto en la un pelota de Ping-pong, con coordenadas {x,y} y una textura  Texture2D.

Primera posibilidad

BoundingSphere Esfera_pelota;
Texture2D Textura_pelota;
Vector2 centro;
Vector2 posicion; //Opcional
float Radio;
float x, y;

En el método Update del objeto o del juego

 //Calcular el centro de la pelota partiendo de las dimenciones de la textura;
centro = new Vector2(Textura_pelota.Width / 2, Textura_pelota.Height / 2);
//sumar al centro de la textura la posicion;
centro += new Vector2(x,y);
//También podríamos usar un vector de posición y la suma seria directa
//centro +=posicion;

//calcular el radio de la esfera partiendo de el ancho de la textura
Radio = Textura_pelota.Height / 2;
//Actualizar la esfera
Esfera_pelota = new BoundingSphere(centro, 0, Radio);

Segunda posibilidad

Se debe tener en cuenta que para reducir el tiempo en las operaciones, lo mejor seria pre-calcular el centro de la esfera y el radio.

Así que podríamos hacerlo en el constructor del juego o del objeto.

//de antemano sabemos los datos de ancho y alto
Esfera_pelota = new BoundingSphere();
Esfera_pelota.Radius = Ancho_Textura / 2;
centro = new Vector2(Ancho_Textura / 2, Alto_Textura / 2);

En el método Update del objeto o del juego

Esfera_pelota.Center = new Vector3(posicion+centro, 0);

// Ó por componentes

Esfera_pelota.Center = new Vector3(x+centro.X, y+centro.Y, 0);

Gracias a los objetos^^ no existen limitaciones a las posibles combinaciones.

El objeto no tiene que ser un circulo puede ser muy útil objetos cono un Avion,  ;) Es mas eficiente!

COLISIONES ESFERA Y CAJA

Realimente es mas fácil saber si dos objetos colisionan que entender como se producen los cálculos, los objetos expuesto con anterioridad posen métodos inmediatos de Intersección o Contención.

Con el mismo método podemos saber si chocan:

• Esfera-Caja
• Caja-Caja
• Caja-Esfera
• Esfera-Esfera.

Método Colisión .Intersects

Si queremos saber si dos Aeroplanos  colisionan simplemente para destruidos o destruir uno de ellos. Si ya hemos definido sus cajas simplemente seleccionamos  una de ellas para que pruebe la colisión, hacemos un simple if y listo ejemplo

if (Avion_caja.Intersects(Mortero_caja)) //los objetos son  Boundingbox validos

{
//Avion buuumm!!!!
//Escribe el codigo aqui
}

igual puede ser:
   Morter_caja.Intersects(Avion_caja)

Como explique antes es lo mismo si el parámetro es Caja o Esfera, el método nos retornara  True cuando los objetos colisionan.

Método Colisión .Contains

A diferencia del método Intersect:

1. Nos permite saber si interceptan "Intersects", No se interceptan  "Disjoint" o  si un objeto contiene al otro por completo "Contains".
2. También permite verificar si un Vector 3D se encuentra en el volumen de limitación.

Para saber el tipo de contención de los objetos se define un tipo enumerado llamado ContainmentType, que contiene las tres definiciones (en idioma ingles).

Por ejemplo si queremos saber si una pelota de ping-pon  esta contenida completamente en la raqueta haríamos

if (Esfera_pelota.Contains(Raqueta_Caja) == ContainmentType.Contains) //Raqueta _caja es un BoundingBox valido
{
//La pelota choco sobre la superficie de la raqueta!!!!
//Escribe el código aquí
}

Recuerda que también puede ser una coordenada especifica tipo Vector3.

EL RAYO Y EL PLANO

Esta referencia es tal vez muy algo avanzada pero puede ser de mucha utilidad.

Ray  o RAYO
Fase general  o  especifica
 

El rayo es un objeto especial que nos puede ser de utilidad para saber si dos objetos se encuentran en rumbo de colisión este contiene un método especial que nos permite calcular la distancia. Interacciona fácilmente con las Cajas y Esferas.

¿Que es un rayo?

Un rayo es realmente una línea dirigida de longitud infinita y contiene:

• Un vector de posición que determina el centro del rayo
• Un vector de dirección que determina hacia a donde apunta el rayo.

El primero es simple e inmediato de entender, pero el segundo podría darnos dolores de cabeza, por que a diferencia del primero la dirección es un vector unitario, sus componentes no son mayores que 1 y es por que solo  contiene la información de dirección.

Código de ejemplo:

Este ejemplo seria útil para revisar si un misil impactara un avión determinado, en este caso requerimos guardar la posición actual y anterior.

Variables:

BoundingBox Avion_Caja; //Tenemos que escribir el código como se explico antes
Ray rayo;
Vector2 centro; //Centro del Rato //opcional
Vector2 posicion; //Posicion del Misil
Vector2 posicion_anterior; //Posicion anterior del objeto Misil
Vector2 direccion; //Guardara la direccion del Rayo
 

En el método Update del objeto o del juego

float? Distancia; //distancia misil al avión
posicion_anterior = posicion; //guargar el estado anterior
posicion -= new Vector2(Velocidad_X, Velocidad_Y);  //avanza el misil o otro código

//Calcular el vector de direccion
//normalizamos
direccion = Vector2.Normalize(posicion - posicion_anterior);

Distancia = rayo.Intersects(Avion_Caaja); //calculo de la distancia
if (Distancia!=null)
 {
   //Se puede hacer aquí prueba de colisión u otra comprobaciones
if (Distancia==0)
 {//Buuuun exploto el avión
  //Escribe tu código
 }
}

El método Intersect del rayo, que también puede ser llamado desde una Caja o una Esfera (Caja-rayo, Esfera-Rayo):

• Puede retornar un valor nulo cuando el objeto no esta en el camino del rayo, por eso el símbolo ?
• Cero  (0) cuando el centro esta contenido en el volumen de limitación.
• Si retorna un valor representara la distancia desde el el centro del rayo hasta hasta el objeto.

Tip1: Como tenemos la dirección (unitario), la magnitud y el vector centro podemos saber a que punto del objeto nos acercamos:

Vector2 Punto_colicion = posicion + direccion * Distancia;

Tip2: Si un objeto desprende de un objeto Caja tendremos que calcular el centro del rayo para que este no provenga de las esquina superior izquierda de la textura.

Plane  o PLANO
Fase  especifica

Usar un Plano 3D para un juego 2D puede ser todo un reto, ^^mas para mi, a pesar de su complejidad matemática el saber en que posición del plano se encuentra nuestro los objetos  lo hace una herramienta sumamente valiosa para las colisiones de objetos complejos.

Sin entrar mucho a Calculo en 3D, un plano tiene una ecuación:

 Ax + By + Cz + D  = 0

{(A,B,C) representan un vector que es normal a la superficie del plano y  D la distancia}

!CONSTRUIR UNA RECTA!

Pues bien no estamos intensados en todo el espacio 3D, solo en dos dimisiones. La ecuación de la recta:

 Ax+By + D = 0

{(A,B) Es el vector normal o perpendicular a la recta y D esta definido como su distancia.}

Como una hoja infinita el plano corta nuestro espacio en dos,  XNA nos permite saber en que lugar de esa región se encuentra nuestro objeto;

• Adelante "Front"
•  Atrás "Back".

Primer método

crear una Recta (para XNA Plano) a partir de vector normal y la distancia

Vector2 direccion = new Vector2 (2,3);
float distancia = 5;
direccion.Normalize();

plane = new Plane(new Vector3(direccion, 0), distancia);

Esto crea una Recta

 2X+3Y+5 = 0

 Ventaja si sabemos la dirección del vector normal sabremos al hacer la prueba de intelección a ciencia cierta y sin dudar en que lado de la recta esta nuestro objeto.

Esto es difícil con solo el pensamiento lo mejor es hacerlo con ayuda de alguna hoja de calculo. La ecuación de ayuda es:

 y = (-A/B)x + (-C/D)

También podemos crear Rectas ( Planos) que sean paralelos a algún eje y es mas fácil con ayuda de alguno vectores predefinidos.

Vector3.Down,Vector3.Up,Vector3.Left y Vector3.Right

Ejemplos:

plane = new Plane(Vector3.Down,distancia); //Mirando hacia arriba +distancia  al eje X
plane = new Plane(Vector3.Up, distancia); //Mirando hacia abajo -distancia  al eje X
plane = new Plane(Vector3.Left, distancia); //Mirando   la izquierda  +distancia  al eje Y
plane = new Plane(Vector3.Right, distancia); //Mirando   la derecha  -distancia  al eje Y

Segundo Metodo

 Construir la recta a través de dos puntos sacrificando el vector normal.

No quiero entrar en detalles sobre el procedimiento matemático, es mas con mi lápiz, mi libro viejo de Calculo Swokowki y una hoja de calculo, pude encontrar una expresión claro puede sera otra ...en fin esta es la función

public Plane Plano2D(Vector2 Punto1, Vector2 Punto2)

{
 float m = (Punto2.Y - Punto1.Y) / (Punto2.X - Punto1.X);
 float A = m;
 float D = -m * Punto1.X + Punto1.Y;
 return new Plane(A, -1, 0, D);
}

Al sacrificar el vector normal tendremos que hacer pruebas para revisar en que lado plano deberán estar nuestros objetos.

Si bien se puede crear un Plano a partir de 3 puntos  (x,y,z) al hacer un punto a cero o escoger mal los puntos tendremos un plano no definido que realmente no ayudara mucho.

Método Colisión .Intersects

Este método es directo en los casos:

• Plano-Esfera
• Plano-Caja
• Esfera-Caja
• Caja-Plano.

Es decir con el mismo método podemos hacer desde estos objetos y nos retornara los valores PlaneIntersectionType. {Front, Back y Intersecting}

Este método lo he usado con éxito en una versión no publicada de Arkalite con física ^^! y junto con las Cajas (BoundingBox) resultan se un efectivo y simple método de colisión.

Aquí el un fragmento de código que use en esa prueba de Arkalite  para el objeto Bola

BB es el BoundingBox del objeto. del cual formo planos a partir de el vectores Max y Min.
_Velocidad es la velocidad del objeto

Esfera es la BoundingSphere del la bola.
Rayo es un rayo definido de la trayectoria de la bola, para saber si la bola se dirige hacia el bounding box.
Aceleracion Es la aceleración de la bola

OTROS MÉTODOS

Este es un breve vistazo a otros métodos de colisiones.

CELDAS (Grid)
Fase general  o  especifica

Las celdas son simples  y fáciles de implementar, se usan generalmente junto con los tile maps.

La idea es dividir la pantalla en celdas:

No_celdas_ancho  = Ancho_pantalla / Ancho_Celda
No_celdas_largo  = Largo_pantalla / Alto_Celda

Si queremos saber si un o mas objeto están en una grilla determinada solo debemos calcular:

Celda_X_actual = Posicion_X_actual_objeto / Ancho_celda
Celda_Y_actual = Posicion_Y_actual_objeto / Alto_celda

[Celda_X(Y)_actual  es tipo flotante y   Posicion_X_actual_objeto tipo entero]

Esto realmente da de una (1) a cuatro (4) posiciones, por cuanto la divisiones no son números Enteros y debemos redondear (aproximar) por arriba y/o abajo cada una.

 Si los objetos comparten celdas en común es por que están en camino de colisión podremos decidir en ese momento:

• Destruirlos
• Retenerlos en la posición de uno o ambos.
• Realizar otro tipo de prueba.

• Este método puede hacerse mas complejo si se consideran las celdas objetos, se guardan las posiciones de los objetos  y se recorre las celdas buscando grupos de objetos comunes a cada celda.
• Se suele optimizar las  búsqueda dividiendo el espacio de forma no uniforme.

Haciendo  el método efectivo y eficiente

• Los objetos deben ser mas o menos uniformes.
• El tamaño de las celdas igual al tamaño de los tiles en el caso de los mapas
• El tamaño de la celdas es un tanto mayor que el objeto principal o el personaje.
• Hablamos de celdas entre 64x64 píxeles  y  256x256 píxeles en promedio

Ejemplo: En una pantalla a resolución xVGA 1024x768 tendríamos 16x12 celdas de 64x64 píxeles.

2D Per Pixel Collision Detection
Fase especifica

Es un método muy popular en XNA,  sus dos principales promotores son  Michael Morton (ziggyware.com)  y  Garykac (XNA Diaries).

La idea detrás de este método es aprovechar la información del canal Alpha o de transparencias, para ello se separa la información de las texturas de los objetos a probar en arreglos  y se recorre punto a punto el arreglo buscando con ayuda  del canal alpha , mas bien si los objetos no son transparentes en esos puntos en los que se sobreponen (Michael Morton lo combina con una combina el método con una comparación de las regiones 2D)

No expondré mas detalles del algoritmo en este sitio  pero pueden visitar en ziggyware.com:

• XNA - 2D Per Pixel Collision Detection
• XNA - Rotated Sprite Per Pixel Collision Detection

Algoritmo en detalle :

Para dos texturas de 64x64pixeles. los arreglos de Enteros sin signo de C# (Uint) de 32bits o 4bytes. (Uint en C#  Biblioteca MSDN)

Cada comparación ocuparía 64x64 x 2 bytes =  8192 bytes x 2 texturas = 16384 bytes

Requiriendo 64x64=4096 comprobaciones, es decir una por cada píxel.

Para otros tamaños de pares de texturas similares:

1. Es extremadamente especifico, dedicamos mucho procesamiento y memoria.
2. Como se observa 16384 comparaciones solo en texturas de 128x128 píxeles. 16384 bytes para una textura de 256x256!.
3. Podríamos aprovechar ese tiempo de CPU  haciendo otras comprobaciones por otros caminos mas eficientes!
4. Es un algoritmo de Celdas y expone el problema de tamaños de celda extremadamente pequeños "a nivel de Byte".

Claro por su facilidad de implementarlo puede ser muy atractivo y hasta una prueba definitiva no hay que sacar mas conclusiones.

QUIERO SABER MAS

Entender como funcionan los métodos puede dar tremendos dolores de cabeza (y quizás una embolia) pero siguieren saber mas pueden visitar estos link's en ingles:

Algoritmos Básicos:

• Guía completa SoftSurfer Algorithm Archive
• Simple Intersection Tests For Games por Miguel Gomez, [Gamasutra]
• XNA  2D Per Pixel Collision Detection por Michael Morton.

Teorema de Separación de Ejes (SAT) :

• 2D Polygon Collision Detection por Laurent Cozic's, implementación del SAT en C#.
• La mejor pagina  Separating Axis Theorem (SAT) y Grid-Based Collision Detection and Raycasting. [Metanet Software] implementados en Adobe Flash.
• Olivier's code junkyard  sección de código muy útil  en C++/Glut/OpenGL.

Sólo los usuarios registrados pueden escribir comentarios.
Por favor valídate o regístrate.

Powered by AkoComment 2.0!