Spatial Partition, 공간분할 [디자인패턴](최적화)

 

 

이 패턴을 사용하는 의도는

 

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

 

게임 자체는 다른 세상을 경험하게 해준다.

나는 현실의 한국 서울에 사는 대학생일지 몰라도

중세시대 성을 지키는 기사가 될 수도 있다.

하지만 몰입을 위해 실제 현실적인 것들을 게임에 다 반영하다보니 게임에서도 현실감을 느낄 수 있다.

 

이 말을 왜했느냐?

현실 감을 줄 수 있는 요소 중 하나인 위치, location(not position)에 대해 알아보려고 한다.

게임 월드에는 공간, space에 대한 개념이 존재해서 객체는 공간 어딘가의 위치에 존재하게 된다.

위치 개념은 여러 형태로 확인 가능하다.

 

가장 분명한 것은 객체가 움직이고 충돌하고 상호작용하는 물리이지만 다른 예도 있다.

오디오 엔진에서는 소리 나는 곳과 플레이어와의 거리에 따라 소리 크기를 조절한다.

멀리 떨어져 있는 플레이어와는 채팅이 불가하게 만들 수도 있다.

 

이를 위해서는 "주변"에 어떤 객체들이 "위치"해 있는지 알아야 한다.

이것을 매 프레임마다 확인한다면 성능이.. 떨어질 것이다.

 

예를 들어서 RTS를 만든다고 해보자.

전장에서는 수백이 넘는 군인들이 뒤엉켜 싸운다.

스타크래프트만 해도 인구수 200이니 400마리 저글링이 떼지어올 수도 있다.

 

즉, 매 프레임마다 검사한다면..?

 

void handleMelee(Unit* units[], int numUnits)
{
  for (int a = 0; a < numUnits - 1; a++)
  {
    for (int b = a + 1; b < numUnits; b++)
    {
      if (units[a]->position() == units[b]->position())
      {
        handleAttack(units[a], units[b]);
      }
    }
  }
}

 

미친 연산을 해야 한다.

O(n^2)의 복잡도를 가지는데.. 이런 복잡도는 사탄이다.

눈에 띄면 바로 제거해야 한다.

 

더욱이나 문제는 배열에 들어있는 유닛이 따로 정렬조차 되어 있지 않다는 것이다.

특정 위치 주변에 있는 유닛을 찾으려면 전체 배열을 순회해야 한다.

문제를 단순화하기 위해서 1차원이라고 생각해보자.

 

 

배열에 있는 유닛을 정렬하면 전체 배열을 훑지 않아도 바로 이진 검색으로 주변 유닛을 찾을 수는 있다.

이렇게 위치에 따라 구성되는 자료구조에 객체를 저장하면 객체를 빠르게 찾을 수 있다는 것을 알 수 있다.

이것을 2차원 이상의 공간에 적용한 것이 공간 분할 패턴이다.

 

---

 

객체들은 공간 위에서 위치 값을 갖는다.

이들 객체를 객체 위치에 따라 구성되는 공간 자료구조에 저장한다.

공간 자료구조를 통해서 같은 위치 혹은 주변에 있는 객체를 빠르게 찾을 수 있다.

객체 위치가 바뀌면 공간 자료구조도 업데이트해 계속해서 객체를 찾을 수 있도록 한다.

 

그렇다면 언제 써야 하는가??

공간 분할 패턴은 살아 움직이는 게임 개체뿐만 아니라

정적인 prop이나 지형을 저장하는데에도 흔하게 사용된다.

복잡한 게임에서는 컨텐츠별로 공간 분할 자료구조를 갖기도 한다.

 

위치 값이 있는 객체가 많고 위치에 따라 객체를 찾는 질의가 성능에 영향을 줄 정도면

이 패턴을 사용한다.

 

---

 

하지만 쓸 때에도 주의 사항은 있다.

공간 분할 패턴으로 앞선 O(N^2)의 시간 복잡도는 보다 줄일 수 있지만 

객체가 많을 때나 의미가 있다.

즉, 객체가 많이 없다면 저렇게 해도 된다는 말이다.

 

공간 분할 패턴에서는 객체를 위치에 따라 정리하기 때문에, 객체의 위치 변경을 처리하기가 훨씬 어렵다.

때문에 객체의 바뀐 위치에 맞춰 자료구조를 재정리해야 하기 때문에 코드가 더 복잡하고 CPU도 많이 쓴다.

즉, 쓰기 전에 써야만하는가? 에 대해서 생각해봐야 한다는 말이다.

또한 추가 메모리도 필요하다.

 

---

 

예제를 통해서 더 알아보자

패턴이라는 것은 의도만 같으면 구현 방법이 다양하다.

이 패턴 역시 다양하게 구현될 수 있지만 여기서는 고정 격자, fixed grid 방법을 통해 알아보자

 

모눈종이가 그냥 fixed grid라고 보면 된다.

 

맵을 정사각형으로 나누는 것과 같다.

전투를 처리할 때에는 같은 칸에 들어 있는 유닛만 신경쓰면 된다.

매번 모든 다른 유닛 전체와 비교한다면 너무나.. 힘들다.

 

유닛을 연결리스트로 저장한 격자 코드를 만들어보자

Unit 클래스는 아래와 같다.

 

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()
  {
    // Clear the 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];
};

 

모든 칸이 유닛의 포인터로 되어 있다.

이제 유닛이 이전 포인터와 다음 포인터를 갖도록 확장해보자

 

class Unit
{
  // Previous code...
private:
  Unit* prev_;
  Unit* next_;
};

 

이를 통해서 배열이 아니라 이중 연결 리스트, double linked list로 유닛을 관리할 수 있다.

 

 

격자 칸은 그 칸에 들어있는 유닛 리스트의 첫 번째 유닛을 포인터로 가리킨다.

유닛은 자기 이전과 이후 유닛을 포인터로 가리킨다.

??굳이 가리켜야 하나??? 라는 생각을 할 수 있다.

왜 그런지는 지켜보자

 

Unit::Unit(Grid* grid, double x, double y)
: grid_(grid),
  x_(x),
  y_(y),
  prev_(NULL),
  next_(NULL)
{
  grid_->add(this);
}

 

먼저 새로 만든 유닛을 적당한 격자 칸에 넣어야 한다.

이건 Unit 클래스 생성자에서 한다.

 

add() 메서드는 아래처럼 정의한다.

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;
  }
}

 

연결리스트 때문에 조금 복잡해진듯 하지만 기본 원리는 단순하다.

유닛이 들어갈 칸을 찾은 뒤 그 칸에 들어 있는 리스트 맨 앞에 유닛을 추가한다.

칸에 이미 유닛 리스트가 들어 있다면 추가한 유닛 뒤에 유닛리스트를 붙인다.

 

또한 일단 모든 유닛을 자기 칸 안에 넣은 뒤에는 유닛끼리 서로 칼을 휘두르게 할 수 있다.

격자를 이용해서 전투를 처리하는 메서드는 아래와 같다.

 

void Grid::handleMelee()
{
  for (int x = 0; x < NUM_CELLS; x++)
  {
    for (int y = 0; y < NUM_CELLS; y++)
    {
      handleCell(cells_[x][y]);
    }
  }
}

 

칸을 순회하면서 handleCell()을 호출하고 이름 그대로 큰 전장을 각각 고립된 전투 공간들로 분할한 셈이다.

각 칸에서는 아래처럼 같이 전투를 처리한다.

 

void Grid::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_;
  }
}

 

포인터로 연결리스트를 순회하기 위한 코드만 다룰 뿐

그 외에는 앞에서 무식하게 만들었던 전투 처리 코드와 같다.

이 코드에서도 모든 유닛 쌍에 대해서 같은 위치에 있는지를 검사하기 때문이다.

 

딱 하나 차이점이 있다면 더 이상 전장에 있는 모든 유닛을 확인하지는 않는다는 것이다.

대신 같은 칸에 들어 있을 정도로 가까운 유닛들만 검사한다.

**이것도 큰 최적화다.

 

하지만 칸이 너무 작아서..

칸마다 하나의 유닛이 있을정도로 작다면 오히려 오버헤드가 커지는 결과를 불러올 수도 있다.

 

---

 

성능 문제는 해결했지만 다른 문제가 생겼다.

유닛이 칸에 묶여 있어야 하다 보니 유닛이 지금 있는 칸 너머로 이동하면

그 칸에 있는 유닛들뿐만아니라 어느 유닛에서도 그 유닛을 볼 수 없게 된다.

 

이를 해결하기 위해서 유닛이 이동할 때마다 추가 작업을 해야 한다.

칸을 넘어가면 유닛을 현재 칸에서 제거하고 새로운 칸에 추가해야 한다.

먼저 Unit 메서드에 이동을 추가한다.

 

void Unit::move(double x, double y)
{
  grid_->move(this, x, y);
}

 

NPC를 제어하는 AI 코드와 플레이어 유닛을 조종하는 유저 입력 코드에서

이 메서드를 호출하면 딱 될 것 같다.

실제 작업은 Grid의 Move에서 실행된다.

 

void Grid::move(Unit* unit, double x, double y)
{
  // See which cell it was in.
  int oldCellX = (int)(unit->x_ / Grid::CELL_SIZE);
  int oldCellY = (int)(unit->y_ / Grid::CELL_SIZE);

  // See which cell it's moving to.
  int cellX = (int)(x / Grid::CELL_SIZE);
  int cellY = (int)(y / Grid::CELL_SIZE);

  unit->x_ = x;
  unit->y_ = y;

  // If it didn't change cells, we're done.
  if (oldCellX == cellX && oldCellY == cellY) return;

  // Unlink it from the list of its old cell.
  if (unit->prev_ != NULL)
  {
    unit->prev_->next_ = unit->next_;
  }

  if (unit->next_ != NULL)
  {
    unit->next_->prev_ = unit->prev_;
  }

  // If it's the head of a list, remove it.
  if (cells_[oldCellX][oldCellY] == unit)
  {
    cells_[oldCellX][oldCellY] = unit->next_;
  }

  // Add it back to the grid at its new cell.
  add(unit);
}

 

코드가 조금 길긴 하지만 그대로 따라 읽으면 된다.

앞에서는 유닛이 다른 칸으로 이동해야 하는지를 검사한다.

굳이 할 필요 없다면 유닛 위치만 업데이트하면 된다.

 

유닛이 다른 칸으로 가야 한다면

현재 칸의 연결 리스트에서 유닛을 제거한 뒤에 새로운 칸의 리스트에 추가한다.

새로운 유닛을 추가하는 것과 마찬가지로 이동 중인 유닛을 새로운 칸의 연결 리스트에 추가한다.

 

이렇게 매 프레임마다 많은 유닛을 연결 리스트에서 넣었다 뺐다 할 수 있기 때문에

추가, 삭제가 빠른 이중 연결 리스트를 사용하게 되는 것이다.

 

사실 근데 유닛들은 서로의 범위 안에서만 상호작용 해야 한다.

즉, 같은 위치에 있는 유닛끼리만 상호작용 했지만 공격 범위를 고려한 게임이 되어야...

진짜 우리가 알고 있는 게임이 될 것이다.

 

칼을 들고 있으면서 공격할 수 있는 거리가 거의 칼 손잡이로 찍는 범위면 화딱지나지 않겠는가?

아무튼 이럴 때는 위치가 같지 않더라도 공격 대상이 될 유닛을 조금 더 넓게 검사하는 것이 좋다.

 

if (distance(unit, other) < ATTACK_DISTANCE)
{
  handleAttack(unit, other);
}

 

범위를 검사할 때는 다른 칸에 들어있는 유닛도

상호작용할 수 있을 정도로 가까울 수 있다는 점도 유의하는 것이다.

 

 

칸만 다르지 가깝다.

사랑과 우정 사이 같은 느낌? 사랑보다는 먼 우정보다는 가까운?

 

그림을 보면 A,B에 대해서 같은 칸의 유닛뿐만 아니라 주변 칸에 들어있는 유닛들도 같이 비교해야 한다.

먼저 handleCell() 에서 내부 루프를 따로 빼보자.

 

void Grid::handleUnit(Unit* unit, Unit* other)
{
  while (other != NULL)
  {
    if (distance(unit, other) < ATTACK_DISTANCE)
    {
      handleAttack(unit, other);
    }

    other = other->next_;
  }
}

 

handleUnit()은 유닛 한 개와 그 유닛이 충돌하는지를 검사할 유닛 리스트를 인수로 받는다.

handleCell()에서는 handleUnit()을 사용하게 바꾼다.

 

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells_[x][y];
  while (unit != NULL)
  {
    // Handle other units in this cell.
    handleUnit(unit, unit->next_);

    unit = unit->next_;
  }
}

 

handleCell()은 유닛리스트가 아닌 칸의 좌표 값을 받는다.

이것 외에는 거의 다 똑같다.

코드를 확장하면 아래와 같다.

 

void Grid::handleCell(int x, int y)
{
  Unit* unit = cells_[x][y];
  while (unit != NULL)
  {
    // Handle other units in this cell.
    handleUnit(unit, unit->next_);

    // Also try the neighboring cells.
    if (x > 0 && y > 0) handleUnit(unit, cells_[x - 1][y - 1]);
    if (x > 0) handleUnit(unit, cells_[x - 1][y]);
    if (y > 0) handleUnit(unit, cells_[x][y - 1]);
    if (x > 0 && y < NUM_CELLS - 1)
    {
      handleUnit(unit, cells_[x - 1][y + 1]);
    }

    unit = unit->next_;
  }
}

 

확장된 handleUnit()에서는 현재 유닛이 주변 8칸 중에서 좌측 4칸에 들어 있는 유닛과 충돌 여부를 검사한다.

주변 유닛 중에서도 공격 범위 안에 들어와 있는 유닛에 대해서는 공격 처리를 한다.

 

 

내부 루프에서는 같은 유닛끼리 두 번 검사하는 것을 막기 위해

현재 유닛을 다음 유닛부터 검사했다.

마찬가지 이유로 주변 칸도 절반만 검사한다.

 

주변 8칸 모두를 검사한다면..?

A의 오른쪽 칸에 B가 있다고 서로 공격 범위에 있다고 해보자

모든 유닛에 대해서 8칸을 검사한다면..?

 

1. A 공격을 검사할 때 오른쪽 B를 찾아 A와 B 사이의 공격 상호작용 발생

2. B 공격을 검사할 때 왼쪽 A를 찾아 A와 B 사이의 공격 상호작용 발생

 

즉, 2번 발생한다.

절반만 찾으면 위의 문제를 해결할 수 있다.

다만 반을 어떻게 나눌지는 개발자의 몫이다.

그렇다면.. 공격 범위가 2칸이라면..? 더 확장하면 고려할 사항이 많아진다.