📌먼저 트리(tree) 자료 구조란?
계층 구조를 가지는 자료구조로, 부모-자식 관계를 통해 데이터를 조직하는 비선형 자료구조입니다. 트리는 일반적인 트리, 이진트리,쿼드트리, K-D 트리가 있습니다.
트리 자료구조를 활용하여 검색, 이미지 압축, N차원의 데이터 관리 등의 알고리즘에 활용할 수 있습니다.
(검색은 BST, 이미지 압축은 Quad Tree, N차원 데이터 관리는 KD-Tree 등등 다양하게 활용 가능합니다.)
📌쿼드 트리
-
쿼드 트리는 대량의 좌표 데이터를 메모리에 압축하여 저장하는 기법으로,
주어진 공간을 4개로 분할하여 재귀적으로 표현합니다. -
쿼드 트리의 가장 유명한 예시로는 검은색과 흰 색밖에 없는 흑백 그림을
압축해 표현한 사례가 있습니다. -
쿼드 트리는 주어진 공간을 항상 4개로 분할해 재귀적으로 표현하기 때문에
쿼드 트리라는 이름이 붙었습니다. -
대량의 좌표 데이터를 메모리 안에 압축해 저장하기 위해 사용하는
여러 기법 중 쿼드 트리가 있습니다.
📌쿼드 트리 유니티에서 활용하기
쿼드 트리 기본 동작 방식
- 초기
처음에는 하나의 큰 사각형(루트 노드)에 모든 데이터를 저장- 분할
일정 개수 이상의 점이 들어오면, 사각형(2차원)을 사분면(자식 노드)으로
나누고, 각 사분면 안에 점들을 분배. 이때, 각 자식 노드는 해당 영역에 포함되는 데이터만 저장- 재분할
각 분할된 영역(사각형) 안에서도 점이 많아지면, 다시 4개로 나누어 더 세분화.- 종료 조건
더 이상 쪼갤 필요가 없을 때(점의 개수가 일정 수 이하가 되었을 때) 멈춤.- 재귀적 수행
이 과정은 재귀적으로 진행되며, 분할이 더 이상 필요 없을 때까지 반복됩니다.
코드는 gpt 도움을 받았습니다 :)
1. 유니티에서 쿼드 트리의 기본 구조
//유니티 쿼드 트리 코드 예시 (QuadTree.cs)
using System.Collections.Generic;
using UnityEngine;
public class QuadTree
{
private int capacity;
private List<Vector2> points;
private Rect boundary;
private bool divided;
private QuadTree northeast;
private QuadTree northwest;
private QuadTree southeast;
private QuadTree southwest;
public QuadTree(Rect boundary, int capacity)
{
this.boundary = boundary;
this.capacity = capacity;
points = new List<Vector2>();
divided = false;
}
public bool Insert(Vector2 point)
{
if (!boundary.Contains(point))
{
return false; // 점이 현재 쿼드 트리 경계 밖에 있음
}
if (points.Count < capacity)
{
points.Add(point);
return true;
}
else
{
if (!divided)
{
Subdivide(); // 서브 노드 생성
}
// 적절한 하위 노드에 점 삽입
if (northeast.Insert(point)) return true;
if (northwest.Insert(point)) return true;
if (southeast.Insert(point)) return true;
if (southwest.Insert(point)) return true;
}
return false;
}
private void Subdivide()
{
float x = boundary.x;
float y = boundary.y;
float w = boundary.width / 2f;
float h = boundary.height / 2f;
Rect ne = new Rect(x + w, y, w, h);
Rect nw = new Rect(x, y, w, h);
Rect se = new Rect(x + w, y - h, w, h);
Rect sw = new Rect(x, y - h, w, h);
northeast = new QuadTree(ne, capacity);
northwest = new QuadTree(nw, capacity);
southeast = new QuadTree(se, capacity);
southwest = new QuadTree(sw, capacity);
divided = true;
}
public void Query(Rect range, List<Vector2> found)
{
if (!boundary.Overlaps(range))
{
return; // 범위가 경계를 벗어난 경우
}
foreach (var point in points)
{
if (range.Contains(point))
{
found.Add(point);
}
}
if (divided)
{
northeast.Query(range, found);
northwest.Query(range, found);
southeast.Query(range, found);
southwest.Query(range, found);
}
}
public void DrawGizmos()
{
// 경계를 시각화
Gizmos.color = Color.white;
Gizmos.DrawWireCube(new Vector3(boundary.center.x, boundary.center.y, 0),
new Vector3(boundary.width, boundary.height, 0));
if (divided)
{
northeast.DrawGizmos();
northwest.DrawGizmos();
southeast.DrawGizmos();
southwest.DrawGizmos();
}
// 점 시각화
foreach (var point in points)
{
Gizmos.color = Color.red;
Gizmos.DrawSphere(new Vector3(point.x, point.y, 0), 0.2f);
}
}2. 활용 예시
public class GameManager : MonoBehaviour
{
private QuadTree quadTree;
public GameObject[] enemies;
public Rect playerFov;
void Start()
{
// 쿼드 트리 생성 (예: 맵 크기 100x100)
quadTree = new QuadTree(new Rect(0, 0, 100, 100));
// 적들 추가
foreach (var enemy in enemies)
{
quadTree.Insert(enemy);
}
}
void Update()
{
// 플레이어의 시야 범위 내 적들 찾기
var enemiesInFov = quadTree.Retrieve(playerFov);
foreach (var enemy in enemiesInFov)
{
Debug.Log("시야 내 적: " + enemy.name);
}
}
}1) 충돌 감지 최적화
여러 개의 객체가 화면에 있을 때, 모든 객체를 일일이 비교하여 충돌을 검사하는 것은 성능에 부담이 될 수 있습니다.
쿼드 트리를 사용하면, 화면을 여러 영역으로 나누어 충돌을 검사할 객체들을 한정할 수 있어 성능을 개선할 수 있습니다.
(비슷한 알고리즘으로는 closest pair of points-최근접쌍, 알고리즘이 있습니다.)
2) FOV(시야 범위) 계산
예를 들어, 플레이어의 시야 범위 내에 있는 적들을 찾고 싶을 때,
쿼드 트리를 활용하여 시야 범위 내의 객체만 효율적으로 찾아낼 수 있습니다.
플레이어가 이동할 때마다 시야 범위 내에 있는 적들을 찾을 수 있습니다.
=> 사실 유니티에는 콜라이더, 리지드 바디 등을 통해서 쉽게 구현이 가능하긴 합니다 :)
