1. 공간 분할

객체를 효과적으로 찾기 위해 객체 위치에 따라 구성되는 자료구조에 저장하는 기법

게임에서는 플레이어의 위치를 기준으로 주변에 어떤 객체들이 위치해 있는지 알아야한다. 이것을 매 프레임마다 확인한다면 성능이 떨어질 것이다. 이 때 효과적인 공간 분할 패턴을 사용할 수 있다.

하지만 공간 분할 패턴에서는 객체를 위치에 따라 정리하기 때문에 객체의 위치 변경을 처리하기가 어렵다. 따라서 객체의 바뀐 위치에 맞춰 자료구조를 재정리해야하기 때문에 코드가 더 복잡해지고 비용이 증가한다.

2. fixed grid 방법을 사용한 구현

1. 맵을 정사각형으로 나누고 전투를 처리할 때 같은 칸에 들어 있는 유닛만 신경쓴다.

• 유닛 클래스

class Unit
{
  friend class Grid:
public:
  Unit(Grid* grid, double x, double y): grid_(grid), x_(x), y_(y) {}
  void move(double x, double y);
private:
  double x_, y_;
  Grid* grid_;
}

Unit에는 2차원 상의 자기 위치 값과 자기가 속해 있는 Grid포인터가 있다. 유닛이 움직일 때 격자에 속해 있는 데이터도 제대로 위치해 있도록 Grid 객체와 왔다 갔다 해야 할 수 있기 때문에 Grid 클래스가 friend로 정의되어 있다.

• 격자 클래스

모든 칸이 유닛의 포인터로 되어있어 해당 유닛의 정보를 가지고 있다.

class Grid
{
public: 
  Grid()
  {
    for(int x = 0; x<NUM_CELLS; x++)
    {
      for(int y=0; y<NUM_CELLS; y++)
      {
        cells_[x][y] = NULL;
      }
    }
  }
  
  static const int NUM_CELLS = 10;
  static const int CELL_SIZE = 20;
private:
  Unit* cells_[NUM_CELLS][NUM_CELLS];
}

• 확장된 유닛 클래스

유닛을 연결리스트(double linked list)로 만들기 위해 이전 포인터와 다음 포인터를 가지도록 확장하자

class Unit
{
private:
  Unit* prev_;
  Unit* next_;
}

• 그리드에 유닛 넣기

void Grid::add(Unit* unit)
{
  // Determine which grid cell it's in.
  int cellX = (int)(unit->x_/ Grid::CELL_SIZE);
  int celly = (int)(unit->y_/ Grid::CELL_SIZE);
  
  //Add to the front of list for the cell it's in.
  unit->prev_ = NULL;
  unit->next_ = cells_[cellX][cellY];
  cells_[cellX][cellY] = unit;
  
  if(unit->next_ != NULL)
  {
    unit->next_->prev_ = unit;
  }
}

3. 기대 효과

같은 칸에 있는 유닛들의 연결리스트를 순회하기 때문에 모든 유닛을 검사하지 않아 최적화가 가능하다.