Resolución de colisión en caso de colisión con múltiples objetos.

15

Tengo objetos estáticos y objetos móviles. Las colisiones se detectan utilizando el teorema del eje de separación.

Por ejemplo, en esta situación tengo dos objetos estáticos (en rojo):

ingrese la descripción de la imagen aquí

y un objeto móvil entre los dos:

ingrese la descripción de la imagen aquí

Mi algoritmo puede calcular la colisión entre dos de estos objetos, y también escupe un vector de resolución perfecta (es decir, un vector de desplazamiento mínimo) a la colisión.

Entonces, por ejemplo, cuando verifico la colisión entre el rectángulo verde y el rectángulo rojo derecho, el algoritmo escupe un vector que me dice cómo necesito mover el rectángulo verde para resolver la colisión:

ingrese la descripción de la imagen aquí

Tenga en cuenta que acabo de dibujar esto rápidamente en MSPaint, por lo que en esa imagen podría ser que el vector de traducción mínima empuje el rectángulo verde en la parte superior, pero voy a suponer aquí que empujarlo hacia la izquierda / derecho es en realidad más corto.

La forma general de abordar esto sería resolver solo la colisión de una colisión por cuadro, en lugar de todas a la vez. Pero en mi caso, esto resultaría en un flip-flop:

Primero, el solucionador detecta dos colisiones pero solo resuelve la colisión entre el rectángulo derecho y el rectángulo verde:

ingrese la descripción de la imagen aquí

Luego, en el siguiente cuadro, detecta solo una colisión que se encuentra entre el rectángulo rojo izquierdo y el rectángulo verde, y lo resuelve:

ingrese la descripción de la imagen aquí

Como puede ver, esto en realidad no resuelve la colisión (por ejemplo, empujando el rectángulo verde hacia la parte superior), y en su lugar simplemente cambia las chanclas entre los dos estados infinitamente.

¿Como puedo resolver esto?

TravisG
fuente
Estás usando rectángulos en tu ejemplo. ¿Su algoritmo de colisión solo resuelve la colisión en un solo eje? Si es así, tiene sentido que ocurra el comportamiento que usted describe.
chaosTechnician
No, puede resolverlos con cualquier tipo de formas en todos los ejes posibles (no solo rectángulos, son los más fáciles de dibujar con MS paint: P) y siempre encontrará el vector más corto que exista que separa los dos objetos .
TravisG
+1 Buena pregunta. Eliminé la "etiqueta" (2D) del título, es algo que debes evitar (ver meta ).
bummzack

Respuestas:

7

Dependiendo exactamente de lo que esté tratando de lograr (alta precisión física o simplemente una simulación en tiempo real lo suficientemente cercana), puede intentar usar contactos especulativos.

Aquí están los detalles: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

Describe en ese artículo lo que necesita saber para implementarlo, y es muy simple en comparación con otros enfoques (como el lanzamiento de esferas y luego la clasificación de las resoluciones de colisión por tiempo de impacto).

Si necesita / quiere más, puede comprar su código fuente por (IIRC) $ 7.

Aquí hay un video de mi implementación en 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Observe cuán estable es la simulación con solo una iteración. Podría usar fácilmente múltiples iteraciones por cuadro para resolver múltiples colisiones a un estado estable, lo que sería más preciso.

Olhovsky
fuente
2

Primero puede calcular todos los vectores necesarios para resolver cada colisión y luego calcular el resultado de ellos.

El único caso en el que esto puede hacer byte es si estos vectores se anulan entre sí, como en su ejemplo. En ese caso, la colisión no se puede resolver.

Mihai Maruseac
fuente
¿Agregar un pequeño vector aleatorio con una magnitud de aproximadamente epsilon * 10 a las colisiones? La aritmética de coma flotante debería hacer el resto.
Martin Sojka
2
Sí, esto puede funcionar, supongo. Pero también puede crear movimientos nerviosos.
Mihai Maruseac
1
Espero que aún pueda obtener una respuesta sobre esto: calcular un resultado soluciona el problema del "bucle infinito", pero reintroduce el problema del "crack", donde moverse mientras se desliza sobre una pared hecha de azulejos del mismo tamaño hace que el cuerpo se ponga atrapado entre las "grietas" de los azulejos. ¿Hay alguna forma de resolver estos dos problemas?
Vittorio Romeo
De acuerdo ... no hay la mejor "respuesta correcta" para resolver una colisión imposible de cuerpo rígido como esa. O se agita, o permite un poco de "hongos" en uno o más de los objetos.
David van brink
0

Si lo observa detenidamente, ese estado de los objetos es (o debería ser) inalcanzable.

Deje que la forma roja más a la izquierda sea la forma R1, y la forma roja más a la derecha sea la forma R2. Deje que la forma verde sea G.

es decir, dado el tamaño y la geometría de los tres objetos, y dado que no todos los objetos son penetrables:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Ahora, todo se reduce a eso, si su algoritmo consulta sus objetos uno por uno, entonces es una cuestión de concurrencia, es decir, en cierto sentido, se supone que el algoritmo verifica TODOS los objetos al mismo tiempo, pero el algoritmo lo limita a hacer objetos y procesarlos uno a la vez ...

Si G se compara con R1 después de que se comprueba con R2, G parecería estar legalmente a la derecha de R1 (si G dice que se acerca a R1 con la dirección del vector <-1, -1> con magnitud arbitraria (o distancia) ), porque la verificación entre R1 y G lo permite, y olvida la verificación entre R2 y G que se realizó antes.

Una solución que puede hacer es recopilar todos los vectores de desplazamiento mínimo en una matriz o cualquier estructura de datos que desee, y elegir uno que resulte legal para TODOS los objetos.

Tenga en cuenta que en un marco dado, el objeto (G, por ejemplo) solo puede tener UNA dirección. (oh hombre, suena como el boyband ...)

Liu Mao Hsing
fuente