¿Un algoritmo simple de colisión de rectángulo 2D que también determina qué lados chocan los rectángulos?

16

Inicialmente intenté implementar una intersección rectangular, que funciona bien. Sin embargo, cuando tengo que aplicar el sistema de física, como la velocidad, la aceleración y los vectores direccionales, tendría que encontrar una manera de determinar qué lado de los rectángulos chocan. Ahora, en mi sistema, no hay un rectángulo girado, por lo que esto simplificó el problema. Sin embargo, no pude encontrar una manera fácil de determinar qué lado del rectángulo colisionó. Una vez he lidiado con este problema antes pero fallé miserablemente.

Lo que hice en el pasado es determinar la distancia entre cada lado rectangular paralelo y verificar si la distancia es cercana a 0 (use un rango de distancia inicialmente definido) o sea 0. Sin embargo, para la aritmética de punto flotante, esto resulta inestable porque de tiempo desconocido transcurre. En algún momento, los rectángulos se intersectarían entre sí antes de cumplir con el rango definido.

Por otro lado, estaba pensando en generar múltiples rectángulos, cada rectángulo para cada lado. Sin embargo, después de pensar de nuevo, sería lo mismo que tener un lado paralelo con la verificación del rango de distancia, solo que ese rango de distancia es el ancho de cada mini rectángulo.

Por lo tanto, ¿alguna sugerencia para este problema?

usuario1542
fuente
¿Está utilizando actualizaciones de posición discretas o continuas? (¿estás actualizando tu velocidad mediante la aceleración una vez cada cuadro y luego calculando la posición, o
estás

Respuestas:

24

Adaptado de mi respuesta a "¿Qué lado fue golpeado?" :

Sugiero calcular la suma Minkowski de B y A, que es un nuevo rectángulo, y verificar dónde se encuentra el centro del rectángulo A en relación con ese nuevo rectángulo (para saber si está ocurriendo una colisión) y sus diagonales (para saber dónde está la colisión está sucediendo):

float w = 0.5 * (A.width() + B.width());
float h = 0.5 * (A.height() + B.height());
float dx = A.centerX() - B.centerX();
float dy = A.centerY() - B.centerY();

if (abs(dx) <= w && abs(dy) <= h)
{
    /* collision! */
    float wy = w * dy;
    float hx = h * dx;

    if (wy > hx)
        if (wy > -hx)
            /* collision at the top */
        else
            /* on the left */
    else
        if (wy > -hx)
            /* on the right */
        else
            /* at the bottom */
}
sam hocevar
fuente
1
Me gustaría agregar que 'arriba' y 'abajo' son relativos a su sistema de coordenadas. En mi juego, por ejemplo, (0,0) está en la parte superior izquierda, por lo que están invertidos de tu ejemplo. Sólo algo para tener en cuenta.
Neikos
Gran solución, funcionó muy bien para mis necesidades.
Opiatefuchs
1
¿Hay algún problema con dx convirtiéndose en 0 o dy convirtiéndose en 0 o ambos? Permítanme razonarlo ... si dx = 0 && dy == 0, eso significa que ambos rectángulos están en el mismo origen, ¿entonces el algoritmo regresa al fondo por defecto? si alguno de ellos es 0, se espera el resultado correcto. Entonces, creo que este algoritmo es correcto, excepto en el caso en que dx == 0 && dy == 0, que debe ser indeterminado y no inferior. Entonces, cuidado y gracias.
Prasanth
1
Ahora, me preguntaba qué sucede cuando dx == dy, w == h ... entonces, también, el código decide que el resultado es un lado cuando en realidad es indeterminado ... imagine dos cuadrados que se crucen de tal manera que el centro de un cuadrado esté en una esquina de otro cuadrado y el centro del otro cuadrado está en la esquina del primer cuadrado. Aquí, el lado debe ser indeterminado, no es correcto ni inferior. ¡¿Son ambos?!
Prasanth