맵 자동 생성(3)

이번 글에서는 만들어진 방들을 연결하기 위한 방법을 다뤄보겠다. 

 

모든 방(노드)를 빠짐없이 연결하고 이를 최대한 효율적으로 연결하기 위해서는 최소스패닝트리 즉, MST알고리즘을 사용하면 된다.

즉, 모든 노드를 가장 효율적으로(사이클 없이) 연결해주는 알고리즘이 MST 이며 이를 직접 구현하는 알고리즘에 Kruscal 알고리즘이 있다.

 

크루스칼 알고리즘의 동작방식은 간단하다.

간선 정보를 받거나 만들거나 해서 그래프에 대한 엣지(간선) 데이터가 존재해야한다. 

 

그 간선 정보들을 가중치를 정렬한다. 여기선 거리를 가중치로 뒀고 거리가 가까워야 효율적인 경로이기 때문에

오름차순 정렬을 한다.

 

1. 그 데이터를 바탕으로 가중치가 작은 간선부터 선택한다.

2. 이 간선을 트리에 추가했을 때, 사이클이 생기는가 확인한다. 

3. 생기지 않으면 추가하고, 사이클이 생기면 패스한다.

4. 1번부터 다시 반복한다. 

 

이게 끝이다. 

 

여기서 하나의 개념을 또 알아야 한다. union-find 알고리즘이다. 

간단하게 두 정점이 같은 집합인지를 체크할 수 있는 알고리즘이며, 그래프에서 두 정점사이에 사이클이 있는지를 확인할 때 자주 사용된다. 

 

전체코드를 먼저 보겠다. 

 

Kruscal.cs

using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using UnityEngine;

public class Kruscal
{
    public List<KruscalNode> rooms;

    public class KruscalNode
    {
        public int Id;
        public Vector2 Center;
    }

    public List<Edge> Run()
    {

        // 모든 edge 추가
        List<Edge> edges = new List<Edge>();

        for (int i = 0; i < rooms.Count; i++)
        {
            for(int j=i+1; j < rooms.Count; j++)
            {
                edges.Add(new Edge(rooms[i].Id, rooms[j].Id, Vector2.Distance(rooms[i].Center, rooms[j].Center)));
            }
        }

        edges.Sort();

        List<Edge> mst = new List<Edge>();
        UnionFind uf = new UnionFind(rooms.Count);
        foreach(Edge e in edges)
        {
            if(uf.Union(e.V1,e.V2))
                mst.Add(e);
        }
        return mst;
    }

}

코드는 생각보다 간단하다. 위에 언급한 절차를 그대로 작성한 것 뿐이다. 

 

Node는 방의 아이디와 방의 중간점을 위치로 거리를 계산하기 위해서 중간위치를 가지게 했다.

 

먼저 간선을 직접 만드는 방법을 택했다. 모든 정점에 대해서 각 정점이 다른 모든 정점과 간선이 있다고 가정한다.

 

그 후 정렬하고, 

말했듯이 사이클이 생기지않으면 mst에 추가하고 그렇지않으면 넘긴다. 

 

다음은 UnionFind.cs 이다.

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using UnityEngine;

public class Edge : IComparable<Edge>
{
    public int V1, V2; // 방 ID
    public float Weight; // 가중치 (유클리드 거리)

    public Edge(int v1, int v2, float weight)
    {
        V1 = v1;
        V2 = v2;
        Weight = weight;
    }

    public int CompareTo(Edge other)
    {
        return Weight.CompareTo(other.Weight);
    }
}

public class UnionFind
{
    private int[] parent, rank;

    public UnionFind(int size)
    {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++)
        {
            parent[i] = i;
        }
    }

    int Find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = Find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    public bool Union(int x, int y)
    {
        int px = Find(x), py = Find(y);
        if (px == py) return false; // 이미 같은 집합 (사이클)
        if (rank[px] < rank[py]) parent[px] = py;
        else if (rank[px] > rank[py]) parent[py] = px;
        else
        {
            parent[py] = px;
            rank[px]++;
        }
        return true; // 연결 성공
    }
}

(Edge클래스는 사실 크루스칼 클래스에 있는게 더 적합해보이긴한다.)

 

만약 코드를 보고 이해가 잘안된다면 직접 그려보거나 그림으로 설명하는 다른 블로그의 글을 보기 바란다. 

처음에 코드만 보고는 이해가 어려울 것이다. 

 

Find 함수는 해당 노드의 루트노드가 어딘지를 찾아준다. 

Union 함수는 둘을 합칠 수 있는지를 보고 둘을 합칠 수 있으면 기존에 같은 사이클이 아니었다는 뜻이므로 true를 리턴하고 

크루스칼 쪽에서 mst에 추가하게 된다.

 

parent 배열은 i 정점의 부모 정점이 parent[i] 라고 보면된다. 

이 때, find를 통해서 루트를 찾게 되는데 parent에는 바로 위 부모가 아니라 루트를 저장해야 나중에 연산 효율이 떨어지지 않는다. 

따라서 루트를 찾고 그 루트정점은 경로의 모든 정점의 부모로 저장하기 위해 재귀를 사용한다.

 

rank 배열은 그냥 합치다보면 트리의 깊이가 아주 깊어져서 비효율적이게 될 수 있기 때문에 rank에 해당 정점을 루트로 했을 때 트리의 깊이를 저장한다. 그래서 트리의 깊이가 더 깊은 쪽에 더 얕은 쪽을 추가해서 트리의 깊이가 깊어지는 속도를 줄일 수 있다고 한다. 

 

그래서 이것들을 사용해서 크루스칼 알고리즘을 실행해보면 mst 를 얻을 수 있다.

 

추후에 이것들을 통해서 복도를 생성하면 된다. 

이것에 관해서는 또 고민할 것들이 많아서 한 번 끊었다.

 

우선 GizmoDraw 를 통해서 초록색 선을 연결해보았다.