20. 최적화 패턴 - 공간 분할

 

20.1 의도 

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

 

20.2 동기

주변에 어떤 객체들이 있는지를 알고 싶을 때 게임 상에 존재하는 모든 객체 사이의 거리를 확인하는 행동(O(n²)의 복잡도)을 매 프레임마다 진행할 경우 성능 병목이 될 수 있다.

위치에 따라 유닛을 정렬하고 나면 전체 배열을 다 훑지 않고도 이진 검색 같은 걸로 주변 유닛을 쉽게 찾을 수 있다. (O(log n)의 복잡도)

 

20.3 패턴

객체들은 공간 위에서의 위치 값을 갖는다. 공간 자료구조를 통해서 같은 위치 혹은 주변에 있는 객체를 빠르게 찾을 수 있다. 객체 위치가 바뀌면 공간 자료구조도 업데이트해 계속해서 객체를 찾을 수 있도록 한다.

 

20.4 언제 쓸 것인가?

공간 분할 패턴은 살아 움직이는 게임 객체뿐만 아니라 정적인 프랍이나 지형을 저장하는 데에도 흔하게 사용된다.

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

 

20.5 주의사항

객체가 많이 없으면 의미가 없다.

객체의 위치 변경을 처리하기가 어렵다. 객체의 바뀐 위치에 맞춰 자료구조를 재정리(정렬)해야하기 때문에 코드가 더 복잡하고 CPU도 더 소모한다.

속도를 위해 메모리를 희생하는 패턴이기 때문에 메모리가 부족한 환경에서는 오히려 손해일 수도 있다.

 

20.6 예제 코드

공간 분할 패턴은 구현 방법에 여러가지 변형이 있고, 변형들이 잘 문서화 되어 있다.

 

예제 코드는 가장 간단한 공간 분할 형식인 고정 격자 방법에 대한 것이다.

class Unit {
    // 유닛이 움직일 때 격자에 속해 있는 데이터도 제대로 위치해 있도록
    // Grid 객체와 왔다 갔다 해야 할 수 있기 때문에 Grid 클래스가 friend로 정의되어 있다.
    friend class Grid; 

public:
    Unit (Grid* grid, double x, double y) // 새로 유닛을 생성하면서 grid의 (x, y) 좌표에 넣는다.
    : grid_(grid), x_(x), y_(y),
    prev_(NULL), next_(NULL){
        grid_->add(this);
    }
    
    void move(double x, double y);
    
private:
    double x_, y_;
    Grid* grid_;
    Unit* prev_; // 이중 연결 리스트로 유닛을 관리하기 위함
    Unit* next_;
};

class Grid {
public:
    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_ = cells[cellX][cellY];
        cells_[cellX][cellY] = unit;
        
        if (unit->next_ != NULL) {
            unit->next_->prev_ = unit;
        }
    }
    
    static const int NUM_CELLS = 10;
    static const int CELL_SIZE = 20;
private:
    // 배열의 각 원소는 해당 격자에 들어있는 unit들중 가장 앞에 있는 unit을 가리킨다.
    Unit* cells_[NUM_CELLS][NUM_CELLS]; 
};

격자의 같은 칸에 위치하는 유닛들은 주변에 있는 유닛들로 간주한다. 주변에 있는 유닛들 끼리 상호작용을 해야하기 때문에 같은 칸에 유닛들이 4개 있다면 6번의 상호작용 처리(handleAttack 함수)가 필요하다.

전체 월드에 있는 모든 유닛을 확인하지 않고 같은 칸에 들어 있을 정도로 가까운 유닛들만 검사한다는 점이 최적화의 핵심이다. 

void Grid::handleMelee() { // 각 셀에서 일어나는 전투들을 모두 수행하는 함수
    for (int x = 0; x < NUM_CELLS; x++) {
        for (int y = 0; y < NUM_CELLS; y++) {
            handleCell(cells_[x][y]);
        }
    }
}

void Grid::handleCell(Unit* unit) { // 각 셀에 있는 유닛들끼리 서로 전투(handleAttack)를 진행함
    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_;
    }
}

 

유닛이 다른 셀로 이동하는 경우

유닛의 move 함수는 포워딩의 역할만 할 뿐 대부분의 처리는 Grid의 move에서 이뤄진다. (Grid 객체 하나가 모든 유닛들을 관리하기 때문)

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

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

매 프레임마다 많은 유닛을 연결 리스트에서 넣었다 뺐다 할 수 있기 때문에, 추가, 삭제가 빠른 이중 연결 리스트를 사용한다.

같은 위치에 있는 유닛을 포함하여 공격 범위(주변의 다른 셀에 닿는 범위)에 있는 유닛들에도 상호작용 처리를 하고 싶다면 기준이 되는 유닛과 같은 위치에 있는 셀, 주변 4개의 셀에 들어있는 모든 unit들과 거리비교 (unit의 x_ y_를 이용)를 하여 ATTACK_DISTANCE보다 작은 경우에만 상호작용 처리(handleAttack 함수)를 진행한다.

 

격자의 주변 셀을 x, y 값 차이가 1 이하인 경우로 정의했을 때, 같은 위치의 셀을 제외한 주변 셀은 8개이지만 4개의 셀만 처리하는 이유는 발생하는 상호작용의 조건이 단순히 두 유닛의 거리에 따른 것(충돌 검사에 가까움, A와 B가 충돌한다는 것을 확인했다면 B와 A를 따로 검사할 필요가 없다)이고, 모든 유닛의 공격 범위가 같다고 가정했기 때문에 8개의 셀을 모두 검사한다면 중복해서 상호작용 처리가 일어 날 수 있기 때문이다.

 

최대 공격 범위가 한 칸의 크기보다 크면 주변 칸을 더 넓게 검색하거나 칸의 크기를 늘리는 방법이 있다.

 

20.7 디자인 결정

다양한 공간 분할 자료구조를 사용하여 객체를 담는 공간을 구현할 수 있다.

 

공간을 계층적으로 나눌 것인가, 균등하게 나눌 것인가?

격자 예제는 모든 공간을 균등하게 나눈 공간 분할이다.

계층적 공간 분할에서는 먼저 공간을 몇 개의 영역으로 나누고, 객체가 많은 영역은 다시 분할한다. 모든 영역에 들어있는 유닛 개수가 특정 개수 이하로 떨어질 떄 까지 이 과정을 재귀적으로 반복한다.

 

균등하게 나누는 경우

ㄴ 단순하다. 구현하기 편하다.

ㄴ 메모리 사용량이 일정하다.

ㄴ 객체가 위치를 이동할 때 자료구조의 업데이트 속도가 빠르다.

 

계층적으로 나누는 경우

ㄴ 빈 공간을 훨씬 효율적으로 처리할 수 있다.

ㄴ 밀집된 영역도 효과적으로 처리할 수 있다. 

객체들이 한 쪽에 몰려있는 경우 효과적이다.

 

객체 개수에 따라 분할 횟수가 달라지는가?

객체 개수와 상관없이 분할한다면

ㄴ 객체가 빠르게 이동할 수 있다. (유닛 하나가 다른 영역으로 이동해도 다른 유닛들까지 움직이진 않으니까)

ㄴ 영역이 균형 잡혀 있지 않을 수 있다.

 

객체 개수에 따라 영역이 다르게 분할된다면

ㄴ 이진 공간 분할(BSP)이나 k-d 트리 같은 공간 분할 방식

ㄴ 영역의 균형 잡힘을 보장할 수 있다. (성능, 프레임 레이트를 일정하게 유지할 수 있다)

ㄴ 전체 객체에 대해 한 번에 분할해놓는게 훨씬 효과적이다. (고정되어 있는 정적 지형이나 아트 리소스에 자주 사용된다.)

 

영역 분할은 고정되어 있지만, 계층은 객체 개수에 따라 달라진다면

ㄴ 분할 영역이 이동하지 않지만 영역에 들어있는 객체 개수가 정해진 수 이상 넘어가면 영역이 1/4 크기의 사각형 4개로 분할되는 쿼드트리

ㄴ 고정 분할과 적응형 분할의 장점을 둘 다 어느정도 가지는 공간 분할 방식

 

객체를 공간 분할 자료구조에만 저장하는가?

객체를 공간 분할 자료구조에만 저장한다면

ㄴ 관리해야 되는 컬렉션이 하나이므로 동기화 걱정을 안해도 된다.

 

다른 컬렉션에도 객체를 둔다면

ㄴ 객체마다 처리해야 할 작업이 있다면 전체 객체를 순회할 때 모든 격자를 탐색해야 한다. 객체를 별도의 컬렉션(Vector<unit*>와 같은)에 저장하면 순회 과정을 훨씬 빠르게 만들 수 있다.