algorithm - ¿Métodos de detección de colisiones de fase amplia?
physics collision-detection (10)
Estoy construyendo un motor de física 2D y quiero agregar detección de colisiones de fase amplia, aunque solo conozco 2 o 3 tipos:
- Comprueba todo contra todo lo demás (O (n ^ 2) complejidad)
- Barrer y podar (ordenar y barrer)
- algo sobre la partición del espacio binario (no estoy seguro de cómo hacerlo)
Pero seguramente hay más opciones ¿verdad? ¿Qué son? ¿Y puede proporcionarse una descripción básica de cada uno o enlaces a descripciones?
He visto this pero estoy pidiendo una lista de algoritmos disponibles, no el mejor para mis necesidades.
En este caso, la "Detección de colisión de fase amplia" es un método utilizado por los motores físicos para determinar qué cuerpos en su simulación están lo suficientemente cerca como para justificar una investigación adicional y posiblemente una resolución de colisión.
Acabo de encontrar una solución que no depende del tamaño de la cuadrícula y es probable que sea O (nlogn) (que es la óptima cuando no hay colisiones) aunque peor en O (n n logn) (cuando todo choca).
También lo implementé y lo probé, aquí está el enlace a la source . Pero no lo he comparado con la solución de fuerza bruta.
Una descripción de cómo funciona: (Estoy buscando colisiones de rectángulos)
en el eje x, ordeno los rectángulos de acuerdo a su borde derecho (O (nlogn))
para cada rect en la lista ordenada tomo el borde izquierdo y hago una búsqueda binaria hasta que encuentre el borde derecho a la izquierda del borde izquierdo e inserto estos rectángulos entre estos índices en un conjunto posible de colisión_de_X_ (estos son n rectángulos, logn búsqueda binaria, n inserta el conjunto en O (log n) por inserción)
en el eje y hago lo mismo
en cada uno de los conjuntos ahora tengo posibles colisiones en x (en un conjunto) y en y (int en el otro), intersecto estos conjuntos y ahora tengo las colisiones tanto en el eje x como en el eje y (eso significa que tomo el elementos comunes) (O (n))
perdón por la mala descripción, espero que lo entiendas mejor de la fuente, también un ejemplo ilustrado aquí: image
El mejor enfoque depende del uso específico, pero la conclusión es que desea subdividir su espacio del mundo de manera tal que (a) cada cuerpo esté exactamente en una subdivisión, (b) cada subdivisión sea lo suficientemente grande como para que un cuerpo en una subdivisión particular solo puede colisionar con cuerpos en esa misma subdivisión o una subdivisión adyacente, y (c) el número de cuerpos en una subdivisión particular es lo más pequeño posible.
La forma de hacerlo depende de cuántos cuerpos tenga, cómo se mueven, cuáles son sus requisitos de rendimiento y cuánto tiempo desea dedicar a su motor. Si está hablando de cuerpos que se mueven en un espacio mayormente abierto, la técnica más simple sería dividir el mundo en una cuadrícula donde cada celda sea más grande que su objeto más grande, y rastrear la lista de objetos en cada celda. Si estás construyendo algo en la escala de un clásico juego de arcade, esta solución puede ser suficiente.
Si estás tratando con cuerpos que se mueven en un mundo abierto más grande, una simple cuadrícula se volverá abrumadora bastante rápido, y probablemente querrás algún tipo de estructura basada en árboles como los quadtrees, como sugiere Arriu.
Si está hablando de mover cuerpos dentro de espacios delimitados en lugar de espacios abiertos, entonces puede considerar un árbol BSP ; el árbol divide el mundo en "espacio en el que se puede caminar" y en "paredes", y el corte de un cuerpo en el árbol determina si está en una posición legal. Dependiendo de la geometría del mundo, también puede usar un BSP para la detección de colisiones de varias fases entre cuerpos en el mundo.
Otra opción para los cuerpos que se mueven en el espacio delimitado sería un motor de portal; Si su mundo puede constar de regiones poligonales convexas donde cada lado del polígono es una pared sólida o un ''portal'' a otro espacio cóncavo, puede determinar fácilmente si un cuerpo está dentro de una región con una prueba de punto en polígono y simplifique la detección de colisiones solo mirando los cuerpos en la misma región o regiones conectadas.
He usado un quad-tree en un proyecto más grande, lo que es bueno para los objetos de juego que no se mueven mucho (menos remociones y reinserciones). El mismo principio se aplica a los octetos.
La Idea básica es que crea una estructura de árbol recursiva que almacena 4 (para quad) u 8 (oct) objetos secundarios del mismo tipo que la raíz del árbol. Cada nodo en el árbol representa una sección del espacio cartesiano, por ejemplo, -100 -> +100 en cada eje aplicable. cada niño representa el mismo espacio, pero subdividido por la mitad (un hijo inmediato del ejemplo representaría, por ejemplo, -100-> 0 en el eje X, y -100-> 0 en el eje Y).
Imagina un cuadrado, o plano, con un conjunto dado de dimensiones. Ahora dibuja una línea a través del centro en cada eje, dividiendo ese plano en 4 planos más pequeños. Ahora toma uno de ellos y vuelve a hacerlo, y otra vez, hasta que alcances un punto en el que el tamaño del segmento del avión sea aproximadamente el tamaño de un objeto de juego. Ahora tienes tu árbol. Sólo los objetos que ocupan el mismo plano, posiblemente pueden chocar. Cuando haya determinado qué objetos pueden colisionar, generará pares de posibles colisiones a partir de ellos. En esta etapa, Broadphase está completo, y puede pasar a la detección de colisión de fase estrecha, que es donde están sus cálculos más precisos y costosos.
El propósito de Broadphase, es utilizar cálculos económicos para generar posibles colisiones y eliminar los contactos que no pueden ocurrir, reduciendo así el trabajo que debe realizar su algoritmo de fase estrecha, haciendo que todo su algoritmo de detección de colisiones sea más eficiente.
Entonces, antes de seguir adelante e intentar implementar tal algoritmo, como usted:
¿Cuántos objetos hay en mi juego? Si hay muchos, probablemente necesito una banda ancha. Si no, entonces la Nnarrowphase debería ser suficiente. Además, ¿estoy tratando con muchos objetos en movimiento?
Las estructuras de los árboles generalmente se ralentizan al mover objetos, ya que pueden cambiar su posición en el árbol a lo largo del tiempo, simplemente moviéndose. Esto requiere que los objetos se eliminen y se vuelvan a insertar en cada fotograma (potencialmente), que es inferior a Ideal.
Si este es el caso, estaría mejor con Sweep and Prune, que mantiene el mínimo / máximo de las extensiones de las formas en su mundo. Los objetos no necesitan ser reinsertados, pero los montones se deben reordenar en cada cuadro, pensamos que esto generalmente es más rápido que un árbol ancho, transversal con remociones y reinserciones.
Dependiendo de su experiencia de codificación, uno puede ser más complicado de codificar sobre otro. Personalmente, he descubierto que los árboles son más intuitivos para codificar, pero menos eficientes y más propensos a errores, ya que plantean otros problemas, como qué hacer si tiene un objeto que se encuentra directamente sobre un eje o el centro. del nodo raíz. Esto se puede resolver mediante el uso de árboles sueltos, que tienen cierta superposición espacial, de modo que siempre se prioriza un nodo secundario sobre otros cuando ocurre un caso así.
Me gustaría recomendar la referencia introductoria a la física de juegos de Ian Millington, Game Physics Engine Development . Tiene una gran sección sobre detección de colisiones de fase amplia con código de muestra.
Recomiendo la partición quadtree . Es bastante simple y funciona muy bien. Aquí hay una demo Flash de la detección de colisiones de fuerza bruta frente a la detección de colisiones de quadtree. (Puede indicarle que muestre la estructura de quadtree). ¿Notó que la detección de colisiones de quadtree es solo el 3% de la fuerza bruta en esa demostración?
Además, si se toma en serio su motor, le recomiendo que busque la detección de colisiones en tiempo real . No es caro y es un gran libro que cubre todo lo que siempre querría saber. (Incluye detección de colisiones basada en GPU).
Si el espacio dentro del cual se mueven tus objetos está limitado, entonces podrías usar una cuadrícula para subdividir tus objetos. Coloque cada objeto en cada celda de la cuadrícula que cubre el objeto (total o parcialmente). Para verificar si el objeto A choca con cualquier otro objeto, determine qué celdas cubre el objeto A, luego obtenga la lista de objetos únicos en esas celdas y, finalmente, pruebe el objeto A contra cada objeto único. Este enfoque funciona mejor si la mayoría de los objetos suelen estar contenidos en una sola celda de cuadrícula.
Si su espacio no está limitado, entonces necesitará implementar algún tipo de cuadrícula dinámica que pueda crecer según la demanda en cada una de las cuatro direcciones (en 2D).
La ventaja de este enfoque sobre un algoritmo más adaptativo (es decir, BSP, Quadtree, Circletree) es que se puede acceder a las celdas en tiempo O (1) (es decir, tiempo constante) en lugar de tiempo O (log N) (es decir, tiempo logarítmico). Sin embargo, estos últimos algoritmos son capaces de adaptarse a una gran variabilidad en la densidad de los objetos. El enfoque de cuadrícula funciona mejor cuando la densidad del objeto es bastante constante en todo el espacio.
Todos los algoritmos de aceleración dependen del uso de una prueba económica para descartar rápidamente los objetos (o grupos de objetos) y, por lo tanto, reducir el número de pruebas costosas que debe realizar. Veo los algoritmos en categorías, cada una de las cuales tiene muchas variaciones.
Particionamiento espacial. Separe el espacio y excluya a los candidatos que se encuentran en diferentes regiones. Por ejemplo, BSP, grillas, octetos, etc.
Particionamiento de objetos. Similar al # 1, pero el agrupamiento se enfoca en los objetos en sí mismos más que en el espacio en el que residen. Por ejemplo, jerarquías de volumen de límites.
Métodos de clasificación y barrido. Ponga los objetos en orden espacialmente y descarte las colisiones entre los que no son adyacentes.
1 y 2 son a menudo jerárquicos, y se repiten en cada partición según sea necesario. Con 3, opcionalmente puede iterar a lo largo de diferentes dimensiones.
Las concesiones dependen mucho de la geometría de la escena. ¿Los objetos se agrupan o están distribuidos de manera uniforme o dispersa? ¿Son todos del mismo tamaño o hay grandes variaciones en el tamaño? ¿Es la escena dinámica? ¿Se puede permitir mucho tiempo de preprocesamiento?
Las pruebas "baratas" están en realidad a lo largo de un espectro de realmente barato a un poco caro. Elegir el mejor algoritmo significa minimizar la relación entre el costo de las pruebas de bajo costo y la reducción en la cantidad de pruebas costosas. Más allá de las preocupaciones algorítmicas, te metes en la optimización, como preocuparte por la localidad de caché.
Una alternativa a QuadTrees o BSPTrees son SphereTrees (CircleTrees en 2D, la implementación sería más o menos la misma). La ventaja que tiene SphereTrees es que manejan muy bien grandes cargas de objetos dinámicos. Si sus objetos se mueven constantemente, BSPTrees y QuadTrees son mucho más lentos en sus actualizaciones de lo que lo sería un Árbol Esfera / Círculo.
Si tiene una buena combinación de objetos estáticos y dinámicos, una solución razonablemente buena es usar un QuadTree / BSPTree para las estadísticas y un árbol de esfera / ciclo para los objetos dinámicos. Solo recuerda que para cualquier objeto dado, deberías verificarlo contra ambos árboles.
Una alternativa son las cuadrículas simples, por ejemplo 20x20 o 100x100 (depende de su mundo y el tamaño de la memoria). La implementación es más simple que una estructura recursiva, como quad / bsp-trees (o árboles de esferas).
Los objetos que cruzan los bordes de las celdas son un poco más simples en este caso, y no degeneran tanto como podría hacer una implementación ingenua de un bsp / quad / oct-tree.
Usando esa (u otras técnicas), deberías poder eliminar rápidamente muchos pares y obtener un conjunto de colisiones potenciales que requieren una mayor investigación.