Cómo lo hicieron: millones de azulejos en Terraria

45

He estado trabajando en un motor de juego similar a Terraria , principalmente como un desafío, y aunque he descubierto la mayor parte, realmente no puedo entender cómo manejan los millones de fichas interactivas / cosechables el juego tiene a la vez. La creación de alrededor de 500,000 mosaicos, que es 1/20 de lo que es posible en Terraria , en mi motor hace que la velocidad de cuadros baje de 60 a alrededor de 20, incluso aunque todavía solo esté visualizando los mosaicos a la vista. Eso sí, no estoy haciendo nada con las fichas, solo las mantengo en la memoria.

Actualización : Código agregado para mostrar cómo hago las cosas.

Esto es parte de una clase, que maneja los mosaicos y los dibuja. Supongo que el culpable es la parte "foreach", que repite todo, incluso los índices vacíos.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        foreach (Tile tile in this.Tiles)
        {
            if (tile != null)
            {
                if (tile.Position.X < -this.Offset.X + 32)
                    continue;
                if (tile.Position.X > -this.Offset.X + 1024 - 48)
                    continue;
                if (tile.Position.Y < -this.Offset.Y + 32)
                    continue;
                if (tile.Position.Y > -this.Offset.Y + 768 - 48)
                    continue;
                tile.Draw(spriteBatch, gameTime);
            }
        }
    }
...

También aquí está el método Tile.Draw, que también podría funcionar con una actualización, ya que cada Tile utiliza cuatro llamadas al método SpriteBatch.Draw. Esto es parte de mi sistema de autotiling, lo que significa dibujar cada esquina dependiendo de los mosaicos vecinos. texture_ * son Rectángulos, se establecen una vez en el nivel de creación, no cada actualización.

...
    public virtual void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        if (this.type == TileType.TileSet)
        {
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position, texture_tl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 0), texture_tr, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(0, 8), texture_bl, this.BlendColor);
            spriteBatch.Draw(this.texture, this.realm.Offset + this.Position + new Vector2(8, 8), texture_br, this.BlendColor);
        }
    }
...

Cualquier crítica o sugerencia a mi código es bienvenida.

Actualización : Solución agregada.

Aquí está el método final de Level.Draw. El método Level.TileAt simplemente verifica los valores ingresados, para evitar excepciones OutOfRange.

...
    public void Draw(SpriteBatch spriteBatch, GameTime gameTime)
    {
        Int32 startx = (Int32)Math.Floor((-this.Offset.X - 32) / 16);
        Int32 endx = (Int32)Math.Ceiling((-this.Offset.X + 1024 + 32) / 16);
        Int32 starty = (Int32)Math.Floor((-this.Offset.Y - 32) / 16);
        Int32 endy = (Int32)Math.Ceiling((-this.Offset.Y + 768 + 32) / 16);

        for (Int32 x = startx; x < endx; x += 1)
        {
            for (Int32 y = starty; y < endy; y += 1)
            {
                Tile tile = this.TileAt(x, y);
                if (tile != null)
                    tile.Draw(spriteBatch, gameTime);

            }
        }
    }
...
William Mariager
fuente
2
¿Estás absolutamente seguro de que solo estás representando lo que está a la vista de la cámara, es decir, es el código para determinar qué representar correctamente?
Cooper
55
El framerrate cae de 60 a 20 fps, ¿solo por la memoria asignada? Eso es muy poco probable, debe haber algo mal. ¿Qué plataforma es? ¿El sistema está intercambiando memoria virtual a disco?
Maik Semder
66
@Drackir En este caso, diría que está mal si incluso hay una clase de mosaico, una matriz de enteros de longitud adecuada debería funcionar, y cuando hay medio millón de objetos, la sobrecarga de OO no es broma. Supongo que es posible hacer con objetos, pero ¿cuál sería el punto? Una matriz entera es muy simple de manejar.
aaaaaaaaaaaa
3
¡Ay! Iterando todos los mosaicos y llamando Dibujar cuatro veces en cada uno que esté a la vista. Definitivamente hay algunas mejoras posibles aquí ...
thedaian
11
No necesita todas las particiones elegantes que se mencionan a continuación para representar solo lo que está a la vista. Es un mapa en mosaico. Ya está dividido en una cuadrícula regular. Simplemente calcule el mosaico en la esquina superior izquierda de la pantalla y en la esquina inferior derecha, y dibuje todo en ese rectángulo.
Blecki

Respuestas:

56

¿Estás recorriendo los 500,000 mosaicos cuando estás renderizando? Si es así, es probable que eso cause parte de tus problemas. Si recorres medio millón de mosaicos al renderizar y medio millón de mosaicos cuando realizas los ticks de 'actualización' en ellos, entonces estás recorriendo un millón de mosaicos cada cuadro.

Obviamente, hay formas de evitar esto. Podrías realizar tus ticks de actualización mientras también renderizas, ahorrándote la mitad del tiempo dedicado a recorrer todos esos mosaicos. Pero eso vincula su código de representación y su código de actualización en una sola función, y generalmente es una IDEA MALA .

Puede realizar un seguimiento de los mosaicos que están en la pantalla y solo recorrerlos (y renderizarlos). Dependiendo de cosas como el tamaño de sus mosaicos y el tamaño de la pantalla, esto podría reducir fácilmente la cantidad de mosaicos que necesita recorrer, y eso le ahorraría bastante tiempo de procesamiento.

Finalmente, y quizás la mejor opción (la mayoría de los juegos mundiales grandes hacen esto), es dividir el terreno en regiones. Divide el mundo en trozos de, por ejemplo, 512x512 fichas, y carga / descarga las regiones a medida que el jugador se acerca o se aleja de una región. Esto también le evita tener que recorrer los mosaicos lejanos para realizar cualquier tipo de tick de 'actualización'.

(Obviamente, si su motor no realiza ningún tipo de actualización en los mosaicos, puede ignorar la parte de estas respuestas que las menciona).

thedaian
fuente
55
La parte de la región parece interesante, si recuerdo bien, así es como lo hace Minecraft, sin embargo, no funciona con la forma en que evoluciona el terreno en Terraria, incluso si no estás cerca, como la propagación de césped, el cultivo de cactus y similares. Editar : a menos que, por supuesto, apliquen el tiempo transcurrido desde la última vez que la región estuvo activa y luego realicen todos los cambios que habrían ocurrido en ese período. Eso podría funcionar realmente.
William Mariager
2
Minecraft definitivamente usa regiones (y los últimos juegos de Ultima lo hicieron, y estoy bastante seguro de que muchos de los juegos de Bethesda lo hacen). Estoy menos seguro de cómo Terraria maneja el terreno, pero es probable que apliquen el tiempo transcurrido a una región "nueva" o que almacenen todo el mapa en la memoria. Esto último exigiría un alto uso de RAM, pero la mayoría de las computadoras modernas podrían manejarlo. También puede haber otras opciones que no se han mencionado.
thedaian
2
@MindWorX: Hacer todas las actualizaciones cuando se recarga no siempre funcionaría; supongamos que tiene un montón de área estéril y luego césped. Te vas por siglos y luego caminas hacia la hierba. Cuando el bloque con la hierba se carga, se pone al día y se extiende en ese bloque, pero no se extenderá a los bloques más cercanos que ya están cargados. Sin embargo, estas cosas progresan MUCHO más lento que el juego: comprueba solo un pequeño subconjunto de los mosaicos en cualquier ciclo de actualización y puedes hacer que el terreno distante viva sin cargar el sistema.
Loren Pechtel
1
Como alternativa (o suplemento) a "ponerse al día" cuando una región se acerca al jugador, en su lugar, podría tener una simulación separada iterando sobre cada región distante y actualizándolas a un ritmo más lento. Puede reservar tiempo para esto en cada cuadro o hacer que se ejecute en un hilo separado. Entonces, por ejemplo, puede actualizar la región en la que se encuentra el reproductor más las 6 regiones adyacentes en cada cuadro, pero también actualizar 1 o 2 regiones adicionales también.
Lewis Wakeford
1
Para cualquiera que se pregunte, Terraria almacena todos sus datos de mosaico en una matriz 2d (el tamaño máximo es 8400x2400). Y luego usa algunas matemáticas simples para decidir qué sección de mosaicos renderizar.
FrenchyNZ
4

Veo un gran error aquí no manejado por ninguna de las respuestas. Por supuesto, nunca debe dibujar e iterar sobre más mosaicos de los que también necesita. Lo que es menos obvio es cómo se definen los mosaicos. Como puedo ver, hiciste una clase de mosaico, siempre solía hacerlo también, pero es un gran error. Probablemente tenga todo tipo de funciones en esa clase y eso crea una gran cantidad de procesamiento innecesario.

Solo debe iterar sobre lo que es realmente necesario para procesar. Así que piense en lo que realmente necesita para los mosaicos. Para dibujarlo solo necesita una textura, pero no desea iterar sobre una imagen real, ya que son grandes para procesar. Simplemente puede hacer un int [,] o incluso un byte sin signo [,] (si no espera más de 255 texturas de mosaico). Todo lo que necesita hacer es iterar sobre estas pequeñas matrices y usar un interruptor o una instrucción if para dibujar la textura.

Entonces, ¿qué necesitas actualizar? El tipo, la salud y el daño parecen suficientes. Todo esto se puede almacenar en bytes. Entonces, ¿por qué no hacer una estructura como esta para el ciclo de actualización:

struct TileUpdate
{
public byte health;
public byte type;
public byte damage;
}

En realidad, podría usar el tipo para dibujar el mosaico. Por lo tanto, puede separar ese (hacer una matriz propia) de la estructura para no iterar sobre los campos innecesarios de salud y daño en el bucle de dibujo. Para actualizar, debe considerar un área más amplia que solo su pantalla para que el mundo del juego se sienta más vivo (las entidades cambian de posición fuera de la pantalla), pero para dibujar cosas solo necesita el mosaico que está visible.

Si mantiene la estructura anterior, solo toma 3 bytes por mosaico. Entonces, para el ahorro y el propósito de la memoria, esto es ideal. Para la velocidad de procesamiento, realmente no importa si usa int o byte, o incluso int si tiene un sistema de 64 bits.

Madmenyo
fuente
1
Sí, las iteraciones posteriores de mi motor evolucionaron para usar eso. Principalmente para reducir el consumo de memoria y para aumentar la velocidad. Los tipos ByRef son lentos en comparación con una matriz llena de estructuras ByVal. Sin embargo, es bueno que hayas agregado esto a la respuesta.
William Mariager
1
Sí, lo encontré mientras buscaba algunos algoritmos aleatorios. Inmediatamente noté que estaba usando su propia clase de mosaico en su código. Es un error muy común cuando eres nuevo. Es bueno ver que todavía está activo desde que publicó esto hace 2 años.
Madmenyo
3
No necesitas tampoco healtho damage. Puede mantener un pequeño búfer de las ubicaciones de los mosaicos elegidos más recientemente y el daño en cada uno. Si se elige un nuevo mosaico y el búfer está lleno, retire la ubicación más antigua antes de agregar el nuevo. Esto limita la cantidad de fichas que puedes extraer a la vez, pero de todos modos hay un límite intrínseco (aproximadamente #players * pick_tile_size). Puede mantener esta lista por jugador si eso lo hace más fácil. El tamaño importa para la velocidad; un tamaño más pequeño significa más mosaicos en cada línea de caché de la CPU.
Sean Middleditch
@SeanMiddleditch Tienes razón, pero ese no era el punto. El punto era detenerse y pensar lo que realmente necesita para dibujar los mosaicos en la pantalla y hacer sus cálculos. Como el OP estaba usando una clase completa, hice un ejemplo simple, simple ayuda mucho en el progreso del aprendizaje. Ahora desbloquee mi tema para la densidad de píxeles, por favor, obviamente es un programador que trata de ver esa pregunta con el ojo de un artista de CG. Dado que este sitio también es para CG para juegos afaik.
Madmenyo
2

Existen diferentes técnicas de codificación que podría usar.

RLE: Entonces comienza con una coordenada (x, y) y luego cuenta cuántos mosaicos existen uno al lado del otro (longitud) a lo largo de uno de los ejes. Ejemplo: (1,1,10,5) significaría que a partir de la coordenada 1,1 hay 10 mosaicos uno al lado del otro tipo 5.

La matriz masiva (mapa de bits): cada elemento de la matriz se aferra al tipo de mosaico que reside en esa área.

EDITAR: acabo de encontrar esta excelente pregunta aquí: ¿ Función semilla aleatoria para la generación de mapas?

El generador de ruido Perlin parece ser una buena respuesta.

Sam Axe
fuente
No estoy realmente seguro de que esté respondiendo la pregunta que se le está haciendo, ya que está hablando de codificación (y ruido perlin), y la pregunta parece tratar con problemas de rendimiento.
Thedaian
1
Usando la codificación adecuada (como el ruido perlin), no puede preocuparse por mantener todos esos mosaicos en la memoria a la vez ... en su lugar, simplemente pida a su codificador (generador de ruido) que le diga qué se supone que debe aparecer en una coordenada dada. Aquí hay un equilibrio entre los ciclos de la CPU y el uso de memoria, y un generador de ruido puede ayudar con ese acto de equilibrio.
Sam Axe
2
El problema aquí es que si está creando un juego que permite a los usuarios modificar el terreno de alguna manera, simplemente usando un generador de ruido para "almacenar" esa información no funcionaría. Además, la generación de ruido es bastante costosa, como lo son la mayoría de las técnicas de codificación. Es mejor guardar los ciclos de la CPU para el juego real (física, colisiones, iluminación, etc.) El ruido Perlin es excelente para la generación del terreno, y la codificación es buena para guardar en el disco, pero hay mejores formas de manejar la memoria en este caso.
Thedaian
Muy buena idea, sin embargo, como thedaian, el terreno interactúa con el usuario, lo que significa que no puedo recuperar matemáticamente la información. Veré el ruido del perlin de todos modos, para generar el terreno base.
William Mariager
1

Probablemente debería particionar el mosaico como ya se sugirió. Por ejemplo, con la estructura Quadtree para deshacerse de cualquier procesamiento potencial (por ejemplo, incluso simplemente en bucle) de los mosaicos innecesarios (no visibles). De esta manera, solo procesa lo que podría necesitar procesamiento y aumentar el tamaño del conjunto de datos (mapa de mosaicos) no causa ninguna penalización de rendimiento práctico. Por supuesto, suponiendo que el árbol esté bien equilibrado.

No quiero sonar aburrido ni nada repitiendo lo "viejo", pero al optimizar, siempre recuerde usar las optimizaciones compatibles con su cadena de herramientas / compilador, debe experimentar un poco con ellas. Y sí, la optimización prematura es la raíz de todo mal. Confía en tu compilador, sabe mejor que tú en la mayoría de los casos, pero siempre, siempremida dos veces y nunca confíe en estimaciones aproximadas. No se trata de tener la implementación rápida del algoritmo más rápido siempre que no sepas dónde está el cuello de botella real. Es por eso que debe usar un generador de perfiles para encontrar las rutas más lentas (activas) del código y centrarse en eliminarlas (u optimizarlas). El conocimiento de bajo nivel de la arquitectura de destino a menudo es esencial para exprimir todo lo que el hardware tiene para ofrecer, así que estudie esos cachés de CPU y aprenda qué es un predictor de rama. Vea lo que su perfilador le dice acerca de la memoria caché / rama aciertos / errores. Y como muestra el uso de alguna forma de estructura de datos de árbol, es mejor tener estructuras de datos inteligentes y algoritmos tontos, que al revés. Los datos son lo primero, cuando se trata de rendimiento. :)

zxcdw
fuente
+1 para "la optimización prematura es la raíz de todo mal" Soy culpable de esto :(
thedaian
16
-1 un quadtree? ¿Exagerar un poco? Cuando todos los mosaicos son del mismo tamaño en un juego 2D como este (que son para terrarios), es extremadamente fácil determinar qué rango de mosaicos hay en la pantalla: es solo el extremo superior izquierdo (en la pantalla) azulejos de la esquina inferior derecha.
BlueRaja - Danny Pflughoeft
1

¿No se trata de demasiadas llamadas de sorteo? Si coloca todas las texturas de mosaico de los mapas en una sola imagen: atlas de mosaico, no habrá cambio de textura durante el renderizado. Y si agrupa todos sus mosaicos en una sola malla, se debe dibujar en una llamada de sorteo.

Sobre la publicidad dinámica ... Tal vez el árbol cuádruple no sea una mala idea. Suponiendo que los mosaicos se colocan en hojas y los nodos que no son hojas son mallas en lotes de sus hijos, la raíz debe contener todos los mosaicos en una sola malla. La eliminación de un mosaico requiere actualizaciones de nodos (reorganización de malla) hasta la raíz. Pero en cada nivel de árbol solo hay un cuarto de la malla reencontrada que no debería ser tanto, 4 * tree_height mesh se une?

Ah, y si usa este árbol en el algoritmo de recorte, no siempre representará el nodo raíz, sino algunos de sus elementos secundarios, por lo que ni siquiera tendrá que actualizar / volver a agrupar todos los nodos hasta la raíz, sino hasta el nodo (no hoja). renderizado en este momento.

Solo mis pensamientos, sin código, tal vez sea una tontería.

llegada
fuente
0

@arrival tiene razón. El problema es el código de dibujo. Estás construyendo una matriz de 4 * 3000 + comandos quad de dibujo (más de 24000 comandos de polígono de dibujo ) por cuadro. Luego, estos comandos se procesan y canalizan a la GPU. Esto es bastante malo.

Hay algunas soluciones

  • Renderiza grandes bloques (por ejemplo, tamaño de pantalla) de mosaicos en una textura estática y dibuja en una sola llamada.
  • Use sombreadores para dibujar los mosaicos sin enviar la geometría a la GPU en cada cuadro (es decir, almacene el mapa de mosaicos en la GPU).
Ark-kun
fuente
0

Lo que hay que hacer es dividir el mundo en regiones. La generación de terreno con ruido de Perlin puede usar una semilla común, de modo que incluso si el mundo no está pregenerado, la semilla formará parte del ruido, que se adapta muy bien al terreno más nuevo en las partes existentes. De esta manera, no necesita calcular más de un pequeño búfer antes de la vista de los jugadores a la vez (unas pocas pantallas alrededor de la actual).

En términos de manejo de cosas como plantas que crecen en áreas alejadas de la pantalla actual de los jugadores, puede tener temporizadores, por ejemplo. Estos temporizadores iterarían a través de dichos archivos que almacenan información sobre las plantas, su posición, etc. Simplemente necesita leer / actualizar / guardar los archivos en los temporizadores. Cuando el jugador llega a esas partes del mundo nuevamente, el motor leería los archivos de manera normal y presentaría los datos más recientes de la planta en la pantalla.

Utilicé esta técnica en un juego similar que hice el año pasado, para la cosecha y la agricultura. El jugador podía caminar lejos de los campos, y al regresar, los artículos habían sido actualizados.

Jason Coombes
fuente
-2

He estado pensando en cómo manejar tantos millones de bloques y lo único que se me ocurre es el Patrón de diseño Flyweight. Si no sabe, le sugiero que lea sobre esto: podría ayudar mucho cuando se trata de ahorrar memoria y procesamiento: http://en.wikipedia.org/wiki/Flyweight_pattern

Tiago Frossard
fuente
3
-1 Esta respuesta es demasiado general para ser útil, y el enlace que proporciona no aborda directamente este problema en particular. El patrón Flyweight es una de las muchas formas de administrar eficientemente grandes conjuntos de datos; ¿Podrías explicar cómo aplicarías este patrón en el contexto específico de almacenar fichas en un juego tipo Terraria?
postgoodismo el