Detección de colisión 2D más rápida

Recientemente he estado trabajando en un juego de disparos 2D de ritmo rápido y me encontré con un gran problema. Detección de colisiones. Claro, está funcionando, pero es muy lento. Mi objetivo es: tener muchos enemigos en la pantalla y hacer que no se toquen. Todos los enemigos persiguen a la entidad del jugador. La mayoría de ellos tienen la misma velocidad, tarde o temprano, todos terminan ocupando el mismo espacio mientras persiguen al jugador. Esto realmente elimina el factor diversión ya que, para el jugador, parece que solo un enemigo te persigue. Para evitar que ocupen el mismo espacio, agregué una detección de colisión (una detección 2D muy básica, el único método que conozco) que es.

Enemy class update method
    Loop through all enemies (continue; if the loop points at this object)
        If enemy object intersects with this object
            Push enemy object away from this enemy object

Esto funciona bien Mientras solo tenga <200 entidades enemigas, eso es. Cuando me acerco a 300-350 entidades enemigas, mi velocidad de fotogramas comienza a caer fuertemente. Primero pensé que era una mala representación, así que eliminé su llamada de dibujo. Esto no ayudó en absoluto, así que, por supuesto, me di cuenta de que era el método de actualización. La única parte pesada en su método de actualización es esta parte de cada enemigo en bucles a través de cada enemigo. Cuando me acerco a 300 enemigos, el juego realiza una iteración escalonada de 90000 (300x300). Mi mi ~

Estoy seguro de que debe haber otra forma de abordar esta detección de colisión. Aunque no tengo idea de cómo. Las páginas que encuentro tratan sobre cómo hacer realmente la colisión entre dos objetos o cómo verificar la colisión entre un objeto y un mosaico. Ya sé esas dos cosas.

tl; dr? ¿Cómo abordo la detección de colisión entre MUCHAS entidades?

Edición rápida: si sirve de ayuda, estoy usando C # XNA.

Ya golpeó su problema directamente en la cabeza, está haciendo que cada entidad verifique con cada otra entidad. Lo que querrá es algún tipo de sistema de 'Nivel de detalle' (es más o menos un gráfico de escena muy simple, solo lo está utilizando para otras cosas además de renderizar :)) donde los posibles candidatos de colisión se seleccionan mejor.

Generalmente hago tres colecciones para sistemas como este. Y cuando habla de la cantidad de entidades que desea tener, puede que incluso necesite ir con un gráfico de escena completo para esto, ya que los datos de seguimiento (3 listas por entidad con una entrada para cada otra entidad) pueden salir rápidamente de control.

Básicamente, aunque tienes tres listas. La primera debe ser una lista muy pequeña de entidades que verificará con interacciones en cada cuadro. Usted determina esto porque están dentro del rango X de la entidad en cuestión. Como se mencionó, el punto de esta lista es contener todas las entidades que razonablemente puedan colisionar con otra este marco.

La siguiente lista son las que estarían en un rango de búfer que podría moverse al rango de la entidad sin demasiado esfuerzo. Llamaremos a este rango X * 1.5 solo por el argumento. Esta es una lista dividida en el tiempo en la que solo actualizará un puñado de ellos por fotograma, pero se asegurará de que los está revisando lo suficientemente rápido como para mantener la apariencia de las cosas funcionando sin problemas.

La tercera lista es la lista de 'todo lo demás' y una forma de evitar que esta valga la pena (escaneando toda la lista de entidades y quizás verificando si está en alguna de las otras listas antes de progresar, tal vez). podría funcionar, o podría empeorar las cosas.) Los objetos en esta lista se revisan menos que nada, ya que definitivamente debería tomar más de unos pocos marcos para colocarse en una de las otras dos listas.

Lo que también tendrá que hacer para mantener esto es cuando esté haciendo las pruebas de colisión, asegúrese de actualizar en qué lista están las entidades. Las que se mueven fuera del rango deben degradarse y las que se acercan deben actualizarse a un lista más activa comprobada.

Asumiendo que está manteniendo las cosas lo suficientemente simples, esto debería satisfacer sus necesidades. Si puede agregar información adicional a un gráfico de escena de representación existente (suponiendo que tenga uno), puede consultarlo para obtener una lista de entidades que están razonablemente dentro del rango que sería aún mejor, ya que ese es el punto completo de un gráfico de escena de todos modos (acceso rápido a una lista de datos relevantes en función de un puesto). Potencialmente, esto requeriría más trabajo y siempre debe considerar lo que necesita hacer frente a lo que prácticamente debería hacer.

Espero que esto ayude.

Debe manejar las colisiones con una estructura de datos ordenada, de modo que pueda tener n * log (n) veces en lugar del terrible n ^ 2. Y n * log (n) es casi lineal, como ya sabrás. Un ejemplo (clásico) es un quadtree, aquí hay un tutorial bastante simple y bien escrito, con gráficos y código (Java):

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect- probable-collisions-in-2d-space/

Rq: es bastante fácil encontrar una implementación para QuadTrees en cualquier idioma. Aún así, debe pensar en la 'granularidad' correcta para el árbol, y cuanto mayor sea el tamaño del árbol, más entidades tenemos que no caben dentro de un nodo.
Rq 2: dado que su partición de espacio se realiza solo para la detección de colisión, tiene la libertad perfecta para dividir el espacio a su gusto. Por ejemplo, no me dividiría en cuatro partes iguales, sino que usaría el centro de barras de las entidades de nivel actuales como centro para la nueva división. 1) el algoritmo sigue siendo n * log (n), 2) pierde la posibilidad de 'reconstruir' la escena del árbol -pero no le importa- y 3) tiene un árbol mucho más equilibrado, menos sobrecarga .
Rq3: Una vez que tienes tu árbol, una 'colisión' entre la pantalla y las entidades te da ... ¡las entidades visibles! en un tiempo más parecido a log (n), entonces ¿por qué no si n es grande? (El peor de los casos es obviamente un tiempo en n para este enfoque).

El árbol de partición de espacio binario, quadtree, octree (para 3D) son árboles posibles que puede generar (o mantener, si es ambicioso) en cada llamada de actualización para cada objeto que desea que se aplique la colisión.

Soy bastante ingenuo cuando se habla de quad o oct tree. Pero creo que este método debería hacer:

Deberá modificar la estructura / clase del jugador. Agregue una matriz / vector de punteros a otra estructura de jugador.

Cada segundo verifica la distancia entre cada dos jugadores. Si es tan bajo que es posible alcanzarlo en 1 segundo, agregue el puntero de ese jugador a la matriz de colisión del jugador actual.

Ahora solo verifique la colisión entre jugadores en la lista de los demás.