data structures - ¿Qué técnica debería usarse para eliminar las verificaciones de colisión 2d?
data-structures collision-detection (3)
Desde el principio, la detección de colisión se siente como un problema O (n ^ 2).
Usted tiene un montón de objetos y necesita verificar si cada objeto choca con cualquiera de los otros objetos. Sin embargo, sé que es tremendamente ineficaz verificar cada objeto contra todos los demás objetos. ¿Por qué hacer un chequeo de colisión relativamente caro entre dos bolas si ni siquiera están cerca unas de otras?
Aquí hay un ejemplo de mi sencillo programa en el que estoy trabajando:
Si tienes 1000 bolas, entonces si fueras con la detección de colisiones ingenua tendrías 1000 ^ 2 controles de colección (¡un millón)! Esta verificación de colisión se ha convertido rápidamente en el cuello de botella en mi aplicación. Necesito implementar una poda de fase amplia.
¿Qué técnicas deberían usarse para eliminar las verificaciones de colisión cuando se trabaja con 2d - objetos circulares? He leído sobre QuadTrees, BSP, hashing espacial, etc. pero es difícil determinar qué método es el más adecuado para este caso de uso.
¿Alguien tiene algún conocimiento sobre lo que podría funcionar mejor?
hashing espacial http://freespace.virgin.net/hugo.elias/models/m_colide.htm
No utilizaría QuadTrees ni nada complicado porque constantemente equilibrarás y volverás a equilibrar los árboles a medida que las bolas se muevan entre ellos. Probablemente sería más eficiente tener una cuadrícula: cada vez que mueves una bola, puedes calcular en qué celda de cuadrícula está y tirarla allí si se cambia. Y cada vez que necesite realizar una prueba de colisión, puede verificar las bolas cuyo centro se encuentre en su cuadrícula, o en las adyacentes si está lo suficientemente cerca del borde.
Puede experimentar con el tamaño de la cuadrícula para encontrar el óptimo. Puede encontrar que depende de la cantidad de bolas que tenga.
Dije esto en un comentario más abajo, pero creo que merece ser parte de la respuesta: solo detecte la colisión cuando algo se mueve, por lo que solo tiene que verificar el movimiento contra las cosas en su cuadrícula (y las adyacentes como se mencionó anteriormente ) De esa manera, si obtienes un montón de cosas en el fondo que no se mueven, muy pronto esos objetos nunca se verifican en busca de colisión, porque nada se está moviendo dentro de su cuadrícula ni se está moviendo dentro o fuera de su cuadrícula.
Secundo el método Grid. Una simulación 2D de bolas no se beneficiará de QuadTrees (que generalmente se usan cuando tienes geometría compleja como personajes y edificios) o BSP (que debes elegir si tienes una dispersión / concentración de objetos muy desigual, como con alta concentración áreas y áreas de baja concentración, en un juego de estrategia o multijugador)