Un objeto tiene una posición y un vector de velocidad. Por lo general, solo se usa la posición para verificar si dos objetos colisionan, esto es problemático para los objetos que se mueven muy rápido, ya que puede suceder que el objeto se mueva tan rápido que esté delante del primer objeto en la primera verificación de colisión y detrás de él en El segundo control de colisión.

Ahora también hay comprobaciones de colisión basadas en líneas, en las que solo se verifica si el vector de movimiento de cada objeto se cruza con el cuadro delimitador del otro. Esto puede verse como una expansión de un punto. Sin embargo, esto solo funciona si el objeto que se mueve rápidamente es realmente pequeño.

Entonces, mi idea es, en lugar de expandir un punto, ¿por qué no expandir un rectángulo? Esto da como resultado un hexágono.

Ahora, hasta ahora todo bien. Pero, ¿cómo verifico si dos hexágonos de este tipo se cruzan? Tenga en cuenta que estos son hexágonos muy específicos.

Pregunta adicional : ¿Es posible calcular exactamente dónde (o más bien después de cuánto tiempo) ocurrió la colisión? Esto podría ser muy útil para detectar lo que realmente sucedió, como dónde y con cuánta potencia y para simular cómo se movieron en el tiempo entre la colisión y el final del cuadro.

La solución es en realidad más simple de lo esperado. El truco es usar la resta de Minkowski antes de tu técnica hexagonal.

Aquí están tus rectángulos A y B, con sus velocidades vAy vB. Tenga en cuenta que vAy vBno son realmente velocidades, son la distancia recorrida durante un cuadro.

Ahora reemplace el rectángulo B con un punto P, y el rectángulo A con el rectángulo C = A + (- B), que tiene dimensiones de la suma de las dimensiones de A y B. Las propiedades de adición de Minkowski indican que se produce una colisión entre el punto y el nuevo rectángulo si y solo si se produce una colisión entre los dos rectángulos originales:

Pero si el rectángulo C se mueve a lo largo del vector vA, y el punto P se mueve a lo largo del vector vB, un simple cambio de marco de referencia nos dice que es lo mismo que si el rectángulo C estuviera quieto, y el punto P se moviera a lo largo del vector vB-vA:

Luego puede usar una fórmula simple de intersección de segmento de caja para indicar dónde se produce la colisión en el nuevo marco de referencia.

El último paso es volver al marco de referencia adecuado. Simplemente divida la distancia recorrida por el punto hasta la intersección dentro del círculo por la longitud del vector vB-vAy obtendrá un valor stal que 0 < s < 1. La colisión ocurre en el momento s * Ten que Tes la duración de su cuadro.

Comentario de madshogo :
Una GRAN ventaja de esta técnica sobre la respuesta de Mr Beast es que si no hay rotación, entonces la "resta de Minkowski" A + (- B) se puede calcular una vez para todos los pasos de tiempo posteriores. !

Así que el único algoritmo que toma tiempo en todo esto (suma de Minkowski, la complejidad O (mn) , donde m es el número de vértices en A y n el número de vértices en B ) se puede usar solamente una vez, haciendo efectivamente detección de colisiones una constante- problema de tiempo!

Más tarde, puede tirar la suma una vez que sepa con certeza que A y B están en diferentes partes de su escena (¿de su quadtree?) Y que ya no colisionarán.

En contraste, el método del Sr. Beast requiere bastantes cálculos en cada paso de tiempo.

Además, para los rectángulos alineados a los ejes, A + (- B) se puede calcular de manera mucho más simple que calculando realmente todas las sumas, vértice por vértice. Simplemente expanda A agregando la altura de B a su altura y el ancho de B a su ancho (la mitad de cada lado).

Pero todo esto solo funciona si ni A ni B están girando y si ambos son convexos. Si hay rotación o si usa formas cóncavas, debe usar volúmenes / áreas barridas.
fin del comentario

En primer lugar, en el caso de los rectángulos alineados a los ejes, la respuesta de Kevin Reid es la mejor y el algoritmo es el más rápido.

Segundo, para formas simples, use velocidades relativas (como se ve a continuación) y el teorema del eje de separación para la detección de colisiones. Se le dirá si ocurre una colisión en el caso de movimiento lineal (sin rotación). Y si hay rotación, necesita un pequeño paso de tiempo para que sea preciso. Ahora, para responder la pregunta:

¿Cómo saber en el caso general si dos formas convexas se cruzan?

Le daré un algoritmo que funciona para todas las formas convexas y no solo para hexágonos.

Supongamos que X e Y son dos formas convexas. Se cruzan si y solo si tienen un punto en común, es decir, hay un punto x ∈ X y un punto y ∈ Y tal que x = y . Si considera el espacio como un espacio vectorial, esto equivale a decir x - y = 0 . Y ahora llegamos a este negocio de Minkowski:

La suma de Minkowski de X y Y es el conjunto de todos los x + y para x ∈ X y y ∈ Y .

Un ejemplo para X e Y

X, Y y su suma Minkowski, X + Y

Supongamos que (-Y) es el conjunto de todos -y para y ∈ Y , dado el párrafo anterior, X e Y se cruzan si y solo si X + (-Y) contiene 0 , es decir, el origen .

Comentario lateral: ¿por qué escribo X + (-Y) en lugar de X - Y ? Bueno, porque en matemáticas, hay una operación llamada la diferencia de Minkowski de A y B, que a veces se escribe X - Y, pero no tiene nada que ver con el conjunto de todos x - y para x ∈ X e y ∈ Y (el verdadero Minkowski La diferencia es un poco más compleja).

Por lo tanto, nos gustaría calcular la suma de Minkowski de X e -Y y determinar si contiene el origen. El origen no es especial en comparación con cualquier otro punto, por lo que para encontrar si el origen está dentro de un determinado dominio, utilizamos un algoritmo que podría decirnos si algún punto dado pertenece a ese dominio.

La suma de X e Y de Minkowski tiene una propiedad genial, que es que si X e Y son convexos, entonces X + Y también lo es. Y descubrir si un punto pertenece a un conjunto convexo es mucho más fácil que si ese conjunto no fuera (se sabe que es) convexo.

No podemos calcular todas las x - y para x ∈ X e y ∈ Y porque hay una infinidad de tales puntos x e y , así que con suerte, dado que X , Y e X + Y son convexos, podemos usar los puntos "más externos" que definen las formas X e Y , que son sus vértices, y obtendremos los puntos más externos de X + Y , y también algunos más.

Estos puntos adicionales están "rodeados" por los más externos de X + Y para que no contribuyan a definir la forma convexa recién obtenida. Decimos que no definen el " casco convexo " del conjunto de puntos. Entonces, lo que hacemos es deshacernos de ellos en preparación para el algoritmo final que nos dice si el origen está dentro del casco convexo.

El casco convexo de X + Y. Hemos eliminado los vértices "internos".

Por lo tanto, obtenemos

Un primer algoritmo ingenuo

boolean intersect(Shape X, Shape Y) {

  SetOfVertices minkowski = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      minkowski.addVertice(x-y);
    }
  }
  return contains(convexHull(minkowski), Vector2D(0,0));

}

Los bucles obviamente tienen complejidad O (mn) , donde m y n son el número de vértices de cada forma. El minkoswkiconjunto contiene elementos mn como máximo. El convexHullalgoritmo tiene una complejidad que depende del algoritmo que utilizó , y puede apuntar a O (k log (k)) donde k es el tamaño del conjunto de puntos, por lo que en nuestro caso obtenemos O (mn log (mn) ) . El containsalgoritmo tiene una complejidad que es lineal con el número de aristas (en 2D) o caras (en 3D) del casco convexo, por lo que realmente depende de sus formas iniciales, pero no será mayor que O (mn) .

Te dejaré googlear el containsalgoritmo para formas convexas, es bastante común. Puedo ponerlo aquí si tengo tiempo.

Pero lo que estamos haciendo es la detección de colisiones, por lo que podemos optimizarlo mucho

Originalmente teníamos dos cuerpos A y B moviéndose sin rotación durante un paso de tiempo dt (por lo que puedo ver mirando sus fotos). Llamemos a v _A y v _B las velocidades respectivas de A y B , que son constantes durante nuestro paso de tiempo de duración dt . Obtenemos lo siguiente:

y, como señala en sus imágenes, estos cuerpos barren áreas (o volúmenes, en 3D) a medida que se mueven:

y terminan como A ' y B' después del paso de tiempo.

Para aplicar nuestro algoritmo ingenuo aquí, solo tendríamos que calcular los volúmenes barridos. Pero no estamos haciendo esto.

En el marco de referencia de B , B no se mueve (¡duh!). Y A tiene una cierta velocidad con respecto a B que obtienes calculando v _A - v _B (puedes hacer lo contrario, calcular la velocidad relativa de B en el marco de referencia de A ).

De izquierda a derecha: velocidades en el marco de referencia base; velocidades relativas; calcular velocidades relativas.

Al considerar a B como inmóvil en su propio marco de referencia, solo tiene que calcular el volumen que A recorre a medida que se mueve durante dt con su velocidad relativa v _A - v _B .

Esto disminuye el número de vértices que se utilizarán en el cálculo de la suma de Minkowski (a veces en gran medida).

Otra posible optimización es en el punto donde calcula el volumen barrido por uno de los cuerpos, digamos A. No tiene que traducir todos los vértices que conforman A. Solo aquellos que pertenecen a bordes (caras en 3D) cuyos "cara" normal exterior la dirección del barrido. Seguramente ya lo habrás notado cuando calculaste las áreas barridas para los cuadrados. Puede saber si una normal es hacia la dirección de barrido utilizando su producto de punto con la dirección de barrido, que tiene que ser positivo.

La última optimización, que no tiene nada que ver con su pregunta sobre las intersecciones, es realmente útil en nuestro caso. Utiliza esas velocidades relativas que mencionamos y el llamado método de eje de separación. Seguramente ya lo sabes.

Suponga que conoce los radios de A y B con respecto a sus centros de masa (es decir, la distancia entre el centro de masa y el vértice más alejado de él), así:

Una colisión puede ocurrir sólo si es posible que el círculo de delimitación de A se encuentran la de B . Vemos aquí que no lo hará, y la manera de decirle a la computadora que consiste en calcular la distancia de C _B a I como en la siguiente imagen y asegurarse de que es más grande que la suma de los radios de A y B . Si es más grande, no hay colisión. Si es más pequeño, entonces colisión.

Esto no funciona muy bien con formas que son bastante largas, pero en el caso de cuadrados u otras formas similares, es una muy buena heurística para descartar colisión .

El teorema del eje de separación aplicado a B y el volumen barrido por ASin embargo, el le dice si ocurre la colisión. La complejidad del algoritmo asociado es lineal con la suma de los números de vértices de cada forma convexa, pero es menos mágico cuando llega el momento de manejar la colisión.

Nuestro nuevo y mejor algoritmo que usa intersecciones para ayudar a detectar colisiones, pero aún no es tan bueno como el teorema del eje de separación para saber si ocurre una colisión

boolean mayCollide(Body A, Body B) {

  Vector2D relativeVelocity = A.velocity - B.velocity;
  if (radiiHeuristic(A, B, relativeVelocity)) {
    return false; // there is a separating axis between them
  }

  Volume sweptA = sweptVolume(A, relativeVelocity);
  return contains(convexHull(minkowskiMinus(sweptA, B)), Vector2D(0,0));

}

boolean radiiHeuristic(A, B, relativeVelocity)) {
  // the code here
}

Volume convexHull(SetOfVertices s) {
  // the code here
}

boolean contains(Volume v, Vector2D p) {
  // the code here
}

SetOfVertices minkowskiMinus(Body X, Body Y) {

  SetOfVertices result = new SetOfVertices();
  for (Vertice x in X) {
    for (Vertice y in Y) {
      result.addVertice(x-y);
    }
  }
  return result;

}

No creo que usar el 'hexágono' sea tan útil. Aquí hay un bosquejo de una forma de obtener colisiones exactas para rectángulos alineados a ejes:

Dos rectángulos alineados con ejes se superponen si y solo si sus rangos de coordenadas X se superponen y sus rangos de coordenadas Y se superponen. (Esto puede verse como un caso especial del teorema del eje de separación). Es decir, si proyecta los rectángulos en los ejes X e Y, ha reducido el problema a dos intersecciones línea-línea.

Calcule el intervalo de tiempo en el que se cruzan las dos líneas en un eje (por ejemplo, comienza en el tiempo (separación actual de objetos / velocidad relativa de los objetos que se aproxima)), y haga lo mismo para el otro eje. Si esos intervalos de tiempo se superponen, entonces el tiempo más temprano dentro de la superposición es el momento de la colisión.

No creo que haya una manera fácil de calcular la colisión de polígonos con más lados que un rectángulo. Lo dividiría en formas primitivas como líneas y cuadrados:

function objectsWillCollide(object1,object2) {
    var lineA, lineB, lineC, lineD;
    //get projected paths of objects and store them in the 'line' variables

    var AC = lineCollision(lineA,lineC);
    var AD = lineCollision(lineA,lineD);
    var BC = lineCollision(lineB,lineC);
    var BD = lineCollision(lineB,lineD);
    var objectToObjectCollision = rectangleCollision(object1.getRectangle(), object2.getRectangle());

    return (AC || AD || BC || BD || objectToObjectCollision);
}

Observe cómo ignoro el estado de inicio de cada objeto, ya que debería haberse verificado durante el cálculo anterior.

Teorema del eje separado

El teorema del eje separado dice "Si podemos encontrar un eje en el que dos formas convexas no se crucen, entonces las dos formas no se cruzan" o más factible para TI:

"Dos formas convexas solo se cruzan si se cruzan en todos los ejes posibles".

Para los rectángulos alineados a los ejes hay exactamente 2 ejes posibles: x e y. Pero el teorema no se limita a los rectángulos, se puede aplicar a cualquier forma convexa simplemente agregando los otros ejes en los que las formas podrían cruzarse. Para obtener más detalles sobre el tema, consulte este tutorial del desarrollador de N: http://www.metanetsoftware.com/technique/tutorialA.html#section1

Implementado se ve así:

axes = [... possible axes ...];
collision = true;
for every index i of axes
{
  range1[i] = shape1.getRangeOnAxis(axes[i]);
  range2[i] = shape2.getRangeOnAxis(axes[i]);
  rangeIntersection[i] = range1[i].intersectionWith(range2[i]);
  if(rangeIntersection[i].length() <= 0)
  {
    collision = false;
    break;
  }
}

Los ejes pueden ser tan representados como vectores normalizados.

Un rango es una línea unidimensional. El inicio debe establecerse en el punto proyectado más pequeño, el final al punto proyectado más grande.

Aplicarlo al rectángulo "barrido"

El hexágono en la pregunta se produce al "barrer" el AABB del objeto. El barrido agrega exactamente un posible eje de colisión a cualquier forma: el vector de movimiento.

shape1 = sweep(originalShape1, movementVectorOfShape1);
shape2 = sweep(originalShape2, movementVectorOfShape2);

axes[0] = vector2f(1.0, 0.0); // X-Axis
axes[1] = vector2f(0.0, 1.0); // Y-Axis
axes[2] = movementVectorOfShape1.normalized();
axes[3] = movementVectorOfShape2.normalized();

Hasta ahora todo bien, ahora ya podemos verificar si los dos hexágonos se cruzan. Pero se pone aún mejor.

Esta solución funcionará para cualquier forma convexa (por ejemplo, triángulos) y cualquier forma convexa barrida (por ejemplo, octágonos barridos). Sin embargo, cuanto más compleja sea la forma, menos efectiva será.

Bonus: donde sucede la magia.

Como dije, los únicos ejes adicionales son los vectores de movimiento. El movimiento es tiempo multiplicado por velocidad, por lo que, en cierto sentido, no son solo ejes espaciales, son ejes espacio-temporales.

Esto significa que podemos derivar el tiempo en que la colisión podría haber ocurrido a partir de estos dos ejes. Para esto necesitamos encontrar la intersección entre las dos intersecciones en los ejes de movimiento. Sin embargo, antes de que podamos hacer esto, debemos normalizar ambos rangos, para poder compararlos.

shapeRange1 = originalShape1.getRangeOnAxis(axes[2]);
shapeRange2 = originalShape2.getRangeOnAxis(axes[3]);
// Project them on a scale from 0-1 so we can compare the time ranges
timeFrame1 = (rangeIntersection[2] - shapeRange1.center())/movementVectorOfShape1.project(axes[2]);
timeFrame2 = (rangeIntersection[3] - shapeRange2.center())/movementVectorOfShape2.project(axes[3]);
timeIntersection = timeFrame1.intersectionWith(timeFrame2);

Cuando hice esta pregunta, ya acepté el compromiso de que habrá algunos falsos positivos raros con este método. Pero me equivoqué, al verificar esta intersección de tiempo podemos probar si la colisión "realmente" ocurrió y podemos resolver esos falsos positivos con ella:

if(collision)
{
  [... timeIntersection = see above ...]
  if(timeIntersection.length() <= 0)
    collision = false;
  else
    collisionTime = timeIntersection.start; // 0: Start of the frame, 1: End of the frame
}

Si observa algún error en los ejemplos de código, avíseme, aún no lo he implementado y, por lo tanto, no pude probarlo.

Siempre que las áreas barridas estén cerradas (sin espacios en el límite formado por las líneas de borde), lo siguiente funcionará (solo reduzca sus pruebas de colisión a línea-línea y punto-rect / punto-tri):

1. ¿Se tocan sus bordes? (colisiones línea-línea) Compruebe si alguna línea de borde de un área barrida se cruza con alguna línea de borde de la otra área barrida. Cada área barrida tiene 6 lados.

2. ¿Está el pequeño dentro del grande? (Utilice formas alineadas por eje (point-rect y point-tri)) Reoriente (rote) las áreas barridas para que la más grande esté alineada con el eje y pruebe si la más pequeña es interna (probando si hay puntos de esquina ( debe ser todo o nada) están dentro del área barrida alineada con el eje). Esto se hace descomponiendo tu hex en tris y rectos.

La prueba que haga primero depende de la probabilidad de cada una (haga primero la más común).

Es posible que le resulte más fácil usar un círculo de delimitación barrido (cápsula en lugar de hex) porque es más fácil dividirlo en dos semicírculos y un rectángulo cuando está alineado en el eje. .. te dejaré dibujar la solución