게임을 만들다 보면 플레이어 주변에서 가장 가까운 객체를 찾아야 하는 경우가 많다.
예를 들어 플레이어가 상호작용할 수 있는 NPC나 아이템을 찾는다고 해보자.
가장 단순하게 구현하면 모든 객체의 거리를 확인하고 가장 가까운 객체를 선택하면 된다.
Entity* nearest = nullptr;
float minDistance = FLT_MAX;
for (Entity* entity : entities)
{
float distance = Distance(player.position, entity.position);
if (distance < minDistance)
{
minDistance = distance;
nearest = entity;
}
}
객체가 N개라면 모든 객체를 한 번씩 확인해야 하기 때문에 시간 복잡도는 O(N)이다.
객체가 100개 정도라면 크게 문제가 되지 않는다.
문제는 객체가 많아졌을 때다.
플레이어
↓
100,000개의 Entity
↓
모든 Entity와 Distance 비교
↓
가장 가까운 Entity 선택
이 과정을 매 프레임 반복한다면 불필요한 연산이 상당히 커질 수 있다.
먼저 거리 계산 자체를 줄일 수 있다
두 위치의 거리를 비교할 때 실제 거리가 필요한 것이 아니라 어느 쪽이 더 가까운지만 판단하는 경우가 많다.
이때 제곱근을 계산하는 Distance 대신 제곱 거리인 sqrMagnitude를 사용할 수 있다.
두 점의 거리는 다음과 같이 계산된다.
distance = √(x² + y² + z²)
하지만 두 거리의 대소만 비교한다면 제곱근은 필요하지 않다.
distanceA < distanceB
↓
distanceA² < distanceB²
따라서 Unity에서는 다음과 같이 작성할 수 있다.
Vector3 offset = entity.position - player.position;
float sqrDistance = offset.sqrMagnitude;
그리고 가장 가까운 객체를 찾는다.
Entity nearest = null;
float minSqrDistance = float.MaxValue;
foreach (Entity entity in entities)
{
Vector3 offset = entity.position - player.position;
float sqrDistance = offset.sqrMagnitude;
if (sqrDistance < minSqrDistance)
{
minSqrDistance = sqrDistance;
nearest = entity;
}
}
이렇게 하면 제곱근 연산을 피할 수 있다.
다만 이것만으로 시간 복잡도가 줄어드는 것은 아니다.
N개 객체
→ N번 비교
O(N)
객체가 정말 많다면 가장 중요한 것은 거리 계산을 빠르게 만드는 것이 아니라 비교해야 할 객체 자체를 줄이는 것이다.
주변 객체만 후보로 가져온다
플레이어와 상호작용할 수 있는 객체가 플레이어로부터 5m 이내에만 존재한다고 해보자.
그렇다면 굳이 월드 전체의 객체를 확인할 필요가 없다.
전체 Entity
↓
상호작용 범위
↓
주변 Entity
↓
Distance 비교
↓
가장 가까운 Entity
예를 들어 Unity에서는 물리 시스템을 이용해 특정 범위 안의 Collider를 가져올 수 있다.
Collider[] colliders =
Physics.OverlapSphere(
player.position,
interactionRadius,
interactionLayer
);
이제 가져온 객체만 검사한다.
전체 Entity = 100,000개
상호작용 범위
→ 30개
30개만 Distance 비교
이렇게 하면 실제 거리 비교 대상이 크게 줄어든다.
그런데 주변 객체를 찾는 것 자체가 문제다
여기서 한 가지 문제가 생긴다.
다음과 같이 모든 Entity를 순회하면서 주변 객체를 찾는다면 결국 처음과 같다.
foreach (Entity entity in allEntities)
{
if (Distance(player.position, entity.position) < radius)
{
candidates.Add(entity);
}
}
전체 Entity가 100,000개라면 주변에 있는 객체가 30개뿐이어도 100,000개를 전부 검사해야 한다.
따라서 객체가 매우 많다면 주변 객체를 빠르게 찾을 수 있는 구조가 필요하다.
Spatial Partitioning
대표적인 방법이 Spatial Partitioning이다.
월드를 일정한 공간으로 나누고 각 공간에 어떤 객체가 존재하는지 관리한다.
가장 단순한 방법이 Grid다.
┌─────┬─────┬─────┐
│ │ │ │
├─────┼─────┼─────┤
│ │ P │ │
├─────┼─────┼─────┤
│ │ │ │
└─────┴─────┴─────┘
플레이어가 가운데 Grid에 있다면 월드 전체의 Entity를 검색하지 않고 현재 Grid와 주변 Grid만 확인한다.
전체 Entity
↓
현재 위치의 Grid 확인
↓
주변 Grid 조회
↓
후보 Entity 획득
↓
Distance 비교
↓
가장 가까운 Entity
예를 들어 전체 Entity가 100,000개라도 주변 Grid에 50개만 존재한다면 실제 비교 대상은 50개가 된다.
이때 중요한 것은 거리 계산을 최적화하는 것보다 후보군을 줄이는 것이다.
Spatial Hash
Grid를 조금 더 효율적으로 관리하려면 Spatial Hash를 사용할 수도 있다.
월드 좌표를 Grid 좌표로 변환하고 해당 좌표를 Key로 사용한다.
World Position
↓
Grid Coordinate
↓
Hash
↓
해당 공간의 Entity 목록
예를 들어:
Hash(10, 20)
→ NPC A
→ NPC B
→ Item C
Hash(10, 21)
→ NPC D
→ Item E
플레이어가 (10, 20) 근처에 있다면 관련된 Hash 영역만 조회하면 된다.
이 방식은 특히 많은 객체가 존재하고 위치가 계속 변하는 게임에서 유용하다.
항상 복잡한 공간 분할이 필요한 것은 아니다
객체가 수백 개 정도라면 단순한 순회만으로도 충분할 수 있다.
객체가 적음
→ 전체 순회
→ Distance 비교
객체가 많아지고 검색 빈도가 높아진다면:
객체가 많음
→ Spatial Partitioning
→ 주변 후보 검색
→ Distance 비교
로 발전시키면 된다.
즉 처음부터 KD-Tree나 Octree 같은 복잡한 구조를 넣을 필요는 없다.
현재 데이터 규모와 검색 빈도에 맞춰 필요한 만큼 최적화하는 것이 중요하다.
결국 핵심은 후보군을 줄이는 것이다
가장 가까운 객체를 찾는 문제에서 단순한 구현은 다음과 같다.
전체 Entity
→ 모든 Entity와 Distance 비교
→ 가장 가까운 Entity
객체가 많아지면 다음과 같이 바꿀 수 있다.
전체 Entity
→ Spatial Partitioning
→ 주변 Entity
→ sqrDistance 비교
→ 가장 가까운 Entity
여기서 각각의 최적화가 담당하는 역할이 다르다.
Spatial Partitioning
→ 비교할 Entity의 수를 줄임
sqrMagnitude
→ 각 Distance 계산 비용을 줄임
결국 N개의 객체를 모두 빠르게 검사하는 것보다, 애초에 검사할 필요가 없는 객체를 후보에서 제거하는 것이 더 큰 최적화가 된다.
게임에서 플레이어 주변의 가장 가까운 객체를 찾는 기능이라면 보통 이 구조부터 생각하면 된다.
Player
→ Interaction Range
→ 주변 후보 검색
→ Distance 비교
→ Nearest Entity
객체 수가 더 커지고 검색 빈도까지 높아진다면 그때 Spatial Hash, Grid, KD-Tree, Octree 등의 공간 자료구조를 선택하면 된다.