En el procesos de desarrollo de videojuegos las colisiones juegan un papel fundamental tanto que sin ellas se puede decir que no hay juego.

Hay diferentes formas de manejar las colisiones dependiendo de muchos factores como por ejemplo si es un juego 2D o 3D o si es juego de automóviles, uno de aventuras o uno de pelea. Para el caso especifico de los videojuegos 2D, si bien hay diferencias entre unos estilos de juego y otros, existen dos estilos fundamentales para detección de colisiones: Colisión de rectángulos y Colisión de Círculos, cada cual se usa según sea conveniente de acuerdo a la figura que mejor pueda contener al cuadro de animación.

Este articulo se enfocara a la detección de colisiones utilizando rectángulos y/o círculos los principios son aplicables en cualquier herramienta, sin embargo para efectos del articulo se utilizara C# y XNA FrameWork. El performance también es fundamental, como suele suceder hay muchas maneras de hacer las cosas y eso se vera en el desarrollo del articulo.

Cuando utilizar un sistema de colisiones determinado?

Depende principalmente de la forma del sprite, es decir desde luego todo sprite es rectangular, pero la figura descrita dentro de el es generalmente irregular y existen casos en los que un cuadrado no daría la precisión adecuada para la forma dibujada en el sprite como se puede ver en la figura descrita a continuación:

En el ejemplo se puede observar una situación tipica, un programa detector de colisiones diría que en ambos casos hay colisión, pero es evidente que solo hay colisión real cuando se usa detección de colisiones usando círculos. Desde luego también ocurren casos contrarios al anterior, como se ve en la siguiente imagen:

Es claro que el personaje al cual le calculan la colisión usando circunferencias esta en desventaja.

Detección de Colisiones Entre Círculos

Para calcular colisiones entre dos círculos se requieren conocer el radio de cada circulo y su posición, realmente y aunque no pareciera, calcular la colisión de dos círculos es sencillo, se debe determinar la distancia entre el centro de un circulo y el centro del otro círculo, si la distancia entre ambos centros es menor que la suma de los radios de ambos círculos entonces existe una colisión entre ellos .

Así que desde luego el paso a seguir es el paso 1: Establecer la distancia entre dos puntos.

Cálculo de la distancia entre dos puntos

La distancia entre dos puntos se determina haciendo uso de la ecuación: que se deriva del álgebra de Pitágoras. La implementación de esta ecuación se muestra a continuación:

El código es C# y la estructura Vector2 hace parte de XNA Framework.

/// <summary>
        /// Calculate the distance between 2 points the algoritm is 100% accurate
        /// as well this algoritm is not extreme fast
        /// </summary>
        /// <param name="p1">Point 1</param>
        /// <param name="p2">Point 1</param>
        /// <returns>The distance between the points</returns>
        public static int AccurateDistance( Vector2 p1,  Vector2 p2)
        {
            return (int) System.Math.Sqrt((p2.X - p1.X) * (p2.X - p1.X) + (p2.Y - p1.Y) * (p2.Y - p1.Y));
        } 

Con esto ya se tiene casi todo hecho, solo es necesario sumar los radios de los círculos y restarles la distancia obtenida, si la distancia es <= a 0 entonces existe colisión.

Sin embargo esta formula tiene una debilidad y es que usada de manera intensa (como suele suceder en un vjuego) puede volverse poco eficiente, así que en su lugar se puede hacer uso de la siguiente implementación, que si bien no brinda un resultado 100% preciso si ofrece una muy cercana aproximación a este y sobre todo es mucho más rápida que la versión anterior, la implementación hace uso de la Serie de Maclaurin:

El código es C# y la estructura Vector2 hace parte de XNA Framework.

/// <summary>
        /// Calculate the distance between 2 points, it use a fast algoritm as well this
        /// algoritm isn't 100% accurate
        /// </summary>
        /// <param name="p1">Point 1</param>
        /// <param name="p2">Point 1</param>
        /// <returns>The distance between the points</returns>
        public static int FastDistance( Vector2 p1, Vector2 p2)
        {
            int x = (int)System.Math.Abs(p2.X - p1.X);
            int y = (int)System.Math.Abs(p2.Y - p1.Y);
 
            int min = x < y ? x : y;
 
            return System.Math.Abs(x + y - (min >> 1) - (min >> 2) + (min >> 4));
        } 

Detección de Colisiones Entre Rectángulos

Para determinar si existe colisión entre dos rectángulos se necesita únicamente conocer su posición y sus dimensiones. El cálculo es sencillo, imaginemos que estamos en un sistema de coordenadas de dos dimensiones, si en el eje X el rectángulo 1 inicia antes que termine el dibujo del rectángulo 2 y si el rectángulo 2 inicia antes de que finalice el dibujo del rectángulo 1 y si hacemos el mismo ejercicio en el eje Y entonces existe una colisión entre los rectángulos, si una de las 4 condiciones falla entonces no hay colisión.

Para una implementación de colisiones básica esta implementación es mas que suficiente, informa cuando hay colisión entre dos rectángulos, he usado algunos parentesis adicionales en el if tan solo por claridad, pero estos no son necesarios.

El código es C# y la estructura Rectangle hace parte de XNA Framework.

/// <summary>
        /// Calculale if two rectangles are colisioning between they
        /// </summary>
        /// <param name="a">Rectangle 1</param>
        /// <param name="b">Rectangle 2</param>
        /// <returns>bool if an intersection exist if not false</returns>
        public static bool RectangleColission( Rectangle a, Rectangle b)
        {
            if ( (a.X < b.X + b.Width) && (b.X < a.X + a.Width) && (a.Y < b.Y + b.Height))
            {
                return b.Y < a.Y + a.Height;
            }
            
            return false;
        } 

Esta función es lo suficientemente rápida para la mayoría de los casos, sin embargo en ocasiones es necesario no solo determinar si existe colisión entre los rectángulos sino adicionalmente calcular el rectángulo resultante de dicha colisión, este caso es muy común cuando se realizan procesos de detección de colisiones mas avanzadas como por ejemplo la colisión perfecta la cual compara en que puntos del rectángulo de intersección dos colores se tocan entre si, esta seria una implementación optimizada que permite en un solo paso obtener el rectángulo de intersección y determinar si existe o no colisión.

/// <summary>
        /// Calculale if two rectangles are colisioning between they and obtain the resulting interect rectangle
        /// </summary>
        /// <param name="a">Rectangle 1</param>
        /// <param name="b">Rectangle 2</param>
        /// <param name="c">output intersection Rectangle </param>
        /// <returns>bool if an intersection exist if not false</returns>
        /// <remarks>if not colission exists the output rectangle is the empty rectangle</remarks>
        public static bool RectangleIntersection( Rectangle a,  Rectangle b, out Rectangle c)
        {
            int x = System.Math.Max(a.X, b.X);
            int num2 = System.Math.Min(a.X + a.Width, b.X + b.Width);
            int y = System.Math.Max(a.Y, b.Y);
            int num4 = System.Math.Min(a.Y + a.Height, b.Y + b.Height);
 
            if (num2 >= x && num4 >= y)
            {
                c.X = x;
                c.Y = y;
                c.Width = num2 - x;
                c.Height = num4 - y;
 
                return true;
            }
            c.Height =c.Width =c.Y =c.X = 0;
            return false;
        } 

En una próxima entrada del blog estare tratando el tema de colisiones por píxel.

Juan Carlos Ruiz Pacheco
Ingeniero de Sistemas