---
title: "빈 곳은 큰 칸 하나로 남긴다"
description: "밀도가 고르지 않으면 칸 크기를 하나로 정할 수 없습니다. 붐비는 칸만 넷으로 쪼개는 쿼드트리(quadtree)의 동작과, 격자보다 나은 자리와 나쁜 자리를 실측으로 갈라 봅니다."
author: "유니얼"
pubDate: 2026-09-18
category: "programming/algorithm/spatial"
tags: ["최적화", "격자", "자료구조"]
canonical: https://blog.unialgames.com/posts/algo-quadtree/
---
균일 격자는 칸 크기를 하나로 정해 놓고 씁니다. 그 값이 맵 전체에 그대로 적용됩니다.

밀도가 고르면 잘 맞습니다. 문제는 **한쪽에 몰려 있을 때**입니다.
광장에 적 300마리가 뭉쳐 있고 나머지 맵은 텅 비어 있다면, 칸 크기를 어디에 맞춰야 할까요.

- 광장에 맞춰 잘게 잡으면 **빈 벌판에도 칸이 수만 개** 생깁니다
- 벌판에 맞춰 크게 잡으면 **광장 한 칸에 300마리**가 들어갑니다. 전부 대 전부로 돌아갑니다

가운데로 타협해도 양쪽 다 나쁩니다. **하나의 값으로는 안 되는 상황**이 있습니다.

## 붐비는 칸만 쪼갠다

발상은 한 줄입니다. **칸 크기를 미리 정하지 말고, 넘칠 때 그 칸만 나눕니다.**

큰 칸 하나로 시작해서, 한 칸에 담긴 것이 정원을 넘으면 그 칸을 넷으로 나누고
안에 있던 것을 다시 나눠 담습니다. 넷 중 한쪽에 또 몰렸으면 그 칸을 또 나눕니다.
빈 곳은 아무도 건드리지 않아서 **큰 칸 그대로** 남습니다.

이것이 **쿼드트리(quadtree)** 입니다. 3차원에서 여덟으로 나누면 옥트리(octree)가 됩니다.


<x-quad>
<script type="application/json">
{
  "label": "붐비는 칸만 쪼개기",
  "size": 16,
  "capacity": 2,
  "maxDepth": 4,
  "points": [[2.5, 2.0], [13.0, 3.5], [3.2, 12.8], [6.0, 7.0], [2.0, 9.0], [11.6, 11.2], [11.9, 11.5], [11.7, 11.4], [12.0, 11.1], [11.8, 11.3]],
  "note": "한 칸에 두 개까지 담고 있다가 넘으면 그 칸만 넷으로 나눕니다"
}
</script>
</x-quad>

물체 열 개가 칸 열세 개에 담겼고, 빽빽한 구석은 네 단계까지 갈라졌습니다.
**같은 그림에 큰 칸과 작은 칸이 같이 있습니다.** 균일 격자가 못 하는 것이 이것입니다.

```csharp
void Insert(Node node, int id, Vector2 p, int depth) {
    if (node.Kids != null) {                    // 이미 나뉜 칸이면 내려간다
        Insert(node.Kids[ChildIndex(node, p)], id, p, depth + 1);
        return;
    }

    node.Items.Add(id);
    if (node.Items.Count <= Capacity || depth >= MaxDepth) return;

    Subdivide(node);                            // 넷으로 나누고
    var moved = node.Items;
    node.Items = Empty;
    foreach (int j in moved)                    // 안에 있던 것을 다시 담는다
        Insert(node, j, PositionOf(j), depth);
}
```

`ChildIndex` 는 가운데를 기준으로 어느 사분면인지만 보면 됩니다.

```csharp
int ChildIndex(Node n, Vector2 p) {
    float half = n.Size * 0.5f;
    int cx = p.x < n.X + half ? 0 : 1;
    int cy = p.y < n.Y + half ? 0 : 1;
    return cy * 2 + cx;
}
```

## 깊이 제한이 없으면 무한히 쪼갠다

거의 같은 자리에 물체 세 개가 겹쳐 있다고 해 보겠습니다.
정원이 둘이면 나눠도 셋이 같은 칸에 남고, 또 나눠도 그대로입니다.
칸 크기는 절반씩 줄어드는데 **셋은 영원히 안 갈라집니다.**

그래서 **깊이 제한**이 필요합니다. 제한에 닿으면 정원을 넘어도 그냥 담아 둡니다.
위 그림에서 마지막 물체가 들어갈 때가 그 경우입니다.

깊이 제한은 **가장 작은 칸의 크기**를 정하는 것과 같습니다.
한 변이 1,024인 맵에서 깊이 10이면 가장 작은 칸이 1입니다.
**물체 크기보다 작은 칸을 만들 이유는 없으니** 거기서 끊으면 됩니다.

## 경계에 걸친 것을 어디에 넣나

점이 아니라 **크기가 있는 물체**를 넣으면 곧바로 부딪히는 문제입니다.
상자가 네 자식에 걸쳐 있으면 어디에 넣어야 할까요. 셋 중 하나를 고릅니다.

| 방법 | 어떻게 | 값 |
| --- | --- | --- |
| 부모에 남긴다 | 자식 하나에 온전히 안 들어가면 그 자리에 둔다 | 큰 물체가 위쪽에 쌓여서 질의마다 딸려 온다 |
| 걸친 자식 전부에 넣는다 | 같은 물체가 여러 칸에 등록된다 | 같은 쌍이 여러 번 나와서 **중복을 걸러야 한다** |
| 칸을 느슨하게 만든다 | 칸의 실제 경계를 두 배로 넓혀 잡는다 | 물체가 언제나 한 칸에만 들어간다. 대신 이웃 칸을 더 본다 |

셋째가 **느슨한 쿼드트리(loose quadtree)** 입니다.
칸마다 담는 경계를 두 배로 잡아 두면, 자기 칸 크기의 절반보다 작은 물체는 언제나 한 칸에 온전히 들어갑니다.
중복 등록도 없고 부모에 쌓이지도 않습니다. 대신 칸끼리 겹치니 질의할 때 이웃을 더 봅니다.

**점만 넣는다면 이 고민이 통째로 없습니다.** 어느 쪽인지 먼저 정하고 시작하세요.

## 격자보다 나은 자리와 나쁜 자리

여기가 이 글에서 가장 중요한 부분입니다. **쿼드트리가 격자보다 언제나 나은 것이 아닙니다.**

1,000×1,000 맵에 물체 1,000개를 두고 두 구조를 같은 질의로 재 봤습니다.
먼저 **찾는 거리가 미리 정해진 질의**, 즉 반경 안의 이웃을 찾는 경우입니다.

| 분포 | 격자 후보 | 격자가 훑은 칸 | 트리 후보 | 트리가 방문한 노드 |
| --- | --- | --- | --- | --- |
| 고르게 퍼짐 | 4,268 | 4,500 | 7,513 | 11,264 |
| 여섯 덩어리로 뭉침 | 52,015 | 4,500 | 42,781 | 30,340 |

**고르게 퍼진 쪽은 격자가 확실히 이깁니다.** 뭉친 쪽도 후보는 트리가 조금 적지만
노드를 타고 내려가는 값이 훨씬 큽니다. 칸 번호를 나눗셈 한 번으로 얻는 격자와,
포인터를 따라 내려가는 트리의 차이입니다.

**격자가 지는 자리는 따로 있습니다. 찾는 거리가 미리 안 정해질 때입니다.**
「가장 가까운 다섯 개」 같은 질의가 그렇습니다. 빽빽한 곳에서는 한 칸만 봐도 되지만
성긴 곳에서는 한참 넓혀야 다섯을 채웁니다. **그 거리를 미리 알 수가 없습니다.**

절반은 여섯 덩어리에 빽빽하게, 절반은 맵 전체에 성기게 뿌려 놓고
각 물체마다 가장 가까운 다섯을 500번 찾았습니다.

| 구조 | 칸 또는 노드 | 후보 | 훑은 칸·노드 | 합 |
| --- | --- | --- | --- | --- |
| 격자 (칸 10) | 639 | 12,202 | 45,852 | 58,054 |
| 격자 (칸 25) | 476 | 26,046 | 12,636 | 38,682 |
| 격자 (칸 50) | 292 | 38,361 | 6,924 | 45,285 |
| 격자 (칸 100) | 99 | 62,907 | 4,516 | 67,423 |
| **쿼드트리** | **393** | **8,829** | **5,970** | **14,799** |

**어느 칸 크기로도 트리를 못 이깁니다.** 잘게 잡으면 성긴 곳에서 빈 칸을 한참 훑고,
크게 잡으면 빽빽한 곳에서 후보가 쏟아집니다. 밀도가 두 배씩 다르면 하나의 값이 양쪽을 다 만족시킬 수 없습니다.
트리는 **자기가 있는 자리의 밀도에 맞는 깊이까지만** 내려갑니다.

정리하면 이렇습니다.

- **반경이 정해진 질의 + 고른 분포** 라면 격자입니다. 그것도 큰 차이로요
- **찾는 거리가 질의마다 다르고 밀도가 들쭉날쭉** 하면 트리입니다
- 애매하면 격자로 시작하세요. 1편의 방식대로 만들면 **다시 지어도 싸서** 갱신 걱정이 없습니다

## 움직이면 트리를 고쳐야 한다

격자에서는 물체가 칸을 옮겨도 목록 두 개만 건드리면 끝입니다. 트리는 그렇지 않습니다.

- 나간 칸이 **비면 형제들과 합쳐야** 합니다. 안 합치면 트리가 계속 자랍니다
- 합치는 조건을 매번 검사하면 그 값이 만만치 않습니다. 네 자식의 합이 정원 이하일 때만 합칩니다
- 들어간 칸이 넘치면 **거기서 또 쪼개집니다**

그래서 **매 프레임 전부 움직이는 것들**에는 트리가 잘 안 맞습니다.
그런 경우에는 아예 매 프레임 트리를 통째로 다시 짓는 쪽이 고치는 것보다 빠를 때도 있습니다.
움직이는 것은 격자에, 안 움직이는 지형은 트리에 넣고 **두 구조를 같이 쓰는 것**도 흔한 선택입니다.

## 정리

쿼드트리는 **칸 크기를 미리 정하지 않는 격자**입니다.

- 정원을 넘은 칸만 넷으로 나눕니다. **빈 곳은 큰 칸 하나로 남습니다**
- **깊이 제한이 반드시 필요합니다.** 같은 자리에 겹친 물체가 있으면 없이는 무한히 쪼갭니다
- 크기가 있는 물체는 경계에 걸칩니다. 부모에 남기거나, 걸친 자식 전부에 넣거나, **칸을 느슨하게** 잡습니다
- **반경이 정해진 질의에서는 격자가 이깁니다.** 트리가 이기는 자리는 찾는 거리가 미리 안 정해지고 밀도가 들쭉날쭉할 때입니다
- 움직이면 쪼개고 합치는 값이 듭니다. 전부 움직이면 통째로 다시 짓거나, 격자와 나눠 쓰는 편이 낫습니다