Spatial Partition
- 객체를 효과적으로 찾기 위해 객체 위치에 따라 구성되는 자료구조에 저장한다.
Motivation
- 현실감을 제공하는 요소 중 하나: 위치(location)
- 공간(space) 개념: 객체는 공간 어딘가의 위치에 존재하게 된다.
- 위치(location) 개념: 여러 형태로 확인 가능
- 물리 충돌 or 오디오(거리에 따른 소리조절)
- 이를 위해 ‘주변에 어떤 객체들이 있는지’ 알아야한다.
- 매 프레임마다 이를 확인 == 성능 병목
전장 위의 유닛들
- RTS 게임을 만든다고 해보자.
- 전장에는 수백이 넘는 유닛들이 싸운다.
- 근접 유닛은 공격하기 전에 적이 어디에 있는지를 알아야 한다.
- 이를 단순하게 구현해보면 다음과 같다.(이중 포문)
1
2
3
4
5
6
7
8
9
10
11
12
13
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차원 전장
- 문제는 배열에 들어 있는 유닛이 따로 정렬되어 있지 않다는 것.
- 유닛을 찾으려면 전체 배열 다 순회해야함.
- 문제를 단순화하기 위해 1차원으로 생각해보자
위와 같으면, 위치를 기준으로
정렬하고 전체 배열을 다 조회하지 않고도 이진 검색 같은 걸로 주변 유닛을 쉽게 찾을 수 있다.이렇게 위치에 따라 구성되는 자료구조에 객체를 저장 => 빠르게 검색 가능
- 이걸 2차원 이상의 공간에 적용한 것이
공간 분할 패턴이다.
- 이걸 2차원 이상의 공간에 적용한 것이
The pattern
객체들은 공간 위에서 위치 값을 갖는다.공간 자료구조: 객체 위치에 따라 구성됨- 같은 위치 혹은 주변 객체를 빠르게 찾을 수 있다.
- 위치 변경 => 공간 자료구조도 업데이트
언제 사용
공간 분할 패턴은 움직이는 게임 객체뿐만이 아니라 정적인 프랍이나 지형을 저장할 때
- 복잡한 게임에는 콘텐츠별로 공간 분할 자료구조를 따로 두기도 한다.
위치 값이 있는 객체가 많고, 위치에 따라 객체를 찾는 쿼리가 성능에 영향을 줄만큼 잦을 경우
주의사항
객체가 많을 때만 의미가 있다.
이진검색 O(log n), 전체 검색 O(nlogn), 비둘기집 정렬 같은 기법을 사용하면 O(n)
공간 분할 패턴 == 객체를 위치에 따라 정리 == 위치 변경 복잡함.
- CPU도 더 소모
- 추가 메모리가 더 필요.
- CPU보다 메모리가 더 부족한 곳에서는 오히려 손해일 수 있다.
해시 테이블에 들어 있는 객체의 해시 키가 자발적으로 변경되는것을 상상해보면 어려운일 이라는것을 알 수 있음.
예제 코드
- 여러 변형들이 잘 문서화 되어있다.
- 이 책에서는 가장 간단한 공간 분할 형식인 고정 격자(fixed-grid)방법을 다룬다.
모눈종이
정사각형 모양의 고정 크기 격자를 모눈종이 모양처럼 겹쳐 놓는다.
유닛을 배열이 아닌 격자 칸 안에 집어넣는다.
칸마다 유닛 리스트가 있어서 유닛 중에서 위치가 칸의 범위 안에 들어오는 것들을 저장한다.
- 전투를 처리할 때에는 같은 칸에 들어 있는 유닛만 신경 쓰면 된다.
- 소규모로 적은 개수의 유닛들만 비교하게하는것.
유닛을 링크드 리스트로 저장한 격자
- 아래와 같이 Unit 클래스를 작성할 수 있다.
- Unit에는 위치 값과 자기가 속한 격자(grid) 객체 포인터가 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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_;
};
유닛이 움직일 때 격자에 속해 있는 데이터도 제대로 위치해 있도록 Grid 객체와 통신해야 할 수 있기 때문에 Grid 클래스가 friend로 정의되어 있다.
격자 클래스는 대략 다음과 같다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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];
};
- 모든 칸(cell)이 유닛의 포인터로 되어 있다.
- 이제 유닛이 이전 포인터와 다음 포인터를 갖도록 해야한다.
1
2
3
4
5
6
7
class Unit
{
// Previous code...
private:
Unit* prev_;
Unit* next_;
};
- 이를 통해서 배열이 아니라 더블 링크드 리스트로 유닛을 관리할 수 있다.
- 격자 칸은 그 칸에 들어 있는 유닛 리스트의 첫 번째 유닛을 포인터로 가리킨다.
- 유닛은 자기 이전과 이후 유닛을 포인터로 가리킨다.
전장 속으로 들어가기
- 먼저 새로 만든 유닛을 적당한 격자 칸에 넣어야 한다.
- Unit 클래스 생성자에서 한다.
1
2
3
4
5
6
7
8
9
Unit::Unit(Grid* grid, double x, double y)
: grid_(grid),
x_(x),
y_(y),
prev_(NULL),
next_(NULL)
{
grid_->add(this);
}
add()메서드는 다음과 같다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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;
}
}
- 위 코드는 유닛이 들어갈 칸을 찾은 뒤 그 칸에 들어 있는 리스트 맨 앞에 유닛을 추가한다.
- 칸에 이미 유닛 리스트가 들어 있다면, 추가한 유닛 뒤에 유닛 리스트를 붙인다.
검의 격돌
모든 유닛을 적절한 칸에 넣은 뒤, 유닛끼리 서로 칼을 휘두르게할 수 있다.
격자를 이용해서 전투를 처리하는 메서드는 다음과 같다.
1
2
3
4
5
6
7
8
9
10
void Grid::handleMelee()
{
for (int x = 0; x < NUM_CELLS; x++)
{
for (int y = 0; y < NUM_CELLS; y++)
{
handleCell(cells_[x][y]);
}
}
}
- 칸을 순회하면서 handleCell()을 호출한다.
- 큰 전장을 각각 고립된 전투 공간들로 분할한 것.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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_;
}
}
- 이 코드에서도 모든 유닛 쌍에 대해서 같은 위치에 있는지를 검사한다.
- 하지만, 모든 유닛을 확인하지 않는다,
- 같은 칸에 들어 있을 정도의 가까운 유닛들만 검사한다.
루프문이 더 많이 중첩해서 성능이 떨어진것처럼 보일 수 있지만, 내부 2중루프에서 검사하는 유닛 개수가 훨씬 적기 때문에 칸마다 순회하는 외부 루프 비용을 상쇄하기에 충분하다.(칸의 분할정도에 따라 성능에 문제가 생길 수 있다)
Charging forward
- 유닛이 칸에 묶여 있음. => 칸 너머로 이동하면 그 칸에 있는 유닛들만이 아니라 어느 유닛에서도 그 유닛을 볼 수 없음.
- 해결
: 유닛 이동시 추가작업 수행
- 칸을 넘어가면 유닛을 현재 칸에서 제거, 새로운 칸에 추가
- 이를 위해 이동용 메서드 추가해야함
- 해결
1
2
3
4
void Unit::move(double x, double y)
{
grid_->move(this, x, y);
}
- 실제 작업은 Grid 클래스의
move()에서 실행된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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);
}
- 위 코드와 같이 매 프레임마다 많은 유닛을 링크드 리스트에 넣으면 삽입/삭제를 빠르게 할 수 있다.
사정거리 안에서
- 예제에서는 같은 위치에 있는 유닛끼리만 상호작용한다.
- 범위안에 있도록 수정해야함.
1
2
3
4
if (distance(unit, other) < ATTACK_DISTANCE)
{
handleAttack(unit, other);
}
- 범위를 검사할 때, 다른 칸에 들어 있는 유닛도 상호작용할 수 있게 해야함.
- 위 와 같이 다른 칸 또한 검사하려면, 먼저
handleCell()에서 내부 루프를 따로 빼야한다.
1
2
3
4
5
6
7
8
9
10
11
12
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()을 사용하게 변경
1
2
3
4
5
6
7
8
9
10
11
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()은 유닛 리스트가 아닌 칸의 좌표값을 받는다.- 이를 아래와같이 확장할 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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칸에 들어 있는 유닛과 충돌여부를 검사한다.주변 유닛 중에서도 공격 범위 안에 들어와 있는 유닛에 대해서는 공격 처리를 한다.
![현재 칸은 U, 주변 검사하는 칸은 x]()
내부 루프에서는 같은 유닛끼리 두 번 검사하는 것을 막기 위해 주변 칸도 절반만 검사한다.
주변 8칸을 모두 검사하면 다음과 같이 된다.
- A공격을 검사할 때 오른쪽 칸에 있는 B를 찾는다. A와 B 사이의 공격을 등록한다.
- B공격을 검사할 때 왼쪽 칸에 있는 A를 찾는다. A와 B를 다시 등록한다.
주변 칸 중 반만 찾으면 이 문제를 해결할 수 있다.
일반적으로 A와 B관계가 비대칭이기 때문에 8칸 다 검사해야한다.(A가 B에 알림, B또한 A에게 알릴필요가 있음)
만약 한 칸의 크기가 짧고 공격범위가 더 넓다면, 주변 칸을 더 넓게해야한다.
디자인 결정
- 공간분할 자료구조에 대해 간략한 설명.
공간을 계층적으로 나눌 것인가, 균등하게 나눌것 인가?
- 계층적 공간 분할: 공간을 몇 개의 영역으로 나눈다. 그런 뒤 객체가 많은 영역은 다시 분할한다.
- 모든 영역에 들어 있는 유닛의 개수가 특정 최대 개수 이하로 떨어질 때까지 이 과정을 재귀적으로 반복한다.(2의 제곱수로 분할)
균등하게 나눈다면
- 더 단순하다
- 매모리 사용량이 일정하다: 공간을 새로 분할하지 않음, 공간 분할에 필요한 메모리양 불변
- 객체가 위치를 이동할 때 자료구조의 업데이트 속도가 빠르다: 계층형 공간 분할 => 여러 계층을 같이 고쳐야할 가능성
계층적으로 나눈다면
- 빈 공간을 훨씬 효율적으로 처리할 수 있다
- 어느 공간에 객체가 없으면, 칸이 비어있어도 칸에 메모리 할당해야함, 매 프레임마다 순회도 해야함.
- 계층형 공간 분할에서는 한산한 공간을 재분할하지 않기 때문에, 크게 비어 있는 공간들은 한 영역으로 남아있게 된다. 그렇기 때문에 작은 영역들을 순회하지 않고 큰 영역 하나만 순회하면 됨.
- 밀집된 영역도 효과적으로 처리 가능
- 많은 객체가 한곳에 뭉쳐 있으면, 비계층형 분할 방식이 비효율적일 수 있다.
- 계층형 분할에서는 상황에 맞게 공간을 재분할, 한 번에 고려해야 할 객체 개수가 너무 많아지지 않도록 해준다.
객체 개수에 따라 분할 횟수가 달라지는가?
- 예제: 분할 크기가 미리 정해짐.
- 적응형: 유닛 개수와 위치에 따라 분할 크기를 조절.
- 성능을 위해 영역마다 비슷한 수의 유닛이 들어갈 수 있도록 균형 잡힌 분할을 만들어야한다.
- 한 칸에 전부 있으면 O(n^2) 수준.
객체 개수와 상관없이 분할한다면
- 객체는 순차적으로 추가될 수 있다
- 적당한 위치를 찾아 넣어줌. -> 성능 걱정 없이 한 번에 처리
객체가 빠르게 이동할 수 있다
- 공간 분할이 고정 => 이동시 이전 영역에서 제거, 다음 분할 영역에서 추가
- 객체 개수에 따라 공간을 분할 => 유닛 하나만 다른 영역으로 이동해도 다른 많은 유닛까지 영역을 옮겨야할 수 있음.
- 레드-블랙 트리, AVL 트리 같은 이진 검색 트리와 마찬가지. 재정렬하거나 여러 노드를 섞어줘야할 필요가 있음.
- 영역이 균형잡혀 있지 않을 수 있다
- 객체가 뭉침 == 비어 있는 영역 메모리 낭비 == 성능 더 떨어질 가능성
객체 개수에 따라 영역이 다르게 분할된다면
- 이진 공간 분할(BSP)이나 k-d트리:
- 공간 분할에서는 양쪽에 같은 수의 객체가 들어 있도록, 월드 공간을 반씩 재귀적으로 쪼갬.
- 양쪽에 객체가 몇개 있는지 계산해야함
경계 볼륨 계층구조(BVH)는 객체 분호에 맞춰서 공간을 분할하는 또 다른 기법이다.
영역의 균형 잡힙을 보장할 수 있다
- 성능을 일정하게 유지 가능.
- 프레임레이트 일정하게 유지 => 단순한 성능향상보다 일정함이 더 중요
- 전체 객체에 대해 한번에 분할해놓는 게 훨씬 효과적
- 공간을 분할하기 전에 전체 객체를 미리 준비해두는 게 최선.
- 보통 게임에서 고정된 정적 지형이나, 아트 리소스에 많이 사용됨
영역 분할은 고정되어 있지만, 계층은 객체 개수에 따라 달라진다면
쿼드트리(quadtree): 고정 분할과 적응형 분할의 장점을 둘 다 어느 정도 가지는 방식
- 전체 공간을 한 영역으로 시작
- 공간에 들어 있는 객체 개수가 정해진 수 이상을 넘어가면 사각형 4개로 분할, 크기는 1/4 고정
쿼드트리 == 2차원 공간 분할, 3차원 공간 == 옥트리(octree), 차원이 더 높지만 동작방식은 같다.
- 이렇게 분할된 사각형에 대해, 각 사각형에 들어 있는 객체 개수가 일정 수 이하가 될 때까지 재귀적으로 반복
- 밀도가 높은 영역만 재귀적으로 분할한다는 면에서 객체 개수에 따라 조정되긴하지만, 분할 영역이 이동하지는 않는다.
- 아래 그림을 보면, 분할 영역들이 바뀌는 것을 확인할 수 있다.
- 객체를 순차적으로 추가할 수 있다
- 위치에 맞는 사각형 칸을 찾아 추가하기만 하면됨.
- 사각형에 들어 있는 유닛이 최대 개수를 넘기면 영역을 분할
- 기존 사각형에 있던 유닛들은 새로운 사각형에 편입
- 이 때 추가작업이 필요, 그러나 이동해야 하는 객체는 항상 유닛 최대 개수 이하, 필요한 성능을 보장받을 수 있음.
- 객체를 하나 추가할 때 분할은 최대 한번
- 제거: 최대 개수 미만이면 합침.
- 객체 이동이 빠름
- 이동: 단순히 추가와 삭제
- 분할 영역이 균형잡힘
- 사각형 내부 유닛 개수 항상 최대 개수 미만
- 한 영역에 많은 유닛이 동시에 못들어가게 막음
객체를 공간 분할 자료구조에만 저장하는가?
- 공간 분할 자료구조에서 게임 객체의 생명주기까지 관리 가능.
- 컬렉션에 객체들을 넣고, 공간 분할 자료구조는 위치 관련 처리를 빠르게 하기 위한 캐시 용도로만 사용할 수도 있다.
객체를 공간 분할 자료구조에만 저장한다면
- 컬렉션이 두 개가 되면서 생기는 메모리 비용과 복잡도 피함
- 한 곳에 두는게 더 싸다.
- 동기화 비용 없음
다른 컬렉션에도 객체를 둔다면
- 전체 객체를 더 빠르게 순회 가능
- 객체마다 계속해서 처리해야 할 작업이 있으면, 위치와 상관 없이 자주 모든 객체를 순회해야함.
- 별도의 컬렉션 저장 => 순회 과정 훨씬 빠르게 (두 개의 자료구조 각자 용도에 맞게 최적화)
관련자료
- 가장 많이 쓰이는 공간 분할 자료구조들
- Grid
- Quadtree
- BSP
- k-d tree
- Bounding volume hierarchy
- 이들 자료구조는 1차원 자료구조를 다차원으로 확장한 것과 다르지 않음.
- Grid == 버킷 정렬(bucket sort)
- BSP, k-d 트리, BVH == 이진 검색 트리
- 쿼드 트리, 옥트리 == 트라이(trie)