Si esta es su primera vez en esta pregunta, sugiero leer primero la parte de pre-actualización a continuación, luego esta parte. Sin embargo, aquí hay una síntesis del problema:
Básicamente, tengo un motor de detección y resolución de colisiones con un sistema de partición espacial de cuadrícula donde importa el orden de colisión y los grupos de colisión. Un cuerpo a la vez debe moverse, luego detectar la colisión, luego resolver las colisiones. Si muevo todos los cuerpos a la vez y luego genero posibles pares de colisión, obviamente es más rápido, pero la resolución se rompe porque no se respeta el orden de colisión. Si muevo un cuerpo a la vez, me veo obligado a hacer que los cuerpos revisen las colisiones, y se convierte en un problema ^ 2. Coloque grupos en la mezcla, y puede imaginar por qué se vuelve muy lento muy rápido con muchos cuerpos.
Actualización: He trabajado muy duro en esto, pero no pude optimizar nada.
También descubrí un gran problema: mi motor depende del orden de colisión.
Intenté una implementación de generación de pares de colisión única , que definitivamente aceleró mucho todo, pero rompió el orden de colisión .
Dejame explicar:
En mi diseño original (sin generar pares), esto sucede:
- un solo cuerpo se mueve
- Después de moverse, refresca sus células y obtiene los cuerpos contra los que choca.
- Si se superpone a un cuerpo que necesita resolver, resuelva la colisión.
Esto significa que si un cuerpo se mueve y golpea una pared (o cualquier otro cuerpo), solo el cuerpo que se ha movido resolverá su colisión y el otro cuerpo no se verá afectado.
Este es el comportamiento que deseo .
Entiendo que no es común para los motores de física, pero tiene muchas ventajas para los juegos de estilo retro .
En el diseño de cuadrícula habitual (que genera pares únicos), esto sucede:
- todos los cuerpos se mueven
- después de que todos los cuerpos se hayan movido, actualice todas las celdas
- generar pares de colisión únicos
- para cada par, maneje la detección y resolución de colisión
en este caso, un movimiento simultáneo podría haber resultado en la superposición de dos cuerpos, y se resolverán al mismo tiempo, lo que efectivamente hace que los cuerpos "se empujen unos a otros" y rompa la estabilidad de colisión con múltiples cuerpos
Este comportamiento es común para los motores de física, pero no es aceptable en mi caso .
También encontré otro problema, que es importante (incluso si no es probable que suceda en una situación del mundo real):
- considerar los cuerpos de los grupos A, B y W
- A choca y resuelve contra W y A
- B choca y resuelve contra W y B
- A no hace nada contra B
- B no hace nada contra A
puede haber una situación en la que muchos cuerpos A y B ocupan la misma celda; en ese caso, hay una gran cantidad de iteraciones innecesarias entre cuerpos que no deben reaccionar entre sí (o solo detectar colisiones pero no resolverlas) .
¡Para 100 cuerpos que ocupan la misma celda, son 100 ^ 100 iteraciones! Esto sucede porque no se generan pares únicos , pero no puedo generar pares únicos , de lo contrario obtendría un comportamiento que no deseo.
¿Hay alguna manera de optimizar este tipo de motor de colisión?
Estas son las pautas que deben respetarse:
¡El orden de colisión es extremadamente importante!
- Los cuerpos deben moverse uno a la vez , luego verificar si hay colisiones, uno a la vez , y resolver después del movimiento, uno a la vez .
Los cuerpos deben tener 3 conjuntos de bits de grupo
- Grupos : grupos a los que pertenece el cuerpo
- GroupsToCheck : agrupa el cuerpo contra el cual debe detectar colisiones
- GroupsNoResolve : agrupa el cuerpo contra el cual no debe resolver la colisión
- Puede haber situaciones en las que solo quiero que se detecte una colisión pero no se resuelva
Pre-actualización:
Prefacio : Soy consciente de que optimizar este cuello de botella no es una necesidad: el motor ya es muy rápido. Sin embargo, por diversión y con fines educativos, me encantaría encontrar una manera de hacer que el motor sea aún más rápido.
Estoy creando un motor de detección / respuesta de colisión 2D C ++ de propósito general, con énfasis en la flexibilidad y la velocidad.
Aquí hay un diagrama muy básico de su arquitectura:
Básicamente, la clase principal es World
, que posee (administra la memoria) de a ResolverBase*
, a SpatialBase*
y a vector<Body*>
.
SpatialBase
es una clase virtual pura que se ocupa de la detección de colisiones de fase amplia.
ResolverBase
es una clase virtual pura que se ocupa de la resolución de colisiones.
Los cuerpos se comunican a la World::SpatialBase*
de SpatialInfo
los objetos, propiedad de los propios cuerpos.
Actualmente hay una clase espacial: Grid : SpatialBase
que es una cuadrícula 2D fija básica. Tiene su propia clase de información, GridInfo : SpatialInfo
.
Así es como se ve su arquitectura:
La Grid
clase posee una matriz 2D de Cell*
. La Cell
clase contiene una colección de (no propiedad) Body*
: una vector<Body*>
que contiene todos los cuerpos que están en la celda.
GridInfo
los objetos también contienen punteros no propietarios a las células en las que se encuentra el cuerpo.
Como dije anteriormente, el motor se basa en grupos.
Body::getGroups()
devuelve unostd::bitset
de todos los grupos de los que forma parte el cuerpo.Body::getGroupsToCheck()
devuelve unostd::bitset
de todos los grupos con los que el cuerpo tiene que verificar la colisión.
Los cuerpos pueden ocupar más de una sola célula. GridInfo siempre almacena punteros no propietarios a las celdas ocupadas.
Después de que un solo cuerpo se mueve, ocurre la detección de colisión. Supongo que todos los cuerpos son cuadros delimitadores alineados con ejes.
Cómo funciona la detección de colisión de fase amplia:
Parte 1: actualización de información espacial
Para cada uno Body
body
:
- Se calculan la celda ocupada superior izquierda y las celdas ocupadas inferior derecha.
- Si difieren de las celdas anteriores,
body.gridInfo.cells
se borra y se llena con todas las celdas que ocupa el cuerpo (2D para el bucle de la celda superior izquierda a la celda inferior derecha).
body
ahora está garantizado para saber qué células ocupa.
Parte 2: controles de colisión reales
Para cada uno Body
body
:
body.gridInfo.handleCollisions
se llama:
void GridInfo::handleCollisions(float mFrameTime)
{
static int paint{-1};
++paint;
for(const auto& c : cells)
for(const auto& b : c->getBodies())
{
if(b->paint == paint) continue;
base.handleCollision(mFrameTime, b);
b->paint = paint;
}
}
void Body::handleCollision(float mFrameTime, Body* mBody)
{
if(mBody == this || !mustCheck(*mBody) || !shape.isOverlapping(mBody->getShape())) return;
auto intersection(getMinIntersection(shape, mBody->getShape()));
onDetection({*mBody, mFrameTime, mBody->getUserData(), intersection});
mBody->onDetection({*this, mFrameTime, userData, -intersection});
if(!resolve || mustIgnoreResolution(*mBody)) return;
bodiesToResolve.push_back(mBody);
}
La colisión se resuelve para cada cuerpo adentro
bodiesToResolve
.Eso es.
Entonces, he estado tratando de optimizar esta detección de colisión de fase amplia durante bastante tiempo. Cada vez que intento algo más que la arquitectura / configuración actual, algo no sale según lo planeado o asumo sobre la simulación que luego se demuestra que es falsa.
Mi pregunta es: ¿cómo puedo optimizar la fase amplia de mi motor de colisión ?
¿Existe algún tipo de optimización mágica de C ++ que se pueda aplicar aquí?
¿Se puede rediseñar la arquitectura para permitir un mayor rendimiento?
- Implementación real: SSVSCollsion
- Body.h , Body.cpp
- World.h , World.cpp
- Grid.h , Grid.cpp
- Cell.h , Cell.cpp
- GridInfo.h , GridInfo.cpp
Salida de Callgrind para la última versión: http://txtup.co/rLJgz
fuente
getBodiesToCheck()
se llamó 5462334 veces y tomó el 35,1% de todo el tiempo de creación de perfiles (Tiempo de acceso de lectura de instrucciones)Respuestas:
getBodiesToCheck()
Podría haber dos problemas con la
getBodiesToCheck()
función; primero:Esta parte es O (n 2 ) ¿no?
En lugar de verificar si el cuerpo ya está en la lista, use pintura en su lugar.
Estás desreferenciando el puntero en la fase de recopilación, pero de todos modos estarías desreferenciando en la fase de prueba, así que si tienes suficiente L1 no es gran cosa. Puede mejorar el rendimiento agregando también sugerencias de búsqueda previa al compilador
__builtin_prefetch
, por ejemplo , aunque eso es más fácil confor(int i=q->length; i-->0; )
bucles clásicos y demás .Es un simple ajuste, pero mi segundo pensamiento es que podría haber una forma más rápida de organizar esto:
Sin embargo, puede pasar a usar mapas de bits y evitar todo el
bodiesToCheck
vector. Aquí hay un enfoque:Ya está utilizando las teclas enteras para los cuerpos, pero luego las busca en mapas y cosas y mantiene listas de ellas. Puede pasar a un asignador de ranuras, que básicamente es solo una matriz o un vector. P.ej:
Lo que esto significa es que todo lo que se necesita para hacer las colisiones reales está en una memoria lineal compatible con la memoria caché, y solo sale al bit específico de implementación y lo conecta a una de estas ranuras si es necesario.
Para realizar un seguimiento de las asignaciones en este vector de los cuerpos puede utilizar una matriz de enteros como un mapa de bits y el uso haciendo girar poco o
__builtin_ffs
etc Esto es muy eficiente para mover a las ranuras que están ocupadas actualmente, o encontrar una ranura desocupada en la matriz. Incluso puede compactar la matriz a veces si crece excesivamente y luego se marcan los lotes eliminados, moviendo los que están al final para llenar los espacios.solo verifique cada colisión una vez
Si ha verificado si a choca con b , no necesita verificar si b también choca con a .
Se deduce del uso de identificadores enteros que evita estas comprobaciones con una simple instrucción if. Si la identificación de una posible colisión es menor o igual que la identificación actual que se está buscando, se puede omitir. De esta manera, solo verificará cada emparejamiento posible una vez; eso representará más de la mitad del número de controles de colisión.
respetar el orden de las colisiones
En lugar de evaluar una colisión tan pronto como se encuentre un par, calcule la distancia para golpear y almacene eso en un montón binario . Estos montones son cómo normalmente se hacen colas prioritarias en la búsqueda de rutas, por lo que es un código de utilidad muy útil.
Marque cada nodo con un número de secuencia, para que pueda decir:
Obviamente, después de que haya reunido todas las colisiones, primero comenzará a aparecer en la cola de prioridad. Entonces, lo primero que obtienes es que A 10 golpea a C 12 en 3. Incrementas el número de secuencia de cada objeto (los 10 bits), evalúas la colisión, calculas sus nuevas rutas y almacenas sus nuevas colisiones en la misma cola. La nueva colisión es A 11 golpea B 12 en 7. La cola ahora tiene:
Luego saltas de la cola de prioridad y su A 10 golpea a B 12 en 6. Pero ves que A 10 está rancio ; A está actualmente en 11. Así que puedes descartar esta colisión.
Es importante no molestarse en tratar de eliminar todas las colisiones obsoletas del árbol; retirar de un montón es costoso. Simplemente deséchalos cuando los revientes.
la cuadrícula
Debería considerar usar un quadtree en su lugar. Es una estructura de datos muy sencilla de implementar. A menudo ve implementaciones que almacenan puntos, pero prefiero almacenar rectificaciones y almacenar el elemento en el nodo que lo contiene. Esto significa que para verificar las colisiones solo tiene que iterar sobre todos los cuerpos y, para cada uno, verificarlo contra esos cuerpos en el mismo nodo de cuatro árboles (utilizando el truco de clasificación descrito anteriormente) y todos aquellos en los nodos de cuatro árboles principales. El quad-tree es en sí mismo la lista de posibles colisiones.
Aquí hay un simple Quadtree:
Almacenamos los objetos móviles por separado porque no tenemos que verificar si los objetos estáticos van a chocar con algo.
Estamos modelando todos los objetos como cuadros delimitadores alineados con ejes (AABB) y los colocamos en el QuadTreeNode más pequeño que los contiene. Cuando un QuadTreeNode tiene muchos hijos, puede subdividirlo más (si esos objetos se distribuyen entre los niños muy bien).
Cada vez que marque el juego, debe volver al quadtree y calcular el movimiento, y las colisiones, de cada objeto móvil. Debe verificarse si hay colisiones con:
Esto generará todas las colisiones posibles, sin orden. Luego haces los movimientos. Debe priorizar estos movimientos por distancia y "quién se mueve primero" (que es su requisito especial), y ejecutarlos en ese orden. Use un montón para esto.
Puede optimizar esta plantilla de quadtree; no necesita almacenar realmente los límites y el punto central; eso es completamente derivable cuando caminas por el árbol. No necesita verificar si un modelo está dentro de los límites, solo verifique de qué lado está del punto central (una prueba de "eje de separación").
Para modelar cosas de vuelo rápido como proyectiles, en lugar de moverlos en cada paso o tener una lista separada de 'viñetas' que siempre verifica, simplemente colóquelos en el árbol con el rectángulo de su vuelo para algunos pasos del juego. Esto significa que se mueven en el árbol cuádruple mucho más raramente, pero no está revisando balas contra paredes lejanas, por lo que es una buena compensación.
Los objetos estáticos grandes deben dividirse en partes componentes; un cubo grande debe tener cada cara almacenada por separado, por ejemplo.
fuente
Apuesto a que solo tienes un montón de errores de caché al iterar sobre los cuerpos. ¿Está agrupando todos sus cuerpos usando algún esquema de diseño orientado a datos? Con una fase ancha N ^ 2, puedo simular cientos y cientos , mientras grabo con fraps, de cuerpos sin ninguna caída de framerate en las regiones inferiores (menos de 60), y todo esto sin un asignador personalizado. Solo imagine lo que se puede hacer con el uso adecuado de caché.
La pista está aquí:
Esto levanta inmediatamente una gran bandera roja. ¿Estás asignando estos cuerpos con nuevas llamadas sin procesar? ¿Hay un asignador personalizado en uso? Es muy importante que tenga todos sus cuerpos en una gran matriz en la que recorre linealmente . Si atravesar la memoria linealmente no es algo que cree que puede implementar, considere usar una lista intrusivamente vinculada.
Además, parece estar usando std :: map. ¿Sabes cómo se asigna la memoria dentro de std :: map? Tendrá una complejidad O (lg (N)) para cada consulta de mapa, y esto probablemente se puede aumentar a O (1) con una tabla hash. Además de esto, la memoria asignada por std :: map también va a dañar tu caché horriblemente.
Mi solución es usar una tabla hash intrusiva en lugar de std :: map. Un buen ejemplo de listas intrusivamente vinculadas y tablas de hash intrusivas se encuentra en la base de Patrick Wyatt dentro de su proyecto coho: https://github.com/webcoyote/coho
En resumen, probablemente necesite crear algunas herramientas personalizadas para usted, a saber, un asignador y algunos contenedores intrusivos. Esto es lo mejor que puedo hacer sin perfilar el código por mí mismo.
fuente
new
cuando empujo cuerpos algetBodiesToCheck
vector, ¿quiere decir que está sucediendo internamente? ¿Hay alguna manera de evitar eso mientras se sigue teniendo una colección de cuerpos de tamaño dinámico?std::map
no es un cuello de botella: también recuerdo haber intentadodense_hash_set
y no haber obtenido ningún tipo de rendimiento.getBodiesToCheck
llamadas por trama. Sospecho que la constante limpieza / empuje en el vector es el cuello de botella de la función en sí. Elcontains
método también es parte de la desaceleración, pero comobodiesToCheck
nunca tiene más de 8-10 cuerpos, debería ser tan lentoReduzca el recuento de cuerpos para verificar cada cuadro:
Solo verifique los cuerpos que realmente pueden moverse. Los objetos estáticos solo deben asignarse a las celdas de colisión una vez después de haber sido creados. Ahora solo verifique las colisiones de los grupos que contienen al menos un objeto dinámico. Esto debería reducir el número de verificaciones en cada cuadro.
Usa un quadtree. Mira mi respuesta detallada aquí
Elimine todas las asignaciones de su código de física. Es posible que desee utilizar un generador de perfiles para esto. Pero solo he analizado la asignación de memoria en C #, por lo que no puedo ayudar con C ++.
¡Buena suerte!
fuente
Veo dos candidatos problemáticos en su función de cuello de botella:
Primero está la parte "contiene"; esta es probablemente la razón principal del cuello de botella. Está iterando a través de cuerpos ya encontrados para cada cuerpo. Tal vez deberías usar algún tipo de hash_table / hash_map en lugar de vector. Luego, la inserción debe ser más rápida (con la búsqueda de duplicidades). Pero no conozco ningún número específico: no tengo idea de cuántos cuerpos se repiten aquí.
El segundo problema podría ser vector :: clear y push_back. Clear puede o no evocar la reasignación. Pero es posible que desee evitarlo. La solución podría ser una matriz de banderas. Pero es probable que tenga muchos objetos, por lo que es ineficaz para la memoria tener una lista de todos los objetos para cada objeto. Algún otro enfoque podría ser bueno, pero no sé qué enfoque: /
fuente
Nota: No sé nada de C ++, solo Java, pero deberías poder descifrar el código. La física es lenguaje universal ¿verdad? También me doy cuenta de que es una publicación de hace un año, pero solo quería compartir esto con todos.
Tengo un patrón de observador que básicamente, después de que la entidad se mueve, devuelve el objeto con el que ha chocado, incluido un objeto NULL. Simplemente pon:
( Estoy rehaciendo Minecraft )
Digamos que estás deambulando por tu mundo. cada vez que llamas
move(1)
, llamacollided()
. si obtienes el bloque que deseas, entonces las partículas vuelan y puedes moverte de izquierda a derecha y de regreso pero no hacia adelante.Usando esto de manera más genérica que solo Minecraft como ejemplo:
Simplemente, tenga una matriz para señalar las coordenadas que, literalmente, como lo hace Java, utiliza punteros.
El uso de este método todavía requiere algo más que a priori método a de detección de colisiones. Podrías repetir esto, pero eso frustra el propósito. Puede aplicar esto a las técnicas de colisión amplia, media y estrecha, pero solo, es una bestia, especialmente cuando funciona bastante bien en juegos 3D y 2D.
Ahora, mirando una vez más, esto significa que, de acuerdo con mi método minecraft collide (), terminaré dentro del bloque, por lo que tendré que mover al jugador fuera de él. En lugar de marcar al jugador, necesito agregar un cuadro delimitador que verifique qué bloque está golpeando cada lado del cuadro. Problema fijo.
el párrafo anterior puede no ser tan fácil con los polígonos si quieres precisión. Para mayor precisión, sugeriría definir un cuadro delimitador de polígonos que no sea un cuadrado, pero que no esté teselado. si no, entonces un rectángulo está bien.
fuente