¿Cómo puedo implementar una detección de colisión 2D rápida y precisa?

11

Soy muy consciente de cómo detectar si dos o más objetos 2D chocan, pero estoy interesado en cómo decidir si se verifica una colisión. En proyectos anteriores, solo tenía que comprobar cada objeto contra cualquier otro objeto (lo sé, O (n ^ 2) nivel de estupidez) y creó un juego menos fluido.

Varios foros aclaman la grandeza de Quadtrees, B-Trees y cualquier otro tipo de árbol o estructura que se te ocurra.

¿Cuál es la estructura más eficiente para determinar si se debe verificar una colisión?

2d collision-detection data-structure Mike Cluck
fuente
1
Una cosa que quizás desee considerar es solo verificar las colisiones de los objetos que se han movido, y los únicos objetos que están cerca de usted. Mi sistema actual funciona bien (cientos de miles de objetos), y eso es todo lo que estoy haciendo.
ultifinitus
Creo que gamedev.stackexchange.com/questions/14369/… podría ayudarte mucho. originalmente estaba destinado a un algoritmo para el procesamiento en paralelo, pero creo que el mismo algoritmo también podría mejorar las aplicaciones de subproceso único.
Ali1S232
1
@ultifinitus Eso es esencialmente lo que estoy preguntando. ¿Cómo determino qué objetos están cerca sin recorrer cada objeto y verificar su posición?
Mike Cluck
Mike, puedes enviarme un correo electrónico para obtener un código específico que usé, está en c ++, o puedo darte la estructura básica, aunque puede ser bastante ambiguo y complicado debido a eso.
ultifinitus
1
No es un duplicado porque estaba preguntando qué tipo de estructura es la más adecuada para determinar si debemos molestarnos en verificar una colisión. Esa otra pregunta era sobre colisiones transparentes versus no transparentes. Sin mencionar que esta pregunta se hizo aproximadamente un año antes de la que vinculaste.
Mike Cluck

Respuestas:

12

Para un juego 2D, a menos que los objetos 2D tengan una distribución muy pesada a un lado de su mapa, una cuadrícula uniforme es casi siempre el camino a seguir. La complejidad de la memoria es sencilla (proporcional a las dimensiones de su mapa), y con una distribución razonable, tiene O (1) tiempo de búsqueda y un promedio de log (numberOfObjects / (filas * columnas)) ^ 2 pruebas de intersección hecho por celda. Puede decidir verificar solo las celdas que han tenido un objeto moviéndose en ellas, lo que hace que la geometría estática sea mucho más eficiente. Es fácil modificar una cuadrícula uniforme sobre la marcha (mucho menos doloroso que en soluciones basadas en árboles), y es más sencillo de implementar. El único momento en que diría que no lo use en un juego 2D es cuando los requisitos de memoria de una cuadrícula uniforme se vuelven demasiado grandes (digamos un simulador espacial donde los niveles son escasos pero enormes).

Darcy Rayner
fuente
¿Cómo trata esta solución con los objetos que bordean 2 o 4 celdas de la cuadrícula?
cenizas999
1
Cualquier celda en la que se superpone el objeto, se considera que está dentro, por lo que un objeto puede estar en varias celdas. La mayoría de las estructuras de datos espaciales tratarán el tema de las superposiciones de manera similar.
Darcy Rayner
Wow, eso es bastante inteligente. +1 Saludos amigo.
cenizas999
1

Si su mundo tiene una dimensión muy "larga" (llámela X), en comparación con otras, puede mantener los objetos en una lista ordenada que puede reordenar a medida que se mueven, y luego la detección de colisión significa solo verificar los objetos que solapamiento en el eje X.

Otra posibilidad es mantener listas activas / pasivas de objetos, y no molestarse con los objetos pasivos (que no se mueven en absoluto).

Si todos son objetos de tamaño mediano que son visibles para el jugador en la pantalla, todo vs todo probablemente no sea tan malo.

Aparte de eso, estoy con Darcy, una cuadrícula uniforme es buena.

MarkR
fuente