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

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.

¡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 ):

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.

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.

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.

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).

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.