---
title: "1만 마리 이웃 탐색을 6.26ms 로, 그리고 기울기가 0 이 된다는 것"
description: "셀 크기를 질의 반경에 맞추면 엔티티당 검사 수가 상수가 됩니다. 19.60ms 가 6.26ms 가 됐는데, 진짜 결과는 그 배수가 아닙니다."
author: "유니얼"
pubDate: 2026-09-09
updatedDate: 2026-09-10
category: "game-dev/unity/dots"
tags: ["Unity", "DOTS", "최적화", "프로파일링"]
canonical: https://blog.unialgames.com/posts/dots-spatial-hash/
---
<x-repo>
<script type="application/json">
{
  "repo": "SeoBYP/ecs-warriors",
  "text": "적 1만 마리를 돌리는 3D 무쌍 액션. 이 글의 코드와 숫자가 전부 여기서 나옵니다.",
  "chips": ["Unity 6000.5.4f1", "Entities 6.5.0", "Burst 1.8.29", "Collections 6.5.0"],
  "links": [
    { "text": "week2-separation.csv (측정 원본)", "path": "docs/benchmarks/week2-separation.csv" },
    { "text": "Week2 진행 기록", "path": "docs/Week2-이동-SpatialHash.md" }
  ],
  "note": "측정 조건: 같은 씬, 회피 반경 1.0, 세기 5. 워밍업 240프레임 뒤 120프레임 평균. 비포커스 프레임 제외."
}
</script>
</x-repo>

1만 마리가 플레이어로 걸어오면 한 점에 뭉쳐 덩어리가 됩니다.
서로 밀어내게 해야 하는데, 그러려면 각자 **자기 근처에 누가 있는지**를 알아야 합니다.

전수 검사면 1만 × 1만 = **1억 번** 입니다. 매 프레임.

공간을 격자로 나눠 두고 자기 칸과 이웃 칸만 보면 된다는 발상 자체는
[전부 검사하지 않으려면 미리 나눠 둔다](/posts/unity-spatial-partition/) 에서 다뤘습니다.
여기서는 그걸 실제로 짜면서 걸린 것들을 씁니다.

## 셀 크기가 곧 계약이다

가장 먼저 정할 것은 셀 크기이고, 이건 취향이 아니라 **회피 반경과 같아야 합니다.**

셀 크기를 반경과 같게 두면 "반경 안의 이웃은 반드시 자기 셀 아니면 인접 8칸 안에 있다" 가
**보장** 됩니다. 그러면 3×3 만 보고 나머지는 아예 안 봐도 됩니다.

셀이 반경보다 작으면 더 넓게 봐야 하고, 크면 한 셀에 너무 많이 들어가서
셀을 나눈 의미가 줄어듭니다.

```csharp
public static class SpatialHash
{
    public const float CellSize = 1f;              // 회피 반경과 같게

    public static int2 ToCell(float3 p) =>
        new int2((int)math.floor(p.x / CellSize), (int)math.floor(p.z / CellSize));

    public static int Key(int2 c) =>
        (c.x * 73856093) ^ (c.y * 19349663);       // 공간 해시 상수
}
```

## 매 프레임 다시 만든다

적이 계속 움직이니 격자도 매 프레임 다시 채웁니다.
`NativeParallelMultiHashMap` 을 `Persistent` 로 한 번 잡아 두고, 프레임마다 비우고 채웁니다.

```csharp
_map.Clear();
new BuildJob { Writer = _map.AsParallelWriter() }.ScheduleParallel();
```

`AsParallelWriter()` 가 있어야 워커 여럿이 동시에 넣을 수 있습니다.
그냥 넘기면 잡 안전성 검사가 거부합니다.

`Persistent` 로 잡았으면 `OnDestroy` 에서 `Dispose()` 는 필수입니다.
안 하면 플레이 모드를 껐다 켤 때마다 누수 경고가 쌓입니다.

조회 쪽은 자기 셀과 인접 8칸을 돌면서 `TryGetFirstValue` / `TryGetNextValue` 로 훑습니다.

## 조용히 실패한 것들

### 해시가 두 개였다

빌드하는 시스템은 `CellKey` 라는 메서드를 쓰고 있었고,
조회하는 잡은 `x + y * 1000` 을 쓰고 있었습니다.

**같은 셀에 대해 다른 키가 나옵니다.** 그러면 넣은 자리와 찾는 자리가 달라서
이웃을 하나도 못 찾습니다.

그런데 **에러가 하나도 안 납니다.** 맵은 정상이고, 조회도 정상이고,
그냥 결과가 항상 비어 있습니다. 화면에서는 회피가 안 되는 것으로만 보입니다.

그래서 해시를 `SpatialHash` 정적 클래스 하나로 몰았습니다.
**빌드와 조회가 같은 함수를 쓰게 강제하는 것**이 이 버그를 구조적으로 막는 유일한 방법입니다.

> `x + y * 1000` 도 지금은 우연히 맞습니다. 월드 반경이 100이라 셀 좌표가 작아서요.
> 월드가 커지면 `(0, 1)` 과 `(1000, 0)` 이 같은 키가 됩니다.
> **지금 안 터지는 것과 맞는 것은 다릅니다.**

### 잡을 만들고 스케줄을 안 했다

회피 잡을 다 짜 놓고 `OnUpdate` 에서 스케줄하는 줄을 안 썼습니다.
컴파일 초록불이고, 화면에서는 그냥 회피가 안 됩니다.

앞의 해시 불일치와 **증상이 똑같습니다.** 원인이 전혀 다른데 화면이 같습니다.
그래서 "회피가 안 된다" 를 보고 원인을 추측하는 게 무의미했습니다.

### 자기 자신을 이웃으로 셌다

맵에는 자기도 들어 있습니다. 그래서 조회하면 거리 0인 자기가 나옵니다.

```csharp
var diff = myPos - neighborPos;
var d = math.length(diff);
if (d > 0.0001f)                    // 이 가드가 없으면
    push += diff / d;               // 0으로 나눠서 NaN
```

**NaN 이 `Position` 에 한 번 들어가면 그 엔티티는 렌더에서 사라지고 영구히 안 돌아옵니다.**
어떤 연산을 해도 NaN 이라서요. 그리고 에러는 안 납니다.

이 가드는 나중에 넉백에서 한 번 더 필요해집니다. 같은 실수를 두 번 할 자리가 있었습니다.

## 의존성은 자동으로 이어진다

맵을 소유한 시스템이 빌드 잡을 먼저 스케줄하고 회피 잡을 이어서 스케줄합니다.
`state.Dependency` 가 자동으로 체인을 걸어 주므로 순서는 보장됩니다.

**단 싱글톤에 담아 다른 시스템으로 넘긴 raw 네이티브 컨테이너는 이 추적을 우회합니다.**
이건 나중에 공격 판정 시스템에서 잡 안전성 예외 2,531개로 터집니다.
여기서는 한 시스템 안에 있어서 문제가 없었습니다.

## 검증

숫자로 확인할 수 있는 것을 하나 잡아 뒀습니다. **점유 셀 개수** 입니다.

적 1만 마리를 넣고 셌더니 **8,310개 셀** 이 채워졌습니다.
셀당 평균 1.2마리입니다.

이 숫자가 말해 주는 게 둘입니다.

- 해시가 **잘 분산되고 있습니다.** 몰려 있으면 점유 셀이 훨씬 적게 나옵니다
- 셀당 1.2마리면 3×3 조회에서 **평균 10마리쯤** 검사한다는 뜻입니다.
  1만 마리를 다 보는 것 대신 열 마리를 봅니다

그리고 화면이 바뀌었습니다. 한 점에 뭉쳐 있던 덩어리가 **균일한 원반 군집**이 됐습니다.

## 그래서 얼마나 빨라졌나

이웃을 찾는 방법만 바꿔서 쟀습니다. 나머지 조건은 전부 같습니다.

<x-calc>
<script type="application/json">
{
  "label": "적 수를 바꿔 보기",
  "inputs": [
    { "id": "i", "label": "적 수", "options": [["1,000", 0], ["2,500", 1], ["5,000", 2], ["10,000", 3]], "default": 3 }
  ],
  "bars": [
    { "label": "전수 검사", "expr": "[6.35,7.60,9.25,19.60][i]", "unit": "ms" },
    { "label": "공간 해시", "expr": "[6.51,6.14,6.21,6.26][i]", "unit": "ms", "accent": true }
  ],
  "verdict": { "expr": "[6.51,6.14,6.21,6.26][i] < [6.35,7.60,9.25,19.60][i]", "yes": "공간 해시가 이득", "no": "공간 해시가 손해" },
  "note": "실측값입니다. 1,000 에서 한 번 밀어 보세요."
}
</script>
</x-calc>

| 적 수 | 전수 검사 | 공간 해시 | 개선 |
| --- | --- | --- | --- |
| 1,000 | 6.35 ms (157 fps) | 6.51 ms (154 fps) | **0.98배** |
| 2,500 | 7.60 (132 fps) | 6.14 (163 fps) | 1.24배 |
| 5,000 | 9.25 (108 fps) | 6.21 (161 fps) | 1.49배 |
| **10,000** | **19.60 (51 fps)** | **6.26 (160 fps)** | **3.13배** |

## 3.13배는 이 표에서 제일 안 중요한 숫자다

3.13배는 **1만 마리일 때의 값** 입니다. 2만 마리면 다른 숫자가 나옵니다.
조건이 바뀌면 같이 바뀌는 숫자를 결과라고 부르기는 어렵습니다.

봐야 할 것은 오른쪽 열이 아니라 **세로로 읽은 모양** 입니다.

**공간 해시 쪽은 완전히 평평합니다.** 6.1에서 6.5 사이입니다.
적이 1천이든 1만이든 프레임타임이 그대로입니다.

이 6.2ms 는 렌더와 이동과 에디터 오버헤드를 합친 **고정 비용** 이고,
이웃 탐색이 거기에 얹은 몫은 사실상 **0에 수렴** 합니다.

**왜 그런지는 앞에서 정한 계약에서 그대로 나옵니다.**
셀 크기를 회피 반경과 같게 뒀으니 밀도가 일정하면 엔티티당 검사 수가 상수입니다.
`O(n · k)` 에서 k 가 안 변합니다.

**전수 검사 쪽은 5,000을 넘기며 무너집니다.**
6.35 → 7.60 → 9.25 → 19.60. 고정비용 6.2를 빼면
0.15 → 1.4 → 3.05 → **13.4** 입니다. 5,000에서 10,000으로 두 배 될 때 **약 4.4배** 입니다.
n² 그대로입니다.

## 꼬리가 더 극적이다

평균만 보면 실제 체감을 놓칩니다. p95 를 보면 이렇습니다.

| 적 수 | 전수 검사 p95 | 공간 해시 p95 |
| --- | --- | --- |
| 10,000 | **28.94 ms** | **7.03 ms** |

평균이 19.60인데 상위 5퍼센트가 28.94입니다. **프레임이 튄다**는 뜻입니다.
공간 해시 쪽은 평균 6.26에 p95 가 7.03이라 거의 붙어 있습니다.

평균 3배 차이보다 이쪽이 플레이 감각에서 더 큽니다.
**일정하게 느린 것과 가끔 튀는 것은 다른 문제** 입니다.

## 예상이 틀린 것 둘

### "O(n²) 면 프레임 폭사" 는 틀렸다

작업 전 예상은 "1억 번이면 프레임이 죽는다" 였습니다.
**전수 검사도 51fps 로 돌았습니다.**

전수 검사 버전도 Burst 로 컴파일되고, SIMD 를 쓰고, 워커 스레드에 병렬로 뿌려집니다.
알고리즘만 다르고 나머지 조건은 전부 같습니다.

그러니 이 비교는 "느린 O(n²) 대 빠른 알고리즘" 이 아닙니다.
**"Burst 로 최적화된 O(n²) 대 Burst + 알고리즘"** 입니다.

읽는 방향이 두 가지입니다.
**Burst 만으로도 1억 연산이 51fps 를 냅니다.** 이것도 놀라운 숫자입니다.
그리고 그 위에 알고리즘을 얹으면 3.13배가 더 나오고, 무엇보다 기울기가 0이 됩니다.

### 1,000 마리에서는 공간 해시가 진다

6.51 대 6.35. **그리드 쪽이 느립니다.**

해시맵을 매 프레임 비우고 다시 채우는 고정 오버헤드가 있는데,
1,000 마리에서는 그 비용이 절약한 것보다 큽니다.
이 프로젝트에서 손익분기점은 **대략 2,000 마리 근처** 입니다.

> **최적화는 공짜가 아닙니다.**
> "무조건 좋은 최적화" 는 없고, 자료구조를 하나 얹는 것은 고정 비용을 하나 사는 일입니다.

적이 항상 500마리인 게임이었다면 이 작업은 **손해였습니다.**
그리고 그건 재 보기 전에는 알 수 없었습니다.

## 여기서 얻은 기준

**배수가 아니라 기울기를 본다.**

배수는 잰 지점에서만 유효한 값이고, 기울기는 "n 이 늘면 어떻게 되는가" 라는
구조에 대한 답입니다. 그리고 게임이 나중에 어디까지 갈지 모르니
구조 쪽이 더 오래 쓸모 있습니다.