---
title: "전부 검사하지 않으려면 미리 나눠 둔다"
description: "적 500마리가 서로 부딪혔는지 보려면 12만 번을 비교해야 합니다. 공간을 칸으로 나눠 두면 같은 칸과 이웃 칸만 보면 됩니다."
author: "유니얼"
pubDate: 2026-09-09
updatedDate: 2026-09-18
category: "game-dev/design-patterns"
tags: ["Unity", "최적화", "격자"]
canonical: https://blog.unialgames.com/posts/unity-spatial-partition/
---
플레이어 주변 5미터 안의 적을 찾습니다.
```csharp
foreach (var e in allEnemies)
{
if (Vector3.Distance(player.position, e.position) < 5f)
nearby.Add(e);
}
```
적이 500마리면 500번 잽니다. 이건 견딜 만합니다.
그런데 **적끼리 서로 부딪혔는지** 보려면 이야기가 달라집니다.
```csharp
for (int i = 0; i < enemies.Count; i++)
for (int j = i + 1; j < enemies.Count; j++)
Check(enemies[i], enemies[j]);
```
500마리면 **124,750번**입니다. 그리고 이게 매 프레임입니다.
## 늘어나는 것은 개수가 아니라 짝
**오브젝트 수를 두 배로 늘리면 비교는 네 배가 됩니다.**
100마리에서 잘 돌던 것이 1000마리에서 갑자기 멈추는 이유입니다.
그런데 저 12만 번 중 대부분은 **볼 필요도 없는 짝**입니다.
맵 왼쪽 끝의 적과 오른쪽 끝의 적이 부딪혔는지는 거리를 재 보지 않아도 압니다.
## 공간을 칸으로 나눈다
미리 격자를 깔아 두고 **각 오브젝트가 어느 칸에 있는지 기록해 둡니다.**
```csharp
public class SpatialGrid
{
readonly Dictionary> cells = new();
readonly float cellSize;
public SpatialGrid(float cellSize) => this.cellSize = cellSize;
Vector2Int CellOf(Vector3 p)
=> new(Mathf.FloorToInt(p.x / cellSize), Mathf.FloorToInt(p.z / cellSize));
public void Add(Enemy e)
{
var c = CellOf(e.transform.position);
if (!cells.TryGetValue(c, out var list))
cells[c] = list = new List();
list.Add(e);
}
}
```
좌표를 칸 번호로 바꾸는 것은 **나눗셈 한 번**입니다.
어디에 있는지 찾으려고 목록을 뒤질 필요가 없습니다.
이제 주변을 찾을 때 **자기 칸과 이웃한 여덟 칸만** 봅니다.
```csharp
public void QueryNearby(Vector3 pos, List result)
{
var center = CellOf(pos);
for (int dx = -1; dx <= 1; dx++)
for (int dy = -1; dy <= 1; dy++)
{
var c = new Vector2Int(center.x + dx, center.y + dy);
if (cells.TryGetValue(c, out var list))
result.AddRange(list);
}
}
```
이웃 칸까지 보는 이유는 경계에 걸친 오브젝트를 놓치지 않기 위해서입니다.
이웃 여덟 칸을 같이 보는 이유가 있습니다.
**기준점이 칸의 가장자리에 있으면 바로 옆 칸에 있는 것이 더 가까울 수 있기 때문**입니다.
자기 칸만 보면 그걸 놓칩니다.
## 칸 크기가 전부입니다
이 방법의 성능은 사실상 칸 크기 하나로 정해집니다.
| 칸이 | 무슨 일이 | |
| --- | --- | --- |
| 너무 크면 | 한 칸에 다 들어간다 | 전부 검사와 같아진다 |
| 너무 작으면 | 빈 칸이 많아지고 이웃 칸 수가 늘어난다 | 칸을 도는 비용이 커진다 |
| 적당하면 | 한 칸에 몇 개씩 | 여기가 목표다 |
시작점은 **검사 반경 정도**로 잡습니다. 5미터 안을 찾을 거면 칸도 5미터로 둡니다.
그러면 이웃 아홉 칸이 검사 반경을 딱 덮습니다.
칸이 반경보다 작으면 아홉 칸으로는 모자라서 더 넓게 봐야 합니다.
반대로 칸이 반경보다 크면 필요 없는 것까지 잔뜩 딸려 옵니다.
## 움직이면 다시 넣어야 합니다
여기가 실제로 성가신 부분입니다. 적이 움직이면 **칸이 바뀝니다.**
매 프레임 전부 지우고 다시 넣으면 그 비용이 만만치 않습니다.
```csharp
public void Move(Enemy e, Vector3 newPos)
{
var oldCell = CellOf(e.LastPosition);
var newCell = CellOf(newPos);
if (oldCell == newCell) return; // 대부분은 여기서 끝난다
cells[oldCell].Remove(e);
Add(e);
}
```
**칸이 안 바뀌었으면 아무것도 안 합니다.** 프레임당 이동 거리가 칸 크기보다 훨씬 작으니
대부분의 오브젝트는 이 줄에서 빠져나갑니다. 앞의 더티 플래그와 같은 발상입니다.
그리고 **안 움직이는 것과 움직이는 것을 나누는 것**이 큽니다.
지형, 건물, 아이템은 한 번 넣고 다시 안 건드립니다.
## 직접 만들기 전에
유니티의 물리 시스템이 **이미 이 일을 하고 있습니다.**
```csharp
var hits = Physics.OverlapSphere(player.position, 5f, enemyLayer);
```
이 한 줄이 전부 검사하지 않습니다. 내부에 공간 자료구조가 있어서 근처만 봅니다.
콜라이더를 붙일 수 있는 대상이라면 **직접 격자를 만들기 전에 이쪽부터 봐야 합니다.**
레이어 마스크로 대상을 좁히면 더 줄어듭니다.
직접 만들 이유는 이런 경우입니다.
- 콜라이더를 붙이고 싶지 않은 것 (수천 개의 데이터 점, 소리, 관심 영역)
- 물리와 무관한 질의 (가장 가까운 아군, 사거리 안의 표적 목록)
- 물리 쿼리가 만드는 배열 할당이 부담일 때
## 다른 나누는 방법들
균일한 격자가 가장 단순하고, 대부분의 게임에서 이것으로 충분합니다.
오브젝트가 고르게 퍼져 있고 크기가 비슷하면 이보다 나은 것이 별로 없습니다.
그 조건이 깨지는 경우가 셋 있고, 각각 다른 방식이 답입니다.
| 무엇이 문제인가 | 어떻게 나누나 | 이름 |
| --- | --- | --- |
| **한쪽에 몰려 있다** | 붐비는 칸만 다시 넷으로 쪼갠다. 빈 칸은 안 쪼갠다 | 쿼드트리 (3D 는 옥트리) |
| **크기가 제각각이다** | 칸으로 나누지 않고 **오브젝트를 묶어** 감싸는 상자를 만든다 | BVH |
| **지형이 고정이고 벽이 많다** | 평면으로 공간을 잘라 미리 트리를 만들어 둔다 | BSP |
**쿼드트리**는 밀도에 적응합니다. 빈 칸이 대부분인데 한 칸에 300개가 들어 있는 상황에서,
그 한 칸만 넷으로 쪼개고 또 붐비면 또 쪼갭니다.
대신 오브젝트가 움직일 때마다 트리를 고쳐야 해서 **갱신 비용이 격자보다 큽니다.**
**BVH** 는 공간이 아니라 오브젝트를 기준으로 묶습니다.
커다란 보스와 작은 총알을 같은 격자에 넣으면 보스가 여러 칸에 걸치는데,
BVH 는 상자가 오브젝트를 감싸는 구조라 크기 차이가 문제가 안 됩니다.
레이캐스트나 절두체 컬링처럼 **길쭉한 질의**에도 격자보다 낫습니다.
**BSP** 는 갱신을 거의 안 하는 대신 미리 만드는 비용이 큽니다.
그래서 움직이는 것에는 안 쓰고 **정적 지형**에 씁니다.
| | 격자 | 쿼드트리 | BVH | BSP |
| --- | --- | --- | --- | --- |
| 만드는 비용 | 낮음 | 중간 | 중간 | **높음** |
| 갱신 비용 | **낮음** | 중간 | 중간 | 매우 높음 |
| 밀도가 치우쳐도 | 나쁨 | **좋음** | 좋음 | 좋음 |
| 크기가 제각각이어도 | 나쁨 | 나쁨 | **좋음** | 보통 |
| 움직이는 대상 | **좋음** | 보통 | 보통 | 안 맞음 |
고르는 기준은 **무엇이 얼마나 자주 바뀌느냐** 입니다.
매 프레임 전부 움직이면 갱신이 싼 격자가 이기고,
거의 안 움직이면 만드는 비용을 한 번 치르고 질의를 싸게 만드는 쪽이 이깁니다.
> **대부분의 프로젝트는 균일 격자에서 시작해도 됩니다.**
> 그것으로 안 될 때 프로파일러가 알려 줍니다.
> 그리고 안 되는 이유가 위의 셋 중 무엇인지를 보고 고르면 됩니다.
## 정리
- 전부 대 전부로 비교하면 개수의 제곱에 비례해 늘어난다. 두 배면 네 배다.
- 그 비교의 대부분은 볼 필요도 없는 짝이다. 멀리 떨어진 것끼리다.
- 공간을 칸으로 나눠 두면 좌표에서 칸 번호를 나눗셈 한 번으로 얻는다.
- 자기 칸과 이웃 여덟 칸만 본다. 이웃까지 보는 것은 경계에 걸친 것을 놓치지 않기 위해서다.
- 성능은 칸 크기가 정한다. 검사 반경 정도로 시작한다.
- 움직이면 다시 넣어야 한다. 칸이 안 바뀌었으면 아무것도 안 하는 것으로 대부분을 거른다.
- 안 움직이는 것과 움직이는 것을 나눈다.
- 유니티 물리가 이미 이 일을 한다. 직접 만들기 전에 `OverlapSphere` 부터 본다.
- 균일 격자로 시작한다. 몰려 있으면 쿼드트리, 크기가 제각각이면 BVH, 정적 지형이면 BSP 다.
- 고르는 기준은 무엇이 얼마나 자주 바뀌느냐다. 자주 움직이면 갱신이 싼 격자가 이긴다.