Mejora de una función O (N ^ 2) (todas las entidades iterando sobre todas las demás entidades)

21

Un poco de historia, estoy codificando un juego de evolución con un amigo en C ++, usando ENTT para el sistema de entidades. Las criaturas caminan en un mapa 2D, comen verdes u otras criaturas, se reproducen y sus rasgos mutan.

Además, el rendimiento está bien (60 fps sin problema) cuando el juego se ejecuta en tiempo real, pero quiero poder acelerarlo significativamente para no tener que esperar 4 horas para ver cambios significativos. Así que quiero obtenerlo lo más rápido posible.

Estoy luchando por encontrar un método eficiente para que las criaturas encuentren su comida. Se supone que cada criatura debe buscar la mejor comida que esté lo suficientemente cerca de ellos.

Captura de pantalla de ejemplo del juego

Si quiere comer, se supone que la criatura que se muestra en el centro mira a su alrededor en un radio de 149.64 (su distancia de visión) y juzga qué alimento debe buscar, que se basa en la nutrición, la distancia y el tipo (carne o planta) .

La función responsable de encontrar a cada criatura su comida es consumir alrededor del 70% del tiempo de ejecución. Simplificando cómo se escribe actualmente, es algo así:

for (creature : all_creatures)
{
  for (food : all_entities_with_food_value)
  {
    // if the food is within the creatures view and it's
    // the best food found yet, it becomes the best food
  }
  // set the best food as the target for creature
  // make the creature chase it (change its state)
}

Esta función se ejecuta cada tic para cada criatura que busca comida, hasta que la criatura encuentre comida y cambie de estado. También se ejecuta cada vez que se genera una nueva comida para criaturas que ya persiguen una comida determinada, para asegurarse de que todos persigan la mejor comida disponible para ellos.

Estoy abierto a ideas sobre cómo hacer que este proceso sea más eficiente. Me encantaría reducir la complejidad de O(norte2) , pero no sé si eso es posible.

Una forma en que ya lo mejoro es clasificando el all_entities_with_food_valuegrupo para que cuando una criatura repita sobre comida demasiado grande para comer, se detenga allí. ¡Cualquier otra mejora es más que bienvenida!

EDITAR: ¡Gracias a todos por las respuestas! Implementé varias cosas de varias respuestas:

Primero y simplemente lo hice para que la función de culpabilidad solo se ejecute una vez cada cinco tics, esto hizo que el juego fuera 4 veces más rápido, sin cambiar visiblemente nada sobre el juego.

Después de eso, almacené en el sistema de búsqueda de alimentos una matriz con la comida generada en el mismo tic que ejecuta. De esta manera, solo necesito comparar la comida que la criatura persigue con las nuevas comidas que aparecieron.

Por último, después de investigar la partición del espacio y considerar BVH y quadtree, elegí este último, ya que siento que es mucho más simple y más adecuado para mi caso. Lo implemento bastante rápido y mejoró enormemente el rendimiento, ¡la búsqueda de alimentos apenas toma tiempo!

Ahora renderizar es lo que me está frenando, pero eso es un problema para otro día. ¡Gracias a todos!

Alexandre Rodrigues
fuente
2
¿Has experimentado con múltiples hilos en múltiples núcleos de CPU ejecutándose simultáneamente?
Ed Marty
66
¿Cuántas criaturas tienes en promedio? No parece ser tan alto, a juzgar por la instantánea. Si ese es siempre el caso, la partición del espacio no ayudará mucho. ¿Has considerado no ejecutar esta función en cada tic? Podrías ejecutarlo cada, digamos, 10 ticks. Los resultados de la simulación no deberían cambiar cualitativamente.
Turnos
44
¿Ha realizado un perfil detallado para descubrir la parte más costosa de la evaluación de alimentos? En lugar de mirar la complejidad general, tal vez necesite ver si hay algún cálculo específico o acceso a la estructura de la memoria que lo está asfixiando.
Harabeck
Una sugerencia ingenua: podría usar un quadtree o una estructura de datos relacionada en lugar de la forma O (N ^ 2) que está haciendo ahora.
Seiyria
3
Como sugirió @Harabeck, profundizaría más para ver en qué parte del bucle se está gastando todo ese tiempo. Si se trata de cálculos de raíz cuadrada para la distancia, por ejemplo, es posible que primero pueda comparar los cables XY para eliminar previamente muchos candidatos antes de tener que hacer el costoso sqrt en los restantes. Agregar if (food.x>creature.x+149.64 or food.x<creature.x-149.64) continue;debería ser más fácil que implementar una estructura de almacenamiento "complicada" SI es lo suficientemente eficiente. (Relacionado: podría ayudarnos si publicara un poco más del código en su bucle interno)
AC

Respuestas:

34

Sé que no conceptualizas esto como colisiones, sin embargo, lo que estás haciendo es colisionar un círculo centrado en la criatura, con toda la comida.

Realmente no desea verificar la comida que sabe que está distante, solo lo que está cerca. Ese es el consejo general para la optimización de colisiones. Me gustaría animar a buscar técnicas para optimizar las colisiones, y no limitarme a C ++ al buscar.


Criatura encontrando comida

Para su escenario, sugeriría poner el mundo en una grilla. Haga que las celdas tengan al menos el radio de los círculos que desea colisionar. Luego puedes elegir la celda en la que se encuentra la criatura y sus hasta ocho vecinos y buscar solo aquellas de hasta nueve celdas.

Nota : podría hacer celdas más pequeñas, lo que significaría que el círculo que está buscando se extendería más allá de los vecinos inmediatos, lo que requeriría que itere allí. Sin embargo, si el problema es que hay demasiada comida, las células más pequeñas podrían significar iterar sobre menos entidades de alimentos en total, lo que en algún momento te favorece. Si sospecha que este es el caso, pruebe.

Si los alimentos no se mueven, puede agregar las entidades de alimentos a la cuadrícula en la creación, de modo que no necesite buscar qué entidades están en la celda. En su lugar, consulta la celda y tiene la lista.

Si haces que el tamaño de las celdas sea una potencia de dos, puedes encontrar la celda en la que se encuentra la criatura simplemente truncando sus coordenadas.

Puede trabajar con la distancia al cuadrado (es decir, no hacer sqrt) mientras compara para encontrar la más cercana. Menos operaciones sqrt significa una ejecución más rápida.


Nueva comida agregada

Cuando se agrega nueva comida, solo las criaturas cercanas necesitan ser despertadas. Es la misma idea, excepto que ahora necesita obtener la lista de criaturas en las celdas.

Mucho más interesante, si anota en la criatura qué tan lejos está de la comida que está persiguiendo ... puede verificar directamente contra esa distancia.

Otra cosa que te ayudará es que la comida sepa qué criaturas la persiguen. Eso te permitirá ejecutar el código para encontrar comida para todas las criaturas que persiguen un pedazo de comida que acaba de comer.

De hecho, comience la simulación sin comida y las criaturas tienen una distancia anotada de infinito. Luego comienza a agregar comida. Actualice las distancias a medida que las criaturas se mueven ... Cuando se come comida, tome la lista de criaturas que la perseguían y luego encuentre un nuevo objetivo. Además de ese caso, todas las demás actualizaciones se manejan cuando se agregan alimentos.


Saltando simulación

Conociendo la velocidad de una criatura, sabes cuánto es hasta que alcanza su objetivo. Si todas las criaturas tienen la misma velocidad, la que alcanzará primero es la que tenga la menor distancia anotada.

Si también conoce el tiempo hasta que agregue más alimentos ... Y esperemos que tenga una previsibilidad similar para la reproducción y la muerte, entonces sabe el tiempo para el próximo evento (ya sea comida agregada o una criatura comiendo).

Salta a ese momento. No es necesario simular criaturas moviéndose.

Theraot
fuente
1
"y busca solo allí". y las celdas vecinas inmediatas, lo que significa 9 celdas en total. ¿Por qué 9? Porque qué pasa si la criatura está justo en la esquina de una celda.
UKMonkey
1
@UKMonkey "Haz que las celdas tengan al menos el radio de los círculos que quieres colisionar", si el lado de la celda es el radio y la criatura está en la esquina ... bueno, supongo que solo necesitas buscar cuatro en ese caso. Sin embargo, claro, podemos hacer que las células sean más pequeñas, lo que podría ser útil si hay demasiada comida y muy pocas criaturas. Editar: lo aclararé.
Theraot
2
Claro, si quieres hacer ejercicio si necesitas buscar en celdas adicionales ... pero dado que la mayoría de las celdas no tendrán comida (de la imagen dada); será más rápido buscar solo 9 celdas, que averiguar cuáles 4 necesita buscar.
UKMonkey
@ UKMonkey, por eso no mencioné eso inicialmente.
Theraot
16

Debe adoptar un algoritmo de partición espacial como BVH para reducir la complejidad. Para ser específico para su caso, debe hacer un árbol que consista en cuadros delimitadores alineados con ejes que contengan piezas de comida.

Para crear una jerarquía, coloque los alimentos cerca uno del otro en AABB, luego coloque esos AABB en AABB más grandes, nuevamente, por distancia entre ellos. Haga esto hasta que tenga un nodo raíz.

Para hacer uso del árbol, primero realice una prueba de intersección círculo-AABB contra un nodo raíz, luego, si ocurre una colisión, pruebe contra los hijos de cada nodo consecutivo. Al final deberías tener un grupo de piezas de comida.

También puede hacer uso de la biblioteca AABB.cc.

Ocelote
fuente
1
De hecho, eso reduciría la complejidad a N log N, pero también sería costoso realizar la partición. Ya que necesito hacer la partición de cada tic (ya que las criaturas se mueven cada tic), ¿valdría la pena? ¿Hay soluciones para ayudar a particionar con menos frecuencia?
Alexandre Rodrigues
3
@AlexandreRodrigues no tiene que reconstruir todo el árbol cada vez, solo actualiza las partes que se mueven, y solo cuando algo sale de un contenedor AABB en particular. Para mejorar aún más el rendimiento, es posible que desee engordar los nodos (dejando algo de espacio entre los hijos) para que no tenga que reconstruir toda la rama en una actualización de hoja.
Ocelote
66
Creo que un BVH podría ser demasiado complejo aquí: una cuadrícula uniforme implementada como una tabla hash es lo suficientemente buena.
Steven
1
@Steven implementando BVH puede ampliar fácilmente la escala de la simulación en el futuro. Y tampoco pierdes nada si lo haces para una simulación a pequeña escala.
Ocelot
2

Si bien los métodos de partición espacial descritos pueden reducir el tiempo, su problema principal no es solo la búsqueda. Es el gran volumen de búsquedas que haces lo que hace que tu tarea sea lenta. Entonces estás optimizando el ciclo interno, pero también puedes optimizar el ciclo externo.

Su problema es que mantiene los datos de las encuestas. Es un poco como tener a los niños en el asiento trasero pidiendo una milésima vez "¿ya llegamos?", No hay necesidad de que el conductor le informe cuando usted esté allí.

En su lugar, debe esforzarse, si es posible, para resolver cada acción hasta su finalización, ponerla en una cola y dejar salir esos eventos de burbuja, esto puede hacer cambios en la cola, pero eso está bien. Esto se llama simulación de eventos discretos. Si puede implementar su simulación de esta manera, entonces está buscando una aceleración considerable que supere con creces la aceleración que puede obtener de la mejor búsqueda de partición espacial.

Para subrayar el punto en una carrera anterior, hice simuladores de fábrica. Simulamos semanas de flujo de material completo de grandes fábricas / aeropuertos en cada nivel de artículo con este método en menos de una hora. Si bien la simulación basada en el paso de tiempo solo podía simular 4-5 veces más rápido que en tiempo real.

También como una fruta muy baja, considera desacoplar tus rutinas de dibujo de tu simulación. Aunque su simulación es simple, todavía hay algunos gastos generales de dibujar cosas. Peor aún, el controlador de pantalla puede limitarlo a x actualizaciones por segundo, mientras que en realidad sus procesadores podrían hacer cosas cientos de veces más rápido. Esto subraya la necesidad de perfilar.

joojaa
fuente
@Theraot no sabemos cómo están estructurados los dibujos. Pero sí, las llamadas se convertirán en cuellos de botella una vez que seas lo suficientemente rápido de todos modos
joojaa
1

Puede usar un algoritmo de línea de barrido para reducir la complejidad a Nlog (N). La teoría es la de los diagramas de Voronoi, que hace una división del área que rodea a una criatura en regiones que consisten en todos los puntos más cercanos a esa criatura que cualquier otra.

El llamado algoritmo de Fortune lo hace por usted en Nlog (N), y la página wiki contiene pseudocódigo para implementarlo. Estoy seguro de que también hay implementaciones de bibliotecas. https://en.wikipedia.org/wiki/Fortune%27s_algorithm

nabla
fuente
Bienvenido a GDSE y gracias por responder. ¿Cómo aplicarías esto exactamente a la situación de OP? La descripción del problema dice que una entidad debe considerar todos los alimentos dentro de su distancia de visión y seleccionar el mejor. Un Voronoi tradicional excluiría en el rango de comida que estaba más cerca de otra entidad. No estoy diciendo que un Voronoi no funcione, pero no es obvio por su descripción cómo OP debería usar uno para el problema como se describe.
Pikalek
Me gusta esta idea, me gustaría verla ampliada. ¿Cómo se representa el diagrama voronoi (como en la estructura de datos de memoria)? ¿Cómo lo consultas?
Theraot
@Theraot no necesitas el diagrama de voronoi solo la misma idea de barrido.
joojaa
-2

La solución más fácil sería integrar un motor de física y usar solo el algoritmo de detección de colisión. Simplemente construya un círculo / esfera alrededor de cada entidad y deje que el motor de física calcule las colisiones. Para 2D, sugeriría Box2D o Chipmunk , y Bullet para 3D.

Si cree que integrar un motor de física completo es demasiado, le sugiero que busque en los algoritmos de colisión específicos. La mayoría de las bibliotecas de detección de colisiones funcionan en dos pasos:

  • Detección de fase amplia: el objetivo de esta etapa es obtener la lista de pares de objetos candidatos que pueden colisionar, lo más rápido posible. Dos opciones comunes son:
    • Barrer y podar : clasifique los cuadros delimitadores a lo largo del eje X y marque ese par de objetos que se cruzan. Repita para cada otro eje. Si un par candidato pasa todas las pruebas, pasa a la siguiente etapa. Este algoritmo es muy bueno para explotar la coherencia temporal: puede mantener las listas de entidades ordenadas y actualizarlas en cada cuadro, pero como están casi ordenadas, será muy rápido. También explota la coherencia espacial: debido a que las entidades se ordenan en orden espacial ascendente, cuando verifica las colisiones, puede detenerse tan pronto como una entidad no colisione, porque todas las siguientes estarán más lejos.
    • Estructuras de datos de partición espacial, como cuadrúpedos, octreos y cuadrículas. Las cuadrículas son fáciles de implementar, pero pueden ser muy derrochadoras si la densidad de la entidad es baja y muy difícil de implementar para espacios ilimitados. Los árboles espaciales estáticos también son fáciles de implementar, pero difíciles de equilibrar o actualizar en su lugar, por lo que tendría que reconstruirlo cada cuadro.
  • Fase estrecha: los pares de candidatos encontrados en la fase amplia se prueban con algoritmos más precisos.
José Franco Campos
fuente