전부 검사하지 않으려면 미리 나눠 둔다

플레이어 주변 5미터 안의 적을 찾습니다.

foreach (var e in allEnemies)
{
    if (Vector3.Distance(player.position, e.position) < 5f)
        nearby.Add(e);
}

적이 500마리면 500번 잽니다. 이건 견딜 만합니다.

그런데 적끼리 서로 부딪혔는지 보려면 이야기가 달라집니다.

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만 번 중 대부분은 볼 필요도 없는 짝입니다. 맵 왼쪽 끝의 적과 오른쪽 끝의 적이 부딪혔는지는 거리를 재 보지 않아도 압니다.

공간을 칸으로 나눈다

미리 격자를 깔아 두고 각 오브젝트가 어느 칸에 있는지 기록해 둡니다.

public class SpatialGrid
{
    readonly Dictionary<Vector2Int, List<Enemy>> 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<Enemy>();
        list.Add(e);
    }
}

좌표를 칸 번호로 바꾸는 것은 나눗셈 한 번입니다. 어디에 있는지 찾으려고 목록을 뒤질 필요가 없습니다.

이제 주변을 찾을 때 자기 칸과 이웃한 여덟 칸만 봅니다.

public void QueryNearby(Vector3 pos, List<Enemy> 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미터로 둡니다. 그러면 이웃 아홉 칸이 검사 반경을 딱 덮습니다.

칸이 반경보다 작으면 아홉 칸으로는 모자라서 더 넓게 봐야 합니다. 반대로 칸이 반경보다 크면 필요 없는 것까지 잔뜩 딸려 옵니다.

움직이면 다시 넣어야 합니다

여기가 실제로 성가신 부분입니다. 적이 움직이면 칸이 바뀝니다. 매 프레임 전부 지우고 다시 넣으면 그 비용이 만만치 않습니다.

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);
}

칸이 안 바뀌었으면 아무것도 안 합니다. 프레임당 이동 거리가 칸 크기보다 훨씬 작으니 대부분의 오브젝트는 이 줄에서 빠져나갑니다. 앞의 더티 플래그와 같은 발상입니다.

그리고 안 움직이는 것과 움직이는 것을 나누는 것이 큽니다. 지형, 건물, 아이템은 한 번 넣고 다시 안 건드립니다.

직접 만들기 전에

유니티의 물리 시스템이 이미 이 일을 하고 있습니다.

var hits = Physics.OverlapSphere(player.position, 5f, enemyLayer);

이 한 줄이 전부 검사하지 않습니다. 내부에 공간 자료구조가 있어서 근처만 봅니다. 콜라이더를 붙일 수 있는 대상이라면 직접 격자를 만들기 전에 이쪽부터 봐야 합니다. 레이어 마스크로 대상을 좁히면 더 줄어듭니다.

직접 만들 이유는 이런 경우입니다.

• 콜라이더를 붙이고 싶지 않은 것 (수천 개의 데이터 점, 소리, 관심 영역)
• 물리와 무관한 질의 (가장 가까운 아군, 사거리 안의 표적 목록)
• 물리 쿼리가 만드는 배열 할당이 부담일 때

다른 나누는 방법들

균일한 격자가 가장 단순하고, 대부분의 게임에서 이것으로 충분합니다. 오브젝트가 고르게 퍼져 있고 크기가 비슷하면 이보다 나은 것이 별로 없습니다.

그 조건이 깨지는 경우가 셋 있고, 각각 다른 방식이 답입니다.

쿼드트리는 밀도에 적응합니다. 빈 칸이 대부분인데 한 칸에 300개가 들어 있는 상황에서, 그 한 칸만 넷으로 쪼개고 또 붐비면 또 쪼갭니다. 대신 오브젝트가 움직일 때마다 트리를 고쳐야 해서 갱신 비용이 격자보다 큽니다.

BVH 는 공간이 아니라 오브젝트를 기준으로 묶습니다. 커다란 보스와 작은 총알을 같은 격자에 넣으면 보스가 여러 칸에 걸치는데, BVH 는 상자가 오브젝트를 감싸는 구조라 크기 차이가 문제가 안 됩니다. 레이캐스트나 절두체 컬링처럼 길쭉한 질의에도 격자보다 낫습니다.

BSP 는 갱신을 거의 안 하는 대신 미리 만드는 비용이 큽니다. 그래서 움직이는 것에는 안 쓰고 정적 지형에 씁니다.

고르는 기준은 무엇이 얼마나 자주 바뀌느냐 입니다. 매 프레임 전부 움직이면 갱신이 싼 격자가 이기고, 거의 안 움직이면 만드는 비용을 한 번 치르고 질의를 싸게 만드는 쪽이 이깁니다.

대부분의 프로젝트는 균일 격자에서 시작해도 됩니다. 그것으로 안 될 때 프로파일러가 알려 줍니다. 그리고 안 되는 이유가 위의 셋 중 무엇인지를 보고 고르면 됩니다.

정리

• 전부 대 전부로 비교하면 개수의 제곱에 비례해 늘어난다. 두 배면 네 배다.
• 그 비교의 대부분은 볼 필요도 없는 짝이다. 멀리 떨어진 것끼리다.
• 공간을 칸으로 나눠 두면 좌표에서 칸 번호를 나눗셈 한 번으로 얻는다.
• 자기 칸과 이웃 여덟 칸만 본다. 이웃까지 보는 것은 경계에 걸친 것을 놓치지 않기 위해서다.
• 성능은 칸 크기가 정한다. 검사 반경 정도로 시작한다.
• 움직이면 다시 넣어야 한다. 칸이 안 바뀌었으면 아무것도 안 하는 것으로 대부분을 거른다.
• 안 움직이는 것과 움직이는 것을 나눈다.
• 유니티 물리가 이미 이 일을 한다. 직접 만들기 전에 OverlapSphere 부터 본다.
• 균일 격자로 시작한다. 몰려 있으면 쿼드트리, 크기가 제각각이면 BVH, 정적 지형이면 BSP 다.
• 고르는 기준은 무엇이 얼마나 자주 바뀌느냐다. 자주 움직이면 갱신이 싼 격자가 이긴다.