Work in progress

The content of this page was not yet updated for Godot 4.2 and may be outdated. If you know how to improve this page or you can confirm that it's up to date, feel free to open a pull request.

データ設定

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

注釈

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

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

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

  • 定数時間、O(1): 「...は増加しません」

  • 対数時間、O(log n): 「...はゆっくりと増加します」

  • 線形時間、O(n): 「"...は同じ割合で増加します」

  • 等。

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

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

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

Godot stores all variables in the scripting API in the Variant class. Variants can store Variant-compatible data structures such as Array and Dictionary as well as Objects.

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

注釈

For those unfamiliar with C++, a Vector is the name of the array object in traditional C++ libraries. It is a "templated" type, meaning that its records can only contain a particular type (denoted by angled brackets). So, for example, a PackedStringArray would be something like a Vector<String>.

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

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

    • 処理: カウンタをインクリメントして次のレコードに行くだけです。

  • Insert(挿入)、Erase(消去)、Move(移動): 位置に依存。一般的に遅い。

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

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

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

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

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

      1. 配列の並びを反転します。

      2. 末尾から配列の変更をするループ処理を実行します。

      3. 配列の並びを再反転します。

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

  • Get, Set: Fastest by position. E.g. can request 0th, 2nd, 10th record, etc. but cannot specify which record you want.

    • 処理: 配列の開始位置から目的のインデックスまでの1回の追加操作。

  • 検索: 最も遅い。値のインデックス/位置を識別します。

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

      • パフォーマンスは、徹底的な検索が必要かどうかによっても異なります。

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

Godot implements Dictionary as an OrderedHashMap<Variant, Variant>. 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 OHM 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.

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

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

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

  2. Maintaining an ever-growing size for the table.

    • HashMaps maintain gaps of unused memory interspersed in the table on purpose to reduce hash collisions and maintain the speed of accesses. This is why it constantly increases in size quadratically by powers of 2.

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()

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

列挙型: 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固有の機能です。この言語はパフォーマンスよりも使いやすさを優先しています。

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

The primary issue with using integers comes up when one wants to print an enum value. As integers, attempting to print MY_ENUM will print 5 or what-have-you, rather than something like "MyEnum". To print an integer enum, one would have to write a Dictionary that maps the corresponding string value for each enum.

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

AnimatedTexture vs. AnimatedSprite2D vs. AnimationPlayer vs. AnimationTree

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

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

  1. the rate at which it moves across each section of the texture (FPS).

  2. テクスチャに含まれる領域の数(フレーム数)。

Godot's RenderingServer then draws the regions in sequence at the prescribed rate. The good news is that this involves no extra logic on the part of the engine. The bad news is that users have very little control.

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 TileMap 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 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 will need to use an AnimationPlayer node in conjunction with the AnimatedSprite2D.

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

  1. Cut-out animations: editing sprites' transforms at runtime.

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

  3. 上記のミックス。

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