[C#] FloodFill 알고리즘과 땅따먹기

카테고리: C# + Unity

2023. 04. 01 4 분 소요

땅따먹기

기본적으로 땅따먹기는 paper.io와 같이 넓은 땅 위에 자신의 시작 지점을 정하고 말을 움직이며 선을 그려 다시 본인의 선에 닿으면 해당 부분 만큼 본인의 땅이 되는 게임이다.

땅따먹기가 사각형만 되었어도, 구현에 어려움을 느끼지 않겠지만 아래와 같이 그려지기 시작하면 내부를 어떻게 채워야 할까 머리가 아파진다.

FloodFill 알고리즘

Flood fill 알고리즘은 일반적으로 2차원 배열에서 사용되는 컴퓨터 그래픽스 및 이미지 처리에서 사용되는 알고리즘이다. 이 알고리즘은 영역 채우기를 위해 사용되며, 특정 시작 지점에서부터 인접한 영역을 찾아 동일한 색으로 채우는 과정을 반복한다.

주어진 시작 좌표를 기준으로 상하좌우로 인접한 픽셀을 검사하면서 같은 색으로 채워진 영역을 찾는다.
해당 픽셀을 방문한 것으로 표시한다.
인접한 픽셀들도 마찬가지로 검사하여 같은 과정을 반복한다.

보통 재귀나, 큐, 스택을 사용하여 구현한다.

하지만, 재귀를 사용하면 쉽게 StackOverflow가 발생해서 일반적으로 큐나 스택을 사용한다.

1. 재귀를 이용한 방법

// isVaild 함수는 해당 point의 좌표가 올바른 위치에 있는지, 벽은 아닌지,
// 이미 색칠한 것은 아닌지 확인하는 함수이다.
// 9는 색칠한 좌표이다.

private void FloodFill_R(ref int[, ] array, Point point) {
    if (isVaild(point.X, point.Y + 1)) {
        array[point.X, point.Y + 1] = 9;
        FloodFill_R(ref array, new Point(point.X, point.Y + 1));
    }
    if (isVaild(point.X + 1, point.Y])) {
        array[point.X + 1, point.Y] = 9;
        FloodFill_R(ref array, new Point(point.X + 1, point.Y));
    }
    if (isVaild(point.X, point.Y - 1])) {
        array[point.X, point.Y - 1] = 9;
        FloodFill_R(ref array, new Point(point.X, point.Y - 1));
    }
    if (isVaild(point.X - 1, point.Y)) {
        array[point.X - 1, point.Y] = 9;
        FloodFill_R(ref array, new Point(point.X - 1, point.Y));
    }
}

2. 스택을 이용한 방법

// isVaild 함수는 해당 point의 좌표가 올바른 위치에 있는지, 벽은 아닌지,
// 이미 색칠한 것은 아닌지 확인하는 함수이다.
// 9는 색칠한 좌표이다.

private void FloodFill_S(ref int[,] array, Point start) {
    Stack<Point> points = new Stack<Point>();
    points.Push(start);

    while (points.Count > 0) {
        Point point = points.Pop();

        if (isVaild(point.X, point.Y + 1)) {
            array[point.X, point.Y + 1] = 9;
            points.Push(new Point(point.X, point.Y + 1));
        }
        if (isVaild(point.X + 1, point.Y)) {
            array[point.X + 1, point.Y] = 9;
            points.Push(new Point(point.X + 1, point.Y));
        }
        if (isVaild(point.X, point.Y - 1)) {
            array[point.X, point.Y - 1] = 9;
            points.Push(new Point(point.X, point.Y - 1));
        }
        if (isVaild(point.X - 1, point.Y)) {
            array[point.X - 1, point.Y] = 9;
            points.Push(new Point(point.X - 1, point.Y));
        }
    }
}