[Design Pattern] 게임 최적화 : 데이터 지역성, 더티 플래그, 오브젝트 풀, 공간 분할

// 개체 
class GameEntity
{
private:
  // 컴포넌트를 포인터로 가지고 있다. 
  AIComponent* ai;
  PhysicsComponent* physics;
  RenderComponent* render;

public:
  GameEntity(AIComponent* a, PhysicsComponent* p, RenderComponent* r) : ai(a), physics(p), render(r) {}
  AIComponent* ai() { return ai; }
  PhysicsComponent* physics() { return physics; }
  RenderComponent* render() { return render; }
};

class World
{
private:
  // 개체들을 포인터로 가지고 있다. 
  Entity* entities[MAX_ENTITIES]; 
  int numEntities;
  
public:
  // 게임 루프 
  void gameLoop()
  {
    while (true)
    {
      // AI를 처리한다
      for (int i = 0; i < numEntities; i++)
        entities[i]->ai()->update();
      
      // 물리를 업데이트한다 
      for (int i = 0; i < numEntities; i++)
        entities[i]->physics()->update();
              
      // 화면에 그린다
      for (int i = 0; i < numEntities; i++)
        entities[i]->render()->update();
    }
  }
};

// 객체들이 들어가는 배열을 마련한다. 
AIComponent* aiComponents = new AIComponent[MAX_ENTITIES];
PhysicsComponent* physicsComponents = new PhysicsComponent[MAX_ENTITIES];
RenderComponent* renderComponents = new RenderComponent[MAX_ENTITIES];

// 그러면 이렇게 게임루프에서 해당 컴포넌트 객체에 바로 접근이 가능하다. 
void gameLoop()
{
  while (true)
  {
    for (int i = 0; i < numEntities; i++)
      aiComponents[i]->update();
  
    for (int i = 0; i < numEntities; i++)
      physicsComponents[i]->update();
          
    for (int i = 0; i < numEntities; i++)
      renderComponents[i]->update();
  }
}

class Partical
{
public:
  void update();
  bool isActive();
};

class ParticalSystem
{
private:
  static const int MAX_PARTICLES = 100000;
  int numParticles;
  Particle particles[MAX_PARTICLES];
  
public:
  ParticalSystem() : numParticles(0) {}
  
  void update()
  {
    for (int i = 0; i < numParicles; i++)
      // 플래그를 검사해서 활성화된 파티클만 업데이트한다. 
      if (particles[i].isActive()) 
        particles[i].update();
    
    // 만약 활성화 파티클이 적으면 어떻게 될까?
    // 계속 건너뛰는 횟수가 많아질 것이며 그만큼 캐시 미스가 발생할 것이다. 
  }
};

// 파티클 활성화하기
void ParticleSystem::activateParticle(int idx)
{
  // 비활성 상태여야한다. 
  assert(idx >= numActive);
  
  // 비활성 파티클의 맨 앞에 있는 것과 바꿔치기한다. 
  swap(particles[idx], particles[numActive]);
  
  numActive++;
}

// 파티클 비활성화하기 
void ParticleSystem::deactivateParticle(int idx)
{
  // 활성 상태여야한다. 
  assert(idx < numActive);
  
  numActive--;
  
  // 활성 파티클의 맨 뒤에 있는 것과 바꿔치기한다. 
  swap(particles[idx], particles[numActive])
}

class AIComponent
{
private:
  Animation* animation;
  double energy;
  Vector goalPos;
  
  // 죽었을 때 아이템을 떨구기 위한 데이터들
  LootType drop;
  int minDrops;
  int maxDrops;
  double chanceOfDrop;

public:
  void update();
  // 매 프레임 마다 애니메이션, 에너지 값, 목표 지점을 확인하고 변경한다. 
  // 또한 죽었을 때 아이템을 떨어뜨리는 데이터들도 확인하고 변경한다. 
};

// 한산한 데이터들
class LootDrop
{
friend class AIComponet;
  LootType drop;
  int minDrops;
  int maxDrops;
  double chanceOfDrop;
};

class AIComponent
{
private:
  // 빈번한 데이터들
  Animation* animation;
  double energy;
  Vector goalPos;
  
  // 한산한 데이터들은 포인터로 가리키게 한다. 
  // AIComponent의 전체 크기가 줄어든다. 
  LootDrop* loot;
};

class Transform
{
public:
  // 아무런 이동, 회전, 크기 변화가 없는 단위행렬로 나타낸 기본 트랜스폼을 반환한다. 
  static Transform origin();
  
  // 객체의 월드 트랜스폼을 계산한다. 
  // 상위 노드를 따라서 로컬 트랜스폼 값을 전부 결합해서 계산한다. 
  Transform combine(Transform& other);
};

class GraphNode
{
private:
  Transform local;
  Mesh* mesh;
  GraphNode* children[MAX_CHILDREN];
  int numChildren;

public:
  GraphNode(Mesh* m) : mesh(m), local(Transform::origin()) {}
};

// 렌더링한다. 
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);
}

class GraphNode
{
private:
  Transform world; // 월드 트랜스폼을 캐시한다.
  bool dirty;      // 더티 플래그 
  
  Transform local;
  Mesh* mesh;
  GraphNode* children[MAX_CHILDREN];
  int numChildren;

public:
  GraphNode(Mesh* m) : mesh(m), local(Transform::origin()), dirty(true) {}
  
  // 로컬 트랜스폼을 변화시킨다.
  void setTransform(Transform l)
  {
    local = l;
    dirty = true; // 더티 플래그가 켜진다. 
  }
  
  // 렌더링한다. 
  void render(Transform parentWorld, bool d)
  {
    dirty |= d;
    if (d)
    {
      // 더티 플래그가 켜졌을 때만 월드 트랜스폼을 계산한다. 
      world = local.combine(parentWorld);
      dirty = false;
    } 
    
    if (mesh) renderMesh(mesh, world);
  
    // 모든 하위 객체들을 재귀적으로 호출한다.
    // 만약 상위 객체 중에 하나라도 d == true 였다면
    // 그 하위 객체들은 모두 업데이트된다. 
    for (int i = 0; i < numChildren; i++)
      children[i]->render(world, d);
  }
};

class Particle
{
private:
  int framesLeft;
  double x, y;
  double xVel, yVel;

public:
  Particle() : framesLeft(0) {}
  
  void init(double _x, double _y, double _xVel, double _yVel, int lifetime)
  {
    x = _x;
    y = _y;
    xVel = _xVel;
    yVel = _yVel;
    framesLeft = lifetime;  
  }

  void animate()
  {
    if (inUse() == false) return;
    
    framesLeft--;
    x += xVel;
    y += yVel;
  }
  
  bool inUse() const { return framesLeft > 0; }
};

class ParticlePool
{
private:
  static const int POOL_SIZE = 100;
  Particle particles[POOL_SIZE];
  
public:
  void create(double _x, double _y, double _xVel, double _yVel, int lifetime)
  {
    for (int i = 0; i < POOL_SIZE; i++)
    {
      // 아직 사용 중이지 않은 객체를 찾아서 초기화한다. 
      if (particles[i].inUse() == false)
      {
        particles[i].init(_x, _y, _xVel, _yVel, lifetime);
        return;
      }
    }
  }
  
  void animate()
  {
    for (int i = 0; i < POOL_SIZE; i++)
      particles[i].animate();
  }
};

class Particle
{
private:
  int framesLeft;
  
  union 
  {
    // 살아 있는 동안의 상태들
    struct
    {
      double x, y;
      double xVel, yVel;
    } live;
    
    // 이 파티클 다음에 사용 가능한 파티클 객체를 가리킨다. 
    Particle* next;
  } state;

public:
  Particle* getNext() const { return state.next; }
  void setNext(Particle* next) { state.next = next; }
  
  bool animate()
  {
    if (inUse() == false) return false;
        
    framesLeft--;
    x += xVel;
    y += yVel;
    
    // 파티클이 죽으면 true를 반환해서
    // 빈칸 리스트에 추가할 수 있도록 한다. 
    return framesLeft == 0;
  }
};

class ParticlePool
{
private:
  Particle* firstAvailable;

public:
  ParticlePool()
  {
    // 처음 파티클부터 사용 가능하다. 
    firstAvailable = &particles[0];
    
    // 모든 파티클은 그 다음 파티클을 가리킨다. 
    for (int i = 0; i < POOL_SIZE - 1; i++)
      particles[i].setNext(&particles[i + 1]);
    
    // 마지막 파티클에서 리스트를 종료한다. 
    particles[POOL_SIZE - 1].setNext(NULL);
  }
  
  void create(double _x, double _y, double _xVel, double _yVel, int lifetime)
  {
    assert(firstAvailable != NULL);
    
    // firstAvailable이 얻은 파티클(newParticle)의 다음 객체를 가리키도록 해서 
    // 얻은 파티클을 빈칸 리스트에서 제외한다. 
    Particle* newParticle = firstAvailable;
    firstAvailable = newParticle->getNext();
    newParticle.init(_x, _y, _xVel, _yVel, lifetime);
  }
  
  void animate()
  {
    for (int i = 0; i < POOL_SIZE; i++)
    {
      // 파티클이 죽으면 
      if (particles[i].animate() == false) continue;
      
      // firstAvailable이 죽은 파티클을 가리키도록 해서
      // 죽은 파티클을 빈칸 리스트에 추가한다. 
      particles[i].setNext(firstAvailable);
      firstAvailable = &particles[i];
    }    
  }
};

// 격자에 존재하는 객체이다. 
class Unit
{
  friend class Grid;

private:
  double x, y;
  
  // 자신이 속한 격자를 가리킨다. 
  Grid* grid; 
  
  // 이전 유닛과 다음 유닛을 가리킨다. (이중 연결 리스트)
  Unit* prev; 
  Unit* next;

public:
  Unit(Grid* g, double _x, double _y) : grid(g), x(_x), y(_y), prev(NULL), next(NULL)
  {
    // 새로 만든 유닛을 적당한 격자 칸에 넣는다. 
    grid->add(this);
  }
  
  // 유닛이 움직이면 추가 작업이 필요하다. 
  void move(double _x, double _y)
  {
    grid->move(this, _x, _y);
  } 
};

class Grid
{
private:
  // 격자의 모든 칸은 유닛의 포인터로 되어 있다. 
  Unit* cells[NUM_CELLS][NUM_CELLS];

public:
  static const int NUM_CELLS = 10;
  static const int CELL_SIZE = 20;

  Grid()
  { 
    // 격자를 모두 지운다. 
    for (int x = 0; x < NUM_CELLS; x++)
      for (int y = 0; y < NUM_CELLS; y++)
        cells[x][y] = NULL;
  }
  
  void add(Unit* unit)
  {
    // 어느 칸에 들어갈지 결정한다. 
    int cellX = (int)(unit->x / Grid::CELL_SIZE);
    int cellY = (int)(unit->y / Grid::CELL_SIZE);
    
    // 칸에 들어 있는 리스트의 맨 앞에 추가한다. 
    unit->prev = NULL;
    unit->next = cell[cellX][cellY];
    if (unit->next != NULL)
      unit->next->prev = unit;
  }
  
  // 전투를 처리한다. 
  void handleMelee()
  {
    for (int x = 0; x < NUM_CELLS; x++)
      for (int y = 0; y < NUM_CELLS; y++)
        handleCell(cells[x][y]);
  }
  
  void handleCell(Unit* unit)
  {
    // 포인터로 연결 리스트를 순회하면서 전투를 처리한다. 
    // 결과적으로 해당 칸에 있는 유닛들만 검사하게 된다. 
    while(unit != NULL)
    {
      Unit* other = unit->next;
      
      while(other != NULL)
        // 완전히 똑같은 위치마나 고려한다. 
        if (unit->x == other->x && unit->y == other->y) 
          handleAttack(unit, other);
    
      other = other->next;
    }
    
    unit = unit->next;
  }
  
  void move(Unit* unit, double x, double y)
  {
    // 유닛이 어느 칸에 있었는지 확인한다. 
    int oldCellX = (int)(unit->x / Grid::CELL_SIZE);
    int oldCellY = (int)(unit->y / Grid::CELL_SIZE);
    
    // 유닛이 어느 칸으로 가야하는지 확인한다. 
    int cellX = (int)(x / Grid::CELL_SIZE);
    int cellY = (int)(y / Grid::CELL_SIZE);
    
    unit->x = x;
    unit->y = y;
    
    // 칸이 바뀌지 않았다면 더 할 일이 없다. 
    if (oldCellX == cellX && oldCellY == cellY) return;
    
    // 이전 칸에 들어 있는 리스트에서 유닛을 제거한다. 
    if (unit->prev != NULL) 
      unit->prev->next = unit->next;
    
    if (unit->next != NULL)
      unit->next->prev = unit->prev;
    
    // 유닛이 칸에 들어 있는 리스트의 머리였다면, 머리를 바꿔준다. 
    if (cells[oldCellX][oldCellY] == unit)
      cells[oldCellX][oldCellY] = unit->next;
    
    // 새로 들어갈 칸에 추가한다. 
    add(unit);
  }
};

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells[x][y];
  
  while(unit != NULL)
  {
    // 이 칸에 들어 있는 유닛들을 처리한다. 
    handleUnit(unit, unit->next);
    
    // 이 칸과 인접한 주변의 8칸 중에서
    // 좌측 4칸에 있는 유닛도 처리한다. 
    if (x > 0)                      handleUnit(unit, cells[x - 1][y]);
    if (y > 0)                      handleUnit(unit, cells[x][y - 1]);
    if (x > 0 && y > 0)             handleUnit(unit, cells[x - 1][y - 1]);
    if (x > 0 && y < NUM_CELLS - 1) handleUnit(unit, cells[x - 1][y + 1]);
    
    unit = unit->next;
  }
}

void Grid::handleUnit(Unit* unit, Unit* other)
{
  while(other != NULL)
  {
    // 범위를 고려한다. 
    if (distance(unit, other) < ATTACK_DISTANCE)
     handleAttack(unit, other);
    
    other = other->next;
  }
}