algorithm - programar - Detección de colisiones de una gran cantidad de círculos

deteccion de colisiones en javascript

Question

¿Cuál es la mejor manera de verificar la colisión de una gran cantidad de círculos?
Es muy fácil detectar la colisión entre dos círculos, pero si comprobamos cada combinación, entonces es O (n ² ), que definitivamente no es una solución óptima.

Podemos suponer que el objeto circular tiene las siguientes propiedades:

• Coordenadas
• Radio
• Velocidad
• Dirección

La velocidad es constante, pero la dirección puede cambiar.

He encontrado dos soluciones, pero tal vez hay algunas soluciones mejores.

Solución 1
Divide todo el espacio en cuadrados superpuestos y busca colisiones solo con círculos que estén en el mismo cuadrado. Los cuadrados deben superponerse para que no haya un problema cuando un círculo se mueve de un cuadrado a otro.

Solución 2
Al principio, las distancias entre cada par de círculos deben calcularse.
Si la distancia es pequeña, estos pares se almacenan en alguna lista, y debemos verificar la colisión en cada actualización.
Si la distancia es grande, almacenamos y después de esa actualización puede haber una colisión (se puede calcular porque conocemos la distancia y las velocitidades). Necesita ser almacenado en algún tipo de cola de prioridad. Después del número de actualizaciones calculado previamente, la distancia debe verificarse nuevamente y luego hacemos el mismo procedimiento: colóquelo en la lista o de nuevo en la cola de prioridad.

Respuestas a las preguntas de Mark Byers

1. ¿Es para un juego?
   Es para simulación, pero también se puede tratar como un juego
2. ¿Desea recalcular la nueva posición cada n milisegundos y también comprueba si hay colisiones en este momento?
   Sí, el tiempo entre las actualizaciones es constante.
3. ¿Desea encontrar la hora en que ocurre la primera / cada colisión?
   No, quiero encontrar cada colisión y hacer ''algo'' cuando ocurra.
4. ¿Qué tan importante es la precisión?
   Depende de a qué te refieres con precisión. Necesito detectar todas las colisiones.
5. ¿Es un gran problema si los círculos muy pequeños y rápidos se pueden pasar uno al otro ocasionalmente?
   Se puede suponer que la velocidad es tan pequeña que no sucederá.

Answer 1

Divida su espacio en regiones y mantenga una lista de los círculos centrados en cada región.

Incluso si usa un esquema muy simple, como colocar todos los círculos en una lista, ordenados por centre.x, entonces puede acelerar las cosas masivamente. Para probar un círculo dado, solo necesitas probarlo contra los círculos a cada lado de la lista, saliendo hasta que llegues a uno que tenga una coordenada x a más de un radio de distancia.

Answer 2

Existen estructuras de datos de " índice espacial " para almacenar sus círculos para una comparación rápida más adelante; Quadtree, r-tree y kd-tree son ejemplos.

La solución 1 parece ser un índice espacial, y la solución 2 se beneficiaría de un índice espacial cada vez que vuelva a calcular sus pares.

Para complicar las cosas, tus objetos se están moviendo, tienen velocidad.

Es normal usar índices espaciales para objetos en juegos y simulaciones, pero principalmente para objetos estacionarios, y típicamente objetos que no reaccionan a una colisión moviéndose.

Es normal en los juegos y tal que se compute todo a intervalos de tiempo establecidos (discretos), por lo que es posible que dos objetos se atraviesen pero no se noten porque se movieron tan rápido. Muchos juegos en realidad ni siquiera evalúan las colisiones en estricto orden cronológico. Tienen un índice espacial para objetos estacionarios, por ejemplo, paredes, y listas para todos los objetos en movimiento que comprueban exhaustivamente (aunque con controles discretos y discretos, como describí).

La detección precisa de colisiones continuas y el lugar donde los objetos reaccionan a las colisiones en las simulaciones suele ser mucho más exigente.

El enfoque de los pares que usted delineó suena prometedor. Puede mantener los pares ordenados por la siguiente colisión, y reinsertarlos cuando hayan colisionado en las nuevas posiciones apropiadas. Solo tiene que ordenar la nueva lista de colisiones generada (O (n lg n)) para los dos objetos y luego fusionar dos listas (las nuevas colisiones para cada objeto y la lista existente de colisiones; insertar las nuevas colisiones, eliminarlas colisiones obsoletas que enumeraban los dos objetos que colisionaron) que es O (n).

Otra solución a esto es adaptar su índice espacial para almacenar los objetos no estrictamente en un sector, sino en cada uno que haya pasado desde el último cálculo, y hacer las cosas discretamente. Esto significa almacenar objetos que se mueven rápidamente en su estructura espacial, y deberá optimizarlo para este caso.

Recuerde que las listas vinculadas o las listas de punteros son muy malas para almacenar en caché los procesadores modernos. Yo recomendaría que almacene copias de sus círculos, sus propiedades importantes para la detección de colisiones en cualquier caso, en una matriz (memoria secuencial) en cada sector de cualquier índice espacial, o en los pares que describió anteriormente.

Como dice Mark en los comentarios, podría ser bastante simple paralelizar los cálculos.

Answer 3

La respuesta más eficiente dependerá en cierta medida de la densidad de los círculos. Si la densidad es baja, colocar la cuadrícula de baja resolución sobre el mapa y marcar los elementos de la cuadrícula que contienen un círculo será probablemente el más eficiente. Esto llevará aproximadamente O(N*m*k) por actualización, donde N es el número total de círculos, m es el número promedio de círculos por punto de cuadrícula k es el número promedio de puntos de cuadrícula cubiertos por un círculo. Si un círculo mueve más de un punto de la cuadrícula por turno, entonces debe modificar m para incluir el número de puntos de cuadrícula barridos.

Por otro lado, si la densidad es extremadamente alta, es mejor que intentes un enfoque de caminar con gráficos. Deje que cada círculo contenga todos los vecinos dentro de una distancia R ( R > r_i para cada radio de círculo r_i ). Luego, si te mueves, consultas todos los círculos en la dirección "adelante" para los vecinos que tienen y agarran cualquier que esté dentro de D; luego, se olvidan todos los que están hacia atrás, que ahora están más lejos que D. Ahora, una actualización completa tomará O(N*n^2) donde n es el número promedio de círculos dentro de un radio R Para algo así como un enrejado hexagonal estrechamente espaciado, esto le dará mejores resultados que el método de cuadrícula anterior.

Answer 4

Podría hacer una versión 2D de un "árbol de esfera" que es un caso especial (y realmente fácil de implementar) del "índice espacial" que Will sugirió. La idea es "combinar" círculos en un círculo "contenedor" hasta que tengas un solo círculo que "contenga" la "gran cantidad de círculos".

Solo para indicar la simplicidad de calcular un "círculo que contiene" (parte superior de mi cabeza): 1) Agregue las ubicaciones centrales de los dos círculos (como vectores) y escale por 1/2, ese es el centro del círculo 2) Reste las ubicaciones centrales de los dos círculos (como vectores), agregue los radios y escale por 1/2, ese es el radio del círculo que lo contiene

Answer 5

Una posible técnica es usar la triangulación de Delaunay en el centro de tus círculos.

considere el centro de cada círculo y aplique la triangulación delaunay. esto tesselará tu superficie en triángulos. esto le permite construir un gráfico donde cada nodo almacena el centro de un triángulo, y cada borde se conecta con el centro de un círculo vecino. la teselación operada arriba limitará el número de vecinos a un valor razonable (6 vecinos en promedio)

ahora, cuando se mueve un círculo, tienes un conjunto limitado de círculos para considerar para la colisión. luego debe aplicar la teselación nuevamente al conjunto de círculos que se ven afectados por el movimiento, pero esta operación involucra solo un subconjunto muy pequeño de círculos (los vecinos del círculo móvil y algunos vecinos de los vecinos)

la parte crítica es la primera teselación, que tomará algún tiempo para realizarse, las teselaciones posteriores no son un problema. y, por supuesto, necesita una implementación eficiente de un gráfico en términos de tiempo y espacio ...

Answer 6

Una sugerencia: no soy un desarrollador de juegos

¿Por qué no precalcular cuándo ocurrirán las colisiones?

como usted especifique

Podemos suponer que el objeto circular tiene las siguientes propiedades:

-Coordina

-Radio

-Velocidad

-Dirección

La velocidad es constante, pero la dirección puede cambiar.

Luego, a medida que cambia la dirección de un objeto, vuelva a calcular los pares afectados. Este método es efectivo si las instrucciones no cambian con demasiada frecuencia.

Answer 7

Como Will mencionó en su respuesta, los árboles de partición espacial son la solución común a este problema. Sin embargo, esos algoritmos a veces requieren algunos ajustes para manejar los objetos en movimiento de manera eficiente. Deberá usar una regla de ajuste de cubeta suelta para que la mayoría de los pasos de movimiento no requieran que un objeto cambie los cubos.

He visto su "solución 1" usada anteriormente para este problema y se la conoce como "hash de colisión". Puede funcionar bien si el espacio con el que se trata es lo suficientemente pequeño como para ser manejable y usted espera que sus objetos estén al menos vagamente cerca de distribuirse uniformemente. Si sus objetos pueden estar agrupados, entonces es obvio cómo eso causa un problema. El uso de un enfoque híbrido de algún tipo de árbol de particiones dentro de cada cuadro hash puede ayudar con esto y puede convertir un enfoque de árbol puro en algo que sea más fácil escalar al mismo tiempo.

La superposición de regiones es una forma de tratar con objetos que se extienden a lo largo de los límites de los cubos de árboles o cuadros de hash. Una solución más común es probar cualquier objeto que cruza el borde contra todos los objetos en la casilla contigua, o insertar el objeto en ambas cajas (aunque eso requiere un manejo adicional para evitar romper las intersecciones).

Answer 8

Supongo que estás haciendo una simulación dinámica molecular de esfera dura, ¿verdad? Acometí el mismo problema muchas veces en Monte Carlo y en simulaciones dinámicas moleculares. Ambas soluciones se mencionan muy a menudo en la literatura sobre simulaciones. Personalmente prefiero la solución 1 , pero ligeramente modificada.

Solución 1
Divida su espacio en celdas rectangulares que no se superponen. Entonces, cuando compruebas un círculo de colisión, buscas todos los círculos dentro de una celda que es tu primer círculo y miras X celdas en cada dirección. Probé muchos valores de X y descubrí que X = 1 es la solución más rápida. Entonces, debe dividir el espacio en el tamaño de las celdas en cada dirección igual a:

Divisor = SimulationBoxSize / MaximumCircleDiameter;
CellSize = SimulationBoxSize / Divisor;

Divisor debe ser mayor que 3, de lo contrario causará errores (si es demasiado pequeño, debe agrandar su cuadro de simulación).
Entonces su algoritmo se verá así:

1. Pon todos los círculos dentro de la caja
2. Crear estructura de celda y almacenar índices o punteros a círculos dentro de una celda (en una matriz o en una lista)
3. Haga un paso en el tiempo (mueva todo) y actualice las posiciones de los círculos dentro de las celdas
4. Mire alrededor de cada círculo en busca de colisión. Debe verificar una celda en todas las direcciones
5. Si hay una colisión, haz algo
6. Ir a 3.

Si lo va a escribir correctamente, entonces tendría algo sobre la complejidad O (N) , ya que la cantidad máxima de círculos dentro de 9 celdas (en 2D) o 27 celdas (en 3D) es constante para cualquier número total de círculos.

Solución 2
Ususaly esto se hace así:

1. Para cada círculo crea una lista de círculos que están en la distancia R < R_max , calcula el tiempo después del cual debemos actualizar las listas (algo sobre T_update = R_max / V_max ; donde V_max es la velocidad máxima actual)
2. Dar un paso en el tiempo
3. Verifique la distancia de cada círculo con círculos en su lista
4. Si hay una colisión, haz algo
5. Si la hora actual es más grande que T_update , vaya a 1.
6. De lo contrario, vaya a 2.

Esta solución con listas a menudo se mejora agregando otra lista con R_max_2 > R_max y con su propio tiempo de expiración T_2 . En esta solución, esta segunda lista se usa para actualizar la primera lista. Por supuesto, después de T_2 debes actualizar todas las listas que son O (N ^ 2) . También tenga cuidado con esta T y T_2 veces, porque si la colisión puede cambiar la velocidad, esos tiempos cambiarían. Además, si introduce algunos avances en su sistema, también causará un cambio de velocidad.

Solución 1 + 2 Puede usar listas para detectar colisiones y celdas para actualizar listas. En un libro se escribió que esta es la mejor solución, pero creo que si creas celdas pequeñas (como en mi ejemplo), entonces la solución 1 es mejor. Pero es mi opinión.

Otras cosas
También puede hacer otras cosas para mejorar la velocidad de simulación:

1. Cuando calcula la distancia r = sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + ...) no tiene que hacer la operación de raíz cuadrada. Puedes comparar r^2 con algún valor, está bien. Además, no tiene que hacer todas las operaciones (x1-x2)*(x1-x2) (es decir, para todas las dimensiones), porque si x*x es más grande que alguna r_collision^2 entonces todas las demás y*y así encendido, resumido, sería más grande.
2. El método de dinámica molecular es muy fácil de paralelar. Puedes hacerlo con hilos o incluso en GPU. Puedes calcular cada distancia en diferentes hilos. En GPU puedes crear fácilmente miles de hilos casi sin costo.

Para las esferas duras también hay un algoritmo eficaz que no realiza pasos a tiempo, sino que busca la colisión más cercana en el tiempo y salta a esta hora y actualiza todas las posiciones. Puede ser bueno para sistemas no densos donde las colisiones no son muy probables.