---
title: "좌표를 칸으로, 칸을 배열로"
description: "균일 격자를 실제로 만들 때 막히는 자리들입니다. 음수 좌표에서 칸 번호가 어긋나는 이유, 맵 밖을 다루는 공간 해시(spatial hash), 같은 쌍을 두 번 보지 않는 법, 칸마다 리스트를 두지 않고 배열 세 개로 짓는 법."
author: "유니얼"
pubDate: 2026-09-18
category: "programming/algorithm/spatial"
tags: ["최적화", "격자", "자료구조"]
canonical: https://blog.unialgames.com/posts/algo-uniform-grid/
---
공간을 칸으로 나눠 두면 가까운 것만 본다는 발상은 한 줄로 끝납니다.
그런데 막상 만들어 보면 **계산이 아니라 구현에서** 막힙니다.
- 맵 가운데를 원점으로 잡았더니 **원점 근처에서만 판정이 이상합니다**
- 맵이 얼마나 커질지 몰라서 **배열 크기를 정할 수가 없습니다**
- 두 물체가 부딪혔다는 신호가 **두 번씩 옵니다**
셋 다 같은 자리에서 나옵니다. 좌표를 칸으로 바꾸고, 칸을 자료구조에 앉히는 자리입니다.
## 좌표를 칸 번호로 바꾸는 한 줄
칸 번호는 좌표를 칸 크기로 나누면 나옵니다. 이렇게 쓰고 싶어집니다.
```csharp
int cx = (int)(x / cellSize); // 여기서 갈립니다
```
`(int)` 캐스팅은 **0 쪽으로 자릅니다.** 양수에서는 내림과 같지만 음수에서는 올림이 됩니다.
칸 크기가 1일 때 무슨 일이 생기는지 보면 이렇습니다.
| `x` | `(int)(x / 1)` | `FloorToInt(x / 1)` |
| --- | --- | --- |
| 1.5 | 1 | 1 |
| 0.5 | 0 | 0 |
| -0.5 | **0** | -1 |
| -1.5 | **-1** | -2 |
**-0.5 와 0.5 가 같은 칸이 됩니다.** 원점을 낀 두 칸이 하나로 붙어서 그 자리만 칸이 두 배로 넓어집니다.
맵 구석을 원점으로 잡으면 음수 좌표가 없으니 안 터지고, 가운데를 원점으로 잡는 순간 터집니다.
**"왜 맵 가운데서만 이상하지" 가 여기서 나옵니다.**
```csharp
int cx = Mathf.FloorToInt(x / cellSize);
```
칸 크기를 2의 거듭제곱으로 잡을 수 있다면 나눗셈 대신 시프트를 씁니다.
```csharp
int cx = (int)x >> shift; // cellSize == 1 << shift
```
**산술 시프트는 음수에서도 내림입니다.** 빠른 길인데 마침 안전한 길이기도 합니다.
다만 `(int)x` 캐스팅이 앞서 있으니, 좌표가 실수라면 그 캐스팅에서 같은 문제가 되돌아옵니다.
시프트를 쓸 거면 **좌표를 먼저 정수로 만드는 자리**를 확인하세요.
## 맵 밖을 다루려면 배열을 버린다
칸 번호가 나왔으면 그 칸의 목록을 찾아야 합니다. 가장 쉬운 방법은 2차원 배열입니다.
그런데 배열은 **맵 크기를 미리 알아야** 만들 수 있습니다.
| 맵 | 칸 크기 2 | 칸 수 |
| --- | --- | --- |
| 100×100 | 50×50 | 2,500 |
| 1,000×1,000 | 500×500 | 250,000 |
| 10,000×10,000 | 5,000×5,000 | **2,500만** |
오픈월드나 절차적으로 늘어나는 맵에서는 아예 못 정합니다.
물체가 1,000개뿐인데 칸 2,500만 개를 들고 있는 것도 말이 안 됩니다.
그래서 **칸 번호를 해시해서 정해진 개수의 버킷에 넣습니다.** 공간 해시(spatial hash)입니다.
```csharp
int Hash(int cx, int cy)
=> ((cx * 73856093) ^ (cy * 19349663)) & (bucketCount - 1);
```
두 큰 소수를 곱해 XOR 하는 이 조합은 공간 해시에서 흔히 쓰는 것입니다.
버킷 수를 2의 거듭제곱으로 잡으면 나머지 연산 대신 `&` 로 끝납니다.
**여기서 해시 충돌은 걱정거리가 아닙니다.** 일반적인 해시 테이블과 다른 점입니다.
멀리 떨어진 두 칸이 같은 버킷에 들어와도, 어차피 꺼낸 다음에 **거리를 재서 거릅니다.**
후보가 조금 늘어날 뿐 답이 틀리지는 않습니다. 그래서 충돌 처리를 따로 안 해도 됩니다.
버킷 수만 물체 수와 비슷하게 잡아 두면 됩니다.
반대로 **칸 번호를 버킷에 같이 저장해 두지 않으면** 안 됩니다.
꺼낸 것이 정말 그 칸의 물체인지 확인할 방법이 없어집니다.
거리로 거르니 결과는 맞지만, 엉뚱한 칸의 물체까지 매번 거리 계산을 하게 됩니다.
## 같은 쌍을 두 번 보지 않기
자기 칸과 이웃 여덟 칸을 보면 A 와 B 의 쌍을 **두 번** 봅니다.
A 에서 B 를 한 번, B 에서 A 를 한 번입니다. 충돌 신호가 두 번 오는 이유가 이것입니다.
이웃을 절반만 보면 같은 쌍을 두 번 세지 않는다. 빠뜨리는 쌍은 없다.
이웃을 **절반만** 보면 됩니다. 자기 칸 안에서는 `j > i` 인 쌍만 보고,
이웃은 오른쪽·왼쪽아래·아래·오른쪽아래 넷만 봅니다.
```csharp
static readonly (int dx, int dy)[] Half = { (1, 0), (-1, 1), (0, 1), (1, 1) };
for (int i = 0; i < ids.Count; i++) {
for (int j = i + 1; j < ids.Count; j++) // 같은 칸
Test(ids[i], ids[j]);
foreach (var (dx, dy) in Half) // 이웃 절반
foreach (var other in CellAt(cx + dx, cy + dy))
Test(ids[i], other);
}
```
빠뜨리는 쌍은 없습니다. 위쪽 네 칸과의 쌍은 **그 칸이 자기 차례일 때** 봅니다.
1,000개를 뿌려 재 보면 검사 횟수가 3,554번에서 1,777번으로 정확히 절반이 됩니다.
## 칸이 반경보다 작으면 겹을 늘려야 한다
이웃 한 겹, 즉 아홉 칸을 보는 것은 **칸 크기가 검사 반경보다 클 때만** 맞습니다.
칸이 반경보다 작으면 한 겹으로는 반경을 못 덮어서 **가까운 쌍을 놓칩니다.**
봐야 하는 겹 수는 이렇게 정해집니다.
```
겹 수 k = ceil(검사 반경 / 칸 크기)
보는 칸 = (2k + 1)²
```
칸을 잘게 쪼개면 거리 검사는 줄지만 **훑어야 하는 칸이 제곱으로 늘어납니다.**
100×100 맵에 물체 1,000개를 뿌리고 검사 반경을 2로 두고 재 봤습니다.
찾아낸 가까운 쌍은 646개로 전부 같고, 드는 일만 다릅니다.
| 칸 크기 | 겹 수 | 보는 칸 | 칸 훑기 | 거리 검사 | 합 |
| --- | --- | --- | --- | --- | --- |
| 0.5 | 4 | 81 | 39,560 | 1,016 | 40,576 |
| 1.0 | 2 | 25 | 11,316 | 1,250 | 12,566 |
| **2.0** | **1** | **9** | **3,184** | **1,777** | **4,961** |
| 4.0 | 1 | 9 | 1,940 | 6,821 | 8,761 |
| 8.0 | 1 | 9 | 672 | 25,514 | 26,186 |
| 25.0 | 1 | 9 | 64 | 201,004 | 201,068 |
**칸 크기를 검사 반경에 맞춘 자리가 바닥입니다.** 양쪽으로 멀어지면 여덟 배, 마흔 배씩 불어납니다.
왼쪽 절반은 칸을 도느라 비싸지고 오른쪽 절반은 거리를 재느라 비싸집니다.
참고로 전부 대 전부로 비교하면 499,500번입니다. 바닥값의 **백 배**입니다.
## 칸마다 리스트를 두지 않는다
남은 것은 그릇입니다. 칸마다 리스트를 하나씩 두는 것이 가장 먼저 떠오릅니다.
```csharp
List[] cells; // 이렇게 하고 싶어지지만
```
이러면 칸 수만큼 리스트를 할당하고, 매 프레임 전부 `Clear()` 하고,
칸을 훑을 때마다 **다른 곳에 흩어진 메모리를 따라갑니다.**
칸이 수천 개면 그 자체가 부담이고, 리스트가 늘어날 때마다 새 배열을 잡습니다.
배열 세 개면 같은 일을 할 수 있습니다. **세고, 더하고, 담습니다.**
```csharp
// 1. 칸마다 몇 개인지 센다
Array.Clear(count, 0, count.Length);
for (int i = 0; i < n; i++) count[CellOf(pos[i])]++;
// 2. 앞에서부터 더해서 각 칸이 쓸 자리의 시작을 정한다
int sum = 0;
for (int c = 0; c < cellCount; c++) {
start[c] = sum;
sum += count[c];
}
start[cellCount] = sum;
// 3. 시작 자리부터 차례로 담는다
Array.Copy(start, cursor, cellCount);
for (int i = 0; i < n; i++) items[cursor[CellOf(pos[i])]++] = i;
```
이제 **한 칸의 물체는 배열에서 붙어 있습니다.**
```csharp
for (int k = start[c]; k < start[c + 1]; k++) {
int id = items[k];
// ...
}
```
얻는 것이 여럿입니다.
- **할당이 없습니다.** 배열 세 개를 한 번 잡아 두고 매 프레임 덮어씁니다. GC 가 볼 것이 없습니다
- **순서대로 읽습니다.** 한 칸의 물체가 붙어 있으니 캐시가 잘 맞습니다
- **잡 시스템에 올릴 수 있습니다.** 리스트가 없으니 네이티브 배열로 그대로 옮겨집니다
- **매 프레임 통째로 다시 지어도 쌉니다.** 물체가 칸을 옮겼는지 따질 필요가 없습니다
값도 있습니다. 비용이 **물체 수에 칸 수를 더한 만큼**입니다.
누적합은 물체가 몇 개든 칸 수만큼 돕니다. 칸이 물체보다 훨씬 많으면 그 부분이 커집니다.
**공간 해시로 버킷 수를 물체 수에 맞춰 두는 것**이 여기서도 값을 합니다.
## 정리
균일 격자는 발상이 아니라 **경계에서 막힙니다.**
- 칸 번호는 **내림**으로 구합니다. `(int)` 캐스팅은 음수에서 0 쪽으로 잘려서 원점 근처 두 칸을 붙여 놓습니다
- 맵 크기를 못 정하면 배열 대신 **해시로 버킷에 넣습니다.** 거리로 거르니 **해시 충돌은 답을 안 깨뜨립니다**
- 이웃은 **절반만** 봅니다. 나머지 절반은 상대 칸이 자기 차례에 봅니다. 검사가 정확히 절반이 됩니다
- 봐야 하는 겹 수는 `ceil(반경 / 칸 크기)` 입니다. **칸을 반경에 맞춘 자리가 바닥**이고 양쪽으로 멀어지면 급하게 비싸집니다
- 그릇은 리스트 배열 대신 **세고, 더하고, 담는** 배열 세 개로 만듭니다. 할당이 없고 한 칸이 메모리에서 붙어 있습니다