Unlimited WordPress themes, graphics, videos & courses! Unlimited asset downloads! From $16.50/m
Advertisement
  1. Game Development
  2. Collision Detection
Gamedevelopment

Detección de colisiones usando el teorema del eje de separación

by
Difficulty:IntermediateLength:LongLanguages:

Spanish (Español) translation by Luis Chiabrera (you can also view the original English article)

El teorema del eje de separación se usa a menudo para verificar las colisiones entre dos polígonos simples, o entre un polígono y un círculo. Al igual que con todos los algoritmos, tiene sus fortalezas y sus debilidades. En este tutorial, repasaremos las matemáticas detrás del teorema y mostraremos cómo se puede usar en el desarrollo de juegos con algunos ejemplos de código y demostraciones.

Nota: Aunque las demostraciones y el código fuente de este tutorial utilizan Flash y AS3, debería poder usar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos.


Lo que dice el teorema

El Teorema del eje de separación (SAT para abreviar) establece esencialmente que si puedes trazar una línea para separar dos polígonos, entonces no chocan. Es así de simple.

SAT collision detection

En el diagrama anterior, puedes ver fácilmente las colisiones que ocurren en la segunda fila. Sin embargo, si intenta comprimir una línea entre las formas, fallará. La primera fila es exactamente lo opuesto. Puede dibujar fácilmente una línea para separar las formas, y no solo una, sino muchas de ellas:

Lines separating shapes

Está bien, no exageremos esto; Creo que entiendes el punto. El argumento clave aquí es que si puede dibujar una línea de este tipo, entonces debe haber un espacio que separa las formas. Entonces, ¿cómo comprobamos esto?


Proyección a lo largo de un eje arbitrario

basic idea of algorithm

Supongamos por ahora que los polígonos a los que nos referimos son cuadrados: box1 a la izquierda y box2 a la derecha. Es fácil ver que estos cuadrados están separados horizontalmente. Un enfoque directo para determinar esto en el código es calcular la distancia horizontal entre los dos cuadrados, luego restar los medios anchos de box1 y box2:

¿Qué pasa si las cajas no están bien orientadas?

oriented boxes

Aunque la evaluación de la brecha sigue siendo la misma, tendremos que pensar en otro enfoque para calcular la longitud entre los centros y las medias anchuras, esta vez a lo largo del eje P. Aquí es donde las matemáticas vectoriales son útiles. Proyectaremos los vectores A y B a lo largo de P para obtener las medias anchuras.

Vamos a hacer una revisión de matemáticas.


Revisión del vector matematico

Comenzaremos por recapitular la definición del producto punto entre dos vectores A y B:

Dot product operation

Podemos definir el producto de puntos usando solo los componentes de los dos vectores:

\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
(A_x)(B_x)+(A_y)(B_y)
\]

Alternativamente, podemos entender el producto de puntos usando las magnitudes de los vectores y el ángulo entre ellos:

\[
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}B_x \\B_y\end{bmatrix}=
A_{magnitude}*B_{magnitude}*cos(theta)
\]

Ahora, intentemos averiguar la proyección del vector A sobre P.

description of image

Refiriéndonos al diagrama anterior, sabemos que el valor de proyección es \ (A_ {magnitud} * cos (theta) \) (donde theta es el ángulo entre A y P). Aunque podemos seguir adelante y calcular este ángulo para obtener la proyección, es complicado. Necesitamos un enfoque más directo:

\[
A. P=A_{magnitude}*P_{magnitude}*cos(theta)\\
A.\frac{P}{P_{magnitude}}=A_{magnitude}*cos(theta)\\
\begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]

Tenga en cuenta que \ (\ begin {bmatrix} P_x / P_ {magnitud} \\ P_y / P_ {magnitud} \ end {bmatrix} \) es en realidad el vector unitario de P.

Ahora, en lugar de usar el lado derecho de la ecuación, como lo estábamos haciendo, podemos optar por el lado izquierdo y seguir llegando al mismo resultado.


Aplicación a un escenario

Antes de continuar, me gustaría aclarar la convención de nomenclatura utilizada para denotar las cuatro esquinas de ambas casillas. Esto se reflejará en el código más adelante:

naming conventions of points

Nuestro escenario es el siguiente:

projection of various lengths

Digamos que ambas cajas están orientadas a 45 ° del eje horizontal. Debemos calcular las siguientes longitudes para determinar la brecha entre las cajas.

  • Proyección de A en el eje P
  • Proyección de B en el eje P
  • Proyección de C en el eje P

Tome nota especial de las direcciones de las flechas. Mientras que la proyección de A y C en P dará un valor positivo, la proyección de B en P producirá un valor negativo ya que los vectores apuntan en direcciones opuestas. Esto se trata en la línea 98 de la implementación de AS3 a continuación:

Aquí hay una demostración usando el código anterior. Haga clic y arrastre el punto central rojo de ambos cuadros y vea los comentarios interactivos.

Para la fuente completa, revise DemoSAT1.as en la descarga de la fuente.


Los defectos

Bueno, podemos ir con la implementación anterior. Pero hay algunos problemas, permítanme señalarlos:

Primero, los vectores A y B son fijos. Entonces, cuando intercambias las posiciones de box1 y box2, la detección de colisión falla.

wrong vector selected

En segundo lugar, solo evaluamos la brecha en un eje, por lo que situaciones como la que se muestra a continuación no se evaluarán correctamente:

only one axis evaluated

Aunque la demostración anterior es defectuosa, aprendimos de ella el concepto de proyección. A continuación, vamos a mejorarlo.


Resolviendo el primer defecto

Primero que todo, necesitaremos obtener las proyecciones de esquinas mínimas y máximas (específicamente los vectores desde el origen hasta las esquinas de las cajas) en P.

projection of minimum and maximum of two boxes

El diagrama de arriba muestra la proyección de las esquinas mínima y máxima en P cuando las cajas están bien orientadas a lo largo de P.

Pero, ¿qué pasa si box1 y box2 no están orientados en consecuencia?

projection if boxes are not oriented accordingly

El diagrama de arriba muestra cuadros que no están bien orientados a lo largo de P, y sus correspondientes proyecciones min-max. En esta situación, tendremos que recorrer cada esquina de cada casilla y seleccionar las correctas según corresponda.

Ahora que tenemos las proyecciones min-max, evaluaremos si las cajas están chocando entre sí. Como?

Checking for collision

Al observar el diagrama anterior, podemos ver claramente la representación geométrica para la proyección de box1.max y box2.min sobre el eje P.

Como puede ver, cuando hay un espacio entre los dos cuadros, box2.min-box1.max será más que cero, o en otras palabras, box2.min> box1.max. Cuando se intercambian las posiciones de las cajas, box1.min> box2.max implica que hay una brecha entre ellas.

Traduciendo esta conclusión en código, obtenemos:


Codigo inicial

Echemos un vistazo a un código más detallado para resolver esto. Tenga en cuenta que el código AS3 aquí no está optimizado. Aunque es largo y descriptivo, la ventaja es que puedes ver cómo funcionan las matemáticas detrás de ellas.

En primer lugar, tenemos que preparar los vectores:

A continuación, obtenemos la proyección min-max en box1. Puedes ver un enfoque similar usado en box2:

Finalmente, evaluamos si hay una colisión en ese eje específico, P:

Aquí hay una demostración de la implementación anterior:

Puede arrastrar cualquiera de los recuadros a través de su punto medio y girarlo con las teclas R y T. El punto rojo indica la esquina máxima para un cuadro, mientras que el amarillo indica el mínimo. Si un cuadro está alineado con P, es posible que estos puntos parpadeen al arrastrar, ya que esas dos esquinas comparten las mismas características.

Echa un vistazo a la fuente completa en DemoSAT2.as en la descarga de la fuente.


Optimización

Si desea acelerar el proceso, no es necesario calcular el vector unitario de P. Por lo tanto, puede omitir una gran cantidad de costosos cálculos del teorema de Pitágoras que involucran a Math.sqrt ():

\[ \begin{bmatrix}A_x \\A_y\end{bmatrix}.
\begin{bmatrix}P_x/P_{magnitude} \\P_y/P_{magnitude}\end{bmatrix}=
A_{magnitude}*cos(theta)
\]

optimisation

El razonamiento es el siguiente (consulte el diagrama anterior para obtener una guía visual sobre las variables):

Ahora, matemáticamente, el signo de desigualdad sigue siendo el mismo si ambos lados de la desigualdad se multiplican por el mismo número, A:

Entonces, si es un vector unitario o no, en realidad no importa, el resultado es el mismo.

Tenga en cuenta que este enfoque es útil si solo está comprobando la superposición. Para encontrar la longitud de penetración exacta de box1 y box2 (que para la mayoría de los juegos probablemente necesites), aún necesitas calcular el vector unitario de P.


Resolviendo la segunda falla

Así que resolvimos el problema para un eje, pero ese no es el final. Todavía tenemos que abordar otros ejes, pero ¿cuáles?

overlappings on axes

El análisis de las cajas es bastante sencillo: comparamos dos ejes P y Q. Para confirmar una colisión, la superposición en todos los ejes debe ser cierta: si hay algún eje sin superposición, podemos concluir que no hay colisión.

¿Qué pasa si las cajas están orientadas de manera diferente?

Haga clic en el botón verde para pasar a otra página. Por lo tanto, en los ejes P, Q, R y S, solo hay un eje que no muestra superposición entre cuadros, y nuestra conclusión es que no hay colisión entre los cuadros.

Pero la pregunta es, ¿cómo decidimos qué ejes comprobar para la superposición? Bueno, tomamos las normales de los polígonos.

normals of boxes

En una forma generalizada, con dos cuadros, tendremos que revisar ocho ejes: n0, n1, n2 y n3 para cada box1 y box2. En una forma generalizada, con dos cuadros, tendremos que revisar ocho ejes: n0, n1, n2 y n3 para cada box1 y box2.

  • n0 y n2 de box1
  • n1 y n3 de box1
  • n0 y n2 de box2
  • n1 y n3 de box2

Así que no necesitamos pasar por los ocho; sólo cuatro lo harán. Y si box1 y box2 comparten la misma orientación, podemos reducir aún más para evaluar solo dos ejes.

¿Qué pasa con otros polígonos?

normals of triangles and pentagons

Desafortunadamente, para el triángulo y el pentágono de arriba no hay tal atajo, así que tendremos que ejecutar controles a lo largo de todas las normales.


Cálculo de las normales

Cada superficie tiene dos normales:

calculating normals

El diagrama de arriba muestra la normal izquierda y derecha de P. Observe los componentes conmutados del vector y el signo de cada uno.

left normals used

Para mi implementación, estoy usando una convención en el sentido de las agujas del reloj, así que uso las normales de la izquierda. A continuación se muestra un extracto de SimpleSquare.as que demuestra esto.


Nueva implementación

Estoy seguro de que puedes encontrar una manera de optimizar el siguiente código. Pero solo para que todos tengamos una idea clara de lo que está sucediendo, he escrito todo en su totalidad:

Verás que algunas de las variables no se calculan necesariamente para alcanzar el resultado. Si cualquiera de separate_P, separate_Q, separate_R y separate_S es verdadero, entonces están separados y no hay necesidad de continuar.

Esto significa que podemos guardar una buena cantidad de evaluación, solo marcando cada uno de esos booleanos después de que se hayan calculado. Requeriría volver a escribir el código, pero creo que puede trabajar en él (o revisar el bloque comentado en DemoSAT3.as).

Aquí hay una demostración de la implementación anterior. Haga clic y arrastre los cuadros a través de sus puntos intermedios, y use las teclas R y T para rotar los cuadros:


Reflexiones posteriores

Cuando se ejecuta este algoritmo, comprueba los superposiciones a través de los ejes normales. Tengo dos observaciones aquí para señalar:

  • SAT es optimista de que no habrá colisión entre polígonos. El algoritmo puede salir y concluir felizmente "sin colisión" una vez que cualquier eje no muestre superposición. Si hubo una colisión, el SAT tendrá que recorrer todos los ejes para llegar a esa conclusión; por lo tanto, cuantas más colisiones haya en realidad, peor será el rendimiento del algoritmo.
  • SAT utiliza la normal de cada uno de los bordes de los polígonos. Así que cuanto más complejos sean los polígonos, más caro será el SAT.

Detección de colisión hexágono-triángulo

Aquí hay otro fragmento de código de ejemplo para verificar una colisión entre un hexágono y un triángulo:

Para obtener el código completo, consulte DemoSAT4.as en la descarga de origen.

La demostración está abajo. La interacción es la misma que en las demostraciones anteriores: arrastre a través de los puntos centrales y use R y T para rotar.


Detección de colisión de caja-círculo

collision with circle

La colisión con un círculo puede ser una de las más simples. Debido a que su proyección es la misma en todas las direcciones (es simplemente el radio del círculo), podemos hacer lo siguiente:

Echa un vistazo a la fuente completa en DemoSAT5.as. Arrastra el círculo o la caja para verlos chocar.


Conclusión

Bueno eso es todo por ahora. Gracias por leer y deje sus comentarios con un comentario o pregunta. ¡Nos vemos en el siguiente tutorial!

Advertisement
Advertisement
Advertisement
Advertisement
Looking for something to help kick start your next project?
Envato Market has a range of items for sale to help get you started.