¿Qué técnica debería usarse para eliminar verificaciones de colisión 2d?

Question

Desde el principio, la detección de colisión se siente como si fuera un problema O (n^2).

Tiene un montón de objetos y necesita comprobar si cada objeto está colisionando 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í es ejemplo de mi programa simple que estoy trabajando:

Si usted tiene 1000 bolas entonces si se fue con la detección de colisiones ingenua que tendría 1000^2 cheques de cobro (una millón)! Esta verificación de colisión se ha convertido rápidamente en el cuello de botella en mi aplicación. I necesita para implementar una poda de fase amplia.

¿Qué técnicas se deben utilizar 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?

Answer 1

spatial hashing. http://freespace.virgin.net/hugo.elias/models/m_colide.htm

Answer 2

No utilizaría QuadTrees ni nada complicado porque siempre equilibrará y reequilibrará los árboles a medida que las bolas se mueven 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.

Lo dije en un comentario a continuación, pero creo que merece ser parte de la respuesta: Solo detecte la colisión cuando algo se mueve, por lo que solo tiene que comprobar el movimiento contra las cosas en su cuadrícula (y 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.

Answer 3

I segundo 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)