Todos los programadores de videojuegos acabamos lidiando alguna vez con este tema la detección de colisiones. Quiero dedicar unos artículos a repasar las colisiones en 2D y la manera eficiente de tratarlas, empezaremos con los conceptos básicos.
Decimos que dos objetos colisionan cuando uno de ellos se sobrepone a otro en este momento debemos disparar una "señal" y tratar dicha colisión en consecuencia, impidiendo el movimiento si es un sólido, restando vida si es un enemigo, etc. Todo dependerá del tipo de juego en este artículo nos vamos a centrar en detectar dichas colisiones.
Simplificación
La simplificación es la clave siempre para todo el tema de representar el mundo real en un ordenador y en la detección de colisiones no es menos. Imaginemos que tenemos los siguientes Sprites.
Si queremos detectar colisiones entre ellas necesitaremos simplificar su geometría para ellos lo que hacemos es envolver los sprites en figuras geométricas simples que podemos detectar si colisionan o no.
Ahora usaremos los dos rectángulos rojos para representar a las naves, si estos colisionan es que las naves colisionan. Si eres buen observador verás que hay casos en los que no será así ya que no representa fielmente a las naves este rectángulo, veremos más adelante como solucionar este problema.
Ahora imaginemos que tenemos unas figuras que son más bien redondeadas como las siguientes caras (se ruega abstenerse de reírse de los pésimos gráficos de un servidor).
Creo que todos vemos claramente que está pidiendo a gritos que se use un círculo y no un rectángulo como delimitador. Así pues vamos a trabajar con círculos y rectángulos para detectar colisiones.
Representación de un rectángulo y un círculo
Lo primero que necesitamos es representar matemáticamente un rectángulo y un círculo. Un rectángulo podemos representarlo mediante un punto p 2D (x, y) que represente la coordenada de la esquina inferior izquierda, un valor w que represente el ancho y un valor h que represente la altura. Por otra parte para representar un círculo usaremos un punto p que represente el centro del mismo y un valor r que defina el radio.
Veamos lo que podría ser estas definiciones en Python.
class Punto:
def __init__(self, x = 0, y = 0):
self.x = x
self.y = y
def __str__(self):
return "(" + str(self.x) + ", " + str(self.y) + ")"
class Rect:
def __init__(self, p, w = 0, h = 0):
self.p = p
self.w = w
self.h = h
class Circ:
def __init__(self, p, r):
self.p = p
self.r = r
Colisión rectángulo - rectángulo
Para que un rectángulo esté colisionando con otro deben cumplirse cuatro cosas, definiendo dos rectángulos como r1 y r2 diremos que colisionan si:
-
Lado derecho de r1 es mayor que lado izquierdo de r2
-
Lado izquierdo de r1 es menor que lado derecho de r2
-
Lado superior de r1 es mayor que lado inferior de r2
-
Lado inferior de r1 es menor que lado superior de r2
Si se cumplen estas cuatro condiciones es que ambos rectángulos están colisionando. Ahora nos queda traducir esto a código, lo haremos como un método de la clase Rect.
def collide(self, r):
# calculamos los valores de los lados
left = self.p.x
right = self.p.y + self.w
top = self.p.y + self.h
bottom = self.p.y
r_left = r.p.x
r_right = r.p.x + r.w
r_top = r.p.y + r.h
r_bottom = r.p.y
return right >= r_left and left <= r_right and top >= r_bottom and bottom <= r_top
He creado variables auxiliares para que se vea mejor, pero no son necesarias. Como vemos la complejidad computacional de calcular si dos rectángulos colisionan es muy poca simplemente comparar cuatro pares de valores.
Colisiones Círculos - Círculo
Saber si dos círculos están colisionando es muy fácil: Si la suma de sus radios es mayor que la distancia entre sus centros entonces existe colisión. Así que básicamente hay que hacer dos cosas: Calcular la distancia entres sus centros (que es la distancia entre dos puntos) y comprobar si es menor que la suma de sus radios.
Para calcular la distancia entre dos puntos lo mejor es añadir un método distancia a nuestra clase punto que reciba otro punto y devuelva la distancia entre ellos. La manera de calcular la distancia entre dos puntos es con el teorema de pitágoras.
def distance(self, p):
return math.sqrt(abs(p.x - self.x)**2 + abs(p.y - self.y)**2)
Ahora con esto definir el método colisión en la clase Círculo es muy simple:
def collide(self, c):
return self.r + c.r > self.p.distance(c.p)
Con esto ya podemos hacer pruebas de colisiones entre círculos y rectángulos. Quedaría ver si fuera necesario en un juego donde haya rectángulos y círculos la detección de colisiones entre círculo - rectángulo, pero básicamente es buscar el punto del rectángulo más cercano al centro del círculo, si este está contenido en el círculo entonces existe colisión. Vemos el código como queda.
import math
class Punto:
def __init__(self, x = 0, y = 0):
self.x = x
self.y = y
def __str__(self):
return "(" + str(self.x) + ", " + str(self.y) + ")"
def distance(self, p):
return math.sqrt(abs(p.x - self.x)**2 + abs(p.y - self.y)**2)
class Rect:
def __init__(self, p, w = 0, h = 0):
self.p = p
self.w = w
self.h = h
def collide(self, r):
# calculamos los valores de los lados
left = self.p.x
right = self.p.y + self.w
top = self.p.y + self.h
bottom = self.p.y
r_left = r.p.x
r_right = r.p.x + r.w
r_top = r.p.y + r.h
r_bottom = r.p.y
return right >= r_left and left <= r_right and top >= r_bottom and bottom <= r_top
class Circ:
def __init__(self, p, r):
self.p = p
self.r = r
def collide(self, c):
return self.r + c.r > self.p.distance(c.p)
r1 = Rect(Punto(4, 2), 40, 20)
r2 = Rect(Punto (9, 2), 30, 30)
c1 = Circ (Punto(8, 3), 30)
c2 = Circ (Punto(50, 4), 2)
print r1.collide(r2)
print c1.collide(c2)
¿Cual elegir?
La duda que se nos podría plantear ahora es que tipo elegir si los rectángulos o los círculos. Vemos que la detección de colisiones entre rectángulos es más rápida ya que en la de círculos hay raíces cuadradas de por medio que siempre son algo más lentas. Pero los círculos tienen una gran ventaja frente a los rectángulos y es que admiten rotaciones. Por mucho que rotes un círculo sigue siendo un círculo en el momento que rotes un rectángulo ya no tienes un rectángulo y estos cálculos tan simples no valen.
Así pues la regla es:
Usa rectángulos para aquellos sprites que no necesiten rotaciones, usa círculos para todo lo demás.
El problema del túnel
Bien hasta ahora hemos hablado de detectar colisiones en un momento del tiempo, saber si en el preciso instante en el que se comprueban los sprites existe colisión. Pero claro los objetos en el juego están en movimiento constante así que imaginemos la siguiente situación.
El círculo a se mueve en el tiempo pasado entre cada comprobación de colisión la distancia que indica su flecha, lo mismo para b. Con a como en el instante que comprobamos la colisión está colisionando con el rectángulo podemos detectarla y actuar en consecuencia, sin embargo, b iba más rapido y atravesado un objeto solido y en el momento de hacer la segunda comprobación ya no está colisionando con él. Esto sin duda es un problema que debemos solucionar.
Búsqueda linear
Una posible solución sería comprobar todos los pasos intermedio con distancia menores al tamaño de los objetos. Así nos aseguramos que no hemos atravesado ningún sólido.
Este método incrementaría exponencialmente el número de comprobaciones de colisión que habría que hacer por cada objeto, así que busquemos una manera más eficiente.
Búsqueda binaria
Esta otra solución consiste en trazar una circunferencia que tenga de diámetro la distancia desplazada y como centro el medio del vector del dezplazamiento.
Si éste círculo delimitador no colisiona con ningún objeto es que no existe colisión, por otro lado si hay una colisión lo que hacemos es dividir el espacio en dos circunferencias y comprobar si existe colisión en alguna de ellas.
Seguimos dividiendo la circunferencia donde encontremos la colisión y desechando la otra hasta que encontremos la colisión.
Como vemos la búsqueda binaria reduce muchísimo las comprobaciones que tenemos que realizar permitiendo una gestión eficiente.
Bouding Box
Al principio comentábamos que podíamos tener el siguiente problema.
Como vemos los círculos delimitadores colisionan, pero las naves realmente no están colisionando. La solución a esto es hacer subdivisiones.
Como vemos la primera imagen es demasiado genérico y no representa para nada a la nave, la segunda sin ser perfecta ya se acerca bastante y la tercera es bastante fiel a los límites de la nave. El problema es que aunque entre más círculos es más fiel a los límites originales también aumenta el número de comprobaciones necesarias ya que hay que comprobar las colisiones de cada círculo. En este caso quizás la solución del medio sea la más óptima en cuando a fidelidad / cálculos.
También aunque la primera sea poco óptima podemos usar el círculo general que engloba al objeto para comprobar si hay colisiones si este círculo no colisiona es que no existe colisión, por otra parte si este colisiona pasamos a comprobar los círculos interiores.
Esto es todo por ahora en el próximo artículo veremos como subdividir el espacio con QuadTree para ahorrar comprobaciones de objetos imposibles.
