공간 분할 (Spatial Partition)
20.1. 의도
객체를 효율적으로 찾기 위해, 객체의 위치에 따라 구성되는 자료구조에 저장합니다.
20.2. 동기
게임은 다른 세상을 경험하게 해줍니다. 다른 세상이라 해도 기본적인 물리나 감각은 보통 현실 세계와 비슷하게 만듭니다. 덕분에 비트와 픽셀로 만들어진 게임 월드에서도 사실감을 느낄 수 있습니다.
이번 장에서는 현실감을 만드는 요소 중 하나인 위치(location)를 살펴봅니다. 게임 월드에는 공간(space)이 있고, 객체는 그 공간 어딘가에 존재합니다. 위치의 의미는 여러 곳에서 드러납니다. 가장 분명한 예는 객체가 이동하고 충돌하며 상호작용하는 물리입니다. 다른 예도 있습니다. 오디오 엔진은 소리가 나는 곳과 플레이어 사이의 거리에 따라 음량을 조절합니다. 멀리 떨어진 플레이어와는 채팅하지 못할 수도 있습니다.
이런 기능을 구현하려면 ‘주변에 어떤 객체가 있는지’를 알아야 합니다. 이를 매 프레임 확인해야 한다면 성능 병목이 될 수 있습니다.
전장 위의 유닛들
실시간 전략 게임을 만든다고 생각해봅시다. 전장에서는 수백 명이 넘는 군인이 뒤엉켜 싸웁니다. 전사는 칼을 휘두르기 전에 적의 위치부터 알아야 합니다. 가장 단순하게 구현하면 모든 유닛 쌍을 검사하여 얼마나 가까운지 확인합니다.
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]);
}
}
}
}
C++
복사
전장의 유닛을 반복해서 순회하는 이중 루프입니다. 매 프레임 유닛 수의 제곱에 비례하는 수의 쌍을 검사합니다. 새 유닛이 추가되면 기존 유닛 모두와 위치를 비교해야 합니다. 유닛이 많아질수록 검사 횟수는 감당하기 어려울 만큼 늘어납니다.
원주 1 실제 내부 루프는 모든 유닛이 아니라 외부 루프에서 아직 방문하지 않은 유닛만 순회합니다. 따라서 같은 쌍을 두 번 검사하지 않습니다. A와 B를 검사했다면 B와 A를 다시 검사할 필요가 없습니다. 그래도 Big O 복잡도는 여전히 O(n²)입니다.
1차원 전장
문제는 배열의 유닛들이 정렬되어 있지 않다는 것입니다. 특정 위치 주변의 유닛을 찾으려면 배열 전체를 순회해야 합니다. 문제를 단순하게 만들기 위해 2차원 전장을 1차원 전선(battleline)으로 생각해봅시다.
그림 20-1. 1차원 전선.
전선 위 위치에 따라 유닛 배열을 정렬하면 전체를 훑지 않고도 이진 검색(binary search) 같은 방법으로 주변 유닛을 쉽게 찾을 수 있습니다.
원주 2 이진 검색의 복잡도는 O(log n)입니다. 따라서 전체 전투 유닛을 찾는 비용은 O(n²)에서 O(n log n)으로 줄어듭니다. 비둘기집 정렬(pigeonhole sort) 같은 기법을 사용하면 O(n)으로 줄일 수도 있습니다.
이처럼 위치에 맞춰 구성한 자료구조에 객체를 저장하면 훨씬 빠르게 찾을 수 있습니다. 이 원리를 2차원 이상의 공간으로 확장한 것이 공간 분할 패턴입니다.
20.3. 패턴
객체마다 공간상의 위치가 있습니다. 객체를 위치에 따라 구성되는 공간 자료구조에 저장합니다. 이 자료구조로 같은 위치나 주변에 있는 객체를 빠르게 찾습니다. 객체가 움직이면 자료구조도 갱신하여 계속 올바르게 찾을 수 있도록 합니다.
20.4. 언제 쓸 것인가?
공간 분할은 움직이는 게임 객체뿐 아니라 정적인 프랍이나 지형을 저장하는 데에도 널리 사용합니다. 복잡한 게임에서는 콘텐츠 종류별로 공간 자료구조를 따로 두기도 합니다.
위치를 가진 객체가 많고, 위치를 기준으로 객체를 찾는 질의가 성능에 영향을 줄 만큼 자주 발생할 때 사용하세요.
20.5. 주의사항
공간 분할을 사용하면 O(n²)의 복잡도를 더 실용적인 수준으로 낮출 수 있습니다. 객체가 많을수록 의미가 큽니다. 반대로 n이 충분히 작다면, 즉 객체가 적다면 굳이 신경 쓸 필요가 없을 수도 있습니다.
객체를 위치별로 정리해두는 만큼 위치 변경을 처리하기는 더 어려워집니다. 바뀐 위치에 맞춰 자료구조를 재정리해야 해서 코드가 복잡해지고 CPU도 추가로 사용합니다. 그만한 가치가 있는지 먼저 확인하세요.
원주 3 해시 테이블에 들어 있는 객체의 해시 키가 테이블 모르게 계속 바뀐다고 생각하면, 왜 어려운지 짐작할 수 있습니다.
공간 자료구조에는 추가 메모리도 필요합니다. 많은 최적화가 그렇듯이 속도를 위해 메모리를 사용합니다. CPU보다 메모리가 더 부족한 환경에서는 오히려 손해일 수 있습니다.
20.6. 예제 코드
패턴은 구현마다 조금씩 다릅니다. 공간 분할도 마찬가지지만, 여러 변형이 잘 문서화되어 있다는 특징이 있습니다. 각 변형의 성능에 관한 증명은 학계의 논문을 참고하세요. 이 책에서는 개념에 집중하므로 가장 간단한 형태인 고정 격자(fixed grid)를 소개합니다.
원주 4 게임에서 많이 사용하는 공간 분할 방식은 이 장의 ‘관련 자료’ 절에 정리되어 있습니다.
모눈종이
전장 전체 위에 일정한 크기의 정사각형 격자를 모눈종이처럼 겹쳐놓습니다. 유닛을 하나의 배열 대신 격자의 각 칸에 넣습니다. 각 칸에는 그 범위 안에 위치한 유닛들을 담는 리스트가 있습니다.
그림 20-2. 전장을 정사각형 조각으로 나눕니다.
전투를 처리할 때에는 같은 칸의 유닛만 신경 쓰면 됩니다. 매번 모든 유닛을 다른 모든 유닛과 비교하는 대신, 전장을 작은 전장들로 나누어 훨씬 적은 수의 유닛끼리 비교하게 합니다.
비교 횟수가 줄어드는 이유 — 유닛 100개를 모두 비교하면 4,950쌍을 검사합니다. 10개 칸에 10개씩 고르게 나누고 같은 칸만 비교하면 45쌍 × 10칸 = 450쌍입니다. 칸 안의 검사 방식은 같지만, 비교 후보가 크게 줄어듭니다. 공격 거리가 있는 경우의 이웃 칸 처리는 뒤에서 추가합니다.
유닛을 연결 리스트로 저장한 격자
이제 기반 코드부터 작성해봅시다. 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_;
};
C++
복사
유닛은 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];
};
C++
복사
각 칸(cell)에는 유닛 포인터를 저장합니다. 이제 유닛에 이전 유닛과 다음 유닛을 가리키는 포인터를 추가합니다.
class Unit {
// 이전 코드...
private:
Unit* prev_;
Unit* next_;
};
C++
복사
이렇게 하면 유닛을 배열 대신 이중 연결 리스트로 관리할 수 있습니다.
그림 20-3. 각 칸은 유닛이 들어 있는 연결 리스트의 머리를 가리킵니다.
격자 칸은 그 칸의 첫 번째 유닛을 가리킵니다. 유닛은 자신 앞뒤의 유닛을 가리킵니다. 이렇게 구성한 이유는 곧 살펴보겠습니다.
원주 5 이 책의 예제에서는 C++ 표준 라이브러리(STL)의 컬렉션을 사용하지 않았습니다. 예제를 이해하는 데 필요한 사전 지식을 줄이고, 코드가 어떻게 작동하는지 투명하게 보여주고 싶었기 때문입니다. 특히 성능 패턴에서는 세부 구현도 중요합니다. 하지만 실제 제품 코드라면 이렇게 할 이유가 없습니다. 게임에 적용할 때에는 불필요하게 애쓰기보다 언어에서 제공하는 컬렉션을 사용하는 편이 좋습니다. 연결 리스트를 매번 처음부터 만들기에는 인생이 너무 짧습니다.
전장 속으로 들어가기
새 유닛을 적절한 격자 칸에 넣어야 합니다. 이 작업은 Unit 생성자에서 합니다.
Unit::Unit(Grid* grid, double x, double y)
: grid_(grid), x_(x), y_(y),
prev_(NULL), next_(NULL) {
grid_->add(this);
}
C++
복사
add()는 다음과 같습니다.
원주 6 월드 좌표를 칸 크기 CELL_SIZE로 나누면 격자 공간의 좌표가 됩니다. 이를 int로 변환해 소수 부분을 버리면 칸의 인덱스를 쉽게 구할 수 있습니다.
void Grid::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;
}
}
C++
복사
연결 리스트 때문에 코드가 조금 복잡해졌지만 원리는 단순합니다. 유닛이 들어갈 칸을 찾고, 그 칸의 리스트 맨 앞에 넣습니다. 이미 다른 유닛이 있다면 기존 리스트를 새 유닛의 뒤에 연결합니다.
좌표를 인덱스로 바꾸는 예 — 칸 크기가 20이고 유닛 위치가 (45, 18)이면 (45 / 20, 18 / 20)의 정수 부분인 (2, 0) 칸에 들어갑니다. 이 예제는 좌표가 격자 범위 안에 있다는 전제입니다. 실제 적용 시에는 음수 좌표와 바깥 경계를 처리해야 하며, 음수에서 정수 변환은 바닥 함수와 다르다는 점도 확인해야 합니다.
검의 격돌
모든 유닛을 칸에 넣었으니 서로 칼을 휘두르게 해봅시다. 격자 전체의 전투 처리는 다음과 같습니다.
void Grid::handleMelee() {
for (int x = 0; x < NUM_CELLS; x++) {
for (int y = 0; y < NUM_CELLS; y++) {
handleCell(cells_[x][y]);
}
}
}
C++
복사
모든 칸을 순회하며 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_;
}
}
C++
복사
포인터로 연결 리스트를 순회하는 부분을 빼면, 앞서 작성한 단순한 전투 처리 코드와 같습니다. 여기서도 유닛 쌍의 위치가 같은지 검사합니다.
차이는 전장의 모든 유닛을 검사하지 않는다는 것입니다. 같은 칸에 들어갈 정도로 가까운 유닛만 검사합니다. 비교할 후보를 줄이는 것이 이번 최적화의 핵심입니다.
원주 7 겉으로는 유닛을 순회하던 이중 루프가 칸과 유닛을 순회하는 삼중 루프가 되었으므로 더 느려 보일 수 있습니다. 옮긴이는 handleMelee()가 x와 y를 도는 이중 루프에서 handleCell()을 부르므로 사중 루프로 볼 수도 있다고 덧붙입니다. 하지만 가장 안쪽 두 루프에서 검사하는 유닛이 훨씬 적으므로 바깥 루프의 비용을 상쇄할 수 있습니다. 다만 격자가 얼마나 잘게 나뉘었는지에 따라 결과가 달라집니다. 칸이 지나치게 촘촘하면 바깥 루프도 문제가 됩니다.
진격
성능 문제는 해결했지만 새 문제가 생겼습니다. 유닛이 특정 칸의 리스트에 묶여 있어서, 현재 칸을 넘어 이동하면 원래 칸의 유닛도 다른 칸의 유닛도 제대로 찾지 못합니다. 전장이 너무 철저하게 분리된 셈입니다.
유닛이 움직일 때 추가 처리가 필요합니다. 경계를 넘으면 현재 칸에서 제거하고 새 칸에 넣어야 합니다. 먼저 Unit에 이동 메서드를 추가합니다.
void Unit::move(double x, double y) {
grid_->move(this, x, y);
}
C++
복사
NPC를 제어하는 AI나 플레이어 유닛을 조종하는 입력 코드가 이 메서드를 호출할 것입니다. 실제 작업은 Grid::move()에서 수행합니다.
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);
}
C++
복사
코드는 길지만 어렵지는 않습니다. 먼저 다른 칸으로 옮겨야 하는지 확인합니다. 그럴 필요가 없으면 위치만 갱신하고 끝냅니다.
다른 칸으로 이동했다면 현재 칸의 연결 리스트에서 제거한 뒤 새 칸의 리스트에 넣습니다. 새 유닛을 넣을 때와 마찬가지로 add()를 사용합니다.
매 프레임 많은 유닛을 리스트에 넣고 빼야 할 수 있으므로, 삽입과 삭제가 빠른 이중 연결 리스트를 사용한 것입니다.
사정거리 안에서
여기까지는 단순하지만 한 가지를 빠뜨렸습니다. 예제는 위치가 정확히 같은 유닛만 상호작용합니다. 체커나 체스 같은 게임이라면 몰라도, 더 사실적인 게임에서는 공격 범위를 고려해야 합니다.
위치가 일치하는지 대신 일정 거리 안에 있는지 검사하면 됩니다.
if (distance(unit, other) < ATTACK_DISTANCE) {
handleAttack(unit, other);
}
C++
복사
이때 다른 칸의 유닛도 충분히 가까워 상호작용할 수 있다는 점에 주의하세요.
그림 20-4. 가깝고도 먼 두 사람.
A와 B의 중심은 서로 다른 칸에 있지만, B는 A의 공격 범위 안에 있습니다. 따라서 같은 칸뿐 아니라 주변 칸의 유닛과도 비교해야 합니다. 먼저 handleCell()의 내부 루프를 별도 메서드로 분리합니다.
void Grid::handleUnit(Unit* unit, Unit* other) {
while (other != NULL) {
if (distance(unit, other) < ATTACK_DISTANCE) {
handleAttack(unit, other);
}
other = other->next_;
}
}
C++
복사
handleUnit()은 유닛 하나와 비교 대상 유닛 리스트를 인수로 받습니다. handleCell()은 이 메서드를 사용하도록 바꿉니다.
void Grid::handleCell(int x, int y) {
Unit* unit = cells_[x][y];
while (unit != NULL) {
// 이 칸의 다른 유닛을 처리합니다.
handleUnit(unit, unit->next_);
unit = unit->next_;
}
}
C++
복사
handleCell()이 이제 리스트 대신 칸 좌표를 받는다는 점 외에는 이전과 같습니다. 여기에 주변 칸 검사를 추가합니다.
void Grid::handleCell(int x, int y) {
Unit* unit = cells_[x][y];
while (unit != NULL) {
// 이 칸의 다른 유닛을 처리합니다.
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_;
}
}
C++
복사
확장된 코드는 주변 여덟 칸 중 그림에 표시한 네 칸의 유닛을 검사합니다. 그중 공격 범위 안에 있는 유닛에 대해서 공격을 처리합니다. 원문은 이를 왼쪽 네 칸이라고 설명하며, 그림에서는 왼쪽 위·왼쪽·왼쪽 아래·위쪽 칸을 표시합니다.
그림 20-5. 주변 칸의 절반을 검사합니다.
원주 8 U는 현재 유닛이 들어 있는 칸이고, X는 검사하는 칸입니다.
단계별 코드 연결하기 — handleCell()의 인수가 (int x, int y)로 바뀌었으므로, 실제로 합칠 때 handleMelee() 안의 호출도 handleCell(x, y)로 바꿔야 합니다. 격자는 후보를 좁히고 distance()가 실제 사정거리를 판정합니다. 따라서 같은 칸에 있다는 사실만으로 공격이 확정되지는 않습니다.
내부 루프에서 현재 유닛의 다음 유닛부터 검사한 이유는 같은 쌍을 두 번 처리하지 않기 위해서였습니다. 주변 칸도 같은 이유로 절반만 검사합니다. 여덟 칸을 모두 검사하면 어떤 일이 일어날까요?
A의 오른쪽 칸에 B가 있고 서로 공격 범위 안에 있다고 가정해봅시다. 모든 유닛이 주변 여덟 칸을 검사하면 다음과 같습니다.
1.
A의 공격을 검사할 때 오른쪽 칸의 B를 찾아 A와 B 사이의 공격을 등록합니다.
2.
B의 공격을 검사할 때 왼쪽 칸의 A를 찾아 같은 공격을 다시 등록합니다.
주변 칸의 절반만 검사하면 이 중복을 막을 수 있습니다. 어느 방향의 절반을 선택하는지 자체는 중요하지 않습니다.
원주 9 일반적인 A와 B의 관계는 비대칭이므로 여덟 칸을 모두 검사해야 하는 경우가 많습니다. 예를 들어 A가 움직일 때 B에게 패킷이나 알림을 보냈어도, B가 움직이면 A에게 별도로 알려야 합니다. 이 예제는 충돌 검사에 가깝습니다. A와 B의 충돌을 확인했다면 B와 A를 다시 확인할 필요가 없으므로 네 칸만 검사합니다. — 옮긴이
한 가지 가정이 더 있습니다. 지금까지는 최대 공격 거리가 한 칸의 크기보다 짧다고 가정했습니다. 칸이 작고 공격 거리가 더 길다면, 더 멀리 있는 주변 칸까지 검색해야 합니다.
보충 GIF · 주변 칸에서 후보를 모은 뒤 실제 거리로 가까운 이웃을 걸러내는 과정
이 예는 검색 반경이 한 칸 너비 이하인 경우입니다. 대상 칸과 주변 8칸을 확인한 다음 거리 검사를 적용합니다. 반경이 더 크다면 탐색할 칸 범위도 넓혀야 하며, 자기 자신은 이웃 결과에서 제외합니다.
20.7. 디자인 결정
공간 분할 자료구조는 잘 정리되어 있고 종류도 아주 많지는 않으므로 각각 살펴볼 수도 있습니다. 여기서는 여러 자료구조의 핵심 선택지를 모아 설명하겠습니다. 나중에 쿼드트리나 이진 공간 분할(BSP)을 배울 때 동작을 이해하고 적절한 자료구조를 고르는 데 도움이 되기를 바랍니다.
계층적으로 나눌 것인가, 균등하게 나눌 것인가?
격자 예제는 공간을 균등한 칸으로 나눴습니다. 반면 계층적 공간 분할은 먼저 공간을 몇 개의 영역으로 나눈 뒤, 객체가 많은 영역을 다시 나눕니다. 모든 영역의 객체 수가 정해진 최대 개수 이하가 될 때까지 재귀적으로 반복합니다.
원주 10 보통 프로그래머가 좋아하는 2, 4, 8 같은 수로 분할합니다.
균등하게 나누는 경우
•
더 단순합니다. 균등한 자료구조는 이해하고 구현하기 쉽습니다.
원주 11 저자는 거의 모든 장에서 ‘가능하면 최대한 단순하게 만들라’고 강조했습니다. 소프트웨어 공학의 많은 부분이 복잡함을 줄이기 위해 나왔습니다.
•
메모리 사용량이 일정합니다. 객체를 추가해도 공간을 새로 나누지 않으므로 분할에 필요한 메모리 양이 변하지 않습니다.
•
객체가 이동했을 때 갱신이 빠릅니다. 위치가 달라지면 자료구조도 바꿔야 할 수 있는데, 계층 구조에서는 여러 계층을 함께 수정해야 할 수도 있습니다.
계층적으로 나누는 경우
빈 공간을 훨씬 효율적으로 처리합니다. 고정 격자에서 전장 한쪽이 텅 비어 있다고 해봅시다. 많은 칸이 비어 있어도 메모리를 할당하고 매 프레임 순회해야 합니다. 계층 구조는 한산한 공간을 더 나누지 않습니다. 넓은 빈 공간이 큰 영역 하나로 남으므로, 수많은 작은 칸 대신 큰 영역 하나만 확인하면 됩니다.
밀집된 영역도 효과적으로 처리합니다. 비계층형 분할에서 다른 영역은 비어 있고 한 영역에만 객체가 몰린다면, 공간 분할을 하지 않을 때보다 오히려 비효율적일 수도 있습니다. 계층형 분할은 상황에 맞게 영역을 더 잘게 나누어 한 번에 고려할 객체 수를 줄입니다.
객체 수에 따라 분할이 달라지는가?
격자 예제는 칸 크기를 미리 정하고 유닛을 거기에 넣었습니다. 적응형 분할에서는 유닛의 수와 위치에 맞춰 영역 크기를 조절할 수 있습니다.
목표는 각 영역에 비슷한 수의 유닛이 들어가도록 균형을 맞추어 성능을 높이는 것입니다. 고정 격자에서 모든 유닛이 한 칸에 몰렸다고 해봅시다. 공격 대상을 찾는 비용은 다시 O(n²)로 되돌아갑니다.
객체 수와 관계없이 분할하는 경우
•
객체를 하나씩 추가하기 쉽습니다. 적절한 영역을 찾아 넣기만 하면 되므로, 전체를 다시 처리할 걱정 없이 개별 추가를 처리할 수 있습니다.
•
이동이 빠릅니다. 고정된 분할에서는 이전 영역에서 빼고 새 영역에 넣으면 됩니다. 반면 객체 수에 따라 나누는 방식은 유닛 하나가 이동해도 다른 많은 유닛의 영역까지 바뀔 수 있습니다.
원주 12 레드-블랙 트리나 AVL 트리 같은 균형 이진 검색 트리와 비슷합니다. 데이터를 추가하다 보면 트리를 재정렬하거나 여러 노드를 옮겨야 할 수 있습니다.
•
영역의 균형을 보장하기 어렵습니다. 분할이 고정되어 있으므로 객체가 골고루 들어가도록 제어하기 어렵습니다. 객체가 한곳에 몰리면 비어 있는 영역에 메모리를 낭비하면서 성능도 떨어질 수 있습니다.
객체 수에 따라 영역이 달라지는 경우
이진 공간 분할(BSP)이나 k-d 트리 같은 방식에서는 양쪽에 같은 수의 객체가 들어가도록 월드를 재귀적으로 둘로 나눌 수 있습니다. 이를 위해 분할 평면을 선택했을 때 양쪽에 객체가 몇 개씩 있는지 계산해야 합니다. 경계 볼륨 계층구조(BVH)도 객체 분포에 맞춰 구성하는 방법입니다.
•
영역의 균형을 보장할 수 있습니다. 단순히 더 빠르다는 것보다 성능을 일정하게 유지한다는 점이 중요합니다. 각 영역의 객체 수가 비슷하면 검색에 걸리는 시간도 일정하게 유지하기 좋습니다. 일정한 프레임 레이트를 위해서는 평균적인 속도 향상보다 이런 예측 가능성이 더 중요할 수 있습니다.
•
전체 객체를 한 번에 준비하여 분할하는 것이 더 효과적입니다. 객체 수에 따라 영역 크기가 달라지므로, 공간을 나누기 전에 전체 객체를 알고 있는 편이 좋습니다. 그래서 이런 방식은 고정된 지형이나 아트 리소스에 더 자주 사용됩니다.
영역의 분할 위치는 고정하고, 계층은 객체 수에 따라 정하는 경우
쿼드트리(quadtree)는 고정 분할과 적응형 분할의 장점을 어느 정도 함께 가집니다. 전체 공간을 하나의 영역으로 시작합니다. 객체 수가 정해진 한도를 넘으면 크기가 각각 원래 면적의 1/4인 네 사각형으로 나눕니다.
원주 13 쿼드트리는 2차원 공간을 분할합니다. 3차원에서는 한 볼륨을 여덟 정육면체로 나누는 옥트리(octree)가 있습니다. 차원이 하나 높다는 것 외에는 동작 방식이 거의 같습니다.
나누어진 사각형에 대해서도 객체 수가 기준 이하가 될 때까지 같은 작업을 반복합니다. 밀집된 부분만 재귀적으로 나누므로 객체 수에 맞춰 구조가 조정되지만, 이미 정해진 분할 경계가 이리저리 이동하지는 않습니다.
다음 그림을 왼쪽에서 오른쪽으로 보면, 밀집된 부분이 차례로 더 잘게 나뉘는 것을 볼 수 있습니다.
그림 20-6. 유닛이 세 개 이상 들어 있는 칸을 재귀적으로 분할합니다.
객체를 하나씩 추가할 수 있습니다. 위치에 맞는 사각형을 찾아 넣고, 최대 개수를 넘으면 그 영역을 나눕니다. 기존 유닛들은 새로 생긴 사각형에 들어갑니다. 원문은 이동시킬 객체 수가 최대 개수 이하이므로 일정한 추가 비용으로 처리할 수 있고, 객체 하나를 넣을 때 분할은 최대 한 번 발생한다고 설명합니다.
제거도 간단합니다. 객체를 뺀 후 부모 사각형 전체의 유닛 수가 최대 개수보다 작아졌다면 하위 영역들을 하나로 합치면 됩니다.
이동도 빠릅니다. 앞의 설명처럼 이동을 삭제와 추가로 처리할 수 있고, 이 작업들은 쿼드트리에서 비교적 빠릅니다.
분할 영역의 객체 수를 제한할 수 있습니다. 각 사각형의 유닛 수를 기준 아래로 유지하므로, 객체가 몰리더라도 한 영역에서 많은 유닛을 한꺼번에 검사하는 상황을 피할 수 있습니다.
원주 14 격자 크기를 끝없이 줄일 수는 없습니다. 객체가 같은 위치에 겹칠 수 있는 게임에서는 한 사각형에 들어가는 최대 유닛 수를 제한하지 못할 수도 있습니다. — 옮긴이
쿼드트리 설명의 전제 — 원문의 ‘삽입당 분할은 최대 한 번’이라는 설명은 일반적인 쿼드트리 전체에 대한 보장은 아닙니다. 분할한 자식 칸에도 객체가 몰리면 더 깊은 분할이 이어질 수 있습니다. 구현에서는 최대 깊이와 최소 칸 크기를 정하고, 동일 위치 객체가 몰릴 때의 처리도 마련합니다. 그림의 핵심은 빈 곳을 계속 쪼개지 않고 밀집된 곳만 세분화한다는 점입니다.
객체를 공간 자료구조에만 저장할 것인가?
공간 자료구조가 게임 객체의 생명주기까지 관리하도록 만들 수 있습니다. 반대로 별도 컬렉션이 객체들을 보관하고, 공간 자료구조는 위치 검색을 빠르게 하기 위한 캐시로만 사용할 수도 있습니다.
공간 자료구조에만 저장하는 경우
두 컬렉션을 유지하는 메모리 비용과 복잡도를 피할 수 있습니다. 같은 객체를 두 곳에서 관리하기보다 한 곳에서 관리하는 것이 저렴합니다. 두 컬렉션을 사용한다면 동기화가 필요합니다. 객체를 만들고 삭제할 때마다 양쪽에 함께 넣거나 빼야 합니다.
다른 컬렉션에도 저장하는 경우
전체 객체를 더 빠르게 순회할 수 있습니다. 객체별로 계속 수행할 일이 있다면 위치와 무관하게 모든 객체를 자주 순회해야 합니다. 예제의 거의 모든 칸이 비어 있다고 해봅시다. 유닛이 있는 칸을 찾으려고 격자 전체를 뒤지는 것은 시간 낭비입니다.
객체를 별도 컬렉션에 저장하면 전체 순회를 훨씬 빠르게 만들 수 있습니다. 두 자료구조를 각각의 목적에 맞게 최적화하는 것입니다.
원주 15 객체를 공간 자료구조뿐 아니라 vector<Unit*> 같은 컬렉션에도 모아두면 전체 객체를 훨씬 빠르게 순회할 수 있습니다. — 옮긴이
20.8. 관련 자료
이 장에서는 특정 공간 자료구조를 깊이 파고들기보다는 높은 수준에서, 그리고 너무 길지 않게 전체적인 원리를 살펴보려 했습니다. 다음 단계는 널리 사용하는 구조들을 배우는 것입니다. 이름은 무서워 보여도 들여다보면 그리 복잡하지 않습니다.
•
격자
•
쿼드트리
•
이진 공간 분할(BSP)
•
k-d 트리
•
경계 볼륨 계층구조(BVH)
이들은 익숙한 1차원 자료구조를 다차원으로 확장한 것으로 이해할 수 있습니다. 대응되는 1차원 구조를 알면 무엇을 선택할지 판단하는 데 도움이 됩니다.
•
격자의 1차원 버전은 버킷 정렬(bucket sort)입니다.
•
BSP, k-d 트리, BVH의 1차원 버전은 이진 검색 트리입니다.
•
쿼드트리와 옥트리의 1차원 버전은 트라이(trie)입니다.