Preferências de dados¶

Já se perguntou se devemos abordar o problema X com a estrutura de dados Y ou Z? Este artigo cobre uma variedade de tópicos relacionados a esses dilemas.

Nota

Este artigo faz referência a operações "[algo]-tempo". Esta terminologia vem da análise de algoritmos do Big O Notation.

Resumindo, ele descreve o pior cenário de duração do tempo de execução. Em termos leigos:

"À medida que o tamanho de um domínio problemático aumenta, o comprimento de execução do algoritmo..."

Tempo constante, O(1)``O(1): "...não aumenta."
Tempo logarítmico, O(log n): "... aumenta em uma taxa lenta."
Tempo linear, O(n): "... aumenta na mesma taxa."
Etc.

Imagine se fosse necessário processar 3 milhões de pontos de dados em um único quadro. Seria impossível criar o recurso com um algoritmo de tempo linear, pois o tamanho dos dados aumentaria o tempo de execução muito além do tempo alocado. Em comparação, o uso de um algoritmo de tempo constante pode lidar com a operação sem problemas.

Em geral, os desenvolvedores desejam evitar o envolvimento em operações de tempo linear o máximo possível. Mas, se mantivermos a escala de uma operação de tempo linear pequena e se não for necessário realizar a operação com frequência, isso pode ser aceitável. Equilibrar esses requisitos e escolher o algoritmo / estrutura de dados certa para o trabalho é parte do que torna as habilidades dos programadores valiosas.

Array vs. Dicionário vs. Objeto¶

O Godot armazena todas as variáveis na API de scripting na classe Variant <https://docs.godotengine.org/en/latest/development/cpp/variant_class.html> _. As variantes podem armazenar estruturas de dados compatíveis com Variant, como Array e Dictionary, bem como Object.

O Godot implementa o Array como um Vector<Variant>. O motor armazena o conteúdo do Array em uma seção contígua da memória, ou seja, eles estão em uma fileira adjacente um ao outro.

Nota

Para aqueles não familiarizados com C++, um Vetor é o nome do objeto Array em bibliotecas C++ tradicionais. É um tipo "modelado", o que significa que seus registros podem conter apenas um tipo particular (denotado por brackets angulares). Então, por exemplo, um PoolStringArray seria algo como um Vector<String>.

Armazenamentos de memória contígua implicam no seguinte desempenho de operação:

Iterar: O mais rápido. Ótimo para loops.
- Op: Tudo que ele faz é incrementar um contador para chegar ao próximo registro.
Inserir, Apagar, Mover: Dependente da posição. Geralmente lento.
- Op: Adicionar/remover/mover conteúdo envolve mover os registros adjacentes (para criar espaço / preencher espaço).
- Adicionar/remover rapidamente do final.
- Adicionar/remover lentamente de uma posição arbitrária.
- Adicionar/remover mais devagar da frente.
- Se fizer muitas inserções/remoções da frente, então...
  inverta o array.
  
  faça um loop que executa as mudanças do Array no final.
  
  reinverta o array.
  Isto faz apenas duas cópias do array (tempo ainda constante, mas lento) em comparação com a cópia de cerca de 1/2 do array, em média, N vezes (tempo linear).
Get, Set: Mais rápido por posição. Ex. pode solicitar 0º, 2º, 10º registro, etc. mas não pode especificar qual registro você deseja.
- Op: 1 operação de adição desde a posição de início do array até o índice desejado.
Find: O mais lento. Identifica o índice/posição de um valor.
- Op: Deve iterar através de array e comparar valores até encontrar uma correspondência.
  O desempenho também depende da necessidade de uma busca exaustiva.
- Se mantidas em ordem, as operações de busca personalizadas podem levar ao tempo logarítmico (relativamente rápido). Os usuários leigos não ficarão confortáveis com isso. Feito reordenando o Array após cada edição e escrevendo um algoritmo de busca com reconhecimento ordenado.

O Godot implementa o Dicionário como um OrderedHashMap<Variant, Variant>`. O motor armazena um pequeno array (inicializado a 2^3 ou 8 registros) de pares de valor-chave. Quando se tenta acessar um valor, eles fornecem uma chave. Ele então hasha a chave, ou seja, converte-a em um número. O "hash" é usado para calcular o índice para o array. Como um array, o OHM então tem uma rápida procura dentro da "tabela" de chaves mapeadas para valores. Quando o HashMap fica muito cheio, ele aumenta para a próxima potência de 2 (assim, 16 registros, depois 32, etc.) e reconstrói a estrutura.

Os hashes são para reduzir a chance de uma colisão de chave. Se ocorrer, a tabela deve recalcular outro índice para o valor que leva em conta a posição anterior. Ao todo, isto resulta em acesso constante a todos os registros em detrimento da memória e de alguma eficiência operacional menor.

Hashear cada chave um número arbitrário de vezes.
- Operações de hash são constantes, portanto, mesmo se um algoritmo precisar fazer mais de um, desde que o número de cálculos de hash não se torne muito dependente da densidade da tabela, as coisas permanecerão rápidas. O que leva a...
Fazendo a manutenção de um tamanho cada vez maior para a tabela.
- HashMaps mantêm lacunas de memória não utilizada intercaladas na tabela de propósito para reduzir as colisões de hash e manter a velocidade dos acessos. É por isso que aumenta constantemente de tamanho quadraticamente em potências de 2.

Como se pode notar, os Dicionários se especializam em tarefas que os Arrays não fazem. Uma visão geral de seus detalhes operacionais é a seguinte:

Iterate: Rápido.
- Op: Itere sobre o vetor interno de hashes do mapa. Retorne cada chave. Depois, os usuários usam a tecla para pular e retornar o valor desejado.
Inserir, Apagar, mover: O mais rápido.
- Op: Hasheia a chave fornecida. Faça 1 operação de adição para pesquisar o valor apropriado (início do array + deslocamento). Mover é dois deles (um inserir, um apagar). O mapa deve fazer alguma manutenção para preservar suas capacidades:
  atualizar Lista encomendada de registros.
  
  determinar se a densidade da tabela exige a ampliação da capacidade da tabela.
- O Dicionário lembra em que ordem os usuários inseriram suas chaves. Isso permite que ele execute iterações confiáveis.
Get, Set: Mais rápido. O mesmo que uma pesquisa por chave.
- Op: O mesmo que inserir/apagar/mover.
Find: Mais lento. Identifica a chave de um valor.
- Op: Deve iterar através de registros e comparar o valor até que uma correspondência seja encontrada.
- Observe que o Godot não fornece este funcionalidade de forma imediata (porque eles não foram feitos para essa tarefa).

O Godot implementa Objetos como recipientes estúpidos, mas dinâmicos, de conteúdo de dados. Objetos consultam fontes de dados quando são feitas perguntas. Por exemplo, para responder à pergunta, "você tem uma propriedade chamada, 'posição'?", ele pode perguntar a sua script ou a ClassDB. É possível encontrar mais informações sobre o que são objetos e como eles funcionam no artigo Aplicando princípios de orientação a objetos em Godot.

O detalhe importante aqui é a complexidade da tarefa do Objeto. Cada vez que ele executa uma destas consultas multi-fonte, ele passa por vários loops de iteração e pesquisas de HashMap. Além disso, as consultas são operações de tempo linear dependentes do tamanho da hierarquia de herança do Objeto. Se a classe que o Objeto consulta (sua classe atual) não encontra nada, a solicitação adia para a próxima classe base, até a classe Objeto original. Embora estas sejam cada uma das operações rápidas isoladamente, o fato de que deve fazer tantas verificações é o que as torna mais lentas do que as duas alternativas para a pesquisa de dados.

Nota

Quando os desenvolvedores mencionam o quão lenta é a API de scripting, é esta cadeia de consultas a que eles se referem. Comparado ao código C++ compilado onde o aplicativo sabe exatamente para onde ir para encontrar qualquer coisa, é inevitável que as operações do API de scripting levem muito mais tempo. Eles devem localizar a fonte de quaisquer dados relevantes antes de tentarem acessá-los.

O motivo pelo qual o GDScript é lento é porque todas as operações que ele executa passam por esse sistema.

O C# pode processar algum conteúdo em velocidades mais altas por meio de bytecode mais otimizado. Mas, se o script C# chamar o conteúdo de uma classe do motor ou se o script tentar acessar algo externo a ele, ele passará por este pipeline.

O NativeScript C++ vai ainda mais longe e mantém tudo interno por padrão. Chamadas para estruturas externas irão através da API de scripting. No NativeScript C++, registrar métodos para expô-los à API de scripting é uma tarefa manual. É neste ponto que as classes externas, não-C++, utilizarão a API para localizá-las.

Portanto, supondo que se estenda de Reference para criar uma estrutura de dados, como um Array ou Dicionário, por que escolher um Objeto em vez das outras duas opções?

Controle: Com objetos vem a capacidade de criar estruturas mais sofisticadas. É possível colocar abstrações sobre os dados para garantir que a API externa não mude em resposta às mudanças na estrutura de dados interna. Além do mais, Objetos podem ter sinais, permitindo um comportamento reativo.
Clareza: Objetos são uma fonte de dados confiável quando se trata dos dados que os scripts e as classes do motor definem para eles. Propriedades podem não conter os valores esperados, mas não é necessário se preocupar se a propriedade existe em primeiro lugar.
Conveniência: Se já houver uma estrutura de dados semelhante em mente, então estender a partir de uma classe existente torna a tarefa de construir a estrutura de dados muito mais fácil. Em comparação, Arrays e Dicionários não atendem a todos os casos de uso que podemos ter.

Objetos também dão aos usuários a oportunidade de criar estruturas de dados ainda mais especializadas. Com ele, é possível projetar sua própria Lista, Árvore de Busca Binária, Heap, Splay Tree, Gráfico, Conjunto Desarticulado e qualquer hospedeiro de outras opções.

"Porque não usar Node para estruturas de árvores?" pode-se perguntar. Bem, a classe Node contém coisas que não serão relevantes para a estrutura de dados personalizada. Como tal, pode ser útil construir o seu próprio tipo de nó ao construir estruturas em árvore.

extends Object
class_name TreeNode

var _parent : TreeNode = null
var _children : = [] setget

func _notification(p_what):
    match p_what:
        NOTIFICATION_PREDELETE:
            # Destructor.
            for a_child in _children:
                a_child.free()

// Can decide whether to expose getters/setters for properties later
public class TreeNode : Object
{
    private TreeNode _parent = null;

    private object[] _children = new object[0];

    public override void Notification(int what)
    {
        switch (what)
        {
            case NotificationPredelete:
                foreach (object child in _children)
                {
                    TreeNode node = child as TreeNode;
                    if (node != null)
                        node.Free();
                }
                break;
            default:
                break;
        }
    }
}

A partir daqui, é possível criar suas próprias estruturas com funcionalidades específicas, limitadas apenas por sua imaginação.

Enumerações: int vs. string¶

A maioria das linguagens oferecem uma opção do tipo enumeração. GDScript não é diferente, mas ao contrário da maioria das outras linguagens, ele permite usar inteiros ou strings para os valores do enum (este último apenas quando se utiliza a palavra-chave export no GDScript). Surge então a pergunta: "qual deve ser usado?"

A resposta curta é: aquele com o qual você se sentir mais confortável". Este é um recurso específico do GDScript e não do scripting do Godot em geral; As linguagens priorizam usabilidade em vez do desempenho.

Em um nível técnico, comparações de inteiros (tempo constante) acontecerão mais rápido que comparações de strings (tempo linear). Se for preciso manter convenções de outras linguagens, então deve-se usar números inteiros.

O problema principal com o uso de inteiros surge quando se deseja imprimir um valor enum. Como inteiros, tentar imprimir MY_ENUM imprimirá 5``ou sei lá o quê, ao invés de algo como ``MyEnum. Para imprimir um enum inteiro, seria preciso escrever um dicionário que mapeia o valor da string correspondente para cada enum.

Se o objetivo principal de usar um enum é para imprimir valores e se deseja agrupá-los como conceitos relacionados, então faz sentido utilizá-los como strings. Dessa forma, uma estrutura de dados separada para executar na impressão é desnecessária.

AnimatedTexture vs. AnimatedSprite vs. AnimationPlayer vs. AnimationTree¶

Em que circunstâncias se deve usar cada uma das classes de animação do Godot? A resposta não pode ser imediatamente clara para novos usuários do Godot.

AnimatedTexture é uma textura que o motor desenha como um loop animado em vez de uma imagem estática. Usuários podem manipular...

a taxa na qual ela se move através de cada seção da textura (fps).
o número de regiões contidas dentro da textura (quadros).

O VisualServer do Godot então desenha as regiões em sequência na taxa prescrita. A boa notícia é que isto não envolve lógica extra por parte do motor. A má notícia é que os usuários têm muito pouco controle.

Observe também que o AnimatedTexture é um Resource ao contrário dos outros objetos Node discutidos aqui. Pode-se criar um nó Sprite que usa Animated Texture como sua textura. Ou (algo que os outros não podem fazer) pode-se adicionar AnimatedTextures como tiles em um TileSet e intergrá-lo com um TileMap para muitos fundos autoanimados que renderizam em uma única chamada de desenho em lote.

O nó AnimatedSprite, em combinação com o recurso SpriteFrames, permite criar uma variedade de sequências de animação através de spritesheets, alternar entre animações, e controlar sua velocidade, deslocamento regional e orientação. Isto os torna bem adequados para controlar animações 2D baseadas em quadros.

Se for necessário acionar outros efeitos em relação a mudanças na animação (por exemplo, criar efeitos de partícula, chamar funções ou manipular outros elementos periféricos além da animação baseada em quadros), será necessário usar um nó AnimationPlayer em conjunto com o AnimatedSprite.

AnimationPlayers também são a ferramenta necessária para projetar sistemas de animação 2D mais complexos, como...

Animações de recorte: editar transformações de sprites durante a execução.
Animações de Malha 2D: definir uma região para a textura do sprite e armando um esqueleto nela. Em seguida anima-se os ossos que esticam e dobram a textura em proporção às relações dos ossos entre si.
Uma mistura das opções acima.

Embora seja necessário um AnimationPlayer para projetar cada uma das sequências individuais de animação para um jogo, também pode ser útil combinar animações para misturar, ou seja, permitir transições suaves entre estas animações. Também pode haver uma estrutura hierárquica entre animações que se planeja para seu objeto. Estes são casos onde a AnimationTree brilha. Pode-se encontrar um guia detalhado sobre o uso da AnimationTree aqui.