redes programar deteccion como colisiones algorithm collision-detection

algorithm - deteccion - como programar colisiones en java



Recursos de uso de técnicas para la detección de colisiones en 2D (5)

Personalmente, me encanta el trabajo de Paul Bourke .

Además, Paul Nettle solía escribir sobre el tema. Él tiene una biblioteca completa de detección de colisiones en 3D, pero puede estar más interesado en las ideas detrás de tales bibliotecas (que son muy aplicables a 2D). Para eso, vea Detección general de colisión para juegos que usan elipsoides .

¿Cuáles son en su opinión los mejores recursos (libros o páginas web) que describen algoritmos o técnicas para usar en la detección de colisiones en un entorno 2D?

Estoy ansioso por aprender diferentes técnicas para hacer juegos más sofisticados y eficientes.

El libro "Detección de colisiones en tiempo real" de Christer Ericson (ISBN: 1-55860-732-3) es un libro reciente (2005) ampliamente elogiado que debería darte algunas buenas respuestas.

Comienza con un manual básico de algunas de las matemáticas que necesitará saber, y luego va a varios tipos de volúmenes delimitadores (esferas, cuadros delimitadores alineados al eje, recuadros delimitadores orientados) comúnmente utilizados en la detección de colisiones.

El siguiente paso para la discusión son numerosos algoritmos para detectar colisiones entre varias combinaciones de primitivas, como líneas, triángulos, esferas, polígonos, planos, volúmenes de delimitación, etc.

También es importante la cobertura de algunos de los principales métodos de división espacial y organización de los objetos (jerarquías de volúmenes, árboles BSP, octrees, etc.). Esto esencialmente acelera la detección de colisiones, ya que le permite subdividir sus objetos para evitar comparaciones innecesarias entre objetos (por ejemplo, sé por mis estructuras de datos que el objeto A está demasiado lejos para golpear el objeto B, así que ni siquiera lo haré un control de distancia).

También incluye alguna cobertura de cómo verificar las colisiones entre objetos en movimiento (intervalos, etc.), pero tenga en cuenta que, aunque este es un libro bastante sólido y cubre bien el material, es para la detección de colisiones, no para la resolución o la respuesta . Por lo tanto, le ayudará a determinar si dos objetos han colisionado, pero realmente no qué hacer al respecto, es decir, cómo resolverlo. Las pruebas de intersección generalmente le darán los datos que necesita para tomar tales decisiones, pero en términos del problema general de escribir un solucionador , que usa rutinas de detección de colisión para detectar colisiones y luego decidir qué hacer con ellas, este libro no cubre eso en profundidad.

La detección de colisiones es a menudo un proceso de dos fases. Algún tipo de algoritmo de "fase amplia" para determinar si dos objetos tienen una posibilidad de superposición (para tratar de evitar n ^ 2 se compara) seguido de un algoritmo de detección de colisión de "fase estrecha", que se basa en los requisitos de geometría de su aplicación .

Sweep and Prune es un algoritmo eficiente de fase amplia bien establecido (con un puñado de variantes que pueden adaptarse o no a su aplicación) para objetos que experimentan movimientos relativamente físicos (las cosas que se mueven locamente o tienen tamaños y regiones delimitadoras diferentes pueden hacer esto inadecuado ) La biblioteca Bullet tiene una implementación 3d para referencia.

La colisión de fase estrecha a menudo puede ser tan simple como "CircleIntersectCircle". De nuevo, las bibliotecas Bullet tienen buenas implementaciones de referencia. En tierra 3D cuando se requiere una detección más precisa para objetos arbitrarios, GJK está entre la crema actual de la cosecha - nada de lo que yo sepa evitaría que se adapte a 2d (pero podría terminar más lento que el simple hecho de forzar todos tus bordes; )

Finalmente, después de que tiene detección de colisión, a menudo necesita algún tipo de respuesta de colisión. El recuadro 2d es un buen punto de partida para una solución de respuesta física.

Si sus objetos se representan como puntos en el espacio 2D, puede usar la intersección de líneas para determinar si dos objetos han colisionado. Puede usar una lógica similar para verificar si un objeto está dentro de otro objeto (y por lo tanto han colisionado incluso si alguna de sus líneas no se está cruzando). La matemática para hacer esto es bastante simple, y debería estar cubierta por cualquier libro de texto sobre geometría básica. Sin embargo, detectar si un objeto ha pasado completamente a través de un objeto puede ser un poco más complicado.