Como eles fizeram isso: milhões de peças em Terraria

45

Estou desenvolvendo um mecanismo de jogo semelhante ao Terraria , principalmente como um desafio, e embora tenha descoberto a maior parte, não consigo entender como eles lidam com os milhões de peças interativas / colhíveis o jogo tem ao mesmo tempo. Criar cerca de 500.000 peças, ou seja 1/20 do que é possível em Terraria , no meu mecanismo faz com que a taxa de quadros caia de 60 para cerca de 20, mesmo que eu ainda esteja apenas exibindo as peças. Veja bem, eu não estou fazendo nada com os ladrilhos, apenas mantendo-os na memória.

Atualização : código adicionado para mostrar como eu faço as coisas.

Isso faz parte de uma classe, que lida com os ladrilhos e os desenha. Acho que o culpado é a parte "foreach", que itera tudo, até índices vazios.

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

Também aqui está o método Tile.Draw, que também pode ser uma atualização, pois cada Tile usa quatro chamadas para o método SpriteBatch.Draw. Isso faz parte do meu sistema de autotiling, o que significa desenhar cada canto, dependendo dos ladrilhos vizinhos. texture_ * são Retângulos, são definidos uma vez na criação do nível, não em cada atualização.

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

Qualquer crítica ou sugestão ao meu código é bem-vinda.

Atualização : Solução adicionada.

Aqui está o método Level.Draw final. O método Level.TileAt simplesmente verifica os valores inseridos, para evitar exceções 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
fonte
2
Você está absolutamente certo de que está apenas processando o que está na visão da câmera, o que significa o código para determinar o que processar correto?
Cooper
5
O framerrate cai de 60 para 20 fps, apenas por causa da memória alocada? Isso é muito improvável, deve haver algo errado. Que plataforma é essa? O sistema está trocando memória virtual para disco?
Maik Semder
6
@ Drackir Nesse caso, eu diria que é errado se houver uma classe de blocos, uma matriz de inteiros de comprimento adequado deve ser, e quando houver meio milhão de objetos, a sobrecarga de OO não é brincadeira. Suponho que seja possível fazer objetos, mas qual seria o objetivo? Uma matriz inteira é simples de manusear.
Aaaaaaaaaaaa
3
Ai! Iterando todas as peças e chamando Draw quatro vezes em cada uma que estiver à vista. Há definitivamente algumas melhorias possíveis aqui ....
thedaian
11
Você não precisa de todo o particionamento sofisticado mencionado abaixo para exibir apenas o que está em exibição. É um mapa de blocos. Já está particionado em uma grade regular. Apenas calcule o bloco na parte superior esquerda da tela e na parte inferior direita e desenhe tudo nesse retângulo.
Blecki

Respostas:

56

Você está percorrendo todos os 500.000 blocos ao renderizar? Nesse caso, isso provavelmente causará parte dos seus problemas. Se você percorrer meio milhão de blocos ao renderizar e meio milhão ao executar a marcação 'update' neles, estará percorrendo um milhão de blocos cada quadro.

Obviamente, existem maneiras de contornar isso. Você pode executar seus ticks de atualização enquanto também renderiza, economizando metade do tempo gasto percorrendo todos esses blocos. Mas isso une seu código de renderização e seu código de atualização em uma única função e geralmente é uma IDEIA RUIM .

Você pode acompanhar os blocos que estão na tela e apenas percorrer (e renderizar) esses. Dependendo de coisas como o tamanho dos ladrilhos e o tamanho da tela, isso pode reduzir facilmente a quantidade de ladrilhos que você precisa percorrer, economizando bastante tempo de processamento.

Finalmente, e talvez a melhor opção (a maioria dos grandes jogos mundiais faça isso), é dividir seu terreno em regiões. Divida o mundo em pedaços de, digamos, blocos de 512x512 e carregue / descarregue as regiões à medida que o jogador se aproxima ou se afasta de uma região. Isso também evita que você precise percorrer blocos distantes para executar qualquer tipo de 'atualização'.

(Obviamente, se seu mecanismo não executar nenhum tipo de atualização nos blocos, você poderá ignorar a parte dessas respostas que menciona isso.)

thedaian
fonte
5
A parte da região parece interessante, se bem me lembro, é assim que o minecraft faz, no entanto, não funciona com a evolução do terreno em Terraria, mesmo que você não esteja nem perto, como grama se espalhando, cactos crescendo e coisas assim. Editar : a menos que, é claro, eles apliquem o tempo decorrido desde a última vez em que a região estava ativa e executam todas as alterações que teriam acontecido naquele período. Isso pode realmente funcionar.
William Mariager
2
O Minecraft definitivamente usa regiões (e os últimos jogos da Ultima fizeram, e tenho certeza que muitos dos jogos da Bethesda o fazem). Tenho menos certeza de como Terraria lida com o terreno, mas eles provavelmente aplicam o tempo decorrido a uma "nova" região ou armazenam o mapa inteiro na memória. Este último exigiria um alto uso de RAM, mas a maioria dos computadores modernos poderia lidar com isso. Pode haver outras opções que não foram mencionadas também.
Thedaian
2
@MindWorX: Fazer todas as atualizações quando recarregadas nem sempre funciona - suponha que você tenha um monte de área árida e depois grama. Você vai embora por séculos e depois caminha em direção à grama. Quando o bloco com a grama carrega, ele alcança e se espalha naquele bloco, mas não se espalha pelos blocos mais próximos que já estão carregados. Porém, essas coisas progridem MUITO mais devagar que o jogo - verifique apenas um pequeno subconjunto dos blocos em qualquer ciclo de atualização e você poderá dar vida a terrenos distantes sem carregar o sistema.
Loren Pechtel 5/08
1
Como alternativa (ou suplemento) a "recuperar o atraso" quando uma região se aproxima do player, você pode fazer uma simulação separada repetindo cada região distante e atualizando-a em uma taxa mais lenta. Você pode reservar um tempo para cada quadro ou executá-lo em um encadeamento separado. Por exemplo, você pode atualizar a região em que o player se encontra, mais as 6 regiões adjacentes a cada quadro, mas também atualizar 1 ou 2 regiões extras.
Lewis Wakeford
1
Para quem se pergunta, a Terraria armazena todos os dados do bloco em uma matriz 2D (o tamanho máximo é 8400x2400). E, em seguida, usa algumas matemáticas simples para decidir qual seção de blocos a ser renderizada.
FrenchyNZ
4

Eu vejo um grande erro aqui não tratado por nenhuma das respostas. Claro que você nunca deve desenhar e iterar sobre mais peças, então você também precisa. O que é menos óbvio é como você define os ladrilhos. Como posso ver, você fez uma aula de ladrilhos, eu sempre fazia isso também, mas é um grande erro. Você provavelmente tem todos os tipos de funções nessa classe e isso cria muito processamento desnecessário.

Você deve apenas repetir o que é realmente necessário para processar. Então pense no que você realmente precisa para os ladrilhos. Para desenhar, você precisa apenas de uma textura, mas não deseja iterar sobre uma imagem real, pois essas são grandes para serem processadas. Você pode simplesmente criar um int [,] ou mesmo um byte não assinado [,] (se você não espera mais que 255 texturas de bloco). Tudo o que você precisa fazer é percorrer essas pequenas matrizes e usar uma opção switch ou if para desenhar a textura.

Então, o que você precisa atualizar? O tipo, a saúde e os danos parecem suficientes. Tudo isso pode ser armazenado em bytes. Então, por que não criar uma estrutura como esta para o loop de atualização:

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

Você pode usar o tipo para desenhar o bloco. Assim, você pode desanexar esse (criar uma matriz própria) da estrutura para não iterar nos campos desnecessários de saúde e dano no loop de desenho. Para fins de atualização, você deve considerar uma área mais ampla do que apenas sua tela, para que o mundo do jogo pareça mais vivo (as entidades mudam de posição fora da tela), mas para o desenho das coisas, você só precisa do bloco visível.

Se você mantiver a estrutura acima, serão necessários apenas 3 bytes por bloco. Portanto, para fins de economia e memória, isso é ideal. Para velocidade de processamento, não importa realmente se você usa int ou byte, ou mesmo int longo, se tiver um sistema de 64 bits.

Madmenyo
fonte
1
Sim, iterações posteriores do meu mecanismo evoluíram para usar isso. Principalmente para reduzir o consumo de memória e aumentar a velocidade. Os tipos ByRef são lentos em comparação com uma matriz preenchida com estruturas ByVal. No entanto, é bom que você tenha adicionado isso à resposta.
precisa
1
Sim, deparei com ele enquanto procurava alguns algoritmos aleatórios. Percebi imediatamente que você estava usando sua própria classe de blocos no seu código. É um erro muito comum quando você é novo. É bom ver que você ainda está ativo desde que você publicou isso há 2 anos.
Madmenyo
3
Você não precisa de um healthou de outro damage. Você pode manter um pequeno buffer dos locais de ladrilhos escolhidos mais recentemente e os danos em cada um. Se um novo bloco for selecionado e o buffer estiver cheio, retire o local mais antigo dele antes de adicionar o novo. Isso limita o número de peças que você pode extrair por vez, mas há um limite intrínseco para isso (de qualquer maneira #players * pick_tile_size). Você pode manter essa lista por jogador, se isso facilitar. Tamanho faz questão de velocidade; tamanho menor significa mais blocos em cada cache da CPU.
Sean Middleditch
@SeanMiddleditch Você está certo, mas esse não era o ponto. O objetivo era parar e pensar no que você realmente precisa para desenhar as peças na tela e fazer seus cálculos. Como o OP estava usando uma classe inteira, fiz um exemplo simples, o simples ajuda muito no progresso da aprendizagem. Agora, desbloqueie meu tópico sobre densidade de pixels, por favor, você é obviamente um programador que tenta encarar essa pergunta com o olhar de um artista de computação gráfica. Uma vez que este site também é para CG para jogos afaik.
Madmenyo 12/01
2

Existem diferentes técnicas de codificação que você pode usar.

RLE: Então você começa com uma coordenada (x, y) e conta quantos blocos iguais existem lado a lado (comprimento) ao longo de um dos eixos. Exemplo: (1,1,10,5) significaria que, a partir da coordenada 1,1, existem 10 blocos lado a lado do tipo 5.

A matriz massiva (bitmap): cada elemento da matriz se apega ao tipo de bloco que reside nessa área.

Edição: Acabei de encontrar esta excelente pergunta aqui: Função de semente aleatória para geração de mapas?

O gerador de ruído Perlin parece ser uma boa resposta.

Sam Axe
fonte
Não tenho certeza se você está respondendo à pergunta que está sendo feita, já que você está falando sobre codificação (e ruído permanente), e a pergunta parece lidar com problemas de desempenho.
Thedaian
1
Usando a codificação adequada (como ruído perlin), você não pode se preocupar em manter todos esses blocos na memória de uma só vez. Em vez disso, basta pedir ao seu codificador (gerador de ruído) para lhe dizer o que deve aparecer em uma determinada coordenada. Há um equilíbrio aqui entre os ciclos da CPU e o uso de memória, e um gerador de ruído pode ajudar com esse ato de equilíbrio.
Sam Ax
2
A questão aqui é que, se você estiver criando um jogo que permita aos usuários modificar o terreno de alguma forma, basta usar um gerador de ruído para "armazenar" essas informações. Além disso, a geração de ruído é bastante cara, assim como a maioria das técnicas de codificação. É melhor salvar os ciclos da CPU para coisas reais de jogo (física, colisões, iluminação etc.). O ruído Perlin é ótimo para a geração de terrenos e a codificação é boa para salvar em disco, mas há maneiras melhores de lidar com a memória nesse caso.
Thedaian
Ótima idéia, no entanto, como a thedaiana, o terreno é interagido pelo usuário, o que significa que não consigo recuperar matematicamente as informações. De qualquer forma, examinarei o ruído permanente, para gerar o terreno base.
William Mariager
1

Você provavelmente deve particionar o mapa de mosaico, conforme já sugerido. Por exemplo, com a estrutura Quadtree, para se livrar de qualquer processamento em potencial (por exemplo, mesmo fazendo um loop) dos blocos desnecessários (não visíveis). Dessa forma, você processa apenas o que pode ser necessário processar e aumentar o tamanho do conjunto de dados (mapa de blocos) não causa nenhuma penalidade de desempenho prático. Claro, assumindo que a árvore esteja bem equilibrada.

Não quero parecer aborrecido ou algo assim repetindo o "antigo", mas ao otimizar, lembre-se sempre de usar as otimizações suportadas pelo seu conjunto de ferramentas / compilador, você deve experimentar um pouco. E sim, a otimização prematura é a raiz de todo mal. Confie no seu compilador, ele sabe melhor do que você na maioria dos casos, mas sempre, sempremeça duas vezes e nunca dependa de estimativas. Não se trata de ter a rápida implementação do algoritmo mais rápido, desde que você não saiba onde está o gargalo real. É por isso que você deve usar um criador de perfil para encontrar os caminhos mais lentos (quentes) do código e se concentrar em eliminá-los (ou otimizá-los). O conhecimento de baixo nível da arquitetura de destino geralmente é essencial para extrair tudo o que o hardware tem a oferecer; portanto, estude esses caches de CPU e aprenda o que é um preditor de ramificação. Veja o que seu criador de perfis diz sobre acertos / erros de cache / ramificação. E, como mostra alguma forma de estrutura de dados em árvore, é melhor ter estruturas de dados inteligentes e algoritmos burros do que o contrário. Os dados vêm em primeiro lugar, quando se trata de desempenho. :)

zxcdw
fonte
+1 para "otimização prematura é a raiz de todo mal" Eu sou culpado desta :(
thedaian
16
-1 um quadtree? Exagerar um pouco? Quando todas as peças têm o mesmo tamanho em um jogo 2D como este (que são para terraria), é extremamente fácil descobrir qual o conjunto de peças na tela - é apenas o canto superior esquerdo (na tela) para o ladrilhos inferior direito.
BlueRaja # Danny Pflughoeft
1

Não se trata de muitas chamadas de empate? Se você colocar todas as texturas de mosaico de seus mapas em um único atlas de mosaico de imagem, não haverá troca de textura durante a renderização. E se você agrupar todas as peças em uma única Malha, ela deverá ser sorteada em uma única chamada.

Sobre o anúncio dinâmico ... Talvez o quad tree não seja uma má idéia. Supondo que os ladrilhos estejam sendo colocados em folhas e os nós que não são folhas são apenas malhas em lotes de suas crianças, a raiz deve conter todos os ladrilhos em lotes em uma malha. A remoção de um bloco requer atualizações de nós (reinicialização de malha) até a raiz. Mas em todo nível de árvore, existe apenas 1/4 da malha rebatida, o que não deve ser tanto, uma malha de 4 * árvores-altura se une?

Ah, e se você usar essa árvore no algoritmo de recorte, você renderizará nem sempre o nó raiz, mas alguns de seus filhos, portanto, você nem precisa atualizar / reiniciar todos os nós até a raiz, mas até o nó (sem folha) você é renderização no momento.

Apenas meus pensamentos, sem código, talvez sem sentido.

chegada
fonte
0

@arrival está certo. O problema é o código do sorteio. Você está construindo uma matriz de 4 * 3000 + comandos quad de desenho (mais de 24000 comandos de polígono de desenho ) por quadro. Em seguida, esses comandos são processados ​​e canalizados para a GPU. Isso é muito ruim.

Existem algumas soluções.

  • Transforme grandes blocos (por exemplo, tamanho da tela) de blocos em uma textura estática e desenhe-os em uma única chamada.
  • Use shaders para desenhar os blocos sem enviar a geometria para a GPU a cada quadro (por exemplo, armazene o mapa de blocos na GPU).
Ark-kun
fonte
0

O que você precisa fazer é dividir o mundo em regiões. A geração de terreno com ruído Perlin pode usar uma semente comum, de modo que, mesmo que o mundo não seja pré-gerado, a semente fará parte do ruído, que agrada agradavelmente o terreno mais recente nas partes existentes. Dessa forma, você não precisa calcular mais do que um pequeno buffer antes da visualização dos jogadores por vez (algumas telas ao redor da atual).

Em termos de manipulação de coisas como plantas que crescem em áreas distantes da tela atual dos jogadores, você pode ter temporizadores, por exemplo. Esses temporizadores iterariam através de arquivos digitados que armazenam informações sobre as plantas, sua posição etc. Você simplesmente precisa ler / atualizar / salvar os arquivos nos temporizadores. Quando o jogador alcança essas partes do mundo novamente, o mecanismo lê os arquivos normalmente e apresenta os dados mais recentes da planta na tela.

Eu usei essa técnica em um jogo semelhante que fiz no ano passado, para colheita e agricultura. O jogador podia andar longe dos campos e, ao retornar, os itens haviam sido atualizados.

Jason Coombes
fonte
-2

Eu estive pensando em como lidar com tantos zilhões de blocos e a única coisa que me vem à cabeça é o Flyweight Design Pattern. Se você não souber, sugiro profundamente que leia sobre isso: pode ajudar muito quando se trata de economizar memória e processamento: http://en.wikipedia.org/wiki/Flyweight_pattern

Tiago Frossard
fonte
3
-1 Esta resposta é geral demais para ser útil, e o link que você fornece não aborda diretamente esse problema específico. O padrão Flyweight é uma das muitas, muitas maneiras de gerenciar grandes conjuntos de dados com eficiência; você poderia explicar como aplicaria esse padrão no contexto específico de armazenamento de peças em um jogo semelhante ao Terraria?
postgoodism