빈 곳은 큰 칸 하나로 남긴다

균일 격자는 칸 크기를 하나로 정해 놓고 씁니다. 그 값이 맵 전체에 그대로 적용됩니다.

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

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

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

붐비는 칸만 쪼갠다

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

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

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

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

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 는 가운데를 기준으로 어느 사분면인지만 보면 됩니다.

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개를 두고 두 구조를 같은 질의로 재 봤습니다. 먼저 찾는 거리가 미리 정해진 질의, 즉 반경 안의 이웃을 찾는 경우입니다.

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

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

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

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

정리하면 이렇습니다.

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

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

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

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

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

정리

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

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