データ設定

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

注釈

This article makes references to "[something]-time" operations. This terminology comes from algorithm analysis' Big O Notation.

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

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

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

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

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

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

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

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

注釈

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

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

  • Iterate(反復): 最速。ループに最適です。

    • 処理: カウンタをインクリメントして次のレコードに行くだけです。
  • Insert(挿入)、Erase(消去)、Move(移動): 位置に依存。一般的に遅い。

    • 処理: コンテンツを追加/削除/移動するには、隣接するレコードを移動する必要があります(スペースを空ける/スペースを塗りつぶす作業)。

    • 末尾からは追加/削除が速い。

    • 任意の位置からは追加/削除が遅い。

    • 先頭からは追加/削除が最も遅い。

    • 先頭から複数の挿入/削除を行う場合には...

      1. 配列の並びを反転します。
      2. 末尾から配列の変更をするループ処理を実行します。
      3. 配列の並びを再反転します。

      この方法なら、操作の最中に配列の約1/2を平均してN回(線形時間)コピーをする代わりに、配列全体の2回のコピーだけで済みます(依然として一定の時間がかかり、遅いですが)。

  • 取得、設定: 位置で指定するので最速。例: 0番目、2番目、10番目のレコードなどを要求できますが、必要なレコードを指定することはできません。

    • 処理: 配列の開始位置から目的のインデックスまでの1回の追加操作。
  • 検索: 最も遅い。値のインデックス/位置を識別します。

    • 処理: 配列を反復処理し、一致するものが見つかるまで値を比較する必要があります。

      • パフォーマンスは、徹底的な検索が必要かどうかによっても異なります。
    • 値が順序付けされている場合、カスタム検索操作によって対数時間 (比較的高速) になります。しかし、素人のユーザーはこれに不慣れです。編集のたびに配列を再ソートし、順序に対応した検索アルゴリズムを作成することで完了します。

Godotは、Dictionaryを ``OrderedHashMap<Variant, Variant>``として実装します。エンジンは、キーと値のペアの巨大な配列(1000レコードに初期化された)を保存します。値にアクセスしようとすると、まず値がキーになります。次に、キーをハッシュします。つまり、キーを数値に変換します。 「ハッシュ」は配列へのインデックスになり、OHM(訳注:オブジェクト・ハンドル・マネージャー?)は値にマップされたキーの概念的な「テーブル」内の値をすばやく検索できます。

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

  1. すべてのキーを任意の回数ハッシュします。

    • ハッシュ操作は定数時間であるため、ハッシュ計算の数がテーブルの密度に依存しすぎない限り、アルゴリズムで複数の処理を行う必要がある場合でも、処理は高速になります。話は続きます...
  2. 巨大なサイズのテーブルを保持します。

    • 1000個のレコードから始まり、テーブルに散在する未使用メモリの大きなギャップを強制する理由は、ハッシュの衝突を最小限に抑え、アクセスの速度を維持するためです。

As one might be able to tell, Dictionaries specialize in tasks that Arrays do not. An overview of their operational details is as follows:

  • 反復処理: 高速。

    • 処理: マップのハッシュの内部ベクトルを反復処理し、各キーを返します。その後、ユーザーはキーを使用して目的の値にジャンプしてリターンします。
  • 挿入、消去、移動: 最速。

    • 処理: 指定されたキーをハッシュします。 1回の追加操作を実行して、適切な値(配列の開始+オフセット)を検索します。移動はこれらの2つです(1つは挿入、1つは消去)。マップは、その機能を維持するためにいくつかのメンテナンスを行う必要があります:

      • レコードの順序付きリストを更新します。
      • テーブルの密度により、テーブルの容量を拡張する必要があるかどうかを判断します。
    • Dictionaryは、ユーザーがキーを挿入した順序を記憶しています。これにより、信頼性の高い反復処理を実行できます。

  • 取得、設定: 最速。キーによる検索と同じです。

    • 処理: 挿入/消去/移動と同じです。
  • 検索: 最も遅い。値のキーを識別します。

    • 処理: レコードを反復処理し、一致が見つかるまで値を比較する必要があります。
    • Godotはすぐにはこの機能を提供しないことに注意してください(これらの機能はこのタスク用ではないため)。

Godotは、Objectをあまり賢くはありませんが、データ コンテンツの動的なコンテナーとして実装します。Objectは、質問が行われるとデータソースに対してクエリを実行します。たとえば、「 'position'というプロパティがありますか?」という質問に答えるために、その script または ClassDB <class_ClassDB>`を要求します。:ref:`doc_what_are_godot_classes の記事で、オブジェクトとは何か、そしてそれらがどのように機能するかについての詳細を見つけることができます。

ここで重要な点は、オブジェクトのタスクの複雑さです。これらのマルチソースクエリの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 を選択するのでしょうか?

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

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

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

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)
    {
        if (what == NotificationPredelete)
        {
            foreach (object child in _children)
            {
                TreeNode node = child as TreeNode;
                if (node != null)
                    node.Free();
            }
        }
    }
}

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

列挙型: int 対 string

Most languages offer an enumeration type option. GDScript is no different, but unlike most other languages, it allows one to use either integers or strings for the enum values (the latter only when using the export keyword in GDScript). The question then arises, "which should one use?"

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

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

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

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

AnimatedTexture 対 AnimatedSprite 対 AnimationPlayer 対 AnimationTree

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

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

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

Godotの VisualServer は、指定されたレートで領域を順番に描画します。良いニュースは、これはエンジンの部分に余分なロジックを含みないことです。悪いニュースは、ユーザーがほとんど制御できないことです。

また、AnimatedTextureは Resource であり、ここで説明した他の Node オブジェクトとは異なります。テクスチャとしてAnimatedTextureを使用する Sprite ノードを作成できます。ほかにも(他ではできません)AnimatedTextureを TileSet のタイルとして追加して TileMap と統合することで、単一のバッチ描画呼び出しですべてをレンダリングできる、多くの自動アニメーション背景を作成できます。

AnimatedSprite ノードは、SpriteFrames リソースと組み合わせて、スプライトシートを通じてさまざまなアニメーション シーケンスを作成し、アニメーションの反復、速度、領域のオフセット、および方向を制御できます。これにより、2Dフレームベースのアニメーションの制御に適しています。

アニメーションの変更に関連して他の効果をトリガーする必要がある場合 (たとえば、パーティクル エフェクトの作成、関数の呼び出し、フレーム ベースのアニメーション以外の他の周辺要素の操作など)、AnimatedSprite と組み合わせて AnimationPlayer ノードを使用する必要があります。

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

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

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