Detección de colisiones

Detección de colisiones es el problema computacional de detectar la intersección de dos o más objetos. La detección de colisiones es un problema clásico de la geometría computacional y tiene aplicaciones en varios campos de la computación, principalmente en gráficos por computadora, juegos de computadora, simulaciones por computadora, robótica y física computacional. Los algoritmos de detección de colisiones se pueden dividir en operaciones en objetos 2D y 3D.

Resumen

Las bolas de billar se golpean unos a otros son un ejemplo clásico aplicable dentro de la ciencia de la detección de colisión.

En la simulación física, se realizan experimentos como jugar al billar. La física de las bolas de billar que rebotan se entiende bien, bajo el paraguas del movimiento de cuerpos rígidos y las colisiones elásticas. Se daría una descripción inicial de la situación, con una descripción física muy precisa de la mesa de billar y de las bolas, así como posiciones iniciales de todas las bolas. Dada una fuerza aplicada a la bola blanca (probablemente como resultado de que un jugador golpee la bola con su taco), queremos calcular las trayectorias, el movimiento preciso y los posibles lugares de descanso de todas las bolas con un programa de computadora. Un programa para simular este juego constaría de varias partes, una de las cuales se encargaría de calcular los impactos precisos entre las bolas de billar. Este ejemplo en particular también resulta estar mal condicionado: un pequeño error en cualquier cálculo provocará cambios drásticos en la posición final de las bolas de billar.

Los videojuegos tienen requisitos similares, con algunas diferencias cruciales. Si bien la simulación por computadora debe simular la física del mundo real con la mayor precisión posible, los juegos de computadora deben simular la física del mundo real de una manera aceptable, en tiempo real y de manera sólida. Se permiten compromisos, siempre que la simulación resultante satisfaga a los jugadores.

Detección de colisiones en simulación por ordenador

Los simuladores físicos difieren en la forma en que reaccionan ante una colisión. Algunos usan la suavidad del material para calcular una fuerza, que resolverá la colisión en los siguientes pasos de tiempo como es en la realidad. Debido a la baja suavidad de algunos materiales, esto requiere mucha CPU. Algunos simuladores estiman el tiempo de colisión por interpolación lineal, revierten la simulación y calculan la colisión por los métodos más abstractos de las leyes de conservación.

Algunos iteran la interpolación lineal (método de Newton) para calcular el tiempo de colisión con una precisión mucho mayor que el resto de la simulación. La detección de colisiones utiliza la coherencia de tiempo para permitir pasos de tiempo aún más finos sin aumentar mucho la demanda de la CPU, como en el control del tráfico aéreo.

Después de una colisión inelástica, pueden ocurrir estados especiales de deslizamiento y reposo y, por ejemplo, Open Dynamics Engine usa restricciones para simularlos. Las restricciones evitan la inercia y, por lo tanto, la inestabilidad. La implementación del descanso por medio de un escenario gráfico evita la deriva.

En otras palabras, los simuladores físicos suelen funcionar de dos maneras, donde la colisión se detecta a posteriori (después de que ocurra la colisión) o a priori (antes de que ocurra la colisión). ocurre). Además de la distinción a posteriori y a priori, casi todos los algoritmos modernos de detección de colisiones se dividen en una jerarquía de algoritmos. A menudo, los términos "discreto" y "continuo" se utilizan en lugar de a posteriori y a priori.

A posteriori (discreto) versus a priori (continuo)

En el caso a posteriori, la simulación física avanza un pequeño paso, luego se verifica para ver si algún objeto se cruza o se considera que se cruza. En cada paso de la simulación, se crea una lista de todos los cuerpos que se cruzan y las posiciones y trayectorias de estos objetos se "fijan" para dar cuenta de la colisión. Este método se llama a posteriori porque normalmente pierde el instante real de la colisión y solo detecta la colisión después de que realmente ha ocurrido.

En los métodos a priori, existe un algoritmo de detección de colisiones que será capaz de predecir con mucha precisión las trayectorias de los cuerpos físicos. Los instantes de colisión se calculan con gran precisión y los cuerpos físicos nunca se interpenetran realmente. Esto se llama a priori porque el algoritmo de detección de colisiones calcula los instantes de colisión antes de actualizar la configuración de los cuerpos físicos.

Los principales beneficios de los métodos a posteriori son los siguientes. En este caso, el algoritmo de detección de colisiones no necesita ser consciente de la miríada de variables físicas; se alimenta al algoritmo una lista simple de cuerpos físicos, y el programa devuelve una lista de cuerpos que se cruzan. El algoritmo de detección de colisiones no necesita comprender la fricción, las colisiones elásticas o, peor aún, las colisiones no elásticas y los cuerpos deformables. Además, los algoritmos a posteriori son en efecto una dimensión más simples que los algoritmos a priori. Un algoritmo a priori debe tratar con la variable tiempo, que está ausente en el problema a posteriori.

Por otro lado, los algoritmos a posteriori causan problemas en el "fixing" paso, donde las intersecciones (que no son físicamente correctas) deben corregirse. Además, si el paso discreto es demasiado grande, la colisión podría pasar desapercibida, dando como resultado que un objeto atraviese a otro si es lo suficientemente rápido o pequeño.

Los beneficios de los algoritmos a priori son una mayor fidelidad y estabilidad. Es difícil (pero no del todo imposible) separar la simulación física del algoritmo de detección de colisiones. Sin embargo, en todos los casos, excepto en los más simples, el problema de determinar con anticipación cuándo chocarán dos cuerpos (dados algunos datos iniciales) no tiene una solución de forma cerrada; generalmente se involucra un buscador de raíces numéricas.

Algunos objetos están en contacto en reposo, es decir, en colisión, pero sin rebotar ni interpenetrarse, como un jarrón que descansa sobre una mesa. En todos los casos, el contacto en reposo requiere un tratamiento especial: si dos objetos chocan (a posteriori) o se deslizan (a priori) y su movimiento relativo está por debajo de un umbral, la fricción se convierte en fricción estática. y ambos objetos están dispuestos en la misma rama del escenario gráfico.

Optimización

Los enfoques obvios para la detección de colisiones para varios objetos son muy lentos. La comparación de cada objeto con todos los demás funcionará, por supuesto, pero es demasiado ineficiente para usarse cuando la cantidad de objetos es grande. Comparar objetos con geometría compleja entre sí de la manera obvia, comparando cada cara con la otra cara, es en sí mismo bastante lento. Por lo tanto, se ha aplicado una investigación considerable para acelerar el problema.

Explotación de la coherencia temporal

En muchas aplicaciones, la configuración de los cuerpos físicos de un paso de tiempo al siguiente cambia muy poco. Es posible que muchos de los objetos no se muevan en absoluto. Se han diseñado algoritmos para que los cálculos realizados en un paso de tiempo anterior se puedan reutilizar en el paso de tiempo actual, lo que resulta en una finalización más rápida del cálculo.

En el nivel aproximado de detección de colisiones, el objetivo es encontrar pares de objetos que puedan intersecarse. Esos pares requerirán un análisis más profundo. Ming C. Lin en la Universidad de California, Berkeley [1], desarrolló uno de los primeros algoritmos de alto rendimiento para esto y sugirió usar cuadros delimitadores alineados con el eje para todos los cuerpos n en la escena.

Cada caja está representada por el producto de tres intervalos (es decir, una caja sería I1× × I2× × I3=[a1,b1]× × [a2,b2]× × [a3,b3]{displaystyle I_{1}times I_{2}times I_{3}=[a_{1},b_{1}times [a_{2},b_{2}]times [a_{3},b_{3}). Un algoritmo común para la detección de colisión de cajas encuadernadas es barrido y ciruela. Observa que dos de esas cajas, I1× × I2× × I3{displaystyle I_{1}times I_{2}times I_{3} y J1× × J2× × J3{displaystyle J_{1}times J_{2}times J_{3} intersecta si, y sólo si, I1{displaystyle I_{1} intersects J1{displaystyle J_{1}, I2{displaystyle I_{2} intersects J2{displaystyle J_{2} y I3{displaystyle I_{3} intersects J3{displaystyle J_{3}. Se supone que, de un paso a otro, si Ik{displaystyle I_{k} y Jk{displaystyle J_{k} intersectar, entonces es muy probable que en el paso siguiente aún intersequen. Del mismo modo, si no se intersectieron en el paso del tiempo anterior, entonces son muy probables que no continúen.

Así que reducimos el problema a la de rastrear, de marco a marco, que intervalos intersectan. Tenemos tres listas de intervalos (uno para cada eje) y todas las listas son de la misma longitud (ya que cada lista tiene longitud n{displaystyle n}, el número de cajas.) En cada lista, se permite que cada intervalo interseque todos los demás intervalos en la lista. Así que para cada lista, tendremos una n× × n{displaystyle ntimes n} matriz M=()mij){displaystyle M=(m_{ij}} de ceros y otros: mij{displaystyle # es 1 si intervalos i{displaystyle i} y j{displaystyle j} intersección, y 0 si no se intersectan.

Por nuestra suposición, la matriz M{displaystyle M} asociado a una lista de intervalos permanecerá esencialmente sin cambios de un paso a otro. Para explotar esto, la lista de intervalos se mantiene como una lista de endpoints etiquetados. Cada elemento de la lista tiene la coordinación de un punto final de un intervalo, así como un entero único que identifica ese intervalo. Luego, clasificamos la lista por coordenadas, y actualizamos la matriz M{displaystyle M} como vamos. No es tan difícil creer que este algoritmo funcionará relativamente rápido si la configuración de cajas de fijación no cambia significativamente de un paso a otro.

En el caso de cuerpos deformables como la simulación de tela, puede que no sea posible usar un algoritmo de poda por pares más específico como se explica a continuación, y un algoritmo de poda de n-cuerpo es lo mejor que puede hacerse

Si se puede colocar un límite superior en la velocidad de los cuerpos físicos en una escena, entonces los pares de objetos se pueden podar según su distancia inicial y el tamaño del paso de tiempo.

Poda por parejas

Una vez que hayamos seleccionado un par de cuerpos físicos para más investigación, necesitamos comprobar las colisiones más cuidadosamente. Sin embargo, en muchas aplicaciones, objetos individuales (si no son demasiado deformables) se describen por un conjunto de primitivos más pequeños, principalmente triángulos. Así que ahora, tenemos dos conjuntos de triángulos, S=S1,S2,...... ,Sn{displaystyle S={S_{1},S_{2},dotsS_{n}} y T=T1,T2,...... ,Tn{displaystyle T={T_{1},T_{2},dots T_{n}} (para la simplicidad, asumiremos que cada conjunto tiene el mismo número de triángulos.)

Lo obvio es revisar todos los triángulos Sj{displaystyle S_{j} contra todos los triángulos Tk{displaystyle T_{k} para las colisiones, pero esto implica n2{displaystyle n^{2} comparaciones, que es muy ineficiente. Si es posible, es deseable utilizar un algoritmo de poda para reducir el número de pares de triángulos que necesitamos comprobar.

La familia de algoritmos más utilizada es conocida como volúmenes jerárquicos método. Como paso previo, para cada objeto (en nuestro ejemplo, S{displaystyle S. y T{displaystyle T}) calcularemos una jerarquía de volúmenes atados. Entonces, en cada paso del tiempo, cuando necesitamos comprobar las colisiones entre S{displaystyle S. y T{displaystyle T}, los volúmenes jerárquicos se utilizan para reducir el número de pares de triángulos bajo consideración. Para la simplicidad, daremos un ejemplo usando esferas ligadas, aunque se ha observado que las esferas son indeseables en muchos casos.

Si E{displaystyle E} es un conjunto de triángulos, podemos precalcular una esfera atada B()E){displaystyle B(E)}. Hay muchas maneras de elegir B()E){displaystyle B(E)}, sólo suponemos que B()E){displaystyle B(E)} es una esfera que contiene completamente E{displaystyle E} y es lo más pequeño posible.

Antes de tiempo, podemos calcular B()S){displaystyle B(S)} y B()T){displaystyle B(T)}. Claramente, si estas dos esferas no se intersectan (y eso es muy fácil de probar), entonces tampoco lo hacen S{displaystyle S. y T{displaystyle T}. Esto no es mucho mejor que un n- algoritmo de poda corporal, sin embargo.

Si E=E1,E2,...... ,Em{displaystyle E={E_{1},E_{2},dots E_{m}} es un conjunto de triángulos, entonces podemos dividirlo en dos mitades L()E):=E1,E2,...... ,Em/2{displaystyle L(E):={E_{1},E_{2},dotsE_{m/2}}} y R()E):=Em/2+1,...... ,Em− − 1,Em{displaystyle R(E):={E_{m/2+1},dotsE_{m-1},E_{m}}}. Podemos hacer esto S{displaystyle S. y T{displaystyle T}, y podemos calcular (antes del tiempo) las esferas de unión B()L()S)),B()R()S)){displaystyle B(L(S)),B(R(S)} y B()L()T)),B()R()T)){displaystyle B(L(T)),B(R(T)}. La esperanza aquí es que estas esferas ligadas son mucho más pequeñas que B()S){displaystyle B(S)} y B()T){displaystyle B(T)}. Y, si, por ejemplo, B()S){displaystyle B(S)} y B()L()T)){displaystyle B(L(T)} no se intersectan, entonces no hay sentido en la comprobación de cualquier triángulo en S{displaystyle S. contra cualquier triángulo en L()T){displaystyle L(T)}.

Como precomputación, podemos tomar cada cuerpo físico (representado por un conjunto de triángulos) y descomponerlo recursivamente en un árbol binario, donde cada nodo N{displaystyle N} representa un conjunto de triángulos, y sus dos hijos representan L()N){displaystyle L(N)} y R()N){displaystyle R(N)}. En cada nodo en el árbol, podemos precomputar la esfera atada B()N){displaystyle B(N)}.

Cuando llega el momento de probar la colisión de un par de objetos, su árbol de esfera delimitadora se puede usar para eliminar muchos pares de triángulos.

Muchas variantes de los algoritmos se obtienen escogiendo algo más que una esfera para B()T){displaystyle B(T)}. Si uno elige las cajas de axis alineadas, se obtiene AABBTrees. Los árboles de caja de sujeción orientados se llaman OBBTrees. Algunos árboles son más fáciles de actualizar si el objeto subyacente cambia. Algunos árboles pueden acomodar primitivos de orden superior, tales como líneas en lugar de triángulos simples.

Detección exacta de colisiones por pares

Una vez que terminamos de podar, nos quedan varios pares de candidatos para verificar la detección exacta de colisiones.

Una observación básica es que para dos objetos convexos cualesquiera que no estén unidos, se puede encontrar un plano en el espacio de modo que un objeto se encuentre completamente en un lado de ese plano y el otro objeto se encuentre en el lado opuesto de ese plano. Esto permite el desarrollo de algoritmos de detección de colisiones muy rápidos para objetos convexos.

El trabajo temprano en esta área implica métodos de "plano separador". Dos triángulos collide esencialmente sólo cuando no pueden ser separados por un plano pasando por tres vértices. Es decir, si los triángulos son v1,v2,v3{displaystyle {v_{1},v_{2},v_{3}} y v4,v5,v6{displaystyle {v_{4},v_{5},v_{6}} donde cada vj{displaystyle v_{j} es un vector en R3{displaystyle mathbb {R} {} {}}}, entonces podemos tomar tres vértices, vi,vj,vk{displaystyle v_{i},v_{j},v_{k}, encontrar un avión pasando por los tres vértices, y comprobar si este es un plano separador. Si tal plano es un plano separador, entonces se considera que los triángulos están descompuestos. Por otro lado, si ninguno de estos aviones está separando planos, entonces los triángulos se consideran intersectados. Hay veinte aviones.

Si los triángulos son coplanares, esta prueba no es completamente exitosa. Se pueden agregar algunos planos adicionales, por ejemplo, planos que son normales a los bordes del triángulo, para solucionar el problema por completo. En otros casos, los objetos que se encuentran en una cara plana necesariamente también deben encontrarse en un ángulo en otro lugar, por lo tanto, la detección de colisión general podrá encontrar la colisión.

Desde entonces se han desarrollado mejores métodos. Hay algoritmos muy rápidos disponibles para encontrar los puntos más cercanos en la superficie de dos objetos poliédricos convexos. Los primeros trabajos de Ming C. Lin utilizaron una variación del algoritmo simplex de la programación lineal. El algoritmo de distancia Gilbert-Johnson-Keerthi ha reemplazado ese enfoque. Estos algoritmos se aproximan al tiempo constante cuando se aplican repetidamente a pares de objetos estacionarios o de movimiento lento, cuando se usan con puntos de partida de la verificación de colisión anterior.

El resultado final de todo este trabajo algorítmico es que la detección de colisiones se puede realizar de manera eficiente para miles de objetos en movimiento en tiempo real en computadoras personales y consolas de juegos típicas.

Poda a priori

Cuando la mayoría de los objetos involucrados son fijos, como es típico en los videojuegos, se pueden usar métodos a priori que usan precálculo para acelerar la ejecución.

La poda también es deseable aquí, tanto la poda de n-cuerpo como la poda por pares, pero los algoritmos deben tener en cuenta el tiempo y los tipos de movimientos utilizados en el sistema físico subyacente.

Cuando se trata de la detección exacta de colisiones por pares, esta depende en gran medida de la trayectoria, y uno casi tiene que usar un algoritmo numérico de búsqueda de raíces para calcular el instante del impacto.

Como ejemplo, considerar dos triángulos que se mueven en el tiempo v1()t),v2()t),v3()t){displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}} y v4()t),v5()t),v6()t){displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}. En cualquier momento, los dos triángulos se pueden comprobar para la intersección utilizando los veinte planos mencionados anteriormente. Sin embargo, podemos hacerlo mejor, ya que estos veinte aviones pueden ser rastreados a tiempo. Si P()u,v,w){displaystyle P(u,v,w)} es el avión pasando por puntos u,v,w{displaystyle u,v,w} dentro R3{displaystyle mathbb {R} {} {}}} entonces hay veinte aviones P()vi()t),vj()t),vk()t)){displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t)}} para rastrear. Cada plano necesita ser rastreado contra tres vértices, esto da sesenta valores a seguir. Usando un buscador de raíz en estas sesenta funciones produce los tiempos exactos de colisión para los dos triángulos dados y las dos trayectorias dadas. Observamos aquí que si se supone que las trayectorias de los vértices son polinomios lineales en t{displaystyle t} entonces las sesenta funciones finales son de hecho polinomios cúbicos, y en este caso excepcional, es posible localizar el tiempo exacto de colisión utilizando la fórmula para las raíces del cúbico. Algunos analistas numéricos sugieren que el uso de la fórmula para las raíces del cúbico no es tan numéricamente estable como el uso de un buscador de raíces para los polinomios.

División espacial

Los algoritmos alternativos se agrupan bajo el paraguas de partición espacial, que incluye octrees, partición de espacio binario (o árboles BSP) y otros enfoques similares. Si uno divide el espacio en varias celdas simples, y si se puede demostrar que dos objetos no están en la misma celda, entonces no es necesario verificar la intersección. Dado que los árboles BSP se pueden precalcular, ese enfoque es muy adecuado para manejar paredes y obstáculos fijos en los juegos. Estos algoritmos son generalmente más antiguos que los algoritmos descritos anteriormente.

Cuadros delimitadores

Los cuadros delimitadores (o volúmenes delimitadores) suelen ser un rectángulo 2D o un paralelepípedo 3D, pero son posibles otras formas. Un cuadro delimitador en un videojuego a veces se denomina Hitbox. Se han probado el diamante delimitador, el paralelogramo delimitador mínimo, el casco convexo, el círculo delimitador o bola delimitadora y la elipse delimitadora, pero los cuadros delimitadores siguen siendo los más populares debido a su simplicidad. Los cuadros delimitadores se utilizan normalmente en la etapa temprana (de poda) de la detección de colisiones, por lo que solo es necesario comparar en detalle los objetos con cuadros delimitadores superpuestos.

Segmentos del centroide del triángulo

Un objeto de malla triangular se usa comúnmente en el modelado de cuerpos en 3D. Normalmente, la función de colisión es una intercepción de triángulo a triángulo o una forma delimitadora asociada con la malla. El centroide de un triángulo es una ubicación del centro de masa tal que se equilibraría en la punta de un lápiz. La simulación solo necesita agregar una dimensión de centroide a los parámetros físicos. Dados los puntos del centroide tanto en el objeto como en el objetivo, es posible definir el segmento de línea que conecta estos dos puntos.

El vector de posición del centroide de un triángulo es el promedio de los vectores de posición de sus vértices. Así que si sus vértices tienen coordenadas cartesianas ()x1,Sí.1,z1){displaystyle (x_{1},y_{1},z_{1}}, ()x2,Sí.2,z2){displaystyle (x_{2},y_{2},z_{2}} y ()x3,Sí.3,z3){displaystyle (x_{3},y_{3},z_{3}} entonces el centroide es ()()x1+x2+x3)3,()Sí.1+Sí.2+Sí.3)3,()z1+z2+z3)3){fnMicrosoft Sans Serif} {fnMicroc {fnMicroc {fn0}}{3}}}{3}}}}}{fc {c} {fn0}}}{3}}}}{3}}}{3}}}{3}}{1}}}}{3}}}}{3}}} {}}}}}}}}}}}}}}} {}}}}}}}}}}}}} {}}}} {}}}}}}} {}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}} {}}}}} {} {}}}} {}}}}}}} {}}}}}}}}}}}}}}}}} {}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}.

Aquí está la función para una distancia de segmento de línea entre dos puntos 3D. distance=()z2− − z1)2+()x2− − x1)2+()Sí.2− − Sí.1)2{displaystyle mathrm {distance} ={2}+(x_{1})^{2}}}}

Aquí, la longitud/distancia del segmento es un "golpe" criterio tamaño del segmento. A medida que los objetos se acercan, la longitud disminuye hasta el valor umbral. Una esfera triangular se convierte en la prueba de geometría efectiva. Una esfera centrada en el baricentro se puede dimensionar para abarcar todos los vértices del triángulo.

Videojuegos

Los videojuegos tienen que dividir su muy limitado tiempo de cómputo entre varias tareas. A pesar de este límite de recursos y del uso de algoritmos de detección de colisiones relativamente primitivos, los programadores han podido crear sistemas creíbles, aunque inexactos, para usar en juegos.

Durante mucho tiempo, los videojuegos tenían un número muy limitado de objetos para tratar, por lo que comprobar todos los pares no era un problema. En los juegos bidimensionales, en algunos casos, el hardware pudo detectar e informar de manera eficiente los píxeles superpuestos entre los sprites en la pantalla. En otros casos, simplemente colocar mosaicos en la pantalla y vincular cada sprite en los mosaicos que se superponen proporciona suficiente poda, y para las comprobaciones por pares, se utilizan rectángulos o círculos delimitadores llamados hitboxes y se consideran suficientemente precisos.

Juegos tridimensionales han utilizado métodos de partición espacial para n{displaystyle n}- la poda corporal, y durante mucho tiempo usó una o varias esferas por objeto 3D real para cheques pares. Exact checks son muy raros, excepto en juegos que intentan simular la realidad de cerca. Incluso entonces, las comprobaciones exactas no se utilizan necesariamente en todos los casos.

Debido a que los juegos no necesitan imitar la física real, la estabilidad no es un gran problema. Casi todos los juegos usan detección de colisiones a posteriori, y las colisiones a menudo se resuelven usando reglas muy simples. Por ejemplo, si un personaje se incrusta en una pared, es posible que simplemente se mueva de regreso a su última ubicación buena conocida. Algunos juegos calcularán la distancia que el personaje puede moverse antes de incrustarse en una pared y solo les permitirán moverse esa distancia.

En muchos casos de videojuegos, la aproximación de los personajes por un punto es suficiente para detectar colisiones con el entorno. En este caso, los árboles de partición de espacios binarios proporcionan un algoritmo viable, eficiente y simple para verificar si un punto está incrustado en el escenario o no. Dicha estructura de datos también se puede usar para manejar la "posición de reposo" situación con gracia cuando un personaje está corriendo por el suelo. Las colisiones entre personajes y las colisiones con proyectiles y peligros se tratan por separado.

Un simulador robusto es aquel que reaccionará a cualquier entrada de manera razonable. Por ejemplo, si imaginamos un videojuego de carreras de autos de alta velocidad, de un paso de simulación al siguiente, es concebible que los autos avancen una distancia considerable a lo largo de la pista de carreras. Si hay un obstáculo poco profundo en la pista (como una pared de ladrillos), no es del todo improbable que el automóvil lo salte por completo, y esto es muy indeseable. En otros casos, la "fijación" que requieren los algoritmos a posteriori no se implementa correctamente, lo que genera errores que pueden atrapar a los personajes en las paredes o permitirles pasar a través de ellas y caer en un vacío sin fin donde puede haber o no un pozo sin fondo mortal, a veces denominado 'infierno negro', 'infierno azul' o 'infierno verde', según el color predominante. Estas son las características de un sistema fallido de detección de colisiones y simulación física. Big Rigs: Over the Road Racing es un ejemplo infame de un juego con un sistema de detección de colisiones defectuoso o posiblemente faltante.

Cuadro de impacto

Un cuadro de diálogo depurado Cabezas de engranaje controlando la caja de un objeto

La caja de un Cabezas de engranaje juguete, controlado por la pantalla anterior

Un hitbox es una forma invisible comúnmente utilizada en los videojuegos para la detección de colisiones en tiempo real; es un tipo de cuadro delimitador. Suele ser un rectángulo (en juegos 2D) o un cuboide (en 3D) que se adjunta y sigue un punto en un objeto visible (como un modelo o un sprite). Las formas circulares o esferoidales también son comunes, aunque todavía se les suele llamar "cajas". Es común que los objetos animados tengan hitboxes adjuntos a cada parte móvil para garantizar la precisión durante el movimiento.

Los hitboxes se utilizan para detectar "unidireccionales" colisiones, como que un personaje sea golpeado por un puñetazo o una bala. No son adecuados para la detección de colisiones con retroalimentación (por ejemplo, chocar contra una pared) debido a la dificultad que experimentan tanto los humanos como la IA para administrar las ubicaciones en constante cambio de un hitbox; este tipo de colisiones generalmente se manejan con cuadros delimitadores alineados con ejes mucho más simples. Los jugadores pueden usar el término "hitbox" para referirse a este tipo de interacciones independientemente.

Un hurtbox es un término relacionado que se usa para diferenciar "objeto que inflige daño" de "objeto que recibe daño". Por ejemplo, un ataque solo puede aterrizar si el hitbox alrededor del puñetazo de un atacante se conecta con uno de los hurtboxes del oponente en su cuerpo, mientras que la colisión de hitboxes opuestos puede resultar en que los jugadores intercambien o cancelen golpes, y oponerse. hurtboxes no interactúan entre sí. El término no está estandarizado en toda la industria; algunos juegos invierten sus definiciones de "hitbox" y "hurtbox", mientras que otros solo usan "hitbox" para ambos lados.