O PlayKids é uma plataforma digital com conteúdos educativos para crianças que possui versões para Android e iOS.. Há diversos tipos de conteúdos, como vídeos, livros e jogos educativos, mas nesse artigo iremos focar nos jogos, especificamente em um deles.

Sempre procuramos desenvolver novidades para o aplicativo  e recentemente adicionamos um jogo com mecânica de Voxel, em que as crianças podem navegar pelo mundo e encaixar blocos como uma espécie de  lego virtual. Iremos apresentar de forma breve a motivação na escolha da mecânica e falar sobre alguns dos desafios técnicos e otimizações por trás da engine.

Motivação

O PlayKids já possui um playground de mini games com diversos jogos: livro de colorir, quebra cabeças, piano, etc. Analisando os dados do produto, pudemos perceber que o livro de colorir, por ampla vantagem, era o jogo mais acessado pelas crianças. A principal diferença dele para os outros jogos está na mecânica: ele é um game sandbox, isto é, um jogo “aberto”, sem fim ou objetivo explícito, no qual a criança pode exercer sua criatividade livremente. Esse tipo de mecânica tende a gerar mais engajamento do usuário, resultando em maior tempo de sessão e sendo menos enjoativo ao longo do tempo.

Basicamente, os jogos mais famosos que se enquadram nessa categoria são: Sims, MMORPGS e  aqueles que o usuário pode alterar o cenário do mundo. Atualmente, os mais procurados são os similares à um lego virtual, em que o jogador possui diversos tipos de blocos à sua disposição, moldando o mundo como quiser.

Captura de Tela 2018-07-17 às 19.08.18.png

Figura 1 – Voxel PlayKids

Por essas razões, resolvemos incluir um mini game com mecânica Voxel dentro do PlayKids, desenvolvido especialmente para crianças na faixa de 3 a 7 anos[1].

Desafios e otimizações da Voxel engine

À primeira vista, uma Voxel engine com operações de inserir/remover cubos, parece algo bastante simples de se fazer, porém o problema está nos detalhes e na escala. Utilizamos a Unity3D para implementar nossa Voxel engine, mas focaremos nos problemas mais genéricos, aplicáveis a quaisquer plataformas.

Otimizações de rendering

A base de uma Voxel engine é uma primitiva extremamente simples: cubo. Um cubo, em computação gráfica, é representado por:

  • 6 faces;
  • Cada face do cubo possui 4 vértices;
  • Cada vértice possui:
    • Vetor3D de posição (X, Y, Z);
    • Vetor3D de direção de vetor normal (X, Y, Z);
    • Vetor3D de cor (R, G, B);
    • Vetor2D de coordenada de textura UV (X, Y);
  • Cada coordenada dos vetores é um float (32 bits)

figura 2

Figura 2 – Elementos que compõem um cubo [2]

Dessa forma cada cubo precisa de: 6x4x(3+3+3+2)x32 = 8488 bits ≈ 1kb de memória.

No caso do PlayKids, até pela faixa etária dos nossos usuários, usamos um mundo de dimensões reduzidas para os padrões de jogos Voxel: 32 blocos Altura x 192 de largura x 192 de profundidade = 1179648 blocos

Se armazenarmos todos os blocos de maneira simples precisaríamos de 1GB de memória. Por se tratar de um aplicativo para dispositivos móveis, não podemos contar com essa quantidade de memória para usarmos só para nossa engine. Além disso, o Voxel é um mini game dentro do PlayKids, precisando coexistir com as outras funcionalidades e serviços do aplicativo.

Só que além da memória, essa quantidade de blocos causaria problemas também na GPU. Cada cubo é formado por 6 faces e cada face é formada por 2 triângulos, resultando em 12 triângulos por cubo para serem renderizados. Para um mundo do tamanho referido anteriormente, isso resultaria em aproximadamente 14 milhões de triângulos e cerca de 1 milhão de draw calls (1 chamada para a API de rendering / triângulo) [3], números toleráveis num desktop mid/high end, porém proibitivo para um dispositivo móvel.

Nossa solução para esse problema é criar uma malha simplificada que renderize os mesmos cubos que seriam visualizados, caso utilizássemos todos os triângulos dos cubos. A figura 3 representa um corte no qual podemos ver como transformar a malha de cubos numa malha simplificada:

figura 3

Figura 3- Diferença nas malhas enviadas para a GPU: (a) usando blocos (912 triângulos); (b) com malha simplificada (39 triângulos)

No primeiro reticulado temos 76 cubos criados, o que resultaria em 912 triângulos para serem renderizados. Consideremos agora a seguinte otimização: nem todos os blocos existentes são visíveis. Os blocos “internos”, isto é, aqueles que não possuem nenhuma face em contato com o ar, não podem ser vistos, a menos que o usuário remova/insira novos blocos. Dessa forma o segundo reticulado, no qual temos 39 triângulos e 78 vértices, reduzindo drasticamente a quantidade de memória e o número de primitivas necessárias para renderizar a mesma quantidade de blocos.

Resolvido o problema de memória e número de primitivas ainda nos resta resolver o problema de draw calls. Uma solução possível é, ao invés de enviar cubos ou triângulos como malhas separadas para a GPU, criar uma única malha gigante para o mundo. Isso, porém, não é uma boa solução uma vez que nosso mundo não é estático. Se criarmos uma única malha gigante, as operações de edição irão gerar um gargalo de CPU, pois será necessário recriar e reenviar toda a malha para a GPU, resultando em stalls de CPU por alguns frames, como podemos ver na figura abaixo:

figura 4

Figura 4- Stall de CPU em operação de edição (criação/destruição) de bloco

Esse problema foi solucionado agrupando as malhas em chunks de 8x8x8 blocos cada. O valor foi obtido empiricamente testando nos devices mais comuns, sendo que esse foi o valor que apresentou uma das melhores razões entre a quantidade de draw calls e a quantidade de vértices modificados nas operações de edição.

figura 5
Figura 5 – Exemplo de divisão de chunks no mundo Voxel

Otimizações baixo nível

Anteriormente tratamos da renderização dos cubos. Precisamos, entretanto, de uma estrutura de dados que nos permita representar o mundo em memória RAM, contendo informações sobre os blocos como o tipo, iluminação (será tratada separadamente em um outro artigo) e algumas informações extras para otimizar a velocidade de algumas operações nos blocos. Dessa forma, para o nosso mundo, vejamos a estrutura de blocos na figura 6:

figura 6

Figura 6 – Classe bloco: a mais enxuta possível

Atenção especial para o uso de byte e short a fim de temos que ter a estrutura a mais enxuta possível, caso contrário iríamos novamente incorrer em problemas de memória. Ao invés de armazenar informações de bloco como por exemplo:

  • Trata-se de um bloco sólido ou indestrutível?
  • Mapeamento de textura UV do bloco

Criamos estruturas a parte que contém essas informações e podem ser acessadas por métodos como na figura 7:

figura 7

Figura 7 – Roteadores de chamadas dentro da classe block

Isso faz com que evitemos armazenar informações redundantes na nossa estrutura de blocos, reduzindo ainda mais a quantidade de memória necessária para armazenar os blocos.

Na nossa estrutura indexamos os blocos nos chunks e indexamos os chunks no mundo. As operações de criar, carregar, salvar o mundo e edição nos blocos, exige vários acessos que não conseguem se beneficiar das variáveis extras _wx, _wy, _wz (posição do bloco no mundo), exigindo conversões para acessar as estruturas. Como a quantidade de blocos é muito grande, algumas otimizações de baixo nível fazem sentido como, por exemplo, trocar operações de divisão por operações bitwise. Por isso utilizamos o tamanho dos chunks como potência de 2. A figura 8 ilustra um exemplo da troca de uma divisão com um denominador potência de 2, por um shift equivalente:

figura 8

Figura 8 – Trocando operações de divisão por shift

A figura 9 mostra uma tabela que pode ser usada para estimarmos a ordem de grandeza das operações aritméticas simples:

figura 9

Figura 9 – Tabela mostrando o tempo médio da execução de várias instruções aritméticas em C# [4]

Podemos notar que comparada à operação de divisão, a operação de shift é cerca de 16 vezes mais rápida. Em situações comuns não há tanta diferença de performance, mas nas operações de carregar e salvar mundo, em que todos os blocos são acessados, a simples troca da divisão pela operação bitwise resultou numa melhora de 27,5% no tempo de loading inicial do mundo (não estamos afirmando que não houve melhora nas operações de remover/criar blocos, principalmente em Androids low end, mas preferimos focar no tempo de loading, pois se trata do pior caso).

Outra questão interessante se refere ao uso de Jagged Arrays vs Multidimensionals Arrays. Na figura abaixo podemos ver o exemplo de ambos tipos de código:

  • Jagged array: int [][] array
  • Multidimensional array: int[,] array

A segunda forma é considerada mais elegante, porém a figura 10 nos mostra que o código assembly gerado para a versão com Multidimensional Array possui uma instrução de call. Essa instrução deixa de ser desprezível quando estamos iterando numa quantidade de blocos dessa ordem de magnitude, sendo que a troca de Multidimensional Arrays por Jagged Arrays resultou numa melhora de 19,3% no tempo de loading.[5]

figura 10

Figura 10 – Código assembly gerado com o uso de Multidimensional Arrays vs Jagged Arrays

Melhorar a forma com que acessávamos nossas estruturas também teve impacto significativo para nossa performance. Nossa indexação de blocos requer uma conversão, que apesar de barata, se torna problemática quando iteramos sobre essa quantidade de blocos. Por isso, a ordem com que fazíamos algumas operações tinha que ser bem cuidadosa. A figura 11 ilustra exemplos de como podemos aproveitar a conversão realizada na indexação sem redundância:

figura 11

Figura 11 – Troca de ordem das operações nos faz usar acessor menos vezes

Na primeira chamada fazemos 3 referências redundantes ao acessor, fazendo com que tenhamos que fazer 3 conversões desnecessárias. Ao modificar o código da primeira função para o da 2ª ou 3ª chamada, passamos a fazer somente uma conversão, tornando o código mais eficiente.

Nas partes mais críticas do código também evitamos fazer alocações de variáveis que só seriam usadas dentro de métodos, a fim de evitar oscilações de performance devido ao garbage collector. Na figura 12 podemos ver um exemplo de uma dessas chamadas. Note que no primeiro caso temos uma variável estática que é alocada somente uma vez durante todo o ciclo de vida do mini game. Apesar disso ser contrário às boas práticas de engenharia de software, se faz bastante útil em casos como esse, em que podem haver muitas chamadas à essa função, poupando assim várias alocações e desalocações de memória desnecessárias.

figura 12

Figura 12 – Uso de variável estática na classe ao invés de variável de método

Dicionários e generics foram os últimos pontos de otimização que precisamos alterar na nossa Voxel engine. Apesar do acesso a elementos de um dicionário ser de complexidade média O(1) é necessário fazer o cálculo de uma função de hash[6], que normalmente envolve várias operações de multiplicação e soma. Foi necessária a troca por um bloco de switch, que troca o cálculo da função de hash por uma jump table (o compilador não converte um bloco de switch em uma jump table em todos os casos), trocando as operações aritméticas complexas por uma simples instrução de jump. A figura 13 ilustra dois blocos de código distintos: o primeiro usando uma implementação com dicionários e o segundo com uma implementação usando bloco de switch.

figura 13

Figura 13 – Trocando o uso de dicionários por bloco de switch

No caso dos generics, a diferença foi medida de forma empírica, uma vez que o código assembly gerado para as duas chamadas possui apenas algumas operações de pilha a mais que a versão não generic. Além disso, também removemos a chamada de acessor usada pelo singleton por uma variável estática, a fim de eliminar o uso do acessor. Normalmente os getters são inlined, mas pudemos observar diferenças de performance na prática.

figura 14

Figura 14 – Removendo o uso a generics e ao getter

Essas outras otimizações resultaram numa melhora de 11,3% na performance do loading:

  • Troca de ordem para reduzir quantidade de referências ao acessor;
  • Usar variável estática de classe;
  • Remover acesso ao generics e getter

Conclusão

Apresentamos aqui as otimizações mais genéricas em relação à renderização dos blocos e de código que pudemos realizar. Outras otimizações, com percentual de melhor até maior, comparadas às apresentadas, foram omitidas por serem muito específicas para o nosso projeto. O algoritmo de criação de malhas/colliders dos blocos foi responsável em melhorar praticamente 50% do resultado. Dessa forma, a principal métrica impactada foi o tempo de loading:

  • V1: tempo de loading médio de 51s e 48% dos usuários desistiram no meio do loading;
  • V2: tempo de loading médio de 8s e 25% dos usuários desistiram no meio do loading;
  • V3: tempo de loading médio de 2s e 12% dos usuários desistiram no meio do loading;

Podemos observar que o impacto de tais otimizações no produto foi essencial: passamos de uma taxa de desistência de 47% para 12%, graças ao tempo de loading que caiu de 51s na primeira iteração para 2s na última. As porcentagens individuais das otimizações mostradas culminaram em porcentagens acumuladas, por isso chegamos a esse resultado expressivo.

Logo, em casos de extrema escala como numa Voxel engine, temos que abandonar algumas boas práticas e focar na performance, fazendo com que nosso produto tenha melhor retenção e usabilidade por parte dos usuários.

Lembrando que a máxima faça primeiro, otimize depois continua valendo. Nossas primeiras versões nos permitiram testar a aceitação do Voxel e, a partir dos gargalos encontrados, como o número de usuários que desistiram no meio do processo de loading, pudemos decidir melhor em que trechos investir em desenvolvimento. Obviamente quanto mais otimizado o código foi ficando, mais difícil e caro ia ficando conseguir extrair mais performance, cabendo ao desenvolvedor decidir se vale a pena e se o esforço necessário vai resultar em impactos significativos para o seu projeto.

Créditos: Caio Verinaud, Charles Barros e Pedro Almeida

Referências

  1. https://playkids.blog/pt/voxel-jogo-educativo/
  2. https://en.wikipedia.org/wiki/Polygon_mesh
  3. https://docs.unity3d.com/Manual/DrawCallBatching.html
  4. https://msdn.microsoft.com/en-us/library/ms973852.aspx
  5. https://docs.unity3d.com/560/Documentation/Manual/BestPracticeUnderstandingPerformanceInUnity8.html
  6. https://en.wikipedia.org/wiki/Hash_table

 

Posted by:Pedro Almeida

One thought on “Desenvolvimento de uma Voxel Engine no PlayKids

Deixe seu comentário