《游戲編程模式》（7）

Chapter 17 數據局部性

通過合理組織數據利用CPU緩存機制來加快記憶體訪問速度。

數據局部性：多級緩存加快了最近訪問過的數據的鄰近記憶體的訪問速度，保持數據位於連續的記憶體中可以提高性能。

找到出現性能問題的地方，不要把時間浪費在非頻繁執行的代碼上。

為了做到緩存友好，可能會犧牲繼承、介面等這些手段帶來的好處。

連續數組：

 1 AIComponent* aiComponents =
 2     new AIComponent[MAX_ENTITIES];
 3 PhysicsComponent* physicsComponents =
 4     new PhysicsComponent[MAX_ENTITIES];
 5 RenderComponent* renderComponents =
 6     new RenderComponent[MAX_ENTITIES]; 
 7 
 8 while (!gameOver)
 9 {
10   // Process AI.
11   for (int i = 0; i < numEntities; i++)
12   {
13     aiComponents[i].update();
14   } 
15 
16   // Update physics.
17   for (int i = 0; i < numEntities; i++)
18   {
19     physicsComponents[i].update();
20   } 
21 
22   // Draw to screen.
23   for (int i = 0; i < numEntities; i++)
24   {
25     renderComponents[i].render();
26   } 
27 
28   // Other game loop machinery for timing...
29 
30 } 

相比GameEntity里幾個指針指向對應component的方案，這個方案提高了每幀執行游戲迴圈時的緩存命中。

包裝數據：

 1 void ParticleSystem::update()
 2 {
 3   for (int i = 0; i < numParticles_; i++)
 4   {
 5     if (particles_[i].isActive())
 6     {
 7       particles_[i].update();
 8     }
 9   }
10 }

更新所有粒子，之前的判斷引發CPU預測失準和流水線停頓。

解決方案是跟蹤被激活粒子的數目：

1. 當粒子被激活時將它與第一個未激活粒子交換位置；
2. 當粒子被滅時將它與最後那個激活的粒子交換位置。

 1 for (int i = 0; i < numActive_; i++)
 2 {
 3   particles[i].update();
 4 }
 5  
 6 
 7 void ParticleSystem::activateParticle(int index)
 8 {
 9   // Shouldn't already be active!
10   assert(index >= numActive_);
11  
12   // Swap it with the first inactive particle
13   // right after the active ones.
14   Particle temp = particles_[numActive_];
15   particles_[numActive_] = particles_[index];
16   particles_[index] = temp;
17  
18   // Now there's one more.
19   numActive_++;
20 
21 } 
22 
23 void ParticleSystem::deactivateParticle(int index)
24 {
25   // Shouldn't already be inactive!
26   assert(index < numActive_); 
27 
28   // There's one fewer.
29   numActive_--;
30 
31   // Swap it with the last active particle
32   // right before the inactive ones.
33   Particle temp = particles_[numActive_];
34   particles_[numActive_] = particles_[index];
35   particles_[index] = temp;
36 
37 }

冷熱分解：

將數據結構分解為冷熱兩部分：

1. 熱數據 每幀需要用到的數據；
2. 冷數據 不會被頻繁使用的數據（分配一個指針塞下）

 1 class AIComponent
 2 {
 3 
 4 public:
 5   // Methods...
 6 
 7 private:
 8   Animation* animation_;
 9   double energy_;
10   Vector goalPos_;
11  
12   LootDrop* loot_;
13 
14 };
15 
16 class LootDrop
17 {
18   friend class AIComponent;
19 
20   LootType drop_;
21   int minDrops_;
22   int maxDrops_;
23   double chanceOfDrop_;
24 
25 };

Chapter 18 臟標記模式

將工作推遲到必要時進行以避免不必要的工作。

衍生數據由原始數據經過一些代價高昂的操作確定。用一個臟標記跟蹤衍生數據是否與原始數據同步，同步時使用緩存數據，不同步時則重新計算衍生數據並清除標記。

臟標記模式增加了代碼複雜性：

1. 用代碼複雜性換取性能的優化；
2. 太慢的計算不行，如一幀內處理不完的；
3. 必須保證每次狀態改動都設置標記（單一API封裝）。 

Example：

矩陣計算

1 class Transform
2 {
3 
4 public:
5   static Transform origin(); 
6 
7   Transform combine(Transform& other);
8 
9 };

GraphNode（初始化dirty_為true）

 1 class GraphNode
 2 {
 3 
 4 public:
 5   GraphNode(Mesh* mesh)
 6   : mesh_(mesh),
 7     local_(Transform::origin()),
 8     dirty_(true)
 9   {}
10 
11   void renderMesh(Mesh* mesh, Transform transform);
12 
13   // Other methods... 
14 
15 private:
16   Transform world_;
17   bool dirty_;
18 
19   Transform local_;
20   Mesh* mesh_;
21 
22   GraphNode* children_[MAX_CHILDREN];
23   int numChildren_;
24 
25 };

設置Transform並設置dirty

1 void GraphNode::setTransform(Transform local)
2 {
3   local_ = local;
4   dirty_ = true;
5 }

渲染：

 1 void GraphNode::render(Transform parentWorld, bool dirty)
 2 {
 3   dirty |= dirty_;
 4   if (dirty)
 5   {
 6     world_ = local_.combine(parentWorld);
 7     dirty_ = false;
 8   } 
 9 
10   if (mesh_) renderMesh(mesh_, world_);
11  
12   for (int i = 0; i < numChildren_; i++)
13   {
14     children_[i]->render(world_, dirty);
15   }
16 }

檢查臟標記並把它繼續傳給子節點。