Attention: Here be dragons

This is the latest (unstable) version of this documentation, which may document features not available in or compatible with released stable versions of Godot.

Checking the stable version of the documentation...

データ設定

問題Xにアプローチするときに、データ構造をYにするかZするかについて悩んだことはありませんか？この記事では、これらのジレンマに関連するさまざまなトピックについて説明します。

注釈

この記事では、「何らかの-時間」操作への言及を行います。この用語はアルゴリズム分析のビッグ・オー記法に由来します。

手短に言えば、実行時間の最悪のシナリオを説明しています。素人の言葉で:

「問題領域のサイズが大きくなるにつれて、アルゴリズムの実行時間の長さが...」

定数時間、O(1): 「...は増加しません」
対数時間、O(log n): 「...はゆっくりと増加します」
線形時間、O(n): 「"...は同じ割合で増加します」
等。

1つのフレーム内で300万個のデータポイントを処理する必要がある場合を想像してください。データのサイズが割り当てられた時間をはるかに超えてランタイムを増加させるので、線形時間アルゴリズムを使用して機能を作成することは不可能です。対照的に、定数時間アルゴリズムを使用すると、問題なく操作を処理できます。

概して、開発者は線形時間操作に可能な限り関与することを避けたいと考えています。ただし、線形時間操作の規模を小さく保ち、操作を頻繁に実行する必要がない場合は、許容できる場合があります。これらの要件のバランスを取り、ジョブに適したアルゴリズム/データ構造を選択することは、プログラマーのスキルを価値あるものにします。

Array(配列) 対 Dictionary(辞書) 対 Object(オブジェクト)

Godot はスクリプト内のすべての変数を Variant(バリアント) クラスに格納します。Variant には Array(配列) や Dictionary(辞書) などの Variant 互換のデータ構造や Object(オブジェクト) を格納できます。

GodotはArrayを Vector <Variant> として実装します。エンジンは配列の内容をメモリの連続したセクションに保存します。つまり配列の要素は互いに隣接する行に格納されます。

注釈

C++ に馴染みのない方のために説明すると、Vector は従来の C++ ライブラリの配列オブジェクトの名前です。これは「テンプレート化された」型であり、そのレコードには特定の型 (山括弧で示される) のみを含めることができます。したがって、たとえば、PackedStringArray は Vector<String> のようになります。

連続したメモリストアは、次の操作パフォーマンスを意味します:

Iterate(反復): 最速。ループに最適です。
- 処理: カウンタをインクリメントして次のレコードに行くだけです。
Insert(挿入)、Erase(消去)、Move(移動): 位置に依存。一般的に遅い。
- 処理: コンテンツを追加/削除/移動するには、隣接するレコードを移動する必要があります(スペースを空ける/スペースを塗りつぶす作業)。
- 末尾からは追加/削除が速い。
- 任意の位置からは追加/削除が遅い。
- 先頭からは追加/削除が最も遅い。
- 先頭から複数の挿入/削除を行う場合には...
  配列の並びを反転します。
  
  末尾から配列の変更をするループ処理を実行します。
  
  配列の並びを再反転します。
  この方法なら、操作の最中に配列の約1/2を平均してN回(線形時間)コピーをする代わりに、配列全体の2回のコピーだけで済みます(依然として一定の時間がかかり、遅いですが)。
取得、設定: 位置で指定するので最速。例: 0番目、2番目、10番目のレコードなどを要求できますが、必要なレコードを指定することはできません。
- 処理: 配列の開始位置から目的のインデックスまでの1回の追加操作。
検索: 最も遅い。値のインデックス/位置を識別します。
- 処理: 配列を反復処理し、一致するものが見つかるまで値を比較する必要があります。
  パフォーマンスは、徹底的な検索が必要かどうかによっても異なります。
- 値が順序付けされている場合、カスタム検索操作によって対数時間 (比較的高速) になります。しかし、素人のユーザーはこれに不慣れです。編集のたびに配列を再ソートし、順序に対応した検索アルゴリズムを作成することで完了します。

Godot implements Dictionary as a HashMap<Variant, Variant, VariantHasher, StringLikeVariantComparator>. The engine stores a small array (initialized to 2^3 or 8 records) of key-value pairs. When one attempts to access a value, they provide it a key. It then hashes the key, i.e. converts it into a number. The "hash" is used to calculate the index into the array. As an array, the HM then has a quick lookup within the "table" of keys mapped to values. When the HashMap becomes too full, it increases to the next power of 2 (so, 16 records, then 32, etc.) and rebuilds the structure.

ハッシュは、キーの衝突の可能性を減らすためのものです。発生した場合、テーブルは以前の位置を考慮した値の別のインデックスを再計算する必要があります。これにより、メモリと若干の運用効率が犠牲になりますが、全体として、すべてのレコードに定数時間でアクセスできます。

すべてのキーを任意の回数ハッシュします。
- ハッシュ操作は定数時間であるため、ハッシュ計算の数がテーブルの密度に依存しすぎない限り、アルゴリズムで複数の処理を行う必要がある場合でも、処理は高速になります。話は続きます...
テーブルのサイズは拡大し続けます。
- HashMap はハッシュ衝突を減らし、アクセス速度を維持するために、意図的にテーブル内に散在する未使用メモリのギャップを維持します。これがサイズが 2 の累乗で常に指数関数的に増加する理由です。

おわかりになると思いますが、Dictionaryは配列以外のタスクに特化しています。その動作の特徴は次のとおりです。

反復処理: 高速。
- 処理: マップのハッシュの内部ベクトルを反復処理し、各キーを返します。その後、ユーザーはキーを使用して目的の値にジャンプしてリターンします。
挿入、消去、移動: 最速。
- 処理: 指定されたキーをハッシュします。 1回の追加操作を実行して、適切な値(配列の開始+オフセット)を検索します。移動はこれらの2つです(1つは挿入、1つは消去)。マップは、その機能を維持するためにいくつかのメンテナンスを行う必要があります:
  レコードの順序付きリストを更新します。
  
  テーブルの密度により、テーブルの容量を拡張する必要があるかどうかを判断します。
- Dictionaryは、ユーザーがキーを挿入した順序を記憶しています。これにより、信頼性の高い反復処理を実行できます。
取得、設定: 最速。キーによる検索と同じです。
- 処理: 挿入/消去/移動と同じです。
検索: 最も遅い。値のキーを識別します。
- 処理: レコードを反復処理し、一致が見つかるまで値を比較する必要があります。
- Godotはすぐにはこの機能を提供しないことに注意してください(これらの機能はこのタスク用ではないため)。

Godotは、Objectをあまり賢くはありませんが、データコンテンツの動的コンテナーとして実装します。Objectは質問されるとデータソースを照会します。たとえば「'position' というプロパティはありますか？」という質問に答えるには、 Script または ClassDB に問い合わせる場合があります。オブジェクトとは何か、どのように機能するかについては、オブジェクト指向の原則をGodotに適用するの記事で詳しく説明されています。

ここで重要な点は、オブジェクトのタスクの複雑さです。これらのマルチソースクエリの1つを実行するたびに、複数の反復ループとHashMapのルックアップを実行します。さらに、クエリはオブジェクトの継承階層サイズに依存する線形時間操作です。 Objectクエリを実行するクラス(現在のクラス)で何も見つからない場合、リクエストはObjectの継承元の基本クラスへと次々に受け渡されます。これらはそれぞれ単独では高速な操作ですが、非常に多くのチェックを行う必要があるという事実が、データを検索するための Array/Dictionary 両方の代替手段よりも遅くなる理由です。

注釈

開発者がスクリプトAPIの速度が遅いと言及するのは、この一連のクエリの参照についてです。アプリケーションが何かを見つける場所を正確に知っているコンパイル済みのC++コードと比較すると、スクリプトAPIでは操作にかかる時間が大幅に長くなることは避けられません。アクセスを行う前に、関連するデータのソースを見つける必要があるからです。

GDScriptが遅いのは、実行するすべての操作がこのシステムを通過するためです。

C#は、より最適化されたバイトコードにより、一部のコンテンツをより高速に処理できます。ただし、C#スクリプトがエンジンクラスのコンテンツを呼び出す場合、またはスクリプトが外部の何かにアクセスしようとする場合、このパイプラインを通過します。

NativeScript C++はさらに進んで、デフォルトですべてを内部に保持します。外部構造への呼び出しは、スクリプトAPIを経由します。 NativeScript C++では、スクリプトAPIに公開するメソッドを登録するのは手動のタスクです。この時点で、外部の非C++クラスがAPIを使用してそれらを見つけます。

では、Array や Dictionary などのデータ構造を作成するために Reference から拡張すると仮定すると、なぜ他の2つのオプションよりも Object を選択するのでしょうか？

コントロール: Object を使用すると、より洗練された構造を作成する機能が提供されます。データを抽象化して、内部データ構造の変更に応じて外部APIが変更されないようにすることができます。さらに、Object はシグナルを持ち、反応的な動作を可能にします。
明快さ: Object は、スクリプトとエンジンクラスが定義するデータに関しては信頼できるデータソースです。プロパティは期待する値を保持していない場合がありますが、プロパティがそもそも存在するかどうかを心配する必要はありません。
利便性: 同様のデータ構造をすでに念頭に置いている場合、既存のクラスから拡張すると、データ構造を構築するタスクがはるかに簡単になります。それに比べて、Array と Dictionary はすべてのユースケースを満たしているわけではありません。

また、Object を使用すると、ユーザーはさらに特殊なデータ構造を作成することもできます。これを使用して、独自のリスト、バイナリ検索ツリー、ヒープ、スプレー木、グラフ、素集合、およびその他のオプションのホストを設計できます。

「ツリー構造にNodeを使用しないのはなぜですか？」と尋ねるかもしれません。 Nodeクラスには、カスタムデータ構造に関係のないものが含まれています。そのため、ツリー構造を構築するときに、独自のノードタイプを構築すると役立ちます。

class_name TreeNode
extends Object

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

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

using Godot;
using System.Collections.Generic;

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

    private List<TreeNode> _children = [];

    public override void _Notification(int what)
    {
        switch (what)
        {
            case NotificationPredelete:
                foreach (TreeNode child in _children)
                {
                    node.Free();
                }
                break;
        }
    }
}

ここから、想像力によってのみ制限される特定の機能を備えた独自の構造を作成できます。

列挙型: int 対 string

ほとんどの言語では、列挙型のオプションが提供されています。GDScript も例外ではありませんが、他のほとんどの言語とは異なり、列挙値に整数または文字列を使用できます (後者は GDScript で @export_enum アノテーションを使用する場合)。そこで「どちらを使用すればよいのか?」という疑問が生じます

簡単な答えは、「どちらが快適か」です。これは、(C++、C#等の)一般的なGodotスクリプトにはない、GDScript固有の機能です。この言語はパフォーマンスよりも使いやすさを優先しています。

技術的なレベルでは、整数の比較 (定数時間) は文字列の比較 (線形時間) よりも高速に行われます。しかし、他の言語の規則を維持したい場合は、整数を使用する必要があります。

整数の使用に関する主な問題は、列挙値を print したいときに発生します。整数として MY_ENUM を出力しようとすると、 "MyEnum" のようなものではなく、 5 などが出力されます。整数列挙を出力するには、各列挙に対応する文字列値をマップする辞書を作成する必要があります。

列挙型を使用する主な目的が値を出力することであり、それらを関連する概念としてグループ化する場合、それらを文字列として使用することは理にかなっています。そうすれば、printで実行するための別個のデータ構造は不要です。

AnimatedTexture 対 AnimatedSprite2D 対 AnimationPlayer 対 AnimationTree

どのような状況でGodotの各アニメーションクラスを使用する必要がありますか？答えは、新しいGodotユーザーにはすぐにはわからないかもしれません。

AnimatedTexture は、エンジンが静的イメージではなくアニメーションループとして描画するテクスチャです。ユーザーは次の操作ができます...

テクスチャの各セクションを移行する速度(FPS)。
テクスチャに含まれる領域の数(フレーム数)。

Godotの RenderingServer は、指定されたレートで領域を順番に描画します。良い点はエンジン側で余分なロジックが不要であることです。悪い点はユーザーが制御できる範囲がほとんどないことです。

Also note that AnimatedTexture is a Resource unlike the other Node objects discussed here. One might create a Sprite2D node that uses AnimatedTexture as its texture. Or (something the others can't do) one could add AnimatedTextures as tiles in a TileSet and integrate it with a TileMapLayer for many auto-animating backgrounds that all render in a single batched draw call.

The AnimatedSprite2D node, in combination with the SpriteFrames resource, allows one to create a variety of animation sequences through spritesheets, flip between animations, and control their speed, regional offset, and orientation. This makes them well-suited to controlling 2D frame-based animations.

If one needs to trigger other effects in relation to animation changes (for example, create particle effects, call functions, or manipulate other peripheral elements besides the frame-based animation), then one will need to use an AnimationPlayer node in conjunction with the AnimatedSprite2D.

AnimationPlayer は、次のようなより複雑な2Dアニメーションシステムを設計する場合に使用する必要があるツールでもあります。

カットアウトアニメーション: 実行時にスプライトのトランスフォームを編集します。
2Dメッシュアニメーション: スプライトのテクスチャの領域を定義し、スケルトンをリギングします。次に、ボーンのアニメーション化を行い、ボーンの相互関係に応じてテクスチャを伸縮させます。
上記のミックス。

ゲームの個々のアニメーションシーケンスをそれぞれ設計するには AnimationPlayer が必要ですが、アニメーションを組み合わせてブレンドすること、つまり、これらのアニメーション間のスムーズな移行を可能にすることにも役立ちます。アニメーション間には、オブジェクトに対して計画している階層構造もあります。これらは AnimationTree が脚光を浴びるケースです。 AnimationTree の使用に関する詳細なガイドはここで見つけることができます。