객체를 효과적으로 찾기 위해 객체 위치에 따라 구성되는 자료구조에 저장한다.
수백 명의 군인이 뒤엉켜 싸우는 게임이 있다.
전사는 칼을 휘두르기 전에 적이 어디에 있는지를 알아야 한다.
그러나 이렇게 무식하게 이중 중첩 루프로 구현한다면, 유닛 수가 많아질수록 검사 횟수가 매우 늘어나게 된다.
(공간 복잡도: O(n^2))
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]);
}
}
}
}1차원 공간이라면 위치에 따라 정렬했을 때 전체 배열을 다 훑지 않아도 이진 검색 등으로 주변 유닛을 찾을 수 있다.
이를 2차원 이상의 공간에 적용한 것이 공간 분할 패턴이다.
공간 분할 패턴
- 객체들은 공간 위에서의 위치 값을 갖는다.
- 객체는 위치에 따라 구성되는 공간 자료구조에 저장한다.
- 공간 자료구조를 통해 같은 위치 혹은 주변에 있는 객체를 빠르게 찾을 수 있다.
- 객체 위치가 바뀌면 공간 자료구조도 업데이트한다.
언제 쓸 것인가?
살아있는 객체 말고 정적인 프랍이나 지형을 저장하는 데에도 흔히 쓰인다.
위치 값이 있는 객체가 많고, 위치에 따라 객체를 찾는 질의가 성능에 영향을 줄 정도로 많을 때 공간 분할 패턴을 사용한다.
주의사항
공간 분할 패턴에서는 객체를 위치에 따라 정리하기 때문에, 객체의 위치 변경 처리가 어렵다.
그런데 공간 분할 패턴은 객체가 많을 수록 의미있는 패턴이다. 즉 객체가 많이 없다면 굳이 사용할 이유가 없다.
또한 공간 분할 자료구조에 추가적인 메모리가 필요하므로, CPU가 메모리보다 부족한 경우에는 오히려 손해이다.
공간 분할 패턴 예제
가장 간단한 공간 분할 형식인 고정 격자 방법을 소개한다.
모눈종이
정사각형 모양의 고정 크기 격자들이 있는 모눈종이 모양의 전장이 있다.
유닛을 격자 칸 안에 넣으며, 칸마다 유닛 리스트가 있다.
전투를 처리할 때 같은 칸에 있는 유닛만 고려한다.
유닛을 연결리스트로 저장한 격자
class Unit {
// 유닛이 이동할 때 Grid에서 데이터 수정하므로 friend class
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_; // 2차원 위치값
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];
};칸->유닛<->유닛<->유닛
격자 칸은 해당 칸에 있는 유닛 중 첫 번째 유닛을 가리킨다.
이렇게 연결리스트로 유닛을 관리한다.
전장 속으로 들어가기
// Unit 생성자에서 알맞은 격자 칸에 유닛 추가
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() {
// 모든 격자 칸을 순회하며 handleCell 호출
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;
// 같은 칸
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_);
// 인접한 칸에 있는 유닛 처리
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이 handleUnit을 사용하게 바꿨다
기존의 handleCell은 해당 격차 칸 내에서만 검사했지만 주변 격자 칸의 유닛도 처리할 수 있게 되었다.
여기서 주의할 점은 인접한 8칸 중 4칸만 검사하고 있는 것이다.
예제는 단순 충돌검사이기 때문에 두 유닛이 인접한지만 검사하면 되기 때문에 중복해서 충돌 검사를 하지 않도록 반만 검사한다.
단, 일반적인 공격은 비대칭이기 때문에 8칸을 모두 검사하는 것이 맞다. (A가 B를 공격, B가 A를 공격하는 것은 다르기 때문)
디자인 결정
공간을 계층적으로 나눌 것인가, 균등하게 나눌 것인가?
앞선 예제들은 공간을 여러 개의 균등한 칸으로 나누었다.
계층적 공간 분할은 공간을 먼저 몇 개의 영역으로 나눈다.
객체가 많은 영역은 다시 분할하여 모든 영역에 있는 유닛 개수가 특정 개수 이하로 떨어질 때까지 재귀적으로 반복한다.
균등 공간 분할
- 단순함
- 메모리 사용량이 일정: 객체를 추가한다고 해서 공간을 새로 분할하지 않기 때문에 공간 분할에 필요한 메모리 양이 일정함
- 객체가 위치 이동 시 자료구조의 업데이트 속도가 빠름
계층 공간 분할
- 빈 공간을 훨씬 효율적으로 처리: 균등 공간 분할은 많은 칸이 비어있더라도 칸을 메모리에 할당하고 매 프레임 순회해야 한다. 계층 공간 분할은 한산한 공간은 재분할하지 않아, 큰 영역 하나만 순회하면 된다.
- 밀집된 영역도 효과적으로 처리: 다른 영역은 텅텅이고 한 영역에만 객체가 몰려있으면,균등 공간 분할이 공간 분할을 안 한 것보다 효율이 떨어질 수 있다. 그러나 계층 공간 분할은 상황에 맞게 공간을 재분할한다.
객체 개수에 따라 분할 횟수가 달라지는가?
예제 코드와 달리 적응형 분할 방식은 유닛 개수와 위치에 따라 분할 크기를 조절한다.
객체 개수와 상관없이 분할
- 객체가 순차적으로 추가될 수 있음: 적절한 위치를 찾아 넣어주기만 하면 된다.
- 객체가 빠르게 이동 가능: 객체 개수를 고려한다면 유닛 하나만 다른 영역에 이동해도 다른 많은 유니까지 영역을 옮겨야 할 수도 있다.
- 영역이 균형 잡히지 않을 가능성 있음
객체 개수에 따라 영역이 다르게 분할
- 영역의 균형 잡힘 보장: 성능을 일정하게 유지할 수 있다. 프레임 레이트 유지를 위해서는 단순 성능 향상보다 일정함이 더 중요하다.
- 전체 객체에 대해 한 번에 분할하는 것이 훨씬 효과적: 객체 개수를 고려한다면 공간을 분할하기 전에 전체 객체를 미리 준비하는 것이 최선이다. 따라서 고정되어 있는 정적 지형이나 아트 리소스에 훨씬 자주 사용된다.
영역 분할은 고정, 계층은 객체 개수에 따라 달라짐
쿼드트리
- 고정 분할과 적응형 분할의 장점을 가진다.
- 전체 공간을 한 영역으로 시작해 한 공간의 객체 개수가 일정 개수 이상이면 1/4로 분할한다.
- 각 사각형의 객체 개수가 일정 수 이하가 될 때까지 재귀적으로 반복한다.
- 객체를 순차적으로 추가 가능: 위치에 맞는 사각형 칸을 찾아 추가하면 된다. 객체를 추가할 때마다 분할을 최대 1번만 발생한다. 객체 제거 시 영역 통합도 최대 한 번이다.
- 빠른 객체 이동
- 분할 영역의 균형
객체를 공간 분할 자료구조에만 저장하는가?
객체를 공간 분할 자료구조에만 저장
컬렉션이 두 개가 되면서 생기는 메모리 비용과 복잡도를 피할 수 있다. (컬렉션이 두 개면 동기화가 필요하다.)
다른 컬렉션에도 객체를 저장
전체 객체를 더 빠르게 순회할 수 있다.
객체마다 계속해서 처리할 작업이 있는데 공간 분할 자료구조에만 저장하면 모든 칸을 전부 뒤져야 한다.
객체를 별도의 컬렉션에도 저장하면 순회 과정이 훨씬 빠르다. > 두 개의 자료구조를 각자 필요에 맞게 최적화할 수 있다.
