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 符號 (英文) 。

長話短說，這種方式是用來表示最糟情況下所需要的執行事件。用業餘的方式來說：

「隨著問題領域變大，演算法的執行時間長度…」

• 常數時間， O(1) ：「…不會增加。」

• 對數時間， O(log n) ：「…緩慢增加。」

• 線性時間， O(n) ：「…等速增加。」

• …等。

試想一下需要在每影格處理 300 萬筆資料點的情況。這時候就沒辦法使用線性時間演算法，因為隨著資料大小的增加，執行時間也會大幅增加。相較之下，使用常數時間演算法來處理就沒有問題。

大致上來說，開發人員總是希望能儘可能避免使用線性時間操作。但，若只保持小規模的線性時間操作，且不需要常常有這類操作，則還算可接受。在需求間找到平衡點，並依據正在進行的工作選擇正確的演算法與資料型別即是使程式設計師技術有價值的部分。

陣列 vs. 字典 vs. 物件

Godot 將腳本 API 中所有的變數都保存在 Variant 類別內。Variant 可以保存 Variant 相容的資料結構，如 Array 與 Dictionary 以及 Object 。

Godot 以 Vector<Variant> 來實作陣列。引擎會將陣列的內容儲存在一段連續的記憶體當中。也就是說，陣列的元素是相鄰的。

備註

對不熟悉 C++ 的人來說，Vector 是傳統 C++ 函式庫中陣列物件的名稱，是一種「樣板型別」，代表內容只能存放特定型別（用尖括號標示）。舉例來說，PackedStringArray 就類似 C++ 的 Vector<String>。

連續記憶體儲存，也就代表了下列操作效能：

• 迭代： 最快。最適合迴圈。

  • 操作：迭代要做的就是增加計數器來移動到下一筆資料。

• 插入、移除、移動： 取決於位置。普通慢。

  • 操作：新增／移除／移動會需要移動相鄰的記錄 (才能騰出空間／填補空間)。

  • 從結尾 新增／移除 - 快速。

  • 從任意位置 新增／移除 - 慢。

  • 從最前面 新增／移除 - 最慢。

  • 若 從前面 進行插入／移除多筆資料，則...

    1. 反轉陣列。

    2. 執行從陣列 結尾 更改的迴圈。

    3. 重新反轉陣列。

    這樣一來，比起平均要複製 N 次大約 1/2 個陣列 (線性時間)， 就只會產生 2 個陣列的副本 (一樣是常數時間，但比較慢)。

• 取值、設值： 依位置 最快。如，可要求第 0、第 2 與第 10 筆記錄…等。但無法指定要哪個記錄。

  • 操作：需要 1 個額外的操作來將陣列從起始位置移至需要的位置。

• 搜尋： 最慢。找到一個值的索引／位置。

  • 操作：必須要迭代陣列並比較各個值，直到找到相符的元素。

    • 效能還會依據是否需要完整的搜尋而有所不同。

  • 若陣列有排序，則搜尋操作可達對數時間 (相對較快)。不過，業餘使用者可能會不太習慣這種方法。這種方法會需要在每次編輯陣列後進行重新排列，並編寫適用於有序陣列的搜尋演算法。

Godot 將字典（Dictionary）實作為 HashMap<Variant, Variant, VariantHasher, StringLikeVariantComparator> 。引擎會儲存一個小型的索引鍵與數值配對陣列（初始化為 2^3，也就是 8 筆記錄）。當要存取某個數值時，會提供一個索引鍵；引擎接著會對該索引鍵進行雜湊，也就是將其轉換為數字。這個 "hash" 會用來計算在陣列中的索引。作為陣列，HashMap 能在這個將鍵映射到值的 表 中快速查找。當 HashMap 過於滿載時，會擴充到下一個 2 的次方（例如 16、32…）並重建結構。

雜湊是為了降低索引鍵碰撞的機率。若發生碰撞，表格就必須要為該數值重新計算另一個索引來處理前一個位置。這樣一來，就可以常數時間來存取所有記錄，但卻需要犧牲一些記憶體與執行效率。

1. 對每個索引鍵雜湊任意次。

   • 雜湊操作為常數時間，所以即使某個演算法需要被執行超過一次，只要雜湊計算的數字不要太依賴表格的密度，就能保持高速。這樣一來…

2. 維護表格持續增長的大小。

   • HashMap 為了減少 hash collision 並維持存取速度，刻意在表格中保留散布的未使用記憶體空間。這也是為什麼它會以 2 的次方持續呈指數級增長的原因。

我們可以說，字典可以做一些陣列沒辦法做的工作。下面列出一些字典能做的操作：

• 迭代： 快速。

  • 操作：在對應表內部的雜湊向量間迭代。回傳每個索引鍵。然後，使用者便能通過該索引鍵來跳至並回傳所需的值。

• 插入、移除、移動： 最快。

  • 操作：雜湊給定的索引鍵。需要 1 個額外操作來找到適當的值 (陣列起始 + 偏移)。移動是由這其中的兩個操作組成的 (一個新增、一個刪除)。對應表為了保持其功能性，必須要做一些維護操作：

    • 更新記錄的有序列表。

    • 判斷表格的密度，決定是否有需要增加表格的大小。

  • 字典會記得使用者插入索引鍵的順序。這樣一來在執行迭代的時候就能確保可靠性。

• 取值、設值： 最快。與 以索引鍵 查詢相同。

  • 操作：與插入／移除／移動相同。

• 查詢： 最慢。需要找出值的索引鍵。

  • 操作：必須要在每個記錄間迭代，並比較各個值來找出相符合的專案。

  • 請注意，Godot 並沒有直接提供這個功能 (因為字典並非設計來做這項工作)。

Godot 實作物件的方法很單純，但卻有動態資料內容容器。物件會在被要求的時候查詢資料來源。舉例來說，當物件需要回答「你有沒有一個叫『position』的屬性？」這種問題時，物件可能會詢問 Script 或 ClassDB 。更多關於物件的資訊以及物件如何運作的資訊，請參考 在 Godot 中套用物件導向原則 一文。

此處有一個重要的細節，就是有關物件工作中的複雜度。每當物件執行一次這種多來源的查詢時，物件會執行 多個 迭代迴圈以及雜湊表查詢。而且，查詢的線性時間會依據物件的繼承與層級大小而異。若物件查詢的類別 (目前的類別) 沒有找到任何東西，則查詢會被傳遞到更上一層，直到最原始的 Object 類別。雖然這些操作單獨來看都很快，但事實上因為這些操作需要做到很多確認，所以會讓查詢比起查詢陣列或字典的兩種方法都來得慢。

備註

當開發人員提到腳本的 API 有多慢時，指的是這個查詢鏈很慢。跟經過編譯的 C++ 程式碼比起來，這些 C++ 程式在查詢會知道要讀取的準確位置，因此相比起來腳本 API 就不可避免地慢很多。腳本 API 必須要在嘗試存取資料前找過所有相關資料的來源。

GDScript 比較慢的原因就是因為在執行所有操作前都必須要經歷過一次這個系統。

C# 可以通過最佳化的 Bytecode 來以更快的速度處理一些內容。但是，若 C# 腳本要呼叫引擎的類別內容，或是腳本試圖存取腳本外部的東西，則還是需要走過一次這個過程。

NativeScript C++ 則更進一步，預設會將所有東西都保持在內部。呼叫外部結構的時候會經過腳本 API。在 NativeScript C++ 中，必須要手動註冊方法並將方法暴露給腳本 API。這樣一來，非 C++ 類別就可以通過 API 來找到這些方法。

因此，假設我們需要繼承 Reference 來建立一個資料結構，類似 Array 或 Dictionary，誰還要用 Object 而不用 Array 或 Dictionary 呢？

1. 控制： 因為物件能建立更複雜的結構，所以我們可以將資料抽象化成抽象層，來確保對外的 API 不會因為內部資料結構的更改而需要跟著改變。而且，物件還可以有訊號，可以作出回應式的行為。

2. 明確： 當使用到腳本與引擎類別定義的資料時，物件是可信任的資料結構。屬性中的值可能與使用者期望的不同，但是在使用時不需要擔心物件上是否有某個屬性。

3. 便利： 在已有類似資料結構的情況下，就可以通過繼承現有類別來更輕鬆地製作資料結構。相較起來，陣列與字典並非適用於所有情況。

物件也讓使用者有機會製作更專門的資料結構。使用物件，開發人員就能設計客製化的列表、二元搜尋樹、堆積、Splay Tree、Graph、非交集集合以及其他選項。

可能有人會問，「為什麼不用 Node 來處理樹狀結構？」。其實，Node 節點包含了一些與客製化資料結構不相關的東西，因此，在自行製作樹狀結構的時候，可以考慮自行建立自製的 Node 型別。

GDScriptC#

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

就這樣，我們能製作適用於特定功能的客製化結構。

列舉型別：整數 vs. 字串

大多數程式語言都提供列舉型別的選項。GDScript 也不例外，但與大多數其他語言不同的是，它允許對列舉值使用整數或字串（後者僅在使用 GDScript 的 @export_enum 註解時）。那麼問題就來了：「應該使用哪一種？」

用一句話來回答的話，就是「哪個用習慣就用哪個。」。這項功能是 GDScript 特有的，而不是 Godot 中所有的腳本語言都這樣。GDScript 首先考慮的是易用性而非效能。

但技術上來說，整數型別的比較 (常數時間) 比字串比較 (線型時間) 要來得快。如果想保持與其他語言一樣的慣例，則應該用整數。

當我們想 印出 列舉型別時，就會遇到使用整數的主要問題了。使用整數時，嘗試印出 MY_ENUM 會得到 5 這樣的值，而不是 "MyEnum" 。如果要印出整數列舉型別，就必須要寫一個將字串值對應到各個列舉值的字典 (Dictionary)。

若使用列舉型別的主要是為了要印出數值，而且想將相關的概念群組化，則可以使用字串。這樣一來，就不需要在印出數值時使用另一個分開的資料結構。

AnimatedTexture vs. AnimatedSprite vs. AnimationPlayer vs. AnimationTree

在哪個情況下該用哪個 Godot 動畫類別？對於新的 Godot 使用者來說，可能無法馬上清楚答案。

AnimatedTexture 是引擎繪製為動畫循環的紋理貼圖，而不是靜態圖片。使用者可以進行如下操作……

1. 在紋理貼圖的各個部分移動的速率 (FPS)。

2. 紋理貼圖中包含的區域數量 (影格數)。

Godot 的 RenderingServer 會依序以指定頻率繪製這些區域。好消息是這不會造成引擎額外負擔，但壞消息是使用者幾乎無法控制。

另外請注意，AnimatedTexture 是一種 Resource ，不同於此處討論的其他 Node 物件。可以創建一個 Sprite2D ，並將 AnimatedTexture 作為其紋理使用。或者（這是其他物件無法做到的），可以將 AnimatedTexture 加入 TileSet 中作為圖塊，並將其整合到 TileMapLayer ，以實現許多自動動畫背景，而這些背景都可以在單一的批次繪圖呼叫中算繪。

結合 AnimatedSprite2D 節點和 SpriteFrames 資源，可以透過 sprite sheet 建立多種動畫序列、切換不同動畫，並控制其速度、區域偏移和方向。這使得它們非常適合控制 2D 逐幀動畫。

如果需要在動畫變更時觸發其他效果（例如，產生粒子特效、呼叫函式，或操作除了基於影格動畫之外的其他周邊元素），那麼就需要搭配 AnimatedSprite2D 使用一個 AnimationPlayer 節點。

當想設計更複雜的 2D 動畫系統時，AnimationPlayer 也是必要工具。更複雜的 2D 動畫系統包含…

1. 剪影動畫： 在執行階段編輯 Sprite 的變換。

2. 2D 網格動畫： 為 Sprite 的材質定義一個區域，並將其骨骼固定在裡面。接著我們為骨骼製作動畫，依據骨骼之間互相的關係來縮放紋理貼圖。

3. 上述型別的組合。

雖然我們需要 AnimationPlayer 來設計遊戲的個別動畫序列，但 AnimationPlayer 也適合用來混合各個動畫，如，在這幾個動畫間平滑地轉換。我們在設計物件的時候，可能也會在動畫間設計出階層結構。這幾種狀況就很適合 AnimationTree 。有關使用 AnimationTree 更深入的指南，請參考 這裡 。