채우기는 어디서 멈출지를 색으로 정한다

세 가지 기능이 있습니다.

• 매치3에서 같은 색 블록이 몇 개나 붙어 있는지 센다
• 그림 도구에서 페인트 통으로 한 영역을 칠한다
• 지뢰찾기에서 빈 칸을 누르면 주변 빈 칸이 한꺼번에 열린다

셋 다 한 칸에서 출발해 조건에 맞는 이웃으로 계속 번져 나가는 일입니다. 코드로는 거의 같고, 이 알고리즘의 이름이 플러드 필(flood fill) 입니다. 격자를 훑는 탐색과 다른 점은 하나뿐입니다. 어디까지 갈 수 있는지를 지형이 아니라 칸의 값이 정합니다.

이웃을 색이 정한다

지금까지 격자에서 이웃을 고르는 조건은 둘이었습니다. 맵 안이어야 하고, 벽이 아니어야 합니다. 채우기에는 조건이 하나 더 붙습니다.

void Fill(int sx, int sy) {
    int target = grid[sx, sy];          // 시작 칸의 값이 기준이 된다
    var stack = new Stack<(int, int)>();
    stack.Push((sx, sy));
    filled[sx, sy] = true;

    while (stack.Count > 0) {
        var (x, y) = stack.Pop();
        Paint(x, 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 (filled[nx, ny]) continue;
            if (grid[nx, ny] != target) continue;   // 이 줄이 경계다
            filled[nx, ny] = true;
            stack.Push((nx, ny));
        }
    }
}

grid[nx, ny] != target 한 줄이 이 알고리즘의 전부입니다. 벽처럼 지도에 박혀 있는 경계가 아니라 시작 칸이 무엇이었느냐에 따라 매번 새로 생기는 경계입니다. 같은 지도라도 파란 블록에서 시작하면 파란 영역이, 빨간 블록에서 시작하면 빨간 영역이 잡힙니다.

스택이든 큐든 결과는 같다

담아 두는 자리를 스택으로 두면 한 갈래로 길게 뻗어 나가고, 큐로 두면 시작 칸에서 동심원처럼 퍼집니다. 그런데 칠해지는 칸의 집합은 똑같습니다. 영역 전체를 칠하는 것이 목적이라 순서가 결과를 안 바꿉니다.

그래서 고르는 기준이 결과가 아니라 다른 데 있습니다.

지뢰찾기에서 칸이 촤르륵 열리는 연출이나, 물이 번지는 효과에 한 칸씩 지연을 주고 싶다면 큐 쪽입니다.

재귀로 짜면 큰 영역에서 터진다

채우기를 재귀로 쓰면 코드가 아주 짧아집니다.

void Fill(int x, int y, int target) {
    if (밖이거나 이미 칠했거나 색이 다르면) return;
    filled[x, y] = true;
    Paint(x, y);

    Fill(x + 1, y, target);
    Fill(x - 1, y, target);
    Fill(x, y + 1, target);
    Fill(x, y - 1, target);
}

영역이 커지면 그대로 호출 깊이가 됩니다. 512 곱하기 512 짜리 캔버스를 전부 칠하면 최악에 26만 번 중첩입니다. 스택 프레임 하나가 수십 바이트만 잡아도 남아나지 않습니다. 게임에서 스택 오버플로는 대개 프로세스 종료이고, try 로 잡히지도 않습니다.

칠할 영역의 크기를 내가 정하는 경우, 예를 들어 매치3 보드가 8 곱하기 8 이라면 재귀로 써도 됩니다. 캔버스나 큰 맵처럼 크기를 사용자가 정하는 경우에는 반드시 직접 만든 스택이나 큐로 씁니다.

네 방향이냐 여덟 방향이냐

이웃의 정의를 바꾸면 같은 지도에서 다른 영역이 나옵니다.

같은 지도, 같은 시작 칸인데 네 칸이 칠해지기도 하고 열한 칸이 칠해지기도 합니다. 둘 중 무엇이 맞는지는 알고리즘이 아니라 게임 규칙이 정합니다.

• 매치3은 네 방향입니다. 가로나 세로로 이어진 것만 매치로 치기 때문입니다. 여덟 방향으로 세면 모서리만 닿은 블록까지 한 덩어리가 됩니다
• 지뢰찾기는 여덟 방향입니다. 칸에 적힌 숫자가 여덟 방향의 지뢰 수라서, 여는 규칙도 같은 여덟 방향이어야 앞뒤가 맞습니다
• 맵에서 섬을 셀 때는 모서리로 닿은 땅을 한 섬으로 볼지부터 정합니다. 그 답이 방향 수입니다

여덟 방향에는 함정이 하나 더 있습니다. 벽이 대각선으로 맞물린 자리를 모서리로 빠져나갑니다. 막아야 한다면 양옆 두 칸이 모두 막혀 있을 때 그 대각선을 이웃에서 빼면 됩니다.

줄 단위로 채우면 큐가 작아진다

칸마다 큐에 넣는 방식은 넓은 영역에서 큐가 크게 부풀어 오릅니다. 페인트 통처럼 수만 칸을 칠하는 경우라면 줄 단위로 처리하는 편이 낫습니다. 스캔라인 플러드 필(scanline flood fill)이라고 부릅니다.

절차는 이렇습니다.

1. 꺼낸 칸에서 왼쪽과 오른쪽으로 끝까지 훑어 그 줄의 구간을 통째로 칠합니다
2. 칠한 구간의 바로 위 줄과 아래 줄만 살펴봅니다
3. 그 줄에서 아직 안 칠해졌고 색이 같은 구간을 찾아, 각 구간의 칸 하나씩만 큐에 넣습니다

큐에 들어가는 것이 칸 수가 아니라 구간 수가 됩니다. 가로로 긴 영역일수록 차이가 커집니다. 가로 1,000칸짜리 줄이 스무 개면 칸 단위로는 2만 개가 큐를 거쳐 가지만, 줄 단위로는 스무 번 남짓입니다.

대신 코드가 길어지고 구간 경계에서 실수하기 쉽습니다. 보드가 작은 게임에서는 굳이 쓸 이유가 없습니다. 큰 캔버스를 칠하는 도구를 만들 때 꺼내는 방법입니다.

색을 무엇으로 비교하나

칸에 든 것이 타일 번호나 블록 종류면 그냥 같은지 보면 됩니다. 픽셀 색이면 이야기가 달라집니다.

그림의 경계는 안티에일리어싱 때문에 중간 색이 한두 픽셀 깔려 있습니다. 정확히 같은 색만 이웃으로 치면 칠하고 난 뒤 원래 색의 테두리가 남습니다. 그래서 허용 오차를 둡니다.

bool SameColor(Color32 a, Color32 b, int tolerance) {
    return Mathf.Abs(a.r - b.r) <= tolerance
        && Mathf.Abs(a.g - b.g) <= tolerance
        && Mathf.Abs(a.b - b.b) <= tolerance;
}

채널별 차이를 보는 방식입니다. 세 채널의 거리를 재는 방법도 있는데, 어느 쪽이든 오차를 키우면 반대 문제가 생깁니다. 경계의 중간 색까지 같은 색으로 쳐 버리면 그 너머로 새어 나갑니다. 오차는 게임 화면을 보면서 맞추는 값이지 계산으로 나오는 값이 아닙니다.

알파를 빼먹는 것도 흔한 실수입니다. 투명한 영역은 RGB 가 제각각이라 눈에는 다 같아 보여도 값이 다릅니다.

다 칠하고 나면

채우기의 결과물은 보통 색이 아니라 칸의 목록입니다. 그 목록으로 무엇을 하느냐가 기능을 가릅니다.

지뢰찾기의 빈 칸 열기가 특히 재미있습니다. 규칙이 이렇습니다.

• 주변 지뢰가 0인 칸은 열고, 이웃을 계속 퍼뜨립니다
• 숫자가 적힌 칸은 열되, 거기서 멈춥니다

여는 것과 퍼뜨리는 것을 갈라 놓은 것입니다. 그래서 빈 영역이 통째로 열리고 그 가장자리에 숫자 한 겹이 함께 드러납니다. 경계 칸을 결과에 포함하되 프런티어에는 넣지 않는 것, 이 손질이 채우기 계열에서 자주 쓰입니다.

정리

채우기는 이웃의 조건에 “값이 같아야 한다” 한 줄을 더한 탐색입니다. 경계가 지도에 박혀 있지 않고 시작 칸이 무엇이었느냐에 따라 매번 새로 생깁니다.

정할 것은 셋입니다.

• 방향 수. 네 방향과 여덟 방향은 같은 지도에서 다른 답을 냅니다. 게임 규칙이 정합니다
• 담아 두는 자리. 결과는 같으니 연출이나 거리 계산이 필요한지로 고릅니다. 다만 영역 크기를 사용자가 정하는 경우 재귀는 쓰지 않습니다
• 같다는 것의 기준. 타일 번호면 그냥 비교하고, 픽셀 색이면 허용 오차를 두되 너무 키우면 경계를 넘어 샙니다

비용은 칠한 칸 수에 비례합니다. 맵 전체가 아니라 그 영역만 훑기 때문에, 보드가 커져도 한 덩어리가 작으면 부담이 없습니다.