髒標識模式 Dirty Flag

遊戲設計模式 Game Programming PatternsOptimization Patterns

意圖

將工作延期至需要其結果時纔去執行，避免不必要的工作。

動機

很多遊戲有場景圖。 那是一個巨大的數據結構，包含了遊戲世界中所有的對象。 渲染引擎使用它決定在屏幕的哪裏畫東西。

最簡單的實現中，場景圖只是對象列表。 每個對象都有模型，或者其他的原始圖形，以及變換。 變換描述了對象在世界中的位置，方向，拉伸。 爲了移動或者旋轉對象，只需簡單地改變它的變換。

當渲染系統描繪對象，它取出對象的模型，對其應用變換，然後將其渲染到遊戲世界中。 如果我們有場景包而不是場景圖，那就是這樣了，生活很簡單。

但是，大多數場景圖都是分層的。 場景圖中的對象也許擁有錨定的父對象。 這種情況下，它的變換依賴於父對象的位置，而不是遊戲世界上的絕對位置。

舉個例子，想象遊戲世界中有一艘海上的海盜船。 桅杆的頂端有瞭望塔，瞭望塔中有海盜，海盜肩上有鸚鵡。 船本身的變換定位船在海上的位置。瞭望塔的變換定位它在船上的位置，諸如此類。

這樣的話，當父對象移動時，子節點也自動地跟着移動。 如果改變了船的自身變換，瞭望塔，海盜和鸚鵡都會隨之變動。 如果當船移動時，就得手動調整每個對象的變換來防止滑動，那可相當令人頭疼。

但是爲了在屏幕上真正地描繪鸚鵡，我需要知道它在世界上的絕對位置。 我會調用父節點相關的變換對對象的自身變換進行變換。 爲了渲染對象，我需要知道對象的世界變換。

自身變換和世界變換

計算對象的世界變換很直接——從根節點開始通過父節點鏈一直追蹤到對象，將經過的所有變換綁在一起。 換言之，鸚鵡的世界變換如下：

我們每幀需要爲遊戲世界的每個對象計算世界變換，因此哪怕每個模型只有一部分矩陣乘法， 它也處於代碼影響性能的關鍵位置上。 保持它們及時更新是有技巧的，因爲當父對象移動時，它影響自己的世界變換，並遞歸影響所有子節點。

最簡單的方法是在渲染時計算變換。 每一幀，我們從最高層遞歸遍歷整個場景圖。 我們計算每個對象的世界變換然後立刻繪製它。

但這完全是在浪費CPU！ 很多遊戲世界的對象不是每幀都在移動。 想想那些構成關卡的靜態幾何圖形。 在沒有改變的情況下每幀計算它們的世界變換是一種浪費。

緩存世界變換

明顯的解決方案是緩存它。 在每個對象中，我們存儲它的自身變換和世界變換。 當我們渲染時使用預計算的世界變換。 如果對象從未移動，緩存的變換永遠是最新的變換，每個人都很開心。

當一個對象確實移動了，簡單的解決方式是之後就更新世界變換。 但是不要忘記層次性！當父節點移動時，我們得計算它的世界變換並遞歸計算它所有的子對象。

想象遊戲中忙碌的時刻。 在一幀中，船在海上顛簸，瞭望塔在風中搖晃，海盜被甩到了邊緣，而鸚鵡撞上了他的腦袋。 我們改變了四個自身變換。如果每次自身變換都立即更新世界變換，會發生什麼？

我只移動四個對象，但我們做了十次世界變換計算。 那就有六次在被渲染器使用前浪費了。 我們計算了鸚鵡的世界變換四次，但它只需渲染一次。

問題在於世界變換也許會依賴於多個自身變換。 由於我們每次變化就立即重新計算，當自身變換依賴的多個世界變換在同一幀發生變化時， 我們就對同一變換做了多次重新計算。

延期重計算

我們會通過解耦自身變換和世界變換的更新來解決這個問題。 這讓我們先在一次批處理中改變自身變換，在這些改變完成之後，在渲染它之前，重新計算它們世界變換。

爲了做到這點，我們爲圖中的每個對象添加標識。 “標識”和“位”在編程中密切相關——都代表處在兩種狀態之一的一小塊數據。 我們稱之爲“真”和“假”，或者有時稱爲“設置”和“清除”。 我之後會交替使用它們。

當自身變換改變了，我們設置它。 當我們需要對象的世界變換時，我們檢查這個位。 如果它被設置了，計算世界變換然後清除標識。 那個標識代表着，“世界變換過時了嗎？” 由於它們沒有被清除，這種“過時的雜亂”被稱爲“髒”。 也就是髒標識。“髒位”也是這個模式通常使用的名字，但是我決定使用不那麼下流的稱呼。

如果我們運用這個模式，然後移動之前例子中所有對象，那麼遊戲最終是這樣的：

這就是你能希望得到的最好結果了——每個受影響對象的世界變換隻被計算一次。 使用僅僅一位數據，這個模式爲我們做了以下事情：

• 它將對象的父節點鏈上的衆多的自身變換變化歸併成對象上的一次計算。

• 它避免了在沒有移動的對象上重新計算。

• 還有一個小小的意外收穫：如果對象在渲染前被刪除了，不必再計算它的世界變換。

模式

一組原始數據隨着時間變化而改變。 使用代價昂貴的過程推定一組導出數據。 用一個“髒”標識追蹤導出數據是否與原始數據保持一致。 它在原始數據改變時被設置。 如果導出數據被請求時，該標識被設置了，那麼重新計算並清除標識 否則的話，使用之前緩存的導出數據。

何時使用

與這本書中的其他模式相比，這個模式解決了一個非常特殊的問題。 同時，就像其他優化一樣，只在性能問題足夠大時，再使用這一模式增加代碼的複雜度。

髒標識在兩種任務上應用：“計算”和“同步”。 在兩種情況下，從原始數據變換到導出數據消耗很多時間，或者有很多其他方面的消耗。

在我們的場景圖例子中，這個過程非常緩慢是因爲需要執行很多數學運算。 在同步上使用這個模式是另一個應用場景， 導出數據在別的地方——在磁盤上或者在網絡另一頭的終端機上——從點A傳輸到點B消耗很大。

這裏是一些其他的應用場景：

• 原始數據的變化速度遠高於導出數據的使用速度。 避免在導出數據使用前原始數據多次變化帶來的不必要計算。 如果你總在原始數據變化後立即使用導出數據，這個模式無法幫忙。

• 增量更新十分困難。 假設海盜船隻能攜帶特定數量的戰利品。我們需要獲取攜帶事物的總重量。 我們可以使用這個模式，然後爲總重量設立髒標識。每次添加或者移除一些戰利品，我們設置這個標識。 當我們需要總量時，將所有戰利品的重量加起來，然後清除標識。

  但是更簡單的解決方法是保存計算總量。 當我們添加或刪除事物，直接從現在的總重量添加或者刪除它的重量。 如果我們可以承擔得起消耗，保持導出數據的更新，那麼更好的選擇是不用這個模式， 每次需要時重新計算導出數據。

這聽起來髒標識很少有能使用的時候，但你總會找到一兩個部分它能幫得上忙。 直接在你的遊戲代碼庫中搜索“dirty”，通常會發現這個模式的使用之處。

記住

哪怕是在說服自己這個模式在這裏很恰當之後，這裏還有一些瑕疵可能會讓你不爽。

延期太久是有代價的

這個模式將某些耗時的工作延期到真正需要結果的時候，但是當它要的時候，通常是現在就要。 但是我們使用這個模式的原因是計算很耗時！

在例子中，這不是問題，因爲我們還是可以在一幀之內計算世界座標，但是可以想象其他情況下，工作需要消耗可觀時間。 如果玩家想要結果時才開始計算，這會引起不愉快的卡頓。

延期的另一個問題是，如果有東西出錯了，你可能根本無法彌補。 當你使用這個模式將狀態持久化時，問題更加突出。

舉個例子，文本編輯器知道文檔有“沒保存的修改”。 在文件標題欄的小點或者星號就是可見的髒標識。 原始數據是在內存中打開的文檔，推導數據是在磁盤上的文件。

很多程序直到文檔關閉或者應用退出才保存到磁盤上。 在大多數情況下這很好，但是如果一不小心踢到了插線板，你的主要工作也就隨風而逝了。

在後臺自動保存備份的編輯器彌補了這一失誤。 自動保存的頻率保持在崩潰時不丟失太多數據和頻繁保存文件之間。

每次狀態改變你都得保證設置標識。

由於推導數據是從原始數據推導而來的，它本質上是緩存。 無論何時緩存了數據，都是需要保證緩存一致性的——在緩存與原始數據不同步時通知之。 在這個模式上，這意味着在任何原始數據變化時設置髒標識。

一處遺漏，你的程序就使用了錯誤的推導數據。 這引起了玩家的困惑和非常難以追蹤的漏洞。 當使用這個模式時，你也得注意，任何修改了原始數據的代碼都得設置髒標識。

一種解決它的方法是將原始數據的修改隱藏在接口之後。 任何想要改變狀態的代碼都要通過API，你可以在API那裏設置髒標識來保證不會遺漏。

得將之前的推導數據保存在內存中。

當推導數據被請求而髒標識沒有設置時，就使用之前計算出的數據。 這很明顯，但這需要在內存中保存推導數據，以防之後再次使用。

如果你沒有使用這個模式，可在需要時計算推導數據，使用完後釋放。 這避免將其存儲回內存的開銷，而代價是每次使用都需要重新計算。

就像很多優化一樣，這種模式以內存換速度。 通過在內存中保存之前計算的結果，避免了在它沒有改變的情況下重新計算。 這種交易在內存便宜而計算昂貴時是划算的。 當你手頭有更多空閒的時間而不是內存的時候，最好在需求時重新計算。

示例代碼

假設我們滿足了超長的需求列表，看看在代碼中是如何應用這個模式的。 就像我之前提到的那樣，矩陣運算背後的數學知識超出了本書的範圍，因此我將其封裝在類中，假設在某處已經實現了：

class Transform
{
public:
  static Transform origin();

  Transform combine(Transform& other);
};

這裏我們唯一需要的操作就是combine()， 這樣可以將父節點鏈上所有的自身變換組合起來獲得對象的世界變換。 同樣有辦法來獲得原點變換——通常使用一個單位矩陣，表示沒有平移，旋轉，或者拉伸。

下面，我們勾勒出場景圖中的對象類。這是在應用模式之前所需的最低限度的東西：

class GraphNode
{
public:
  GraphNode(Mesh* mesh)
  : mesh_(mesh),
    local_(Transform::origin())
  {}

private:
  Transform local_;
  Mesh* mesh_;

  GraphNode* children_[MAX_CHILDREN];
  int numChildren_;
};

每個節點都有自身變換描述了它和父節點之間的關係。 它有代表對象圖形的真實網格。（將mesh_置爲NULL來處理子節點的不可見節點。） 最終，每個節點都包含一個有可能爲空的子節點集合。

通過這樣，“場景圖”只是簡單的GraphNode，它是所有的子節點（以及孫子節點）的根。

GraphNode* graph_ = new GraphNode(NULL);
// 向根圖節點增加子節點……

爲了渲染場景圖，我們需要的就是從根節點開始遍歷節點樹，然後使用正確的世界變換爲每個節點的網格調用函數：

void renderMesh(Mesh* mesh, Transform transform);

我們不會直接在這裏實現，但在真正的實現中它會做渲染器爲了將網格繪製在世界上給定的位置所需要的一切。 如果對場景圖中的每個節點都正確有效地調用，這就愉快地完成了。

尚未優化的遍歷

讓我們開始吧，我們做一個簡單的遍歷，在渲染需要時去計算所有的世界位置。 這沒有優化，但它很簡單。我們添加一個新方法給GraphNode：

void GraphNode::render(Transform parentWorld)
{
  Transform world = local_.combine(parentWorld);

  if (mesh_) renderMesh(mesh_, world);

  for (int i = 0; i < numChildren_; i++)
  {
    children_[i]->render(world);
  }
}

使用parentWorld將父節點的世界變換傳入節點。 這樣，需要獲得這個節點的世界變換隻需要將其和節點的自身變換相結合。 不需要向上遍歷父節點去計算世界變換，因爲我們可以在向下遍歷時計算。

我們計算了節點的世界變換，將其存儲到world，如果有網格，渲染它。 最後我們遍歷進入子節點，傳入這個節點的世界變換。 無論如何，這是一個緊密的，簡單的遍歷方法。

爲了繪製整個場景圖，我們從根節點開始整個過程。

graph_->render(Transform::origin());

讓我們變髒

所以代碼做了正確的事情——它在正確的地方渲染正確的網格——但是它沒有高效地完成。 它每幀在圖中的每個節點上調用local_.combine(parentWorld)。 讓我們看看這個模式是如何修復這一點的。首先，我們給GraphNode添加兩個字段：

class GraphNode
{
public:
  GraphNode(Mesh* mesh)
  : mesh_(mesh),
    local_(Transform::origin()),
    dirty_(true)
  {}

  // 其他方法……

private:
  Transform world_;
  bool dirty_;
  // 其他字段……
};

world_字段緩存了上一次計算出來的世界變換，dirty_當然就是髒標識字段。 注意標識初始爲true。當我們創建新節點時，我們還沒有計算它的世界變換。 初始時，它與自身變換不是同步的。

我們需要這個模式的唯一原因是對象可以移動，因此讓我們添加對這點的支持：

void GraphNode::setTransform(Transform local)
{
  local_ = local;
  dirty_ = true;
}

這裏重要的部分是同時設置髒標識。我們忘了什麼嗎？是的——子節點！

當父節點移動時，它所有子節點的世界座標也改變了。 但是這裏，我們不設置它們的髒標識。 我們可以那樣做，但是那要遞歸，很緩慢。我們可以在渲染時做點更聰明的事。讓我們看看：

void GraphNode::render(Transform parentWorld, bool dirty)
{
  dirty |= dirty_;
  if (dirty)
  {
    world_ = local_.combine(parentWorld);
    dirty_ = false;
  }

  if (mesh_) renderMesh(mesh_, world_);

  for (int i = 0; i < numChildren_; i++)
  {
    children_[i]->render(world_, dirty);
  }
}

這與原先的原始實現很相似。 關鍵改變是我們在計算世界變換之前去檢查節點是不是髒的，然後將結果存在字段中而不是本地變量中。 如果節點是乾淨的，我們完全跳過了combine()，使用老的但是正確的world_值。

這裏的技巧是dirty參數。 如果父節點鏈上有任何節點是髒的，那麼就是true。 當我們順着層次遍歷下來時，parentWorld用同樣的方式更新它的世界變換，dirty追蹤父節點鏈是否有髒。

這讓我們避免遞歸地調用setTransform()標註每個子節點的dirty_標識。 相反，我們在渲染時將父節點的髒標識傳遞給子節點，然後看看是否需要重新計算它的世界變換。

這裏的結果正是我們需要的： 改變節點的自身變換隻是一些聲明，渲染世界時只計算從上一幀以來所需的最小數量的世界變換。

設計決策

這種模式非常具體，所以只需注意幾點：

什麼時候清空髒標識？

• 當結果被請求時：

  • 如果不需要結果，可以完全避免計算。 如果原始數據變化的速度比推導數據獲取的速度快得多，這效果很明顯。

  • 如果計算消耗大量時間，這會造成可察覺的卡頓。 將工作推遲到玩家想要結果的時候會嚴重影響遊戲體驗。 這部分工作一般足夠快，不會構成問題，但是如果構成問題，你就需要提前做這些工作。

• 在精心設計的檢查點處：

  有時候，會有某個時間點適合這麼做，或在遊戲過程中某個自然適合處理推遲計算的時機去做。 例如，只有海盜船駛入港口才會去保存遊戲。 如果同步點不是遊戲的機制，我們會將這些工作隱藏在加載畫面或者過場動畫之後。

  • 這種工作不會影響到玩家體驗。 不像前一個選項，你總會在遊戲緊張運行時打斷玩家的注意力。

  • 在工作時喪失了控制權。 這和前一個選項相反。你在處理時能進行微觀控制，確保有效且優雅地處理它。

    你不能保證玩家真的到了檢查點或者滿足了定義的條件。 如果他們在遊戲中迷失了，或者遊戲進入了奇怪的狀態，最終工作會推遲得超乎預料的晚。

• 在後臺處理：

  通常情況下，你在第一次更改時啓動固定時長的計時器，然後在計時器到時間後處理之間的所有變化。

  • 可以控制工作進行的頻率。 通過調節計時器，可以保證它發生得像預期一樣頻繁（或者不頻繁）。

  • 更多的冗餘工作。 如果原始狀態在計時器運行之間只改變了很少的部分，最終處理的大部分都是沒有改變的數據。

  • 需要支持異步工作。 在“後臺”處理數據意味着玩家可以同時繼續做事。 這就意味着你將會需要線程或者其他並行支持，這樣遊戲在處理數據的同時仍然可以繼續遊玩。

    由於玩家很可能與處理中的狀態交互，你也需要考慮保持並行修改的安全性。

髒追蹤的粒度有多細？

假設我們的海盜遊戲允許玩家建造並個性化自己的船。 船在線時會自動保存，這樣玩家可以在離線後重新恢復。 我們使用髒標識記錄船的哪塊甲板被修改了並需要發送到服務器。 每一塊發送給服務器的數據都包括了修改的數據和一些描述改動發生在何處的元數據。

• 如果粒度更細：

  假設你爲甲板上的每個小木板都拍上一個髒標識。

  • 你只需處理真正改變的數據。 你只將船上修改了的數據發送到服務器。

• 如果粒度更粗：

  或者，我們可以爲每層甲板關聯一個髒標識。改變它上面的任何東西都會讓整個甲板變髒。

  • 最終需要處理沒有變化的數據。 在甲板上添加一個桶，就要將整層甲板發送到服務器。

  • 用在存儲髒標識上的內存更少。 爲甲板上添加十個桶只需要一位來追蹤。

  • 固定開銷花費的時間更少。 當處理某些修改後的數據時，通常處理數據之前有些固定的工作要做。 在這個例子中，是確認船上改動在哪裏的元數據。 處理的塊越大，那麼要處理的數量就越少，這就意味着有更小的開銷。

參見

• 在遊戲之外，這個模式在像Angular的瀏覽器方向框架中是很常見的。 它們使用髒標識來追蹤哪個數據在瀏覽器中被改變了，需要將其推向服務器。

• 物理引擎追蹤哪些對象在運動中哪些在休息。 由於休息的骨骼直到有力施加在上面纔會移動，在被碰到時纔會需要處理。 “正在移動”就是一個髒標識，標註哪個對象上面有力施加並需要物理解析。