타일맵도 스킬 트리도 결국 같은 모양이다

게임을 만들다 보면 이름만 다르고 모양이 같은 문제를 여러 번 만납니다.

• 타일맵에서 적이 플레이어에게 가는 길을 찾는다
• 이 스킬을 찍을 수 있는지, 선행 스킬이 다 찍혀 있는지 확인한다
• 절차적으로 만든 던전에서 모든 방이 실제로 이어져 있는지 검사한다

셋 다 점과 그 점들을 잇는 선의 문제입니다. 여기에 붙은 이름이 그래프입니다. 문제를 그래프로 옮겨 놓으면 셋에 같은 코드를 씁니다. 옮기는 첫 단계가 저장하는 방법을 정하는 것입니다.

점과 선에 이름을 붙이면

점을 정점, 정점을 잇는 선을 간선이라고 부릅니다. 그래프는 이 둘의 묶음입니다.

무엇을 정점으로 두고 무엇을 간선으로 둘지는 문제마다 다릅니다.

간선에는 성질이 둘 붙을 수 있습니다.

• 방향. A 에서 B 로는 가는데 B 에서 A 로는 못 가는 경우입니다. 선행 스킬, 한 방향 점프대, 낭떠러지가 그렇습니다. 양쪽이 같으면 방향 없는 간선으로 둡니다
• 가중치. 지나는 데 드는 비용입니다. 늪은 3, 포장된 길은 1 처럼 칸마다 다르게 둘 수 있습니다. 비용이 전부 같으면 가중치가 없는 것으로 봅니다

이 둘을 어떻게 두느냐가 나중에 쓸 수 있는 알고리즘을 정합니다. 가중치가 없으면 단순히 넓게 퍼뜨리는 탐색으로 최단 거리가 나오고, 가중치가 있으면 다익스트라 계열이 필요합니다.

저장하는 방법은 둘이다

같은 그래프를 두 가지로 저장할 수 있습니다.

인접 행렬은 정점 수 V 에 대해 V 곱하기 V 짜리 표를 만들고, 두 정점이 이어졌으면 그 칸에 1 을 적습니다. 가중치가 있으면 1 대신 비용을 적습니다.

인접 리스트는 정점마다 배열이나 리스트를 하나씩 두고 이어진 이웃만 넣습니다. 간선 하나가 양방향이면 양쪽 목록에 한 번씩 들어갑니다.

정점 다섯에 간선 다섯인 위 그래프에서 행렬은 칸 스물다섯 개를 쓰고 리스트는 열 개를 씁니다. 정점이 늘면 이 차이가 벌어집니다.

정점이 늘면 무엇이 벌어지는가

행렬이 쓰는 칸은 간선이 몇 개든 항상 V 의 제곱입니다. 리스트가 쓰는 칸은 정점 하나에 평균 몇 개가 붙어 있느냐에 따라 정해집니다.

정점 하나에 붙은 이웃 수가 정점 수에 가까워질수록 둘이 만납니다. 모든 정점이 서로 다 이어진 그래프라면 행렬과 리스트가 쓰는 칸이 같아지고, 그때는 표 한 장이 더 단순합니다. 게임에서 다루는 그래프는 대부분 반대쪽입니다. 타일맵 한 칸은 이웃이 넷이고, 방 하나에 붙은 통로는 두셋입니다.

무엇을 얻고 무엇을 잃는가

그래서 고르는 기준은 이렇게 정리됩니다.

게임 코드에서 마주치는 그래프는 거의 첫 줄과 마지막 줄에 해당합니다. 기본값은 인접 리스트입니다.

코드로 보면

두 코드가 하는 일은 같습니다. 다른 것은 Visit 에 닿기까지 몇 칸을 읽었느냐입니다. 이웃이 넷인 정점에서 리스트는 네 칸을 읽고, 행렬은 정점 수만큼 읽어 나머지를 버립니다.

가중치가 있으면 bool 대신 비용을 담습니다. 리스트라면 List<(int to, float cost)> 처럼 이웃과 비용을 같이 넣고, 행렬이라면 float[,] 에 비용을 적되 이어지지 않은 칸을 float.PositiveInfinity 로 채웁니다. 0 으로 채우면 “비용 0 으로 이어진 간선” 과 구별이 안 됩니다.

격자는 저장하지 않아도 그래프다

타일맵을 그래프로 쓰겠다고 인접 리스트를 만들 필요는 없습니다. 100 곱하기 100 짜리 맵이면 정점이 만 개이고, 이걸 행렬로 잡으면 칸이 1억 개인데 실제로 이어진 간선은 이만 개 남짓입니다. 리스트로 잡아도 사만 칸을 따로 들고 있어야 합니다.

그런데 격자에는 규칙이 있습니다. (x, y) 의 이웃은 언제나 (x, y-1), (x, y+1), (x-1, y), (x+1, y) 입니다. 이어져 있다는 사실이 좌표 안에 이미 들어 있습니다. 그래서 간선을 저장하는 대신 필요할 때 계산합니다. 이렇게 저장하지 않고 규칙으로만 존재하는 그래프를 암묵 그래프라고 부릅니다.

코드는 방향 배열 하나면 됩니다.

static readonly int[] DX = { 0, 0, -1, 1 };
static readonly int[] DY = { -1, 1, 0, 0 };

IEnumerable<(int x, int y)> Neighbors(int x, int y) {
    for (int d = 0; d < DX.Length; d++) {
        int nx = x + DX[d];
        int ny = y + DY[d];
        if (nx < 0 || ny < 0 || nx >= Width || ny >= Height) continue;
        if (Blocked[nx, ny]) continue;
        yield return (nx, ny);
    }
}

맵 밖을 걸러내는 줄과 벽을 걸러내는 줄이 간선을 만드는 자리입니다. 벽을 부수면 간선이 생기고 문을 잠그면 간선이 사라지는데, 자료구조는 아무것도 안 고쳐도 됩니다.

대각선을 넣을 때는 두 가지를 같이 정해야 합니다.

• 비용. 대각선 한 칸은 가로 한 칸보다 깁니다. 가로세로를 1 로 두면 대각선은 1.414 쯤입니다. 전부 1 로 두면 대각선으로 도는 길이 더 싸 보여서 경로가 지그재그로 나옵니다
• 모서리 통과. 벽 두 장이 직각으로 만난 안쪽 모서리를 대각선으로 스치고 지나가는 문제입니다. 양옆 두 칸이 모두 막혀 있으면 그 대각선은 이웃으로 치지 않는다는 규칙을 넣어 막습니다. 안 넣으면 캐릭터가 벽 모서리를 뚫고 지나갑니다

정점을 번호로 다뤄야 할 때는 y * Width + x 로 칸 하나를 정수 하나에 접습니다. 방문 표시나 비용 배열을 일차원 배열로 잡을 수 있어서 격자를 다루는 코드가 짧아집니다.

정리

점과 선으로 보이면 그래프이고, 그래프로 옮기면 서로 달라 보이던 문제에 같은 코드를 쓸 수 있습니다.

저장하는 방법은 둘입니다. 인접 행렬은 정점 수의 제곱만큼 칸을 쓰는 대신 두 정점이 이어졌는지를 한 번에 답하고, 인접 리스트는 간선 수만큼만 쓰면서 이웃을 정확히 훑습니다. 게임에서 다루는 그래프는 정점이 많고 이웃은 몇 개뿐인 쪽이라 기본값은 인접 리스트입니다.

그리고 격자는 둘 중 어느 것도 아닙니다. 이웃이 좌표 계산으로 나오므로 간선을 저장하지 않습니다. 방향 배열과 범위 검사, 벽 검사 세 줄이 간선의 전부입니다.