¿Cómo funciona un motor de colisión?

¿Cómo funciona exactamente un motor de colisión ?

Esta es una pregunta extremadamente amplia. ¿Qué código hace que las cosas reboten entre sí, qué código hace que el jugador camine contra una pared en lugar de atravesar la pared? ¿Cómo actualiza constantemente el código la posición de los jugadores y la posición de los objetos para mantener la gravedad y la colisión funcionando como debería?

Si no sabes qué es un motor de colisión, básicamente se usa generalmente en juegos de plataformas para hacer que el jugador golpee con fuerza las paredes y cosas por el estilo. Existe el tipo 2D y el tipo 3D, pero todos logran lo mismo: colisión.

Entonces, ¿qué hace que un motor de colisión funcione?

Hay una gran diferencia entre un motor de colisión y un motor de física. No hacen lo mismo, aunque el motor de física generalmente se basa en un motor de colisión.

El motor de colisión se divide en dos partes: detección de colisión y respuesta de colisión. Este último es generalmente parte del motor de física. Esta es la razón por la cual los motores de colisión y los motores de física generalmente se incorporan a la misma biblioteca.

La detección de colisión viene en dos formas, discreta y continua. Los motores avanzados admiten ambos, ya que tienen diferentes propiedades. En general, la detección continua de colisiones es muy costosa y solo se usa donde realmente se necesita. La mayoría de las colisiones y la física se manejan utilizando métodos discretos. En métodos discretos, los objetos terminarán penetrando entre sí, y el motor de física trabaja para separarlos. Por lo tanto, el motor no impide que un jugador camine parcialmente a través de una pared o el piso, simplemente lo repara después de detectar que el jugador está parcialmente en la pared / piso. Aquí me centraré en la detección discreta de colisiones, ya que eso es lo que tengo más experiencia implementando desde cero.

Detección de colisiones

La detección de colisiones es relativamente fácil. Cada objeto tiene una transformación y una forma (posiblemente múltiples formas). Los enfoques ingenuos harían que el motor de colisión haga un bucle O (n ^ 2) a través de todos los pares de objetos y compruebe si hay superposición entre los pares. En los enfoques más inteligentes, existen múltiples estructuras de datos espaciales (por ejemplo, para objetos estáticos frente a dinámicos), una forma delimitadora para cada objeto y subformas convexas de varias partes para cada objeto.

Las estructuras de datos espaciales incluyen cosas como KD-Trees, árboles Dynamic AABB, Octrees / Quadtrees, árboles de particiones de espacio binario, etc. Cada uno tiene sus ventajas y desventajas, por lo que algunos motores de gama alta usan más de uno. Los árboles AABB dinámicos, por ejemplo, son realmente muy rápidos y buenos para manejar muchos objetos en movimiento, mientras que un árbol KD puede ser más adecuado para la geometría de nivel estático con el que colisionan los objetos. Hay otras opciones tambien.

La fase amplia utiliza las estructuras de datos espaciales y un volumen delimitador abstracto para cada objeto. Un volumen delimitador es una forma simple que encierra todo el objeto, generalmente con el objetivo de encerrarlo de la forma más "ajustada" posible sin dejar de ser barato para realizar pruebas de colisión. Las formas delimitadoras más comunes son los cuadros delimitadores alineados por eje, los cuadros delimitadores alineados por objetos, las esferas y las cápsulas. Los AABB generalmente se consideran los más rápidos y fáciles (las esferas son más y más rápidas en algunos casos, pero muchas de esas estructuras de datos espaciales requerirían convertir la esfera en un AABB de todos modos), pero también tienden a adaptarse a muchos objetos bastante mal. Las cápsulas son populares en los motores 3D para manejar colisiones a nivel de personaje. Algunos motores usarán dos formas limitantes,

La última fase de la detección de colisión es detectar exactamente dónde se cruza la geometría. Esto generalmente implica el uso de una malla (o un polígono en 2D), aunque no siempre. El propósito de esta fase es descubrir si los objetos realmente colisionan, si se requiere un nivel de detalle fino (por ejemplo, colisión de bala en un tirador, donde desea poder ignorar los disparos que apenas fallan), y también para averiguar exactamente dónde chocan los objetos, lo que afectará la forma en que responden los objetos. Por ejemplo, si una caja está sentada en el borde de una mesa, el motor debe saber en qué puntos está empujando la mesa contra la caja; dependiendo de qué tan lejos esté la caja, la caja puede comenzar a inclinarse y caerse.

Contact Manifold Generation

Los algoritmos utilizados aquí incluyen los populares algoritmos GJK y Minkowski Portal Refinement, así como la prueba del eje de separación. Debido a que los algoritmos populares generalmente solo funcionan para formas convexas, es necesario dividir muchos objetos complejos en subobjetos convexos y hacer pruebas de colisión para cada uno individualmente. Esta es una de las razones por las que las mallas simplificadas a menudo se usan para colisiones, así como la reducción en el tiempo de procesamiento para usar menos triángulos.

Algunos de estos algoritmos no solo le dicen que los objetos han chocado con seguridad, sino también dónde chocaron: qué tan lejos se están penetrando y cuáles son los "puntos de contacto". Algunos de los algoritmos requieren pasos adicionales, como el recorte de polígonos, para obtener esta información.

Respuesta física

En este punto, se ha descubierto un contacto y hay suficiente información para que el motor de física procese el contacto. El manejo físico puede ser muy complejo. Algoritmos más simples funcionan para algunos juegos, pero incluso algo tan aparentemente sencillo como mantener estable una pila de cajas resulta ser bastante difícil y requiere mucho trabajo y trucos no obvios.

En el nivel más básico, el motor de física hará algo como esto: tomará los objetos que colisionan y su múltiple de contacto y calculará las nuevas posiciones requeridas para separar los objetos colisionados. Moverá los objetos a estas nuevas posiciones. También calculará el cambio de velocidad resultante de este empuje, combinado con los valores de restitución (rebote) y fricción. El motor de física también aplicará cualquier otra fuerza que actúe sobre los objetos, como la gravedad, para calcular las nuevas velocidades de los objetos y luego (el siguiente cuadro) sus nuevas posiciones.

La respuesta física más avanzada se complica rápidamente. El enfoque anterior se descompondrá en muchas situaciones, incluido un objeto sentado encima de otros dos. Tratar con cada par por sí solo causará "jitter" y los objetos rebotarán mucho. La técnica más básica es hacer varias iteraciones de corrección de velocidad sobre los pares de objetos que chocan. Por ejemplo, con una caja "A" encima de otras dos cajas "B" y "C", la colisión AB se manejará primero, haciendo que la caja A se incline más hacia la caja C. Luego se maneja la colisión AC, por la noche sale un poco de las casillas, pero tirando de A hacia abajo y dentro de B. Luego se realiza otra iteración, por lo que el error AB causado por la corrección de CA se resuelve ligeramente, creando un poco más de error en la respuesta de CA. Que se maneja cuando AC se procesa nuevamente. El número de iteraciones realizadas no es fijo, y no hay ningún punto en el que se vuelva "perfecto", sino más bien el número de iteraciones que deja de dar resultados significativos. 10 iteraciones es un primer intento típico, pero se requieren ajustes para determinar el mejor número para un motor en particular y las necesidades de un juego en particular.

Almacenamiento en caché de contactos

Hay otros trucos que resultan realmente útiles (más o menos necesarios) cuando se trata con muchos tipos de juegos. El almacenamiento en caché de contactos es uno de los más útiles. Con un caché de contactos, cada conjunto de objetos en colisión se guarda en una tabla de búsqueda. Cada cuadro, cuando se detecta una colisión, se consulta esta memoria caché para ver si los objetos estaban anteriormente en contacto. Si los objetos no estaban previamente en contacto, entonces se puede generar un evento de "nueva colisión". Si los objetos estuvieron previamente en contacto, la información se puede usar para proporcionar una respuesta más estable. Las entradas en el caché de contactos que no se actualizaron en un marco indican dos objetos que se separaron y se puede generar un evento de "objeto de separación". La lógica del juego a menudo tiene usos para estos eventos.

También es posible que la lógica del juego responda a nuevos eventos de colisión y los marque como ignorados. Esto es realmente útil para implementar algunas características comunes en las plataformas, como las plataformas por las que puedes saltar pero pararte. Las implementaciones ingenuas pueden ignorar las colisiones que tienen una plataforma hacia abajo-> colisión de personaje normal (indicando que la cabeza del jugador golpeó la parte inferior de la plataforma), pero sin el almacenamiento en caché de contacto, esto se romperá si la cabeza del jugador se asoma a través de la plataforma y luego comienza caer. En ese punto, el contacto normal puede terminar apuntando hacia arriba, haciendo que el jugador aparezca a través de la plataforma cuando no debería. Con el almacenamiento en caché de contactos, el motor puede observar de manera confiable la colisión inicial normal e ignorar todos los eventos de contacto adicionales hasta que la plataforma y el jugador se separen nuevamente.

Dormido

Otra técnica muy útil es marcar los objetos como "dormidos" si no están interactuando con ellos. Los objetos dormidos no reciben actualizaciones físicas, no chocan con otros objetos dormidos, y básicamente se quedan allí congelados a tiempo hasta que otro objeto no dormido choca con ellos.

El impacto es que todos los pares de objetos en colisión que están sentados allí sin hacer nada no requieren tiempo de procesamiento. Además, debido a que no hay una cantidad constante de pequeñas correcciones físicas, las pilas serán estables.

Un objeto es candidato para dormir cuando ha tenido una velocidad cercana a cero durante más de un cuadro. Tenga en cuenta que el épsilon que usa para probar esta velocidad cercana a cero probablemente será un poco más alto que el épsilon de comparación de punto flotante habitual, ya que debería esperar cierta fluctuación con los objetos apilados, y desea que pilas de objetos enteros se queden dormidos si ' permanecer "lo suficientemente cerca" del establo. El umbral, por supuesto, requerirá ajustes y experimentación.

Restricciones

La última parte importante de muchos motores de física es el solucionador de restricciones. El propósito de dicho sistema es facilitar la implementación de cosas como resortes, motores, eje de rueda, cuerpos blandos simulados, telas, cuerdas y cadenas, y a veces incluso fluidos (aunque el fluido a menudo se implementa como un sistema completamente diferente).

Incluso los conceptos básicos de la resolución de restricciones pueden ser muy intensivos en matemáticas y van más allá de mi experiencia en este tema. Recomiendo echar un vistazo a la excelente serie de artículos de Randy Gaul sobre física para obtener una explicación más detallada del tema.

El problema general: determine cuál de todas las combinaciones posibles de objetos tiene un volumen de intersección distinto de cero.

El enfoque general ingenuo es simple: para cada posible par de objetos, calcule el volumen de intersección. Esto generalmente no es práctico, ya que requiere O (n ^ 2) operaciones de intersección relativamente caras.

Por lo tanto, las implementaciones prácticas a menudo son especializadas, haciendo ciertas suposiciones para evitar la verificación de intersecciones o la reducción de su costo. La partición espacial aprovecha el hecho de que los objetos son típicamente pequeños en relación con el volumen total, y típicamente reducirán el número de comparaciones con O (n log n). Las cajas delimitadoras y las esferas delimitadoras alineadas con el eje proporcionan comprobaciones de intersección gruesas y económicas, siempre que los objetos obedezcan ciertas suposiciones de compacidad. Y así.

Un "motor de colisión" que utilicé me pareció extremadamente fácil de entender.

Básicamente, API proporcionó un tipo de objetos que tienen un método collidesWith, tal que

1. sus parámetros eran diferentes tipos de objetos que eran "elegibles" para colisión
2. devolvió verdadero o falso dependiendo de si la colisión ocurrió o no
3. había una opción que permitía elegir si todos los rectángulos delimitadores para los objetos desencadenaban un evento de colisión o solo píxeles opacos dentro de estos rectángulos (detección de nivel de píxeles)

En mi solicitud, solo invoqué periódicamente collidesWithpara averiguar si la colisión ocurrió o no.

Bastante simple, ¿no?

Quizás lo único que requirió un poco de imaginación fue cuando los rectángulos delimitadores no eran suficientes para simular la geometría de los objetos que colisionan. En este caso, uno simplemente tendría que usar varios objetos colisionables en lugar de uno.

En general, cuando descubre que el rectángulo de colisión simple no hace lo que necesita, inventa una forma de descomponer las cosas en subelementos más rectangulares para que, cuando se combinen, estos elementos simulen / aproximen el comportamiento deseado.

• A los usuarios finales simplemente no les importa cuántos objetos hay detrás de la escena. Son felices siempre y cuando el resultado final se sienta como esperaban, por ejemplo, como una casa con una cerca de patio trasero alrededor:

  

Creo que estás un poco confundido sobre lo que estás hablando, y estás hablando de algunas cosas diferentes.

la capacidad de decir que este elemento se mueve de la ubicación X a la ubicación Y se basa en la física (esto también ataca cómo se mueven y por qué se mueven)

El método que se utiliza para la detección de colisiones se determina en función de la estructura de su juego. si su juego es un gran mundo abierto, entonces debería considerar la partición del espacio (quad-tree [oct-tree para 3D], BSP, una cuadrícula tradicional o el enfoque de prueba de todo a la antigua)

La mejor manera de implementar un sistema de detección de colisión es hacerlo por pasos.

1. coloque todos los objetos en un volumen / forma delimitador genérico, y luego pruebe esos

2. si 1 pasó, repita con una repetición de volumen / forma más compleja hasta que esté listo para probar la geometría absoluta

3. pruebe la geometría absoluta. El número de veces que repite el paso 2 se determinará según la complejidad de sus formas y cuán precisas sean esas formas.

debe considerar que cada uno de estos pasos es temprano, y con el propósito de eliminar colisiones a medida que avanza, y solo volver verdadero en el paso 3 si realmente se tocan.

Entonces, para la última parte es la resolución de colisión. Esto determina lo que sucede después de que encuentra una colisión y ha demostrado que realmente es una colisión, y qué hacer al respecto. esto generalmente es manejado por la física.

el bucle tradicional se ve así:

receive input
update physics
collision detection
collision resolution
render
repeat

En el nivel de la tarjeta gráfica (donde se trata generalmente de triángulos), la idea general es dividir la escena de alguna manera para que no tenga que verificar todos los triángulos N (esto puede hacerse como un paso de preprocesamiento ), y luego averigua dónde estás en la escena y verifica solo esos 10-50 triángulos en esa partición.

Ver árboles BSP y Kd para más información. También hay otros enfoques de partición.

En primer lugar, creo que el trabajo más importante de un motor de colisión es determinar qué no es necesario verificar para colisión en una situación particular cuadro por cuadro y eliminar esos objetos de otras verificaciones.

En segundo lugar, pero también importante, verifique de manera más detallada (precisa) los objetos restantes que no fueron seleccionados en ese primer paso.

En tercer lugar, utilice los métodos más eficientes / apropiados para realizar las verificaciones.