공간 분할 (Spatial Partition)

동기

게임 월드에는 공간이라는 개념이 있기 때문에 게임 오브젝트는 공간 어딘가의 위치에 존재하게 된다.

플레이어는 공간 내에 존재하는 모든 오브젝트와 거리에 상관없이 상호작용 하거나 렌더링 할 필요 없이 일정 거리 이내의 오브젝트들과 상호작용 하거나 렌더링 해주는걸로 충분하다.

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

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²)의 시간 복잡도를 소모하게된다. 유닛 수가 많아지면 검사 횟수가 기하급수적으로 늘어나게 되어 성능이 수직 하락하는 문제가 생긴다.

일단 당장 눈에 보이는 문제는 정렬이 되어 있지 않다는 것이다. 만약 거리순으로 정렬이 되어있다면 이진 탐색 등으로 매우 빠른 시간내에 주변 유닛을 탐색할 수 있다.

위의 예시처럼 전체 범위에 대해 1차원 배열을 사용한 것처럼 여러 범위로 쪼개어 확장시키면 2차원 이상의 공간을 사용할 수 있고 이것이 바로 공간 분할 패턴이다.

패턴

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

언제 쓸 것인가?

동적 오브젝트 뿐만 아니라 지형 등의 정적 오브젝트를 저장하는 데에도 흔하게 사용된다.

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

위치 값이 있는 객체가 많고, 위치에 따라 객체를 찾는 질의가 성능에 영향을 줄 정도로 잦을 때 사용한다.

주의사항

공간 분할 패턴을 사용하면 O(n²)인 복잡도를 쓸만한 수준으로 낮출 수 있지만 이는 객체가 많을수록 의미가 생긴다.

만약 n이 충분히 작으면 굳이 신경 쓸 필요가 없다.

객체를 위치에 따라 정리하기 때문에 객체의 위치 변경을 처리하기가 매우 어렵다.

객체의 바뀐 위치에 맞춰서 자료구조를 재정리해야 하기 때문에 코드가 더 복잡해질 뿐더러 CPU도 더 많이 소모하므로 공간 분할 패턴을 적용할만한 값어치가 있는지를 먼저 확인해보아야 한다.

게다가 일반적인 최적화들처럼 속도를 위해 메모리를 희생하기 때문에 메모리가 부족한 환경이라면 오히려 손해일 수도 있다.

예제

전체 전장을 모눈종이의 칸처럼 고정 크기로 나누고 유닛들을 배열이 아니라 격자 안에 넣는다.

칸마다 유닛 리스트가 존재하고 유닛이 해당 칸의 범위 안에 들어오면 그 유닛을 리스트에 저장한다.

그 이후에 전투를 처리할 때는 같은 칸 안에 들어있는 유닛만 신경 쓰면 되기 때문에 훨씬 적은 숫자의 유닛들과 비교할 수 있게 된다.

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* 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] = nullptr;
            }
        }
    }
    
    static const int NUM_CELLS = 10;
    static const int CELL_SIZE = 20;
    
private:
    Unit* cells_[NUM_CELLS][NUM_CELLS];
};

각 유닛은 2차원 위치 좌표와 자신이 속해있는 그리드의 포인터를 가진다.

연결 리스트로 구현할 것이기 때문에 prev, next 포인터 역시 만들어둔다.

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


void Grid::add(Unit* unit) {
    int cellX = (int)(unit->x_ / Grid::CELL_SIZE);
    int cellY = (int)(unit->y_ / Grid::CELL_SIZE);
    
    unit->prev_ = nullptr;
    unit->next_ = cells+[cellX][cellY];
    cells_[cellX][cellY] = unit;
    
    if (unit->next_ != nullptr)
        unit->next_->prev_ = unit;
}

이제 유닛은 새로 생성될때마다 그리드에 속함과 동시에 리스트에 추가한다. 흐름 자체는 단순하다.

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

void Grid::handleCell(Unit* unit) {
    while (unit != nullptr) {
        Unit* other = unit->next_;
        while (other != nullptr) {
            if (unit->x_ == other->x_ && unit->y_ == other->y_)
                handleAttack(unit, other);
            other = other->next_;
        }
        unit = unit->next_;
    }
}

코드만 보면 기존과 동일하게 모든 칸을 순회하며 함수를 호출하지만 차이가 있다면 맵에 존재하는 모든 유닛을 완전탐색 하는것이 아니라 같은 칸에 들어있는 유닛들만 확인하게 되므로 해당 칸을 기준으로 본다면 연산량이 대폭 줄어든다.

성능적인 문제는 해결된듯 하지만 유닛이 항상 칸에 묶여 있어야 하다보니 유닛이 다른 칸으로 이동할 때마다 현재 칸의 리스트에서 제거하고 이동하는 칸의 리스트에 추가해주는 작업을 해주어야 한다.

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;
    
    // 변동이 없으면 작업X
    if (oldCellX == cellX && oldCellY == cellY)
        return;
        
    if (unit->prev_ != nullptr)
        unit->prev_->next_ = unit->next_;
        
    if (unit->next_ != nullptr)
        unit->next_->prev_ = unit->prev_;
    
    // 헤드 교체
    if (cells_[oldCellX][oldCellY] == unit)
        cells_[oldCellX][oldCellY] = unit->next_;
        
    add(unit);
}

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

여태까지는 같은 칸 안에 있는 유닛들만 검사했지만, 장거리 공격이 가능한 경우라면 같은 칸이 아니더라도 범위를 조금 더 넓게 검사하도록 바꾸면 된다.

위의 그림처럼 사거리 안에 들었음에도 다른 칸인 경우를 꼭 고려해야 한다.

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

void Grid::handleCell(int x, int y) {
    Unit* unit = cells_[x][y];
    while (unit != nullptr) {
        handleUnit(unit, unit->next_);
        unit = unit->next_;
    }
}

handleCell 안에서 내부 루프를 따로 빼내어 HandleUnit으로 만든다.

handleCell은 더 이상 유닛 리스트가 아닌 칸의 좌표 값을 받도록 변경한다.

void Grid::handleCell(int x, int y) {
    Unit* unit = cells_[x][y];
    while (unit != nullptr) {
        handleUnit(unit, unit->next_);
        
        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_;
    }
}

handleCell을 확장시켜서 주변 8칸 중 좌측 4칸에 대해 충돌 여부를 검사한다.

절반만 검사하는 이유는 중복 처리 문제를 해결하기 위함이지만 일반적으로는 A, B의 관계가 비대칭이기 때문에 주변 칸을 모두 검사해야한다.

디자인 결정

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

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

유닛 개수와 위치에 따라 분할 크기를 조절한다. 예제처럼 크기를 모두 균일하게 분할했다가 모든 유닛이 한 칸에 몰려있다면 O(n²)으로 성능이 퇴보하기 때문이다.

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

공간 분할 자료구조와 관련된 내용으로는 격자, 쿼드트리, 이진 공간 분할, k-d트리, 경계 볼륨 계층구조를 찾아보면 된다.

덧붙여서,

격자의 1차원 버전은 버킷 정렬

BSP, k-d트리, BVH의 1차원 버전은 이진 탐색 트리

쿼드트리, 옥트리의 1차원 버전은 트라이다.

객체 풀 (Object Pool)

동기

파티클 시스템을 통해 파티클을 생성, 제거하는 과정에서 메모리 단편화가 생기면 안된다.

메모리 단편화가 빈번하게 발생하지 않더라도 메모리 단편화를 계속 방치하면 지속적으로 힙에 구멍을 내기 때문에 시간이 누적되면 결국 게임이 뻗어버린다.

패턴

재사용 가능한 객체들을 모아놓은 객체 풀 클래스를 정의한다. 여기에 들어가는 객체는 현재 자신이 사용 중이닞 ㅇ부를 알 수 있는 방법을 제공해야 한다. 풀은 초기화될 때 사용할 객체들을 미리 생성하고, 이들 객체를 사용 안함 상태로 초기화한다.

새로운 객체가 필요하면 풀에 요청한다. 풀은 사용 가능한 객체를 찾아서 사용 중으로 초기화한 뒤 반환한다. 객체를 더 이상 사용하지 않는다면 사용 안 함 상태로 되돌리고 이런 식으로 메모리나 다른 자원 할당을 신경 쓰지 않고 마음껏 객체를 생성, 삭제할 수 있다.

언제 쓸 것인가?

보통 오브젝트나 파티클같이 시각적으로 보이는 것에 많이 사용된다.

위와 같은 경우에 사용할 수 있다.

주의사항

보통 new, delete로 메모리를 관리한다. GC가 지원되는 언어는 GC로 관리한다.

객체 풀을 만들 때, 얼마나 사용될지 예측하여 크기를 조절해야 한다. 너무 작으면 크래시가 나고 너무 크면 메모리 낭비와 다를 바가 없다.

한 번에 사용 가능한 객체의 개수가 정해져 있기 때문에 장점일수도 있고 단점일수도 있다.

어찌 되었건 간에 객체 풀의 모든 객체가 사용 중이어서 재사용 할 객체를 반환받지 못해서 오버런이 발생할 때를 대비해 두어야 한다.

아예 풀이 부족하지 않도록 최악의 상황을 고려해서 풀을 크게 잡거나 객체 미생성, 기존 객체를 강제로 제거, 풀의 크기를 늘리는 등 해결 방법은 여러 가지가 있으며 각자 장단점이 존재한다.

대부분의 객체 풀은 배열로 구현한다.

풀에 들어가는 객체가 전부 같은 타입이면 상관없지만 크기가 다양한 서로 다른 타입이면 메모리를 낭비하게 된다.

이런 경우는 객체의 크기별로 풀을 나누는 게 좋다.

재사용되는 객체는 저절로 초기화되지 않기 때문에 재사용시에는 주의해서 반드시 객체를 완전히 초기화해야 한다.

예제

class Particle {
public:
    Particle() : frameLeft_(0) {}
    void init(double x, double y, double xVel, double yVel, int lifetime);
    void animate();
    bool inUse() const { return frameLeft_ > 0; }
    
private:
    int frameLeft_;
    double x_, y_;
    double xVel_, yVel_;
};

void Particle::init(double x, double y, double xVel, double yVel, int lifetime) {
    x_ = x;
    y_ = y;
    xVel_ = xVel;
    yVel_ = yVel;
    frameLeft_ = lifetime;
}

파티클은 최초 생성 시 사용 안 함 상태로 초기화되고 나중에 init이 호출되면 파티클이 사용 중 상태로 바뀐다.

void Particle::animate() { // 업데이트 메서드 패턴 사용
    if (!inUse()) return;
    
    frameLeft_--;
    x_ += xVel_;
    y_ += yVel_;
}

매 프레임마다 animate를 호출하며 재사용 가능한 파티클을 확인하여 사용한다.

class ParticlePool {
public:
    void create(double x, double y, double xVel, double yVel, int lifetime);
    void animate();
    
private:
    static const int POOL_SIZE = 100;
    Particle particles_[POOL_SIZE];
};

void ParticlePool::animate() {
    for (int i = 0; i < POOL_SIZE; ++i)
        particles_[i].animate();
}

void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime) {
    for (int i = 0; i < POOL_SIZE; ++i) {
        if (!particles_[i].inUse()) {
            particles_[i].init(x, y, xVel, yVel, lifetime);
            return;
        }
    }
}

객체 풀 클래스는 꽤 단순하다.

매 프레임마다 animate를 호출해서 풀에 들어 있는 파티클을 순차적으로 애니메이션한다.

새로운 파티클을 생성하는 것도 어렵지 않다. 사용 중이지 않은 파티클을 찾아서 초기화하여 재사용 준비만 시켜주면 된다.

파티클들은 생명 주기가 끝나면 스스로 비활성화된다.

다 좋아보이지만 사용 가능한 객체를 찾기 위해 매 프레임마다 전체 컬렉션을 순회하는 문제가 있다.

◾ 빈칸 리스트

사용 가능한 파티클을 찾느라 전체 컬렉션을 순회하며 낭비하고 싶지 않으면 사용 가능한 파티클을 계속 추적해야 한다. 사용 가능한 파티클 포인터를 별도의 리스트에 저장하는 것도 한 방법이지만 풀에 들어 있는 객체 개수만큼의 포인터가 들어 있는 리스트를 따로 관리해야 한다.

리스트를 따로 관리하는 대신 사용하지 않는 파티클 객체의 데이터 일부를 활용할 수 있다.

class Particle {
public:
    Particle* getNext() const { return state_.next; }
    void setNext(Particle* next) {
        state_.next = next;
    }
    
private:
    int frameLeft_;
    
    union {
        struct {
            double x, y;
            double xVel, yVel;
        } live;
        
        Particle* next;
    } state_;
};

별도로 관리되어야 하는 생명주기를 제외한 모든 멤버 변수를 공용체 내부의 구조체 안으로 옮긴다.

파티클이 활성화 된 동안에는 구조체의 데이터를 사용하고 비활성화 되었을 때는 구조체의 데이터가 필요 없기 때문에 포인터로 사용 가능한 다음 파티클을 가리키면 추가 메모리 낭비 없이 리스트를 만들 수 있다.

이를 빈칸 리스트 기법이라고 부른다.

빈칸 리스트 기법을 적용하기 위해 코드를 일부 수정해야 한다.

class ParticlePool {
    // ...
private:
    Particle* firstAvailable_; // head
};

ParticlePool::ParticlePool() {
    firstAvailable_ = &particles_[0];
    
    for (int i = 0; i < POOL_SIZE - 1; ++i)
        particles_[i].setNext(&particles_[i+1]);
    
    particles_[POOL_SIZE-1].setNext(nullptr);
}

풀을 최초 생성시에는 모든 파티클이 사용 가능하기 때문에 배열 전체를 관통하여 리스트를 만든다.

void ParticlePool::create(double x, double y, double xVel, double yVel, int lifetime) {
    assert(firstAvailable_ != nullptr);
    
    Particle* newParticle = firstAvailable_;
    firstAvailable_ = newParticle->getNext();
    newParticle->init(x, y, xVel, yVel, lifetime);
}

새로운 파티클 생성시에는 첫 번째로 사용 가능한 파티클의 포인터를 바로 얻어오면 된다.

bool Particle::animate() {
    if (!inUse()) return false;
    
    frameLeft_--;
    x_ += xVel_;
    y_ += yVel_;
    
    return frameLeft_ == 0;
}

파티클의 생명주기를 알 수 있도록 반환 값을 bool로 바꾼다.

void ParticlePool::animate() {
    for (int i = 0; i < POOL_SIZE; ++i) {
        if (particles_[i].animate()) {
            particles_[i].setNext(firstAvailable_);
            firstAvailable_ = &particles_[i];
        }
    }
}

추가 메모리 낭비 없이 상수 시간에 생성, 삭제가 가능한 아름다운 객체 풀이 완성됐다.

디자인 결정

풀과 객체의 커플링 여부와 재사용 될 객체를 초기화 할때 주의할 점이 있다.

객체가 풀과 커플링된다면 더 간단하게 구현할 수 있고 객체가 풀을 통해서만 생성될 수 있도록 강제할 수 있다.

커플링되지 않는다면 어떤 객체라도 풀에 넣을 수 있지만 사용 여부를 객체의 외부에서 관리해야 한다.

재사용될 객체를 풀 안에서 초기화한다면 풀은 객체를 완전히 캡슐화 시킬 수 있고 풀 클래스는 객체가 초기화 되는 방법과 결합된다.

객체를 풀 밖에서 초기화한다면 풀의 인터페이스는 단순해진다. 하지만 객체 생성이 실패할 때의 예외 처리를 구현해 두어야 할 수 있다.

객체 풀 패턴은 경량 패턴과 비슷한 점이 많다. 둘 다 재사용 가능한 객체 집합을 관리하지만 재사용의 의미에 차이가 있다.

더티 플래그 (Dirty Flag)

쉽게 말해서 지연 평가(Lazy Evaluation)의 일종이다.

동기

월드에 존재하는 오브젝트들을 렌더링 하려면 장면 그래프라는 거대한 자료구조에 저장해야 한다. 렌더링 코드는 이 장면 그래프를 이용해서 어떤 것들을 렌더링 해야하는지를 결정하기 때문이다.

매우 간단하게 만든다면 객체 리스트 하나만 존재하면 되지만 장면 그래프는 거의 계층형으로 이루어져 있기 때문에 적합한 자료구조가 아니다.

계층형이라 함은 쉽게 말해서 트랜스폼의 부모 자식 관계이다. 부모의 트랜스폼이 변하면 자식의 트랜스폼도 바뀐다.

그리고 렌더링을 하려면 로컬 트랜스폼이 아닌 월드 트랜스폼을 알아야만 렌더링 할 수 있다.

로컬 트랜스폼을 월드 트랜스폼으로 변환하는 것은 어렵지 않다. 문제는 이 연산을 모든 객체에 대해서 매 프레임 수행하면 성능 하락은 피할 수 없다.

특히 지형같은 경우는 전혀 움직이지 않는데 이것까지 매번 월드 트랜스폼으로 변환하는 연산을 수행하는 것은 자원의 낭비다.

객체가 움직이지 않는 경우를 대비하기 위해 월드 트랜스폼 값을 캐싱하면 최적화가 좀 더 이루어진다.

하지만 최상위 부모의 트랜스폼이 변화하면 계층을 따라 내려오면서 재귀적으로 연산이 이루어지는데, 그림으로 보이다시피 중복된 연산이 많이 발생한다. 객체는 고작 4개가 움직였을 뿐이지만 중복된 연산으로 인해 10회의 연산량이 발생한다.

캐싱으로는 이 문제를 해결할 수 없다.

대신 로컬 트랜스폼과 월드 트랜스폼 연산을 분리시키고 연산을 뒤로 미룸으로써 연산량을 줄이는 방법을 선택한다.

이를 위해서 장면 그래프에 들어가는 객체에 플래그를 추가한다.

로컬 트랜스폼의 값이 바뀌면 플래그를 켜고 객체의 월드 트랜스폼 값이 필요할 때에는 플래그를 검사한다. 플래그가 켜져있으면 월드 트랜스폼을 계산한 뒤에 플래그를 끈다.

이제 와서 얘기하는 것이지만 패턴 이름이 더티 플래그인 이유는 "더 이상 맞지 않음" 을 나타내는 플래그를 더티라고 부르기 때문에 더티 플래그이다.

월드 트랜스폼으로 변환하는 연산을 렌더링 할 때로 미뤄서 연산량을 4회로 줄였다.

움직이지 않는 객체는 계산을 하지 않고 렌더링 전에 제거될 객체는 월드 트랜스폼 변환 연산을 하지 않아도 된다.

패턴

계속해서 변경되는 기본 값이 있다. 파생 값은 기본 값에 비싼 작업을 거쳐야 얻을 수 있다. 더티 플래그는 파생 값이 참조하는 기본 값의 변경 여부를 추적한다. 즉, 더티 플래그는 기본 값이 변경되면 켜진다. 파생 값을 써야 할 떄 더티 플래그가 켜져 있다면 다시 계산한 뒤에 플래그를 끈다. 플래그가 꺼져 있다면 이전에 캐시해놓은 파생 값을 그대로 사용한다.

언제 쓸 것인가?

마찬가지로 코드가 복잡해지는 것을 감수할 정도로 성능 문제가 심할 때에만 적용해야 한다.

계산과 동기화라는 두 종류의 작업에 사용되고 두 작업 모두 기본 값으로부터 파생 값을 얻는 게 오래 걸리거나 비용이 크다는 문제가 있다.

파생 값이 사용되는 횟수보다 기본 값이 더 자주 변경되어야 하고 점진적으로 업데이트 하기가 어려운 경우에 적용하기 좋고 그게 아니라면 별로 도움이 되지 않는다.

주의사항

계산을 오래 지연시키려면 비용이 든다. GC를 정리하는것도 일종의 지연인데 GC 정리를 너무 빨리하는것도 성능의 하락이 생기지만 너무 늦게 정리하는것도 비용이 크게 발생된다.

그리고 지연 도중에 뭔가 잘못되었을 경우 작업이 전부 날아갈 수도 있다는 문제도 있다.

상태가 변할 때마다 플래그를 일일이 켜줘야 하는 번거로움도 있다. 한군데라도 놓치면 무효화된 파생 값을 사용해서 잡기 어려운 버그가 발생할 수도 있다.

또한 더티 플래그가 꺼져 있으면 캐싱된 값을 그대로 사용해야 하기 때문에 이전 파생값을 캐싱해둬야 한다.

다른 최적화 방법들과 마찬가지로 더티 플래그 패턴 역시 속도를 위해 메모리를 희생한다.

예제

class Transform {
public:
    static Transform origin();
    Transform combine(Transform& other);
};

combine은 상위 노드를 따라서 로컬 트랜스폼을 전부 결합하여 월드 트랜스폼으로 변환한 값을 반환한다.

origin은 아무 변화가 없는 단위행렬로 나타낸 기본 트랜스폼을 반환한다. 

class GraphNode {
public:
    GraphNode(Mesh* mesh) : mesh_(mesh), local(Transform::origin()) {}
    
private:
    Transform local_;
    Mesh* mesh_;
    GraphNode* children_[MAX_CHILDREN];
    int numChildren_;
};

더티 플래그 패턴을 적용하기 전의 클래스 구조이다.

GraphNode* graph_ = new GraphNode(nullptr); // 하위 노드를 루트에 추가

void renderMesh(Mesh* mesh, Transform transform); // 메시 렌더링

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

/* == */

graph_->render(Tranform::origin()); // 루트 노드부터 순회하며 렌더링

더티 플래그를 사용하지 않고 단순히 장면 그래프를 루트 노드부터 순회하며 렌더링한다.

class GraphNode {
public:
    GraphNode(Mesh* mesh) : mesh_(mesh), local(Transform::origin()), dirty_(true) {}
    void setTransform(Transform local) {
        local_ = local;
        dirty_ = true;
    }
    // ...
    
private:
    Transform world_;
    bool dirty_;
    // ...
};

로컬 트랜스폼이 변하면 더티 플래그를 켜준다.

void GraphNode::render(Transform parentWorld, bool dirty) {
    dirty |= dirty_; // 상위 노드의 플래그 중 하나라도 켜져있으면 켜진다
    
    if (dirty) [
        world_ = local_.combine(parentWorld);
        dirty_ = false;
    }
    
    if (mesh_) renderMesh(mesh_, world_);
    
    for (int i = 0; i < numChildren_; i++)
        children_[i]->render(world_, dirty);
}

재귀구조 대신 더티 플래그를 매개변수로 사용해서 연산 비용을 줄인다.

더티 플래그가 켜진 경우에만 월드 트랜스폼을 계산하고 더티 플래그를 꺼준다.

디자인 결정

더티 플래그를 끄는 시점도 상황에 따라서 결정할 수 있다.

데이터 지역성 (Data Locality)

동기

하드웨어 발전을 따라서 데이터의 연산 속도는 빨라졌지만 데이터를 가져오는 속도는 크게 달라지지 않았다.

CPU는 램에서 데이터를 1바이트 가져오는 데에만 몇 백 CPU 사이클 정도를 소모한다. 매 번 이렇게 사이클을 소모하면 사실상 거의 대부분의 시간을 데이터를 기다리는 대기시간일텐데, 실제로는 그렇게 동작하지 않는다.

그 이유는 참조 지역성에 기반을 둔다.

데이터를 1바이트라도 가져오게 된다면 인접한 연속된 메모리를 선택하여 캐시에 복사한다.

추후 필요한 데이터가 캐시 라인 안에 들어있다면 CPU는 대기하지 않고 데이터를 바로 가져온다.

필요한 데이터가 없어서 캐시 미스가 발생하면 그때는 CPU가 멈춰서 데이터를 기다리며 사이클을 낭비한다.

그래서 자료구조를 최대한 잘 만들어서 캐시 미스가 발생하는 것을 최대한 피해야 한다.

패턴

CPU는 메모리 접근 속도를 높이기 위한 캐시를 여러 개 둔다. 캐시를 사용하면 최근에 접근한 메모리 근처에 있는 메모리를 훨씬 빠르게 접근할 수 있다. 데이터 지역성을 높일수록, 즉 데이터를 처리하는 순서대로 연속된 메모리에 둘수록 캐시를 통해서 성능을 향상할 수 있다.

언제 쓸 것인가?

다른 최적화 기법과 마찬가지로, 성능 문제가 있을 때 써야 한다. 필요없는 곳에 최적화를 해봤자 코드만 복잡해지고 유연성이 떨어질 뿐이다.

특히나 데이터 지역성 패턴은 성능 문제가 캐시 미스 때문인지를 확인해봐야 한다. 다른 이유 때문에 도입하는 것이라면 전혀 도움이 안 된다.

처음부터 캐시 최적화를 하겠다고 많은 시간을 낭비할 필요는 없지만 자료구조를 캐시하기 좋게 만들려고 노력할 필요는 있다.

주의사항

C++에서는 인터페이스를 사용하려면 포인터나 레퍼런스를 통해 객체에 접근해야 한다. 그런데 포인터를 쓰게 되면 캐시 미스가 발생하게 된다.

그래서 데이터 지역성 패턴을 적용하려면 추상화를 일부 희생해야한다.

예제

..
private:
    AIComponent* ai_;
    PhysicsComponent* physics_;
    RenderComponent* render_;
    
/* --- */

while (!gameOver) {
    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];
    
/* --- */

while (!gameOver) {
    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();
}

각 개체 안에 포인터로 들고있는 대신 외부의 동적 배열로 끌어내려서 포인터가 아닌 객체에 바로 접근하여 캐시 적중률을 높인다.

작업 전과 후의 속도 차이는 실행 환경마다 다르겠지만 책 기준으로는 50배가 차이 난다.

캡슐화도 많이 깨먹지 않아서 나쁘지 않다. 게임 루프에서 컴포넌트를 직접 업데이트 하기는 하지만 이전 코드도 어차피 함수 호출로 컴포넌트에 직접 접근하고 있었다. 단순히 컴포넌트가 사용되는 방식만 바뀌었을 뿐이다.

본래 게임 개체(GameEntity) 안에 있던 컴포넌트를 게임 루프로 끌어내렸기 때문에 게임 개체 클래스는 딱히 들고 있을만한 컴포넌트는 없지만 그렇다고 게임 개체 클래스를 없앨 필요는 없다.

대신 자기가 본래 소유했어야 할 컴포넌트에 대한 포인터를 가지도록 만들면 된다.

이번에는 파티클 시스템을 예로 들어보자.

class Particle {
public:
    void update() { /* ... */ }
};


class ParticleSystem {
public:
    ParticleSystem() : numParticles_(0) {}
    void update() {
        for (int i = 0; i < numParticles_; ++i)
            particles_[i].update();
    }
    
private:
    static const int MAX_PARTICLES = 100000;
    int numParticles_;
    Particle particles_[MAX_PARTICLES];
};

파티클을 객체 풀에 관리하는 파티클 시스템 클래스이다.

항상 객체 풀에 들어있는 모든 파티클을 사용하는 것은 아니기 때문에 루프를 전부 순회하며 처리할 필요는 없다.

대신 플래그 변수를 둬서 활성화된 파티클만 골라서 처리시키면 간단하게 해결 될 것이다.

하지만 이것 역시 캐시 적중에 관한 측면에서 보면 같이 읽어들인 인접한 파티클 데이터들이 활성화된 상태가 아니라면 무용지물이 된다.

게다가 활성화된 파티클이 적을수록 메모리를 더 자주 건너뛰게 되어서 이 방법 역시 캐시 미스가 더 자주 발생한다.

이번에는 활성화된 파티클들만 앞으로 모아서 처리하면 캐시 적중률이 높아진다.

정렬이라는 단어를 사용할 수 있겠지만 사실 매 프레임마다 배열의 모든 요소들을 정렬할 필요는 없고 활성 파티클만 앞으로 모아두면 된다.

// 비활성 -> 활성
void ParticleSystem::activeParticle(int index) {
    assert(index >= numActive_);
    
    swap(particles_[numActive_], particles_[index]);
    numActive_++;
}

// 활성 -> 비활성
void ParticleSystem::deactiveParticle(int index) {
    assert(index < numActive_);
    
    numActive_--;
    swap(particles_[numActive_], particles_[index]);
}

성능적으로는 만족스러울지 모르지만 객체지향성을 어느 정도 포기해야 한다.

덧붙여서 Particle과 ParticleSystem 클래스가 서로 강하게 커플링 되어있지만 어차피 하나의 개념이 두개의 클래스로 나누어진 것 뿐이기 때문에 크게 상관이 없다.

마지막으로 호출 횟수에 따라 구분해보자.

예를 들어 AI 컴포넌트는 현재 재생중인 애니메이션, 이동 중인 목표 지점, 스탯 등이 들어있고 매 프레임마다 값을 확인하고 변경한다.

그런데 죽을 때 어떤 아이템을 떨어트릴지에 대한 데이터는 죽는 순간 딱 한번만 사용되기 때문에 굳이 위와 같은 컴포넌트에서 멤버로 같이 관리하여 컴포넌트 크기를 늘릴 필요는 없다.

class AIComponent {
public:
    // methods
    
private:
    Animation* animation_;
    double energy_;
    Vector goalPos_;
    LootDrop* loot_; // 사용 빈도가 적은 데이터들
};

class LootDrop {
private:
    friend class AIComponent;
    LootType drop_;
    int minDrops_;
    int maxDrops_;
    double chanceOfDrop_;
};

이런 데이터들을 따로 분리시켜서 포인터로 들고있게 하면 컴포넌트의 크기를 줄일 수 있기 때문에 캐시 라인에 컴포넌트를 더 올려서 캐시 적중률을 높일 수 있다.

디자인 결정

결론만 먼저 내리자면 이 패턴은 데이터를 메모리에 어떻게 배치하느냐에 따라 성능이 크게 영향을 받는다는 사고 방식을 갖게 하는 것이 목적이다. 구현 방법에 왕도는 없고 다양하게 구현할 수 있다.

그런데 데이터 지역성을 적용한다면 다형성은 어떻게 처리할 것인가에 생각해 볼 필요가 있다.

가장 쉬운 방법으로는 상속을 받지 않는것이다. 가장 안전하고 쉽고 빠르지만 상속을 받지 않기때문에 코드가 유연하지 않게 된다.

두 번째 방법으로는 타입별로 배열을 준비해서 각기 다른 배열에 넣고 관리하는 것이다. 대신 이 경우는 커플링이 생기고 확장성이 좋지 않아진다.

마지막으로 데이터 지역성을 적용하지 않고 하나의 컬렉션에 포인터를 모아놓는 방법이 있다. 캐시를 신경쓰지 않는다면 보통 이게 자연스러운 방식이다.

서비스 중개자 (Service Locator)

동기

메모리 할당이나 로그, 난수 생성 등을 사용하지 않는 게임코드는 찾아보기 어려울 정도로 정말 많이 사용된다.

이런 시스템은 게임 전체에서 사용 가능해야 하는 일종의 서비스라고 볼 수 있다.

바로 직전에 만들어봤던 오디오 시스템만 해도 여러 게임 시스템과 연결되어 있었다.

AudioSystem::playSound(VERY_LOUD_BANG); // 정적 클래스
AudioSystem::instance()->playSound(VERY_LOUD_BANG); // 싱글턴

둘 중 무엇이 되었던 간에 오디오 시스템을 사용하는 클래스는 강한 커플링도 함께 생긴다.

물론 사운드를 출력하려면 어느 정도의 커플링을 피할 수는 없지만 오디오를 구현한 구체 클래스를 바로 접근할 수 있게 하는 것은 별로 옳지 않다.

전화번호부에 비유를 해보자. 누군가의 연락처를 알고 싶다면 전화번호부에서 이름으로 찾으면 된다. 만약 이사를 가게된다면 전화국을 통해 전화번호부를 업데이트하면 다른 사람들이 새로운 주소를 찾아볼 수 있다.

진짜 주소가 아닌 대리 주소를 적어도 상관이 없다. 그저 정보를 찾는 쪽(호출하는 쪽)에서 전화번호부를 통해 나를 찾게 함으로써 찾을 방법은 한곳에서 편하게 관리할 수 있다.

이것이 서비스 중개자 패턴의 핵심이다. 서비스를 사용하는 코드로부터 서비스가 누구인지(서비스를 구현한 구체 클래스 타입이 무엇인지), 어디에 있는지(클래스 인스턴스를 어떻게 얻을지)를 몰라도 되게 해준다.

패턴

서비스는 여러 기능을 추상 인터페이스로 정의한다. 구체 서비스 제공자는 이런 서비스 인터페이스를 상속받아 구현한다. 이와 별도인 서비스 중개자는 서비스 제공자의 실제 타입과 이를 등록하는 과정은 숨긴채 적절한 서비스 제공자를 찾아 서비스에 대한 접근을 제공한다.

언제 쓸 것인가?

전역적으로 접근하는것은 싱글턴에서도 언급했듯이 문제가 생기기 쉽기 때문에 절제해서 사용하는 게 좋다.

만약 접근해야 할 객체가 있다면 전역 메커니즘을 먼저 떠올리는 대신 필요한 객체를 인수로 넘겨줄 수 없는지부터 생각해 볼 필요가 있다.

다만 직접 객체를 넘기는 방식이 불필요하거나 오히려 코드를 읽기 어렵게 만드는 경우도 있다.

예를 들어 로그나 메모리 관리 같은 시스템이 모듈의 공개 API에 포함되어 있으면 안된다.

렌더링 함수의 매개변수에는 렌더링에 관련된 것만 있어야지 로그 같은 게 섞여 있을 필요가 없을 뿐더러 있어서도 안된다.

게임 내에서 오디오나 디스플레이 시스템은 단 하나만이 존재하는데 이걸 굳이 인수로 넘겨주는것은 쓸데없이 복잡성만 늘리는 셈이 된다.

서비스 중개자 패턴은 사실상 싱글턴 패턴이지만 좀 더 유연하고 더 설정하기 좋은 싱글턴 패턴이다.

물론 근간은 싱글턴이기 때문에 잘못 사용하면 싱글턴의 단점이 그대로 나타난다.

주의사항

두 코드가 커플링되는 의존성을 런타임 시점까지 미루는 부분이 가장 어렵다.

유연성을 얻는 대신 코드만 봐서는 어떤 의존성을 사용하는지 알기 어렵다는 비용이 발생한다.

싱글턴이나 정적 클래스와 달리 서비스 객체를 등록해야만 사용할 수 있기 때문에 필요한 객체가 없을 때를 대비해야 한다.

서비스 중개자는 전역에서 접근 가능하기 때문에 각 서비스들은 어느 환경에서나 문제 없이 동작해야만 한다.

특정한 곳에서만 사용하고 특정할 때에는 사용하면 안 된다면 정확히 정해진 곳에서만 실행되는 걸 보장할 수 없기 때문에 서비스로는 적합하지 않다.

만약 어떤 클래스가 특정 상황에서만 실행되어야 한다면 서비스 중개자 패턴은 적용하지 않는 것이 안전하다.

예제

class Audio {
public:
    virtual ~Audio() {}
    virtual void playSound(int soundID) = 0;
    virtual void stopSound(int soundID) = 0;
    virtual void stopAllSounds() = 0;
};

이벤트 큐에서 다뤘던 오디오 시스템을 서비스 중개자를 통해서 다른 코드에 오디오 시스템을 제공하도록 변경한다.

우선 인터페이스를 정의한다.

class ConsoleAudio : public Audio {
public:
    virtual void playSound(int soundID) override { ... }
    virtual void stopSound(int soundID) override { ... }
    virtual void stopAllSounds() override { ... }
};

인터페이스 만으로는 아무것도 할 수 없기 때문에 구체 클래스를 구현한다.

우선 단순한 중개자부터 시작하자.

class Locator {
public:
    static Audio* getAudio() { return service_; }
    static void provide(Audio* service) { service_ = service; }
    
private:
    static Audio* service_;
};

정적 함수인 getAudio가 중개 역할을 하게 된다.

Audio *audio = Locator::getAudio();
audio->playSound(VERY_LOUD_BANG);

Audio 클래스가 제공하는 인터페이스를 통해 서비스 인스턴스를 반환받는다.

ConsoleAudio* audio = new ConsoleAudio();
Locator::provice(audio);

중개자가 서비스를 등록하는 방법이다. 매우 단순하다. getAudio를 호출하기 전에 먼저 서비스 제공자를 외부 코드에서 등록해주면 된다. 

playSound를 호출하는 쪽에서는 추상 클래스의 인터페이스만 알 뿐 구체 클래스에 대해서는 전혀 모른다는 것이 핵심이다.

중개자인 Locator 클래스 역시 서비스 제공자의 구체 클래스와는 커플링되지 않는다.

어떤 구체 클래스가 사용될지는 서비스를 제공하는 초기화 코드에서만 알아낼 수 있다.

재미있는점은 상위 추상 클래스인 Audio 자신은 서비스 중개자를 통해 여기저기에 접근된다는 사실을 모른다.

Audio 인터페이스만 놓고 보면 일반적인 상위 추상 클래스이므로 꼭 서비스 중개자 패턴용으로 만들지 않은 기존의 클래스에도 서비스 중개자 패턴을 적용할 수 있다.

구현과 적용 자체는 어렵지 않고 단순하지만 서비스 제공자가 서비스를 등록하기 전에 서비스를 사용하려고 접근하면 nullptr을 반환하기 때문에 호출하는 쪽에서 nullptr 검사를 하지 않으면 크래시되는 문제가 있다.

호출하는 쪽에서 nullptr 검사를 일일이 수행하는 대신 아예 null객체를 반환하도록 하면 훨씬 깔끔해진다.

서비스 제공자를 찾지 못하거나 만들지 못해서 nullptr을 반환해야 할 때, 대신 같은 인터페이스를 구현한 널 객체를 생성해서 반환해준다.

class NullAudio : public Audio {
public:
    virtual void playSound(int soundID) override { /* 아무것도 하지 않는다 */ }
    virtual void stopSound(int soundID) override { /* 아무것도 하지 않는다 */ }
    virtual void stopAllSounds() override { /* 아무것도 하지 않는다 */ }
};

널 객체 자체는 아무런 기능이 구현되어 있지 않지만 받는 쪽에서는 실제 객체를 받은 것처럼 안전하게 작업을 진행할 수 있다.

class Locator {
public:
    static void initialize() {
        service_ = &nullService_;
    }
    static Audio& getAudio() { return *service_; }
    static void provide(Audio* service) {
        if (service == nullptr)
            service_ = &nullService_;
        else
            service_ = service;
    }

private:
    static Audio* service_;
    static NullAudio nullService_;
};

이제 Locator는 언제나 유효한 객체를 반환한다는 점이 보장되기 때문에 호출하는 쪽에서는 서비스가 준비되었는지를 신경쓰거나 nullptr 검사를 할 필요가 전혀 없이 그냥 호출만 하면 된다.

덧붙여서 널 객체는 의도적으로 특정 서비스를 찾지 못하게 하고 싶을때도 사용할 수 있다.

어떤 시스템을 잠시 못쓰게 하고 싶다면 그냥 서비스를 등록하지 않으면 된다. 그러면 알아서 널 객체를 반환해준다.

게임을 개발하다 보면, 어떤 일이 벌어지는지 알기 위해서 원하는 이벤트에 간단하게 로그를 설치해야 할 때가 있다.

이럴 때는 보통 로그를 생성하는 함수를 이곳저곳에 집어넣게 되는데, 시간이 지나면 로그가 너무 많아지는 문제가 생긴다.

AI 프로그래머는 사운드 출력에 관심이 없고, 사운드 개발자는 AI의 상태 변화에 관심이 없는 등 필요 없는 로그가 있음에도 일괄적으로 기록되기 때문에 원하는 로그를 찾기 위해서 다른 사람들이 기록한 로그까지 같이 뒤져봐야 한다.

조건적으로 로그를 남기고 싶은 시스템이 서비스로 노출되어 있다면, 데코레이터 패턴을 적용시켜서 원하는 로그만 온오프하거나 최종 빌드시에 로그를 전부 제거시킬수도 있다.

class LoggedAudio : public Audio {
public:
    LoggedAudio(Audio& wrapped) : wrapped_(wrapped) {}
    virtual void playSound(int soundID) {
        log("사운드 출력");
        wrapped_.playSound(soundID);
    }
    virtual void stopSound(int soundID) {
        log("사운드 중지");
        wrapped_>stopSound(soundID);
    }
    virtual void stopAllSounds() {
        log("모든 사운드 중지");
        wrapped_.stopAllSounds();
    }

private:
    void log(const char* message) { /* 로그를 남기는 코드 */ }
    Audio& wrapped_;
};

다른 오디오 서비스 제공자를 래핑하면서 동일한 인터페이스를 상속받는다.

기능 요청을 받으면 로그를 기록하고 실제 기능 요청은 래핑한 서비스에 전달한다.

void enableAudioLogging() {
    // 기존 서비스 decorate
    Audio* service = new LoggedAudio(Locator::getAudio());
    Locator::provide(service);
}

로그를 키고싶으면 위의 함수를 호출해주면 되고 비활성화 할때는 로그 기능이 빠진 서비스 제공자를 등록하면 된다.

만약 널객체에 데코레이터 패턴을 적용한다면 기능은 빠지고 로그만 출력시킬 수도 있다.

디자인 결정

◾ 서비스는 어떻게 등록되는가?

class Locator {
public:
    static Audio& getAudio() { return service_; }

private:
#if DEBUG
    static DebugAudio service_;
#else
    static ReleaseAudio service_;
#endif
};

◾ 서비스를 못 찾으면 어떻게 할 것인가?

널 서비스를 반환하는 형태가 가장 좋아보이지만 의외로 단언문을 걸어서 게임을 중단시키는 경우가 가장 많이 사용된다.

게임이 출시될쯤이면 이미 테스트를 많이 통과했을 것이고 게임이 실행될 환경도 어느정도 구체화되기 때문에 서비스를 찾지 못할 가능성은 매우 적다.

◾ 서비스의 범위는 어떻게 잡을 것인가?

여태까지는 전역적인 접근을 허용했고 이게 일반적이지만 특정 클래스 및 하위 클래스에만 접근을 제한시킬수도 있다.

전역에서 접근이 가능하다면 전체 코드에서 같은 서비스를 사용하도록 할 수 있지만 언제 어디에서 서비스가 사용되는지를 제어할 수 없다.

특정 클래스에만 접근을 제한시킨다면 커플링을 제어할 수 있지만 중복 작업을 해야 할 수도 있다.

각자의 서비스에 참조해야 하기 때문에 코드 중복을 피할 수 없다.

하위 클래스 샌드박스 패턴을 적용시켜봤자 결국 최상위 클래스와 커플링이 생긴다.

서비스가 특정 분야에 한정되어 있다면 특정 클래스로 접근 범위를 좁히는 편이 좋다.