public List<(Leaf, Leaf)> GenerateKruskalMST(List<Leaf> leaves, float extraConnectionChance = 0.3f)//최소신장트리 즉 모든 Leaf를 노드로 잡고 각 방의 거리를 오름차순으로 정렬하여 빠짐없이 연결하는 로직
{
List<(Leaf, Leaf, float)> edges = new();
for (int i = 0; i < leaves.Count; i++)
{
for (int j = i + 1; j < leaves.Count; j++)
{
float dist = Vector2.Distance(leaves[i].rect.center, leaves[j].rect.center);
edges.Add((leaves[i], leaves[j], dist));
}
}
edges.Sort((a, b) => a.Item3.CompareTo(b.Item3));//거리에 따라 오름차순 정렬 가까운방부터 순서대로 정렬한다.
Dictionary<Leaf, Leaf> parent = new(); // 유니온-파인드 구조 초기화 쿠르스칼에서 쓰는 방식 Prisma에선 start에서 가장가까운것을 연결하나 연결구조가 좋지않다.
foreach (var leaf in leaves)//딕셔너리에 본인 Leaf를 키값으로 하며 value 값으로 지정 예를 들어 각 방이 있으면 자신이 대장인셈
{
parent[leaf] = leaf;//key값은 현재 졸개 value 값은 대장을 의미
}
Leaf Find(Leaf x)// 유니온-파인드
{
if (parent[x] != x)//x가 현재 자신의 대장이이라면 x를 반환
parent[x] = Find(parent[x]); //x의 대장을 x의 대장의 대장으로 한다. 재귀하여 최종 대장을 찾는다.
return parent[x];//x의 최종 방장을 반환 두 그룹을 연합시킨다.
}
void Union(Leaf a, Leaf b)
{
Leaf rootA = Find(a);//각 멤버의 최종 대장을 찾음
Leaf rootB = Find(b);
if (rootA != rootB)//최종 대장이 다르면 한쪽 대장을 상대 대장으로 지정
parent[rootA] = rootB;
}
List<(Leaf, Leaf)> mstEdges = new();//간선 리스트
List<(Leaf, Leaf)> extraEdges = new();//추가 연결 위한 리스트
foreach (var (a, b, _) in edges)//_는 사용하지 않는다는 의미 아무거나 넣어도 무방 튜플 역시 var()로 통일가능
{
if (Find(a) != Find(b))//a와 b의 총대장이 다를경우
{
Union(a, b);//연합시킴
mstEdges.Add((a, b));//거리가 가장 짧은 leaf 간선부터 연결시키며 모든 노드들이 연결될때까지 반복함
}
else
{
extraEdges.Add((a, b));
}
}
foreach (var (a, b) in extraEdges)
{
if (IsAdjacent(a, b) && UnityEngine.Random.value < extraConnectionChance)
{
mstEdges.Add((a, b)); //30퍼 확률로 연결된 인접한 leaf연결
}
}
return mstEdges;
}
bool IsAdjacent(Leaf a, Leaf b)
{
return a.rect.Overlaps(ExpandRect(b.rect, 1)); //b 크기를 1 늘려서 겹치는지 확인
}
RectInt ExpandRect(RectInt rect, int amount)
{
return new RectInt(rect.x - amount, rect.y - amount, rect.width + 2 * amount, rect.height + 2 * rect.height);
}초기 구성
[A] => A
[B] => B
[C] => C
[D] => D
Find 메서드에선 각 노드의 대표노드를 찾는다 만약 대표노드의 대표노드가 본인일 경우 본인을 return해준다.
즉 각 노드의 최종대표를 찾는 메서드이다.
쿠르스칼 방식에선 각 노드간에 모든 연결을 이중 for문으로 찾아준뒤 거리에 따라 오름차순으로 sort해준다
거리순으로 AB CD AC ... 이라고 했을때
A와 B 유니온
[A] => A
[B] => A
[C] => C
[D] => D
유니온에선 두 노드의 최종대표를 Find 해준뒤 만약 다르다면 B노드의 대표를 A로 바꿔준뒤 연결 정보를 edge에 추가해준다.
A와 B의 대표가 다르므로 B의 대표를 A로 지정 후 A와 B연결 edge 추가
C와 D 유니온
[A] => A
[B] => A
[C] => C
[D] => C
A와 C 유니온
[A] => A
[B] => A
[C] => A
[D] => C
현재 ABCD 모두 최종 대표가 A가 되었으므로 모든 노드가 연결완료 이후 유니온해도 변경사항이나 edge 추가 사항없음
edge List
A,B
C,D
A,C
모든 노드가 연결되었다