Detector de Colisiones 2D en C++

[Phoer]

Buscando por la web he encontrado varios hilos sobre este tema, pero o eran en otro lenguaje programativo, o no trataban lo que yo buscaba o, simplemente, los enlaces estaban cortados. Mediante google me he encontrado con una situación parecida, por lo que acabo recurriendo a abrir un nuevo tema...

Hace tiempo creé desde 0 un detector de colisiones en 2D bastante simple, el cual simplemente te decía si había colisión entre 2 quad [pasando por la posición y tamaño de cada uno]. El tema colisión lo tengo dominado, pero el problema viene cuando debe determinar por dónde viene la colisión. Dandole muchas vueltas [soy un poco reacio a que internet me saque las castañas del fuego hasta que no me doy medio por vencido], he determinado que lo mejor es conocer el rectángulo de inserción que se crea en la colisión [véase el espacio en el que coinciden ambas imagenes]. A simple vista parece bastante fácil, y seguro que existen mil códigos optimizados del asunto, pero al parecer se esconden demasiado bien :/

Alguna idea?

[blau]

Pregunta: ¿No te sirve el vector resultante de restar las posiciones centrales de los dos quads?

D = (CB-CA);

Podrias sacar el angulo de la colision muy facilmente, angulo = Math.Atan2(D.Y, D.X);

Y para la mayoria de cosas podria valerte una aproximacion asi, si no necesitas algo con una fisica realista.

Y en caso de necesitar uns fisica mas realista, si puedes pasate a choque de circunferencias, que tb es sencilla y es una buena aproximacion.

Y si no te vale, pues ya se complica bastante mas, y quizas podrias verte alguna libreria de fisicas.

[Phoer]

Hmm si, supongo, no lo había pensado, aunque también es verdad que el rectángulo que esto crea es bastante mayor...

Lo he estado mirando detenidamente y creo que no, no es lo que busco, ya que en ciertos casos [como por ejemplo que una imagen sea mucho más grande que la otra] no surtiría el efecto deseado, al menos con el posible enfoque que yo le he dado a ese planteamiento...

[fjfnaranjo]

Pues a ver, si no me equivoco, tu algoritmo de antes lo que hace es comprobar si un cuadrado colisiona con otro (quad es un término algo amplio xD), y lo que quieres ahora es tratar de deducir el lugar por el que un cuadrado está entrando en otro (alguna de las 4 esquinas o uno de los lados).

Si este es el caso, no necesitas trigonometría (las funciones trigonométricas son relativamente caras y se pueden evitar muchas veces).

Te pondría algo de código pero no entiendo lo que quieres hacer exactamente, ni como pretendes resolver los siguientes dos problemas:

- Determinar cual de los cuadrados es el que está entrando en otro.
- Tener en cuenta la excepción de que un cuadrado se desplace sobre el otro a tanta velocidad que parezca estar entrando por el lado contrario al que está realmente.

¿Podrías comentar el problema con algún ejemplo concreto? A lo mejor así te podemos orientar mejor.

[Phoer]

Estoy con un proyecto basado en los Super Mario Bros., plataformeros 2D bastante simplones. En este caso, nos encontramos con varios elementos, de momento 3 [ordenados por importancia]:

- Prota
- Malosos
- Escenario

En el prota se calcula si ha habido colisión tanto con el enemigo como con el escenario, y el enemigo únicamente lo hace con el escenario. Así pues, me interesa saber por qué lado [o esquina, claro está] colisionan los objetos, y para ello necesito calcular el tamaño del rectángulo formado a raíz de la colisión. Realmente es fácil, y seguro que hay una función que me lo resuelve, pero por ahora sólo puedo imaginarme mil funciones dependiendo de cada caso [de si entra por la esquina superior derecha o izquierda, inferior derecha o izquierda, por arriba, abajo, derecha o izquierda]. Debido a que el prota es más grande que los enemigos pero menor a los elementos del escenario, lo que ha propuesto antes blau no es del todo factible

Debido a que en el juego nada va excesivamente rápido, el segundo punto que has apuntado no me preocupa

[blau]

No lo pillo...

has detectado la colision y ¿solo necesitas saber por que lado, y sin rotaciones de rectangulos? ¿Y que mas te dan las dimensiones?

Si tenemos dos rectangulos (R1,R2), en las que tienes las sisguiente posiciones definidas=> Left,Right,Top,Bottom  = Centro +- Tamaño/2

Si (R1.Left>R2.Right) || (R1.Right<R2.Left)  || (R1.Bottom>R2.Top) || (R1.Top<R2.Bottom) =>  No colisiona

D = R2.Centro - R1.Centro;

angulo = Math.Atan2(D.Y, -D.X);

si (angulo en [90º, -90º]) por un lado sino por el otro

o mas detallado si (angulo en [45º, -45º] por un lado, si (angulo en [45º, 135º] por arriba, ....

vamos que te puedes complicar lo que quieras con casuistica... pero esto son tres lineas y te vale. ;)

[fjfnaranjo]

En el prota se calcula si ha habido colisión tanto con el enemigo como con el escenario, y el enemigo únicamente lo hace con el escenario. Así pues, me interesa saber por qué lado [o esquina, claro está] colisionan los objetos, y para ello necesito calcular el tamaño del rect...

Si no leo mal, no necesitas nada de eso.

Con una resta sacas fácilmente si la colisión está a la izquierda o a la derecha. Con otra, si está arriba o abajo. Con lo cual ya tienes todas las posibles opciones calculadas, sin areas, ni ángulos, ni nada de nada...

¿Qué quieres hacer una función de respuesta para las colisiones? Pues con los datos de antes y el resultado de las restas puedes sacar facilmente donde debe estar el cuadro antes de la colisión (de nuevo, sin áreas ni ángulos ni nada de nada...).

Sigue sin estar resuelto el tema de que algo vaya muy rapido, y se meta muy dentro de un área de colisión, de forma que parezca que a entrado por el lugar contrario.

EDIT: No había visto la respuesta de blau, que básicamente va por el mismo sitio.

[TrOnTxU]

Hola,

yo creo que una cosa es detectar la colision, y otra la respuesta a la misma.

Como dicen blau y fjfnaranjo hay comprobaciones simples para detectar si dos rectangulos en un plano se intersectan, y para calcular la interseccion resultante.
Detectar con que lado se produce la colision, es complicado si como dices los rectangulos varian, algunos se mueven, otros, no, unos son mas grandes que otros, etc, etc.

Como siempre: divide y venceras. Lo primero separa la deteccion (si quieres tambien puedes obtener la interseccion en el mismo metodo) de la respuesta. Un ejemplo de posibles metodos de deteccion (en pseudocodigo rollo UML), si quieres separar:

Código [Seleccionar] Expand


HayColision(rectA : Rect, rectB : Rect) : boolean
Intersectan(rectA : Rect, rectB : Rect, out rectC : Rect) : bool


Luego separa el procesado de la colision/respuesta con el escenario:

Para un mario (estilo clasico) compuesto por mapas de celdas o tile maps, una capa de tile map sirve de colision. Ademas en esa capa cada tile de colision puede tener sus propiedades, como por ejemplo "suelo", "techo", "pared", etc...

Si lo que tienes son una "coleccion" de rectangulos para definir las colisiones del mapa, te aconsejo que les añadas estas propiedades, u otras parecidas. Esto te puede ayudar a saber que tipo de respuesta debes procesar.
Esto te ayudaria a reducir el coste de proceso, ya que tienes informacion "precalculada".

Esto te debe servir para calcular la colision/respuesta con el escenario con todos los personajes (player, enemigos, ...)


En cuanto a las colisiones entre "sprites" (personaje, enemigos, items, oloquequieras) no entiendo para que quieres saber la direccion.
Si lo que quieres es saber si estas pisando a un enemigo rollo salto mario es facil (suponiendo que el eje de coordenadas este en el borde superior izquierdo):
personaje.y < enemigo.y && personaje.isJump


Espero que esas sean las respuestas a tus dudas  ^_^'

Un saludo


EDIT: depues de releer creo que he entendido un poco mejor la pregunta  Oo

Primero mola saber la velocidad del sprite. pero sin velocidad:
* Si como dices todo rect de escenario debe ser mayor que el rect del personaje:

Código [Seleccionar] Expand


Result res = NADA;
if (Intersectan(player.rect, collider, out intersecion) )
{
    if (interseccion.w == player.rect.w && interseccion.h == player.rect.h) return DENTRO; // Opcional

    if (interseccion.w > 0)
    {
        res |= (player.rect.left < collider.right) ? RIGHT : LEFT;
    }

    if (interseccion.h > 0)
    {
        res |= (player.rect.bottom > collider.up) ? DOWN : UP;
    }

}
return res;

[Phoer]

A ver, me interesa saber por dónde colisiona cada cosa porque realmente es importante: no es lo mismo que el personaje "mate" al enemigo pisándolo que no al revés. En ambos casos hay colisión, pero si hay colisión y no es el protagonista el que está encima del maloso, pues mueres. A ver, vamos a hacer una representación "gráfica" de lo que me encuentro:


_________
|                     |
|                     |
|      Mario     |
|          ____ |__
|____|____ |     |
          | Maloso  |
          |_______|

A simple vista, evidentemente parece que el Mario esté matando al maloso, pero el caso es que cuando pasa por la función que me determina por dónde colisiona, me devuelve true en DOWN y RIGHT, pero sabiendo la intersección, el espacio que se solapa, si veo que y > x, implica que hay mayor colisión por abajo. Hacer una función para el ejemplo es sencillo, pero si en vez de colisionar por la esquina inferior derecha del Mario es en la izquierda, hay parámetros que cambian y que, por ahora, mi solución sería meterle un tostón de código...

[Warchief]

(Perdon por falta de tildes)

<EDIT> No entiendo bien el problema que tienes, voy a releer y rehacer respuesta</EDIT>

La respuesta original comentaba esto http://www.metanetsoftware.com/technique/tutorialA.html
Pero seguramente es parecido a lo que usas para DOWN y RIGHT.

[Phoer]

El problema que tengo es que, con el código que tengo ahora, con el ejemplo anterior me indica que hay colisión por dos lados [abajo y derecha], pero me interesa saber el amaño del rectángulo que se crea ya que, si la X es mayor que la Y, quiere decir que la colisión es por abajo. No sé, es que más creo que ya no puedo explicarme :/

[TrOnTxU]

El problema que tengo es que, con el código que tengo ahora, con el ejemplo anterior me indica que hay colisión por dos lados [abajo y derecha], pero me interesa saber el amaño del rectángulo que se crea ya que, si la X es mayor que la Y, quiere decir que la colisión es por abajo. No sé, es que más creo que ya no puedo explicarme :/

Yo creo que te entiendo, si sabes que el personaje colisiona por abajo con el enemigo es que lo estas pisando.
El codigo que te he puesto SOLO DEBE FUNCIONAR con los rects del escenario (que dices que son mas grandes que el rect dle personaje), si los enemigos son mas pequeños que el player no tiene porque funcionar.

Como te he dicho antes:

En cuanto a las colisiones entre "sprites" (personaje, enemigos, items, oloquequieras) no entiendo para que quieres saber la direccion.
Si lo que quieres es saber si estas pisando a un enemigo rollo salto mario es facil (suponiendo que el eje de coordenadas este en el borde superior izquierdo):
personaje.y < enemigo.y && personaje.isJump

Con lo que el rollo seria para la colision de personaje y enemigo:

Código [Seleccionar] Expand

if (HayColision(player.rect, enemigo.rect)
{
    if (personaje.rect.bottom < enemigo.rect.bottom && personaje.isJump && personaje.vel.y > 0) //por ejemplo
    {
        // Pisas enemigo: algo parecido a enemigo.Kill()
    }
    else
    {
        // El enemigo te mata:  personaje.Die()
    }
}
Como he dicho antes suponiendo el eje de coordenadas en el borde superior izquierdo de la pantalla

La comprobaciones pueden variar dependiendo del resto de la implementacion, si no tienes velocidad puedes hacer:

Código [Seleccionar] Expand

if (personaje.rect.bottom < (enemigo.rect.top + (enemigo.rect.w/2)) )...
o simplemente (mi preferida)

Código [Seleccionar] Expand

if (personaje.rect.bottom < enemigo.rect.bottom)...
O cosas asi, el rollo es que tu decides que condiciones quieres para que "mario" mate o, "pise" al enemigo. Por supuesto debes comprobar las excepciones que se pueden dar, y ver si te interesa que pase en esa situacion, pero yo me decanto por una comprobacion sencilla.
Es el tipo de comprobacion que he visto y mas tarde implementado en todos los plataformas 2D en los que he participado (que tampoco son mas de 2, pero bueno han funcionado bien).
Ademas este "tipo de comprobacion" tambien se encontrba en alguno de los plataformas de estos que hacia Hammer Tech. como demos del DIV, en auqella maravillosa epoca donde el 2D "dominaba el mundo"  0:-)
Y la verdad es que funcionaba ...


Bueno, espero haberte ayudado, pero en mi opinion estas intentando hacer algo un poco extraño con las intersecciones, que igual te pueden ofrecer menos informacion de la que necesitas para desarrollar tus ideas, pero weno...

Un saludo

[Hechelion]

Personalmente creo que se están mucho problema para algo que bajo otro enfoque tiene una solución mucho más simple.

Por lo que entiendo, el problema no es determinar el área de intersección (aunque es tu pregunta original), si no, determinar cuando mario está aplastando a un enemigo (mucho más simple de resolver)

Para saber si mario está aplastando a un enemigo, solo tienes una posibilidad, y es que mario esté cayendo, por consiguiente, si hay colisión (mario y un maloso) y la velocidad de vertical de mario es positiva (va cayendo) entonces mario está aplastando al maloso.

Los problemas de esa lógica surgen con malos que salten o vuelen, así que vamos a agregar otra condición y será calcula diferencia vertical entre 2 vertices de cada rectángulo. Por ejemplo, entre los 2 vértices inferiores izquierdos (estos están a nivel del suelo).

(Mario_Vertice3 - Maloso_Vertice3) < 0 AND Mario_VelVertical > 0
Te dice que mario está sobre el maloso y que está cayendo sobre él, que para un juego 2D debería resolver el 90% de las colisiones

[Phoer]

El caso es que no hay solamente dos direcciones, arriba y abajo, sino que también hay colisión derecha e izquierda, y tampoco hay únicamente colisión con los malosos, sino también con el escenario


[esta imagen es puramente representativa y nunca se dará el caso .__. ]

Teniendo en cuenta esta imagen, aunque hay 3 objetos colisionables [además del Mario], nos encontramos con 7 colisiones:

- La caja colisiona por la esquina superior derecha, lo que devolvería true tanto en la colisión por arriba como por la derecha
- La tubería de la izquierda choca en esa dirección, pero al ser más alta, también devolvería valor true al preguntarle si colisiona por arriba
- El suelo, al ser mucho más grande, colisiona por ambos lados y por abajo, evidentemente

Por ello mismo me interesa saber el tamaño de las intersecciones :/ Una vez encuentre una función que me devuelva el tamaño ya se habrá solucionado el dichoso problema -.-

[TrOnTxU]

Cada vez preguntas una cosa, yo creo que no lo tienes claro, pero weno ...

Suponemos que tienes un struct de este tipo:

Código [Seleccionar] Expand


struct Rect
{
    int x;
    int y;
    int w;
    int h;
}:

Y suponiendo que el eje de coordenadas esta ariba a la izquierda:
El algoritmo para calcular la interseccion:

Código [Seleccionar] Expand


bool TamanyoInterseccion(const Rect &a, const Rect &b, int &w, int &h)
{
    int maxL = (a.x > b.x) ? a.x : b.x;
    int minR = ( (a.x+a.w) < (b.x+b.w) ) ? (a.x+a.w) :  (b.x+b.w);

    int maxT = (a.y > b.y) ? a.y : b.y;
    int minB = ( (a.y+a.h) < ( b.y+b.h) ) ? (a.y+a.h) : (b.y+b.h);

    w = minR - maxL;
    h = minB - maxT;

    return (w > 0 && h > 0);
}


Si w y h "vuelven" negativases que no hay interseccion.

Era eso lo que querias??


EDIT: de todas formas sigo pensando que no te servirá ...
Necesitas que entre en juego la velocidad del personaje, y tratar de forma distinta las colisiones con el escenario y con los enemigos, como se te ha ido repitiendo todo el rato.