Pular para o conteúdo principal

13 postagens marcadas com "godot"

Ver todas os Marcadores

Thiago Lages de Alencar

(Wang tiles foi proposto pelo matemático Hao Wang em 1961)

Assuma que teremos um conjunto de tiles onde cada lado está pintado de apenas uma cor. Por exemplo:

Exemplo de 5 tiles diferentes

  1. Cada lado com uma cor.
  2. Dois lados com a mesma cor.
  3. Todos os lados com a mesma cor.
  4. Dois lados adjacentes com a mesma cor.
  5. Variação das cores já vistas só que em posições diferentes.
note

Por simplicidade mudaremos para duas cores apenas.

A ideia é reutilizar os mesmos tiles quantas vezes quisermos para botar eles lado a lado e formar um plano, porém com as cores laterais do tiles sempre casando. No exemplo seguinte temos 5 tiles e 2 exemplos de planos formados por eles:

Exemplo utilizando 5 tiles diferentes para criar 2 combinações de plano

Importante notar que:

  • Tiles não podem se sobrepor.
  • Tiles não podem ser rotacionados ou refletidos.

Pois não é possível saber se seriam tiles válidos sem conhecer a imagem utilizada neles.

Automation

Embora reutilização de tiles para gerar diversos planos/mapas não seja especial, Wang tiles adiciona a lógica de relacionar os tiles entre si. Isto nos permite verificar se um tile é válido numa determinada posição.

Por exemplo, possuindo 2 cores e 4 lados, podemos formar 16 (24) tiles diferentes:

Todas os possíveis tiles com duas cores e quatro lados

note

Adicionamos um quadrado cinza no centro de cada tile.

Botamos estes tiles na game engine Godot e nela definimos a relação entre os tiles.

Ao começar a pintar tiles dentro da game engine, podemos ver que ela consegue verificar qual tile é válido naquela posição ou se precisa alterar os vizinhos.

Em segundos conseguimos construir planos onde os tiles tem uma conexão entre si.

Variations

É importante notar que não há problema criar variações do mesmo tile. Por exemplo:

Mesmos 16 porém com a adição de 3 tiles com todos os lados verdes

No momento de preencher por um tile válido naquela posição, a ferramenta iria ter que escolher entre 4 tiles diferentes. Algumas ferramentas como Godot escolheram aleatoriamente:

Antes
Exemplo de plano criado utilizando os 16 tiles

Depois
Exemplo 3 de plano criado utilizando os tiles, porém com árvores

Rotation & Reflection

Na proposta de Wang não se pode rotacionar e refletir tiles pois não existe garantia que a imagem continuará fazendo sentido após rotacionada ou refletida.

Porém como criador dos tiles, somos capazes de deduzir está informação e apenas fazer os tiles necessários. Vamos pegar este conjunto de tiles:

Todas os possíveis tiles com duas cores e quatro lados

Alguns destes tiles são variações dos anteriores porém rotacionados ou refletidos. Levando isto em conta, podemos minimizar para 6 tiles apenas:

Seis tiles que conseguem representar os mesmo tiles acima

É importante notar que só é possível se conhecermos a imagem. Botando a mesma árvore utilizada anteriormente em um dos tiles, podemos ver o tile perder o sentido quando rotacionado mas não quando refletido:

Árvore adicionada a um tile e suas variações de rotação e reflexão

Example

Todos nossos tiles tem sido com cores, porém as cores apenas servem para representar a relação entre os tiles.

Para deixar isto claro, vamos substituir o desenho dos tiles por desenhos que melhor representem um labirinto. Vamos trocar azul por arbustos e verde por terra:

Comparação do tiles bases com tiles do labirinto

Utilizando estes tiles com suas rotações/relexões, podemos criar em segundos o nosso labirinto:

Tiles do labirinto

note

Este labirinto está com cara de circuitos da placa mãe. 🤔

References

Thiago Lages de Alencar

Eu passei um dia inteiro curioso para saber o como funcionava contagem por referência no GDScript (não o conceito mas sim os detalhes tecnicos). Triste por ver que a documentação não conseguiu tirar as dúvidas que eu tinha e até pensei que só saberia mais testando ou olhando o código em C++.

Até que por acaso esbarrei em um comentário de um video que simplesmente explica muito bem.

I've been following along in the course, but this particular video contains a lot of misinformation about Godot's internals. I'll clarify below:

All variables defined in Godot's scripting API are wrapped in an object called a Variant. Each Variant is capable of storing different data types (int, string, bool, Object, Array, Dictionary, Color, Transform, etc.). You can see a list of the supported types TYPE_* enum values in the @GlobalScope class API documentation. This Variant class is why GDScript is able to change variable data types dynamically. Internally, every variable is a Variant. When you specify that a variable is typed and can only contain a single type, it is the GDScript language implementation, not Godot Engine, that blocks the type change.

Now, if a Variant B is assigned to another Variant A, then MOST of the time, the B's value is "copied by value", meaning that the direct value is copied from B to A. There is no reference counting of any kind. They are primitive values. In fact, reference counting primitive values is generally a waste of time and less performant than just copying them directly. This is because, for reference counting, you have to pass around a memory address in order to refer to the variable (because there is only one instance of the variable), and then getting the variable involves looking up the memory address. But for primitive numeric values such as int, float, or bool, passing the direct value takes just as much memory (less than 64 bits or 8 bytes) as passing a memory address. And if you pass a direct value, then the other Variant doesn't have to look up the value in the first place; they already have it.

There are only three data types in Godot 3.2.x and prior that "copy by reference", i.e. pass a memory address when assigning to a new variable: Object, Array, and Dictionary. EVERYTHING else will copy by value. In Godot 4.0 and beyond, the various Pool*Array classes, such as PoolIntArray, PoolStringArray, etc., will also be updated to copy by reference. With "copy by reference" data types, if you create one of those values and assign it to two variables, then modifying either one of the variables' values will modify both variables' values, since they both refer to the same memory address.

var x = [1, 2, 3]
var y = x
x.push_back(4) # y is now also [1,2,3,4]

As for reference counting, that is ONLY supported in Object classes that extend the Reference class. The top of the class hierarchy looks a bit like this...

  • Object
    • Node
      • CanvasItem
        • Node2D
        • Control
      • Spatial
    • Reference
      • Resource

So, Object has only direct new/free methods for allocating and deleting memory. Node and its subtypes can allocate memory, but 1) they can .free() immediately just like Objects or .queue_free() to schedule their deletion till the next frame (where you can more safely delete a large group of nodes at once), and 2) if you delete a Node, it also deletes all of that Node's children, so an entire tree of nodes can be deleted just by deleting the root node of that tree. With Reference, you never delete it directly. It just auto-deletes when you stop having any references to it due to the fact that it actually DOES do reference-counting.

var ref = Reference.new()
ref = null # the Reference object has now been freed

Resources behave just like References, except in their case, they can track their reference by their filepath as well. That is, if you do load("res://my_file.gd"), then you may end up loading a cached instance rather than allocating an entirely new object. If the engine's internal ResourceCache finds that the resource has already been loaded, then the load() function will just return the memory address of the existing object rather than creating a new one.

Also note that the practice of creating an object pool for nodes and the like can be useful, but for different reasons than in other engines. This topic is quite advanced for people who may be learning programming for the first time, but: in stuff like C# (Unity), memory is "garbage collected", i.e. the program tracks memory for you and auto-deletes it on your behalf. This can lead to random pauses in a game if the garbage collector suddenly starts up and interrupts gameplay to clean up memory. Object pooling, i.e. creating a group of objects and then just cycling through them rather than deleting and creating constantly, was a strategy to re-use existing memory for objects so as to stop the garbage collector from needing to run in the first place. But Godot does memory allocation manually and in small increments. It is designed in such a way that constantly creating and deleting objects doesn't lead to long-term memory fragmentation, i.e. it doesn't mess up your computer. You can read about this in the "development" section of the official documentation. Anyway, object pooling IS useful if, for performance reasons, you don't want to waste TIME deleting and creating large objects, but you won't need to worry about stuttering or memory issues, so most of the time, it's perfectly fine in Godot to just create and delete objects as you need them.

*Algumas adaptações foram feitas para melhorar aleitura (adicionar nova linha, transformar em bullet points, etc) mas nenhuma alteração em palavras ou frases foram feitas.

Reference

Thiago Lages de Alencar

Em vez de focar no que eu deveria para fazer um jogo, eu me distrai tentando ganhar desempenho onde não precisava...


Eu pretendia ter um Array de buffs e a ideia era verificar se cada um dos buffs já expirou para remover quando eles acabassem. Primeira coisa que pensei foi em percorrer ele e ir removendo um a um os que expiraram.

Conforme fui olhando a documentação de Array percebi um desafio que me chamou atenção... Remoção pode ser custoso:

void erase (Variant value)

Note: On large arrays, this method will be slower if the removed element is close to the beginning of the array (index 0). This is because all elements placed after the removed element have to be reindexed.

void remove (int position)

Note: On large arrays, this method will be slower if the removed element is close to the beginning of the array (index 0). This is because all elements placed after the removed element have to be reindexed.

Variant pop_front()

Note: On large arrays, this method is much slower than pop_back as it will reindex all the array's elements every time it's called. The larger the array, the slower pop_front will be.

Primeiro fiz o código mais simples para isto, juntar todos que expiraram e depois remove-los um a um:

var expired: Array[Buff] = []

for buff in _buffs:
if buff.timeout():
expired.append(buff)

for buff in expired:
_buffs.erase(buff)

Pensei nisto porque sei que não posso remover elementos do Array enquanto o percorro, isso iria causar uma bagunça durante o processo (pode fazer com que você pule elementos enquanto percorre e reindexia).

Mas o que eu aprendi em uma aula da faculdade é que posso evitar este problema se eu percorrer o Array de trás para frente (apenas use isso se você não liga para a ordem em que os elementos vão ser removidos).

for in in range(_buffs.size() -1, -1, -1):
if _buffs[i].timeout():
_buffs.erase(_buffs[i])

Bem mais rápido que a versão anterior e o Godot ainda consegue me sugerir os métodos a serem usados de cada elementos (pois eu usei tipagem no Array).

Não satisfeito com o fato que reindexar tem um custo grande, resolvi fazer mais uma tentativa:

var up_to_date: Array[Buff] = []

for buff in _buffs:
if not buff.timeout():
up_to_date.append(buff)

_buffs = up_to_date

Em vez de me preocupar em remover, apenas anoto os buffs bons para depois sobreescrever o Array.

Lado positivo: append() é bem mais barato que erase() pois não precisa reindexar.

Cada uma dessas maneira melhorou para quando eu precisava remover MUITOS elementos de um Array MUITO grande.

Por exemplo, no caso de um Array com 5k ok e 5k precisando ser removidos a diferença foi de 648117µs para 2286µs (até eu estou me perguntando se eu medi corretamente isto pq isso seria um aumento de 28.000%?)

Voltando para a realidade... Isto não é um caso normal e as chances disso acontecer em um jogo é quase impossível (até para MMORPG 5k buffs é muito).

Pelo lado positivo está função não é custosa, mesmo nos casos pequenos ela chega a ter o custo de 0~100% a mais que anterior.

Note

Depois de tudo isso eu pensei... eu não deveria estar dando queue_free() nestes meus Nodes? 🤔

Não era mais fácil deixar que os Nodes dessem queue_free() neles mesmo quando dessem timeout? 🤔