공간 분할 패턴
공간 분할 패턴은 코딩 테스트를 준비한 분이라면 이미 알고 계실 수 있습니다.
공간 분할 패턴으로 유명한 알고리즘에는 쿼드 트리, 옥트리, BSP 등 다양한 공간 분할 알고리즘이 있습니다.
공간 분할 패턴의 목적과 구조
목적
1.
성능 최적화: 객체들을 효율적으로 정리하고 검색하여 렌더링 및 충돌 검출의 성능을 향상시킵니다.
2.
리소스 관리: 메모리 사용량을 최적화하고 처리할 객체의 수를 줄입니다.
a.
처리할 개채 수를 줄인다는 건, 어떤 것을 처리할 지 미리 정의한다는 것을 의미합니다.
3.
시각적 정확성: 뷰포트 내에서만 필요한 객체를 렌더링하여 시각적 정확성을 높입니다.
구조 및 패턴
1.
Quadtree (2D 게임용): 평면을 4개의 사각형 영역으로 나눕니다. 주로 2D 게임에 사용됩니다.
2.
Octree (3D 게임용): 공간을 8개의 큐브로 나눕니다. 3D 게임과 어플리케이션에서 널리 사용됩니다.
3.
BSP (Binary Space Partitioning): 공간을 이진 트리로 분할하여 관리합니다. 주로 복잡한 실내 환경에서 사용됩니다.
공간 분할 패턴의 장,단점.
•
장점
◦
효율적인 검색: 객체 검색 시간을 단축할 수 있습니다.
▪
사실 위, 방법이 공간 분할 패턴의 전부라 할 수 있습니다.
◦
동적 환경 적합성: 객체가 추가되거나 제거될 때 빠르게 적응합니다.
◦
렌더링 최적화: 불필요한 렌더링을 줄일 수 있습니다.
•
단점
◦
복잡성 증가: 구현이 복잡해질 수 있습니다.
◦
오버헤드 발생: 작은 객체나 많은 수의 객체가 있을 경우, 오버헤드가 발생할 수 있습니다.
◦
동적 객체 처리: 빠르게 움직이는 객체를 처리하는 것이 어려울 수 있습니다..
공간 분할 패턴 UML
공간 분할 패턴의 UML은 상황에 따라서 다르므로, 특정한 정형화된 구조는 없습니다.
그러나, 주로 노드를 활용하여 해당 공간을 파악하는 구조를 사용합니다.
공간 분할 패턴 구현
2D 공간 분할에서 가장 기본적으로 사용하는 쿼드 트리를 예시로 설명하겠습니다.
public class QuadTreeNode {
private int MAX_OBJECTS = 10;
private List<GameObject> objects;
private Rect bounds;
private QuadTreeNode[] nodes;
public QuadTreeNode(Rect bounds) {
this.bounds = bounds;
objects = new List<GameObject>();
nodes = new QuadTreeNode[4];
}
}
C#
복사
쿼드 트리의 기본적인 노드 구조입니다.
MAX_OBJECTS : 해당 영역에 존재할 수 있는 오브젝트의 최대 갯수입니다.
objects : 해당 영역에 존재하는 오브젝트 입니다.
bounds : Rect를 사용해서 해당 영역을 표시합니다.
nodes : 해당 영역을 세분화할 때 표시하는 노드입니다.
분할 깊이: 여기서는 사용하지 않았지만, 분할 깊이를 사용하면 해당 영역의 bounds의 크기를 즉시 알 수 있습니다.
예) 1: 원본 크기, 2: 원본 크기 / 4
위와 같은 방식 때문에 사용법에 따라 구조 자체가 달라집니다. 예를 들어 2D 게임에서 특정 노드의 Depth 2에 해당하는 상위 노드의 오브젝트들을 모두 알고 싶다면, parent를 기억해야 할 것입니다.
분할 함수 (Subdivide)
private void Subdivide() {
float subWidth = bounds.width / 2f;
float subHeight = bounds.height / 2f;
float x = bounds.x;
float y = bounds.y;
nodes[0] = new QuadTreeNode(new Rect(x + subWidth, y, subWidth, subHeight));
nodes[1] = new QuadTreeNode(new Rect(x, y, subWidth, subHeight));
nodes[2] = new QuadTreeNode(new Rect(x, y + subHeight, subWidth, subHeight));
nodes[3] = new QuadTreeNode(new Rect(x + subWidth, y + subHeight, subWidth, subHeight));
}
C#
복사
Quadtree를 분할하는 함수는 현재 노드를 네 개의 하위 영역으로 나누며, 이 각각의 하위 노드에 대한 QuadTreeNode 인스턴스를 생성합니다.
객체 추가 및 관리
Quadtree에 객체를 추가하고 적절한 노드에 분배하는 함수를 정의합니다.
public void Insert(GameObject obj) {
if (nodes[0] != null) {
int index = GetIndex(obj.GetComponent<Collider2D>().bounds);
if (index != -1) {
nodes[index].Insert(obj);
return;
}
}
objects.Add(obj);
if (objects.Count > MAX_OBJECTS) {
if (nodes[0] == null) {
Subdivide();
}
int i = 0;
while (i < objects.Count) {
int index = GetIndex(objects[i].GetComponent<Collider2D>().bounds);
if (index != -1) {
nodes[index].Insert(objects[i]);
objects.RemoveAt(i);
} else {
i++;
}
}
}
}
C#
복사
GetIndex 함수는 Quadtree에서 객체가 속할 노드의 인덱스를 결정하는 데 사용됩니다. 이 함수는 주어진 객체의 경계(Rect 형식)를 받아, 객체가 현재 노드의 어느 부분에 위치하는지 판단합니다. Quadtree에서는 네 개의 영역이 있으므로, 이 함수는 네 가지 경우 (북서, 북동, 남서, 남동) 중 하나를 반환하거나, 객체가 특정 하위 노드에 완전히 속하지 않는 경우 -1을 반환합니다.
private int GetIndex(Rect objectBounds) {
int index = -1;
double verticalMidpoint = bounds.x + bounds.width / 2;
double horizontalMidpoint = bounds.y + bounds.height / 2;
// 객체가 수평 중앙선 위쪽에 있는지 여부
bool topQuadrant = (objectBounds.y < horizontalMidpoint && objectBounds.y + objectBounds.height < horizontalMidpoint);
// 객체가 수평 중앙선 아래쪽에 있는지 여부
bool bottomQuadrant = (objectBounds.y > horizontalMidpoint);
// 객체가 수직 중앙선 왼쪽에 있는지 여부
if (objectBounds.x < verticalMidpoint && objectBounds.x + objectBounds.width < verticalMidpoint) {
if (topQuadrant) {
index = 1; // 북서
} else if (bottomQuadrant) {
index = 2; // 남서
}
}
// 객체가 수직 중앙선 오른쪽에 있는지 여부
else if (objectBounds.x > verticalMidpoint) {
if (topQuadrant) {
index = 0; // 북동
} else if (bottomQuadrant) {
index = 3; // 남동
}
}
return index;
}
C#
복사
