Trabajando con muchos cubos. ¿Mejorando el desempeño?

12

Editar: Para resumir la pregunta, tengo un mundo basado en voxel (estilo Minecraft (Gracias Pato Comunista)) que sufre de bajo rendimiento. No soy positivo con respecto a la fuente, pero me gustaría cualquier consejo posible sobre cómo deshacerse de él.

Estoy trabajando en un proyecto donde un mundo consiste en una gran cantidad de cubos (te daría un número, pero es mundos definidos por el usuario). Mi prueba es alrededor de bloques (48 x 32 x 48).

Básicamente, estos bloques no hacen nada por sí mismos. Solo se sientan allí.

Comienzan a usarse cuando se trata de la interacción del jugador.

Necesito verificar con qué cubos interactúa el mouse del usuario (pasar el mouse, hacer clic, etc.) y detectar la colisión a medida que el jugador se mueve.

Ahora tenía una gran cantidad de retraso al principio, recorriendo cada bloque.

Me las arreglé para disminuir ese retraso, recorriendo todos los bloques y descubriendo qué bloques están dentro de un rango particular del personaje, y luego solo recorriendo esos bloques para la detección de colisión, etc.

Sin embargo, todavía voy a un deprimente 2 fps.

¿Alguien tiene alguna otra idea sobre cómo podría disminuir este retraso?

Por cierto, estoy usando XNA (C #) y sí, es 3d.

Joel
fuente
¿Te refieres a Minecraft? Es decir, voxel?
El pato comunista
44
¿Has mirado en octrees? en.wikipedia.org/wiki/Octree
bummzack
1
¿Has intentado perfilar tu juego? Puede mostrar algunas áreas clave donde se pasa la mayor parte del tiempo. Puede que no sea lo que crees que es.
deceleratedcaviar
2
En lugar de dibujar las 6 caras de cada cubo, solo puedes dibujar las caras que no están en contacto con nada
David Ashmore
1
@David: Sí, o podría dejar de hacer una sola llamada de extracción por cubo primero, y luego preocuparse por los polígonos individuales más tarde.
Olhovsky

Respuestas:

20

¡Parece que estás buscando aprender sobre los árboles!

Y lo digo en serio, si actualmente estás recorriendo una matriz de todos tus cubos, entonces realmente deberías buscar en varias estructuras de datos espaciales. Para este caso, la mejor manera de volver a imaginar su mundo de cubos es como un árbol.

Antes de entrar en las razones de por qué, pensemos en nuestro problema. Estamos buscando una solución donde, por el menor costo posible, podamos recuperar una lista de cubos cercanos con los que el jugador podría estar chocando. Esta lista debe ser lo más pequeña y precisa posible.

Ahora para determinar esta zona, necesitamos asignar el espacio de coordenadas de nuestro jugador al espacio de coordenadas del mapa de cubos; es decir, necesitamos asignar la posición de coma flotante del jugador a un índice discreto de la matriz multidimensional de cubos (la notación de ejemplo podría ser world[31][31][31], es decir, el centro exacto para una matriz multidimensional 64 * 64 * 64).

Podríamos simplemente calcular los bloques circundantes usando esta misma indexación discreta, tal vez muestreando solo los cubos cercanos, pero esto aún requiere un recálculo constante y no permite ningún objeto que no sea discreto en su ubicación (es decir, puede que no se asigne al cubo mapa).

La situación ideal es un conjunto de cubos que contienen nuestros conjuntos de cubos para secciones particulares de nuestro mapa de cubos, divididos en partes iguales, por lo que en lugar de volver a calcular el área circundante, simplemente nos movemos dentro y fuera de estas zonas . Para cualquier cálculo no trivial, mantener nuestros datos de esta manera podría eliminar la iteración de todos los cubos, y solo estos conjuntos individuales que están cerca.

La pregunta es: ¿Cómo implementamos esto?

Para el mundo 64 * 64 * 64, imagínelo desglosado en 8 * 8 * 8 zonas . Esto significa que en su mundo, tendrá 8 zonas por eje (X, Y, Z). Cada una de estas zonas contendrá 8 cubos, fácilmente recuperables por este nuevo índice simplificado.

Si necesita realizar una operación en un conjunto de cubos cercanos, en lugar de iterar cada cubo en su mundo, simplemente puede iterar sobre estas zonas , desglosando el número máximo de iteraciones desde el 64 * 64 * 64 original (262144) hasta solo 520 (8 * 8 * 8 + 8).

Ahora aleja este mundo de zonas y coloca las zonas en superzonas más grandes ; en donde cada superzona contiene 2 * 2 * 2 zonas regulares . A medida que su mundo actualmente contiene 512 (8 * 8 * 8) zonas , podemos romper los 8 * 8 * 8 zonas en 64 (4 * 4 * 4) Grandes zonas dividiendo 8 zonas por 2 zonas por super-zona . Aplicando la misma lógica desde arriba, esto rompería las iteraciones máximas de 512 a 8 para encontrar la superzona ; y luego un máximo de 64 para encontrar la zona de procedimiento(total máximo 72)! Puede ver cómo esto ya le está ahorrando muchas iteraciones (262144: 72).

Estoy seguro de que ahora puedes ver lo útiles que son los árboles. Cada zona es una rama en el árbol, con cada superzona como una rama precedente. Simplemente estás atravesando el árbol para encontrar lo que necesitas; utilizando conjuntos de datos más pequeños para minimizar el costo general.

El siguiente diagrama debería ayudarlo a visualizar el concepto. (imagen de Wikipedia: Octrees ): Octree

Descargo de responsabilidad:

En una configuración ideal como la anterior, donde su mundo de vóxel ya se presenta en una matriz multidimensional de tamaño fijo, simplemente puede consultar la posición del jugador, ¡luego indexar los bloques circundantes con un costo O (1)! (Ver explicación de Olhovsky) Pero esto se vuelve más difícil cuando comienzas a considerar que tu mundo rara vez tiene un tamaño fijo en un juego de vóxel; y es posible que necesite que su estructura de datos sea capaz de cargar súper zonas completas desde el disco duro a la memoria. A diferencia de una matriz multidimensional de tamaño fijo, los árboles lo permiten fácilmente sin dedicar demasiado tiempo a algoritmos combinatorios.

caviar desacelerado
fuente
Yo diría que lo entiendo, pero desafortunadamente no. Las cajas de colisión de los bloques no se mueven, solo la caja de colisión del jugador. Y ahora tengo un método que (sin recorrer todos los bloques) devuelve todos los bloques que están dentro de un radio de 5 bloques del jugador. Perdón por la molestia, pero ¿alguna aclaración? Por cierto, para hacerlo más simple, ¿podría asumir que el mundo es de 64 x 64 x 64?
Joel
Y sigo obteniendo alrededor de 5 fps :(
Joel
Reescribí mi respuesta, avíseme si ayudó.
deceleratedcaviar
Así que reduzco los bloques en los que podría estar el jugador, usando esta técnica de octree. Estoy bastante seguro de que lo entiendo. Pero, ¿sugiere que use mi detección de colisión una vez que la haya reducido a una pequeña selección de bloques, o tiene algún otro método?
Joel
2
A menos que el jugador sea muy grande en relación con el tamaño de los cubos, entonces verificar la colisión alrededor del jugador es probablemente la forma más rápida. Si el jugador no ocupa más espacio que un cubo, por ejemplo, solo necesita verificar 27 cubos circundantes como máximo para encontrar una colisión. Esto no requiere un árbol, ya que puede indexar directamente en esas ubicaciones de cubos, suponiendo que almacene los cubos en una matriz en la que puede indexar, con una ranura asignada para cada ubicación de cubo posible.
Olhovsky
13

Estoy de acuerdo con la respuesta de Daniels, ya que iterar a través de grandes cantidades de cajas es la causa más probable, y que al usar la partición espacial podría acelerar mucho el juego, pero el problema también podría estar en otro lado y podría estar perdiendo el tiempo. .

Para aumentar significativamente la velocidad de tu juego, necesitas crear un perfil de tu código. Identifique dónde está el cuello de botella, esto le permitirá realizar las mayores mejoras.

Hay muchas formas de crear un perfil de su código, puede usar su propia clase de análisis de rendimiento (que podría hacer uso de la clase Cronómetro (MSDN) ), o podría usar PIX para tener una idea general de lo ocupada que está la CPU / GPU .

También puede colocar marcadores de eventos PIX en su código, que se mostrarán como regiones coloreadas en las lecturas de PIX. No hay una interfaz oficial de C # para estas funciones, pero este hilo muestra cómo puede hacer una interfaz de C # usted mismo.

CiscoIPPhone
fuente
2
+1, totalmente de acuerdo. No debería buscar algoritmos, debería analizar el perfil de su código. Supongo que no tiene nada que ver con el hecho de que estás iterando a través de los bloques (no son tantos), es lo que estás haciendo con cada bloque. En última instancia, sí, debe tener un método mejor que la fuerza bruta, pero si no puede manejar una iteración simple en cubos de 48x32x48, debe repensar lo que está haciendo con cada cubo, no cómo está haciendo un bucle.
Tim Holt
44
@Tim: a menos que su jugador sea lo suficientemente grande como para ocupar un espacio de 48x32x48, entonces no debería estar iterando en ningún lugar cerca de esa cantidad de cubos. Si está iterando a través de 73000 cubos por cuadro, entonces puedo decirle sin hacer ningún perfil, que vale la pena que lo arregle, si no es por otra razón que aprender a evitar hacer decenas de miles de veces más iteraciones que son necesarios. Esto no es lo que yo llamaría optimización micro o prematura.
Olhovsky
Mi jugador tiene menos del tamaño de 1 cubo, aunque puede ser más grande en algún momento (pero no mucho)
Joel
Randomman159: Entonces solo necesitas probar contra sus 27 cubos circundantes para encontrar una colisión. Mira mi respuesta.
Olhovsky
6

Si su jugador es grande en relación con el tamaño de los cubos, entonces probablemente desee un octree u otra estructura de partición espacial, como han sugerido otros.

Sin embargo, si su jugador es pequeño en relación con el tamaño de los cubos, entonces probablemente la forma más rápida de detectar una colisión con los cubos es hacer una búsqueda lineal simple del área alrededor del jugador.

Como su jugador es más pequeño que 1 cubo, entonces solo necesita probar la colisión contra los 27 cubos vecinos, como máximo.

Esto supone que almacena los cubos en una matriz en la que puede indexar, con una ranura en la matriz para cada cubo.

Como otros han señalado, debe perfilar su código para ver qué es lo que realmente lo está frenando.

Sin embargo, si tuviera que adivinar, diría que probablemente estás haciendo una llamada de extracción para cada cubo, lo que sería tu cuello de botella con diferencia. Para arreglar eso, deberías buscar instancias de geometría.

Olhovsky
fuente
O podría tener un 'cuadro delimitador' que rodea al jugador, y luego simplemente verifica con qué objetos está colisionando para determinar con qué objetos debe colisionar el jugador. Un buen motor de física podrá hacer todas las optimizaciones por usted; también permitirá más que solo 'bloques' para colisionar.
deceleratedcaviar
Personalmente, no me gustaría confiar en la fase ancha de un motor de física para probar contra 73000 cubos por mí, cuando podría escribir dos docenas de líneas de código para probar la colisión de manera eficiente. Además, probablemente no tiene un motor de física para aprovechar en este momento.
Olhovsky
1

Una sugerencia más para acelerar las cosas: tus bloqueos son aproximadamente fijos, eso significa que no hay forma de que un jugador pueda chocar con la mayoría de ellos. Agregue un booleano a los bloques que indiquen si están expuestos o no. (Esto se puede volver a calcular mirando a sus vecinos). Un bloque que no está expuesto no tiene que verificarse por colisiones.

Es obvio que Minecraft hace algo similar a esto: una vez golpeé un trozo sin carga que me dio una visión del mundo, pude ver a través del suelo sólido, todo lo que apareció fue los espacios abiertos (el lado opuesto de ellos eran una superficie expuesta y, por lo tanto, renderizados).

Loren Pechtel
fuente
-1

Tuve ese problema con mi motor de vóxel.

Solución: (Mucho más simple que los octreos) En lugar de recorrer todos los bloques, simplemente use una ecuación para determinar la posición del bloque en la matriz de bloques.

BlockIndex = (x * WorldWidth * WorldHeight) + (z * WorldHeight) + y;

Entonces, si quieres ver si existe un bloque:

Blocks[BlockIndex].Type > -1;

O como quiera determinar si existe el bloque.

BMW
fuente
El problema aquí es más complicado, porque solo tiene 2 coordenadas para su mouse, para probar con el mundo 3D. Si la vista era de arriba hacia abajo, podría encontrar 2 de los 3 índices correctos para la posición del mouse, y luego recorrer la altura, comenzando desde arriba, más cerca de la cámara, y encontrar la primera aparición de un bloque.
Markus von Broady