[WinAPI] 땅따먹기: 경로 병합과 점령 영역 선택

TL;DR — 재사용한 Win32/GDI+ 게임 골격 위에 경계 이동, 경로 기록, 영역 선택으로 이어지는 땅따먹기 규칙을 구현했습니다. 플레이어가 만든 경로와 기존 경계를 결합해 두 후보 영역을 만들고, 보스를 포함한 영역은 남긴 채 반대쪽 면적을 점령률에 반영했습니다. 이 글에서는 상태 기반 이동, 교차 횟수를 이용한 내부 판정, 외적을 이용한 면적 계산을 중심으로 설계와 구현 흐름을 정리합니다.

Open Table of contents

들어가며
1. 경계, 새 경로, 계산 책임을 분리했습니다
2. 상태 기반으로 경로를 완성했습니다
3. 기존 경계와 새 경로로 두 후보를 만들었습니다
4. 교차 횟수로 보스가 포함된 영역을 판정했습니다
5. 외적을 누적해 점령 면적을 계산했습니다
정리하며
참고 자료

들어가며

이 프로젝트는 WinAPI 기반 2D 게임 골격을 활용해 약 2~3주 동안 제작한 땅따먹기 프로토타입입니다. 공통 message loop와 manager 구조는 기존 골격을 재사용하고, Player, Map, GameUtil, SceneStage01에 프로젝트 고유의 이동과 영역 계산 규칙을 구현했습니다.

땅따먹기의 한 번의 플레이는 다음 흐름으로 이어집니다.

플레이어가 기존 경계에서 출발해 새로운 경로를 만듭니다.
새 경로가 다시 경계에 닿으면 두 개의 후보 영역을 구성합니다.
보스가 포함된 영역을 판정해 다음 플레이 영역으로 남깁니다.
반대쪽 영역의 면적을 계산해 누적 점령률에 반영합니다.

이 글에서는 각 단계를 어떤 데이터와 상태로 나눴는지, 그리고 게임 규칙에 맞춰 기하 계산을 어떻게 단순화했는지 설명합니다.

사전 지식: C++의 vector와 다각형의 꼭짓점·선분에 대한 기본 이해를 전제로 합니다.

1. 경계, 새 경로, 계산 책임을 분리했습니다

Map::path는 현재 플레이할 수 있는 영역의 경계를 꼭짓점 순서대로 저장합니다. 초기에는 직사각형이지만, 영역을 점령할 때마다 선택한 후보 영역이 새로운 Map::path가 됩니다.

플레이어가 경계를 벗어나 이동하는 동안에는 꺾이는 지점만 Player::pushing에 기록합니다. 처음에는 열린 선이지만, 시작점과 끝점이 모두 기존 경계에 닿으면 경계의 일부와 결합해 닫힌 영역을 만들 수 있습니다.

구성 요소	역할
`SceneStage01`	플레이어, 맵, 적을 배치하고 스테이지를 구성
`Player`	입력 처리, 이동 상태 전환, 새로운 경로 기록
`Map`	현재 경계와 누적 점령 면적, 전체 면적 관리
`GameUtil`	경계 판정, 후보 영역 조립, 내부 판정, 면적 계산

프레임마다 바뀌는 입력과 이동은 Player가 담당하고, 다각형을 다루는 계산은 GameUtil로 분리했습니다. 덕분에 플레이어는 언제 경로를 완성할지만 결정하고, 완성된 경로를 어느 영역으로 반영할지는 별도의 계산 흐름으로 처리할 수 있었습니다.

2. 상태 기반으로 경로를 완성했습니다

플레이어의 이동은 ONPATH, PUSHING, END_PUSH, BACK 네 상태로 나눴습니다. 경계를 따라 이동하다가 내부로 들어가면 경로 기록을 시작하고, 다시 경계에 닿으면 영역 계산으로 넘어갑니다. 입력을 취소하거나 충돌하면 새 경로를 확정하지 않고 출발 지점으로 돌아갑니다.

ONPATH
  +-- 경계 이탈 --> PUSHING
                        +-- 경계 재접촉 --> END_PUSH --> 영역 병합 --> ONPATH
                        `-- 취소/충돌 ----> BACK ------> 경계 복귀 --> ONPATH

PUSHING 상태에서는 매 프레임의 위치를 모두 저장하지 않고 방향이 바뀌는 지점만 추가합니다. 이동을 상하좌우로 제한했기 때문에 기록되는 경로도 수평·수직 선분으로 구성됩니다. 기존 경계에 도달하면 마지막 위치를 경계 선분에 맞춰 보정하고 END_PUSH로 전환합니다.

이 구조를 선택한 이유는 영역 계산에 전달되는 입력을 단순하게 유지하기 위해서입니다. GameUtil::merge()에는 항상 기존 경계에서 출발해 다시 경계에 닿은 경로만 전달됩니다. 병합 전에는 Map::path를 바꾸지 않으므로 취소되거나 충돌한 이동도 현재 영역에 영향을 주지 않습니다.

3. 기존 경계와 새 경로로 두 후보를 만들었습니다

완성된 경로의 시작점과 끝점은 기존 경계를 두 구간으로 나눕니다. 각 경계 구간에 플레이어 경로를 서로 반대 방향으로 이어 붙이면 하나의 경계에서 두 개의 닫힌 후보 영역을 만들 수 있습니다.

현재 경계 + 플레이어 경로
  +-- 경계 구간 A + 정방향 경로 --> 후보 A
  `-- 경계 구간 B + 역방향 경로 --> 후보 B

코드의 left, right는 화면에서의 방향이 아니라 두 조립 결과를 구분하는 이름입니다. 시작점과 끝점이 서로 다른 경계 선분에 있으면 경계를 순서대로 순회하며 두 구간을 나누고, 한쪽에는 pushing을 정방향으로, 다른 쪽에는 역방향으로 연결합니다.

두 끝점이 같은 경계 선분에 있을 때는 새 경로의 진행 방향을 확인해 꼭짓점 순서를 맞춥니다. 다각형의 꼭짓점 순서는 이후 내부 판정과 면적 부호에 영향을 주기 때문에, 어느 구간을 붙이는지만큼 연결 방향도 중요합니다.

범용 다각형 자르기 알고리즘 대신 이 방식을 선택한 이유는 게임의 입력이 상하좌우 이동으로 제한돼 있었기 때문입니다. 수평·수직 경계와 하나의 완성된 경로만 처리하면 되므로, 이미 순서가 정해진 꼭짓점을 직접 조립하는 편이 게임 규칙을 구현하기에 충분했습니다.

4. 교차 횟수로 보스가 포함된 영역을 판정했습니다

두 후보를 만든 뒤에는 어느 쪽을 다음 플레이 영역으로 남길지 결정해야 합니다. 이 프로젝트에서는 보스를 계속 플레이 영역 안에 남기는 것이 규칙이므로, 보스 중심이 포함된 후보를 유지했습니다.

점이 다각형 안에 있는지는 보스 중심에서 오른쪽으로 반직선을 그어 경계와 만나는 횟수로 판단했습니다. 오른쪽 무한대의 바깥 영역에서 보스 중심까지 거슬러 온다고 생각하면, 경계를 한 번 지날 때마다 바깥과 안쪽이 바뀝니다. 따라서 교차 횟수가 홀수이면 내부, 짝수이면 외부입니다.

판정할 점을 $q=(x,y)$ , 한 경계 선분의 두 끝점을 $p_1=(x_1,y_1)$ , $p_2=(x_2,y_2)$ 라고 하겠습니다. 먼저 선분이 점의 $y$ 좌표를 가로지르는지 확인합니다.

\min(y_1,y_2) < y \leq \max(y_1,y_2)

조건을 만족하면 해당 높이에서 선분과 반직선이 만나는 $x$ 좌표를 계산합니다.

x_{cross}=x_1+\frac{(x_2-x_1)(y-y_1)}{y_2-y_1}

$x < x_{cross}$ 이면 판정할 점의 오른쪽에서 경계를 만난 것이므로 교차 횟수를 하나 늘립니다. $y$ 범위의 한쪽은 <, 다른 쪽은 <=로 비교해 반직선이 꼭짓점을 지날 때 이웃한 두 선분을 모두 세는 문제를 피했습니다.

if (min(p1.y, p2.y) < pos.y && pos.y <= max(p1.y, p2.y))
{
    float nx =
        (p2.x - p1.x) * (pos.y - p1.y) / (p2.y - p1.y) + p1.x;

    if (pos.x < nx)
    {
        count++;
    }
}

return count % 2 > 0;GameUtil.cpp

이 방식은 꼭짓점 순서가 유지된 단순 다각형이라면 오목한 형태에도 같은 규칙을 적용할 수 있습니다. 별도의 충돌 도형을 만들지 않고 후보 영역의 꼭짓점과 보스 중심만으로 판단할 수 있다는 점도 현재 구조와 잘 맞았습니다.

보스가 포함된 후보를 찾으면 그 후보를 다음 Map::path로 저장하고, 반대 후보를 점령한 영역으로 처리합니다.

if (bossIsInLeft)
{
    map->setPath(left);
    map->setCurArea(map->getCurArea() + rightArea);
}
else
{
    map->setPath(right);
    map->setCurArea(map->getCurArea() + leftArea);
}GameUtil.cpp

5. 외적을 누적해 점령 면적을 계산했습니다

점령 영역은 매번 직사각형으로 만들어지지 않습니다. 플레이어가 여러 번 방향을 바꾸면 오목한 부분을 포함한 다각형이 만들어질 수 있습니다. 따라서 첫 꼭짓점 $p_0$ 을 기준으로 이웃한 두 꼭짓점 $p_i$ , $p_{i+1}$ 이 만드는 삼각형의 부호 있는 넓이를 차례로 더했습니다.

두 벡터의 2차원 외적은 다음과 같습니다.

(p_i-p_0)\times(p_{i+1}-p_0) = (x_i-x_0)(y_{i+1}-y_0)-(y_i-y_0)(x_{i+1}-x_0)

외적의 절댓값은 두 벡터가 만드는 평행사변형의 넓이이므로, 절반을 취하면 삼각형의 넓이가 됩니다. 이를 모든 삼각형에 대해 더하면 다각형의 면적을 구할 수 있습니다.

A=\frac{1}{2}\left|\sum_{i=1}^{n-2}(p_i-p_0)\times(p_{i+1}-p_0)\right|

여기서 삼각형은 다각형을 실제로 겹치지 않게 분할한 결과가 아닙니다. 첫 꼭짓점과 각 경계 선분을 연결해 만든 가상의 삼각형이며, 다각형 바깥으로 잡힌 부분은 외적의 반대 부호로 상쇄됩니다.

예를 들어 다음처럼 가운데가 오목하게 들어간 영역을 생각할 수 있습니다.

p7 ---- p6       p3 ---- p2
|        |       |        |
|        p5 ---- p4       |
|                         |
p0 --------------------- p1

꼭짓점을 $p_0=(0,0)$ , $p_1=(4,0)$ , $p_2=(4,4)$ , $p_3=(3,4)$ , $p_4=(3,1)$ , $p_5=(1,1)$ , $p_6=(1,4)$ , $p_7=(0,4)$ 순서로 저장했다고 하겠습니다. 이때 각 경계 선분에 대한 외적을 누적하면 다음과 같습니다.

16+4-9+2+3+4=20

오목하게 들어가는 $p_3\rightarrow p_4$ 구간은 외적이 $-9$ 가 되어 바깥쪽에 잡힌 넓이를 빼줍니다. 마지막에 합계의 절댓값을 취하고 절반으로 나누면 실제 면적은 $10$ 이 됩니다. 이는 $4\times4$ 직사각형에서 가운데 $2\times3$ 영역을 뺀 결과와 같습니다.

외적의 부호는 꼭짓점을 시계 방향으로 순회했는지, 반시계 방향으로 순회했는지도 나타냅니다. 후보를 조립하는 방향에 따라 전체 합이 양수 또는 음수가 될 수 있으므로, 개별 외적이 아니라 전체 합에만 마지막으로 절댓값을 적용했습니다.

이 계산을 선택한 이유는 후보 영역을 이미 순서가 있는 꼭짓점 배열로 보유하고 있었기 때문입니다. 추가 도형이나 별도 라이브러리 없이 꼭짓점을 한 번 순회하는 것만으로 면적을 얻을 수 있습니다.

선택이 끝나면 다음 값이 함께 갱신됩니다.

보스를 포함한 후보는 다음 이동에 사용할 Map::path가 됩니다.
반대 후보의 면적은 Map::curArea에 누적됩니다.
curArea / totalArea는 점령률 UI와 스테이지 종료 판정에 사용됩니다.

GDI+의 FillPolygon은 갱신된 Map::path를 화면에 채워 그립니다. 플레이어가 만든 경로가 영역 계산을 거쳐 다음 이동 경계와 화면 표시, 점령률로 이어지면서 한 번의 점령 과정이 완성됩니다.

정리하며

핵심 요약:

플레이어 이동을 상태로 나눠 경로 생성과 취소, 영역 확정을 구분했습니다.
기존 경계의 두 구간과 새 경로를 결합해 후보 영역 두 개를 만들었습니다.
오른쪽 반직선의 교차 횟수가 홀수인지 확인해 보스를 포함한 후보를 선택했습니다.
꼭짓점 사이의 외적을 누적해 반대 후보의 면적을 계산하고 점령률에 반영했습니다.
갱신된 경계는 다음 이동 제한과 내부 판정, 화면 렌더링에 함께 사용했습니다.

이 프로젝트에서는 게임의 이동 규칙을 수평·수직 경로로 제한하고, 그 전제에 맞춰 상태 관리와 다각형 계산을 연결했습니다. 범용 기하 처리를 만드는 대신 필요한 규칙을 명확한 데이터 흐름으로 구성한 것이 핵심 설계 선택이었습니다.

참고 자료

W. Randolph Franklin — PNPOLY: Point Inclusion in Polygon Test — 교차 횟수를 이용한 다각형 내부 판정 원리를 참고했습니다.
Microsoft Learn — Graphics::FillPolygon — 점 배열로 다각형을 채워 그리는 GDI+ API를 확인했습니다.

이 게시물은 학습한 내용을 바탕으로 초안을 작성한 뒤, LLM의 도움을 받아 내용을 검수하고 다듬어 완성되었습니다.