Algoritmo para detectar colisiones entre rectángulos

Si estás desarrollando un juego, lo más probable es que necesites detectar si se produce o no una colisión. En algunos frameworks de programación de videojuegos existen métodos predefinidos para comprobar si [las colisiones] se dan o no (por ejemplo en pygame). En mi caso, estoy desarrollando un juego para Android y no quiero usar ningún framework (además de que no sé si existe alguno) por lo tanto, tengo que programar mi propio método.

Vamos con la teoría. Empezaremos viendo como se puede detectar una colisión entre dos líneas (imaginemos que estamos en una dimensión) .

#graficoshechosconpaint

Bueno, en la imagen superior podemos ver dos líneas que vamos a asumir que están en una dimensión y por lo tanto chocan. Esas líneas están descritas por los puntos A -> B y C->D .  A partir de este dibujo podemos asumir que si A < C < B las líneas chocan. Pero, ¿ qué pasa si el dibujo es así?

Lo que pasa es que la condición  A < C < B no se cumple en este caso y de todas formas podemos comprobar que sí hay una colisión. Por lo tanto, debemos buscar una condición más genérica que extienda a la anterior y fácilmente podemos ver que esa condición es : A < D < B . Finalmente la condición final es :

Si (A<C<BA<D<B) hay colisión, en cualquier otro caso no hay colisión.

Extendiendo el caso a 2 dimensiones ya no hay mucho que pensar. Obviamente no podemos usar la condición anterior porque : 1) hay el doble de puntos y 2) hay el doble de dimensiones (xD).   No hay que ser un genio matemático para descubrir que lo que hay que hacer es aplicar la condición anterior en las dos dimensiones del espacio que usamos.

Hay podemos ver un par de rectángulos (bueno, son cuadrados pero no importa) definidos por tres puntos, el primero A, B y C y el segundo por tres puntos A’, B’ y C’. El otro punto no importa para determinar una posible colisión. Bueno, lo primero sería comprobar si interfieren en el eje X . Aquí se usaría la condición anterior : A< A’ < B o A< B’ < B. Luego, habría que comprobar si interfieren en el eje Y, y aquí es donde viene lo “nuevo” (es lo mismo de antes solo que cambiando el eje). La condición final para detectar una colisión entre dos rectángulos es :

Si ((Ax < A’x < Bx o Ax < B’x < Bx) y ( Ay < A’y < Cy o Ay < C’y < Cy)) hay colisión, en cualquier otro caso no hay colisión.

Una posible implementación de esta solución en java es esta :

class Rectangulo {

public int[] A,B,C ; // Aqui son guardados los puntos, A[0] = Ax y A[1] = Ay.

public Rectangulo(int[] a, int[] b, int[] c)

{

A = a;

B = b;

C = c;

}

public Boolean hayColision(Rectangulo R) {

if (((A[0] < R.A[0] && R.A[0]< B[0]) || (A[0] < R.B[0] && R.B[0] < B[0])) && ((  A[1] < R.A[1] && R.A[1] < C[1] ) || (A[1] < R.C[1] && R.B[1] < C[1]))

return true;

return false;

}

}

Supongo que nadie usará esta clase, pero creo que está bien para demostrar como funciona.


Anuncios

Acerca de Braulio

"CEO" de Alfffa Solutions Ver todas las entradas de Braulio

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: