[Unity] 본진과 연결된 영토만 점수로 인정하기 — BFS와 고립 복구

Paint War의 타일은 단순히 색깔만 칠해져 있다고 점수로 인정되지 않습니다. 본진으로부터 연결된 타일인지 확인해야 하며, 중간 길이 끊기면 기존 영토가 고립될 수도 있습니다. 이 연결 여부를 BFS로 계산했습니다.

1. 소유권과 유효한 영토는 같은 개념이 아닙니다

어떤 타일에 플레이어 색이 남아 있더라도 본진과 연결되지 않았으면 점수로 인정할 수 없습니다. 그래서 TileGridState의 소유자 정보와 ConnectedTerritoryState의 연결 여부를 구분했습니다.

연결 판정의 출발점은 각 플레이어의 보호된 본진 타일입니다. 여기서 상하좌우 네 방향으로 같은 소유자의 타일만 따라가며 영역을 넓혀 갑니다.

2. Queue를 이용한 너비 우선 탐색(BFS)

ConnectedTerritoryState는 그리드 크기에 맞는 queue, connected, visited 배열을 먼저 생성합니다. 연결 계산을 할 때마다 큰 컬렉션을 새로 만들지 않고 재사용하기 위한 구성입니다.

int head = 0, tail = 0;
// 소유자가 같은 본진 타일을 queue에 넣은 뒤
while (head < tail)
{
    int flat = queue[head++];
    connectedCounts[ownerValue]++;
    int x = flat / size, y = flat % size;
    for (int d = 0; d < Directions.Length; d++)
    {
        int nx = x + Directions[d].x;
        int ny = y + Directions[d].y;
        if (nx < 0 || ny < 0 || nx >= size || ny >= size)
            continue;
        int next = nx * size + ny;
        if (connected[next] ||
            (destroyed != null && destroyed[next]) ||
            owners[next] != owner) continue;
        connected[next] = true;
        queue[tail++] = next;
    }
}

코드는 핵심 부분을 발췌한 것입니다. flat은 2차원 좌표를 x * size + y로 펼친 인덱스입니다. head와 tail을 사용한 배열 큐이기 때문에 일반 Queue 객체를 탐색마다 새로 만들 필요가 없습니다.

탐색에서 다른 소유자, 파괴된 타일, 이미 방문한 타일은 제외합니다. 결과적으로 본진에서 도달한 칸만 connected에 표시됩니다.

3. 연결이 끊긴 순간 바로 삭제하지 않기

타일 연결이 끊어졌다고 즉시 초기화하면 복구할 시간이 없습니다. 실제 구현에서는 이전 계산에서 연결되어 있었지만 이번에는 연결되지 않은 타일을 감지해 isolatedSince로 고립 시각을 기록합니다.

bool newlyIsolated = sameOwnerAsPreviousBatch &&
    visited[i] && !connected[i];
bool remainsPending = isolatedSince[i] >= 0f &&
    isolatedOwner[i] == owner;

설정된 유예 시간이 지나기 전 다시 본진에 연결되면 고립 상태를 해제합니다. 반대로 유예 시간이 지났는데도 연결이 복구되지 않았다면 CollectExpired()에서 붕괴 대상 타일을 수집합니다.

여기서 주의할 점은 처음부터 연결되지 않은 새 타일을 기존 연결 영토가 끊긴 것으로 취급하지 않는다는 것입니다. previousOwners와 이전 연결 배열을 비교하는 이유가 바로 여기에 있습니다.

4. 점수와 봇도 같은 계산 결과를 사용하기

TilePaintManager.CountConnectedTerritory()는 연결된 영토 개수를 반환합니다. 봇 AI의 BotTerritoryAnalyzer 역시 이 값을 조회하므로 점수 판정과 봇의 목표 판단이 서로 다른 방식으로 BFS를 수행하지 않습니다.

---

정리

타일 소유권 → 본진 기준 BFS → 연결된 칸 집계 → 고립 판정 → 복구/붕괴 순서로 영토 규칙을 구성했습니다. 게임 규칙을 한 곳에 두면 표시·점수·AI가 공통 기준으로 동작할 수 있다는 점이 중요했습니다.

---

참고한 구현 코드

• LGH/Scripts/Tiles/ConnectedTerritoryState.cs
• LGH/Scripts/Tiles/TilePaintManager.cs
• LGH/Scripts/Bot/BotTerritoryAnalyzer.cs