Kruskal 알고리즘을 이용한 맵 생성

📌 기존 문제점: Binary Tree 방식의 한계

기존에 사용하던 Binary Tree 기반 미로 생성 방식은 간단하지만 한 가지 치명적인 단점이 있었습니다.

우측 혹은 아래로 일직선으로 뚫리는 길이 많아서 미로의 다양성이 떨어진다!

if (rand() % 2)
    carveRight();
else
    carveDown();

• 이처럼 1/2 확률로 단순하게 방향을 정해주기 때문에 규칙적인 패턴의 맵이 자주 생성됨
• 마치 바둑판처럼 predictable한 구조가 생겨서 게임의 재미 요소를 감소시킴

---

💡 해결 전략: Kruskal 알고리즘 도입

Kruskal 알고리즘은 최소 스패닝 트리(MST)를 만드는 탐욕 알고리즘입니다.

• 미로의 각 뚫린 지점을 정점(Vertex)으로 보고,
• 이웃 정점과의 연결 후보를 간선(Edge)로 설정
• 각 간선에 랜덤한 비용(Cost)을 부여
• 비용이 가장 적은 간선부터 선택하여 사이클이 없는 트리를 구성

최소 비용으로 모든 정점을 연결하면서도 무작위성이 보장되는 미로 생성 방식!

---

🛠️ 핵심 아이디어 요약

요소	Kruskal 기반 미로 생성에서의 의미
정점(Vertex)	미로에서 뚫려 있는 좌표 (홀수 x, y)
간선(Edge)	오른쪽, 아래 인접 좌표와의 연결 후보
비용(Cost)	rand() % 100 랜덤값
MST	모든 좌표가 연결된 유일한 경로의 조합

---

🧱 미로 맵 생성 과정

1️⃣ 타일 초기화 (벽 + 통로 구성)

for (int32 y = 0; y < _size; y++) {
    for (int32 x = 0; x < _size; x++) {
        _tile[y][x] = (x % 2 == 0 || y % 2 == 0) ? WALL : EMPTY;
    }
}

• 짝수 좌표: 벽
• 홀수 좌표: 이동 가능한 통로 후보

---

2️⃣ 간선 후보 등록

for (int32 y = 0; y < _size; y++) {
    for (int32 x = 0; x < _size; x++) {
        if (x % 2 == 0 || y % 2 == 0) continue;

        if (x < _size - 2)  // 우측 후보
            edges.push_back({ rand() % 100, {y, x}, {y, x + 2} });

        if (y < _size - 2)  // 아래쪽 후보
            edges.push_back({ rand() % 100, {y, x}, {y + 2, x} });
    }
}

• 각 정점에서 우측, 아래쪽으로 연결할 수 있는 경우만 간선으로 등록
• rand() % 100을 이용해 비용(cost) 부여

---

3️⃣ 간선 정렬 (오름차순)

std::sort(edges.begin(), edges.end());

• 비용 기준으로 가장 작은 간선부터 선택할 수 있게 정렬

---

4️⃣ Kruskal 알고리즘 적용

DisjointSet sets(_size * _size);

for (CostEdge& edge : edges) {
    int u = edge.u.y * _size + edge.u.x;
    int v = edge.v.y * _size + edge.v.x;

    if (sets.Find(u) == sets.Find(v))
        continue;

    sets.Merge(u, v);

    // 중간 지점을 비워 길 생성
    int y = (edge.u.y + edge.v.y) / 2;
    int x = (edge.u.x + edge.v.x) / 2;
    _tile[y][x] = EMPTY;
}

• Disjoint Set을 이용해 사이클 방지
• 연결된 두 지점이 서로 다른 그룹이면 병합
• 병합 시, 두 지점 사이에 위치한 벽을 제거하여 길을 생성

---

🧠 Disjoint Set 구조

class DisjointSet {
public:
    DisjointSet(int n) : _parent(n), _rank(n, 1) {
        for (int i = 0; i < n; i++) _parent[i] = i;
    }

    int Find(int u) {
        if (u == _parent[u]) return u;
        return _parent[u] = Find(_parent[u]);  // 경로 압축
    }

    void Merge(int u, int v) {
        u = Find(u);
        v = Find(v);
        if (u == v) return;

        if (_rank[u] > _rank[v]) swap(u, v);
        _parent[u] = v;
        if (_rank[u] == _rank[v]) _rank[v]++;
    }

private:
    vector<int> _parent;
    vector<int> _rank;
};

• Find: 경로 압축
• Merge: Union By Rank 최적화

---