절차적 맵 생성
절차적 맵 생성(Procedural Map Generation)은 컴퓨터 알고리즘을 사용하여 게임 맵을 자동으로 생성하는 기술입니다. 이 방법은 동적이고 예측할 수 없는 환경을 제공해 게임의 재미와 재사용 가능성을 크게 향상시킵니다.
로그라이크 게임에서 매번 새로운 맵을 만들 때, 오픈월드 게임에서 넓은 맵을 비교적 적은 시간으로 제작할 때 주로 사용됩니다.
장점
무한성 : 난수생성기와 알고리즘에 의해 생성되므로 무한한 수의 맵을 생성할 수 있습니다.
다양성 : 난수, 변수에 따라 다른 맵이 생성되어 플레이어에게 새로운 경험을 제공합니다.
효율성 : 맵을 수동으로 디자인하는 것에 비해 시간/리소스를 절약할 수 있습니다.
단점
예측 불가능 : 때때로 불균형하거나 클리어가 불가능한 맵이 생성될 수 있습니다.
디자인 제어 어려움 : 맵의 특정 부분만 제어하고 싶을 때 어려움이 있습니다.
여기를 보시면 절차적 맵을 어떻게 생성하는지 자세히 설명해주신 분이 계십니다.
그 중 핵심인 Delaunay Triangulation을 포함한 맵 간 연결을 구현하고,
이어서 맵 생성까지 만들어보겠습니다.
Delaunay Triangulation
드로네 삼각분할(Delaunay Triangulation)은 주어진 점 집합을 이용해 삼각형으로 분할하는 방법 중 하나로, 한 삼각형의 외접원 내에 다른 삼각형의 꼭짓점이 존재하지 않는 성질을 가집니다.
이 DT를 구하는 알고리즘 중 하나가 Bowyer-Watson algorithm 입니다.
Bowyer-Watson Algorithm
코드의 양이 많아서 여기선 핵심적인 부분만 설명하겠습니다.
코드 전문을 확인하고 싶으시면 제 Github링크 에 들어가셔서 확인해보시면 될 것 같습니다.
Bowyer-Watson Algorithm의 Pseudo-code 는 위키피디아에서 보실 수 있습니다.
아래는 해당 Pseudo-code를 토대로 만든 함수입니다.
public class DelaunayTriangulation : MonoBehaviour
{
public static HashSet<Triangle> Triangulate(IEnumerable<Vertex> vertices)
{
Triangle superTriangle = CalcSuperTriangle(vertices);
HashSet<Triangle> triangulation = new HashSet<Triangle>
{
superTriangle
};
foreach (var vertex in vertices)
{
HashSet<Triangle> badTriangles = new HashSet<Triangle>();
foreach (var triangle in triangulation)
{
if (triangle.IsInCircumCircle(vertex))
badTriangles.Add(triangle);
}
HashSet<Edge> polygon = new HashSet<Edge>();
foreach (var badTriangle in badTriangles)
{
foreach (var edge in badTriangle.edges)
{
bool isShared = false;
foreach (var otherTriangle in badTriangles)
{
if (badTriangle == otherTriangle)
continue;
if (otherTriangle.HasEdge(edge))
isShared = true;
}
if (!isShared)
polygon.Add(edge);
}
}
triangulation.ExceptWith(badTriangles);
foreach (var edge in polygon)
{
triangulation.Add(new Triangle(vertex, edge.a, edge.b));
}
}
triangulation.RemoveWhere((Triangle t) => t.HasSameVertex(superTriangle));
return triangulation;
}
}
혹시, 위 코드와 Pseudo-code를 따라가도 이해가 안되시면 유튜브에 시각화가 잘 되어있으니 참고하시기 바랍니다. (저는 유튜브 보고 이해했습니다.)
하지만, 저 코드만으로 Delaunay Triangulation을 구현할 수는 없습니다.
일단, 점을 나타내는 Vertex, Vertex 두 개를 잇는 Edge, Vertex 세 개를 갖는 Triangle까지 총 세 개의 클래스를 먼저 만들어봅시다.
1. Vertex, Edge, Triangle
Vertex와 Edge는 구현하는데 큰 어려움이 없습니다.
Equals(+GetHashCode)나 operator<, > 등 필요한 부분 구현하시면 됩니다.
제 기준 어려운 부분은 세 Vertex의 외접원안에 특정 Vertex가 안에 있는지 확인하는 부분 이었습니다.
거리 계산으로 포함관계를 확인하기 위해 외접원의 중심과 반지름을 구해야 합니다.
외접원의 좌표 및 반지름 계산식은 여기를 참고하시기 바랍니다.
public Triangle(Vertex a, Vertex b, Vertex c)
{
// 초기화 코드 생략
// ...
//
float D = (a.x * (b.y - c.y) +
b.x * (c.y - a.y) +
c.x * (a.y - b.y)) * 2;
// 외접원의 x, y좌표
circumCenterX = ((a.x * a.x + a.y * a.y) * (b.y - c.y) +
(b.x * b.x + b.y * b.y) * (c.y - a.y) +
(c.x * c.x + c.y * c.y) * (a.y - b.y)) / D;
circumCenterY = ((a.x * a.x + a.y * a.y) * (c.x - b.x) +
(b.x * b.x + b.y * b.y) * (a.x - c.x) +
(c.x * c.x + c.y * c.y) * (b.x - a.x)) / D;
float dx = a.x - circumCenterX;
float dy = a.y - circumCenterY;
// 반지름 제곱
circumRadius2 = dx * dx + dy * dy;
}
// 주요 함수 생략
// ...
//
// 반지름(제곱)과 중심에서 점까지의 거리 비교
public bool IsInCircumCircle(Vertex v)
{
float dx = v.x - circumCenterX;
float dy = v.y - circumCenterY;
float dis = dx * dx + dy * dy;
return dis < circumRadius2;
}
}
2. CalcSuperTriangle
Psuedo-code를 보시면, Boywer-Watson Algorithm의 첫 시작은 모든 점을 포함하는 아주 큰 삼각형을 만드는 것 부터 시작입니다. 일본의 오니기리를 생각하시면 아이디어를 쉽게 떠올릴 수 있습니다.
검정색 김 부분에 점들이 모여있다고 생각하고, 삼각형 모양의 각 꼭짓점을 구하시면 됩니다.
private static Triangle CalcSuperTriangle(IEnumerable<Vertex> vertices)
{
int minX = int.MaxValue;
int maxX = int.MinValue;
int minY = int.MaxValue;
int maxY = int.MinValue;
foreach(var v in vertices)
{
minX = Mathf.Min(minX, v.x);
maxX = Mathf.Max(maxX, v.x);
minY = Mathf.Min(minY, v.y);
maxY = Mathf.Max(maxY, v.y);
}
int dx = (maxX - minX + 1);
Vertex v1 = new Vertex(minX - dx - 1, minY - 1);
Vertex v2 = new Vertex((minX + maxX)/2, maxY + (maxY - minY) + 1);
Vertex v3 = new Vertex(maxX + dx + 1, minY - 1);
return new Triangle(v1, v2, v3);
}수정 (24.03.31)
테스트를 하던 도중에 SuperTriangle 크기를 구하는 부분에서 논리적 오류가 있었습니다.
SuperTriangle은 무한대에 가까운 값이어야 완전하게 모든 좌표에 대해서 커버가 가능합니다.
아래는 해당 오류가 일어났던 Input입니다.
43 19
44 36
25 37
59 15
10 43 (x)
41 29
45 51
29 72
29 62
25 10 (x)위에 제가 설명한대로만 만들면 해당 테스트케이스에 대해서 이어지지 않은 점이 존재하게 됩니다.
즉, 이대로 Procedural Map Generate 를 진행하면 방 하나만 연결되지 않습니다.
해당 문제를 해결하기 위해 SuperTriangle의 값을 키웠습니다.
Vertex v1 = new Vertex((minX - dx - 1) *2, minY - 1 - (maxY + (maxY - minY) + 1));
Vertex v2 = new Vertex((minX + maxX)/2, (maxY + (maxY - minY) + 1)*2);
Vertex v3 = new Vertex((maxX + dx + 1)* 2, minY - 1 - (maxY + (maxY - minY) + 1));랜덤으로 좌표를 지정했기 때문에 이것도 완전하게 보장되지는 않을 것 같습니다.
예외처리에 대해서는 추후에 던전의 입구 및 출구를 지정할 때, 입구에서 어떠한 방에도 도달할 수 없다면 가장 가까운 방까지의 복도를 생성하도록 구현하겠습니다.
MST (Kruskal Algorithm)
Boywer-Watson algorithm으로 모든 점을 이어줬지만 이대로 던전을 만들게 되면 던전이 복잡해지고 다양성이 적어집니다.
모든 방이 이어지면서도 간선의 수를 줄일 수 있는 최소 스패닝 트리를 이용하고, 랜덤으로 추가적인 간선을 추가해 너무 단순하지도 복잡하지도 않게 이어보겠습니다.
Because we don't want every single room to be linked to every other with a corridor (that would make for a very confusing layout), we then construct a Minimal Spanning Tree using the previous graph.
public static List<Edge> MinimumSpanningTree(IEnumerable<Edge> graph)
{
List<Edge> ret = new List<Edge>();
List<Edge> edges = new List<Edge>(graph);
edges.Sort(Edge.LengthCompare);
HashSet<Vertex> points = new HashSet<Vertex>();
foreach (var edge in edges)
{
points.Add(edge.a);
points.Add(edge.b);
}
Dictionary<Vertex, Vertex> parents = new Dictionary<Vertex, Vertex>();
foreach (var point in points)
parents[point] = point;
Vertex find(Vertex x)
{
if (parents[x] == x) return x;
parents[x] = find(parents[x]);
return parents[x];
}
void Union(Edge edge)
{
var x_par = find(edge.a);
var y_par = find(edge.b);
// 이미 이어진 경우에는 랜덤으로 몇개만 선택
if (x_par == y_par)
{
if (Random.Range(0, 6) == 0)
{
ret.Add(edge);
}
return;
}
ret.Add(edge);
if (x_par < y_par) parents[y_par] = x_par;
else parents[x_par] = y_par;
}
foreach (var edge in edges) Union(edge);
return ret;
}얼핏 보기에는 단순한 Kruskal 같지만 몇가지 주의해야할 점이 있습니다.
주의할 점
- Edge를 크기 순으로 정렬하고 HashSet에 Add하여 중복을 없앱니다.
- 정수가 아닌 Vertex입니다. 위에서 만든 HashSet으로 Dictionary를 만들어 parents를 나타냅니다.
- Union함수에서 부모가 같을 때 확률적으로 ret에 add해서 선형적인 던전이 나오는 경우를 방지했습니다.
마무리
여기까지 Delaunay Triangulation 및 MST에 대해 알아봤습니다.
Github에 오픈소스들 잘 나와있으니, 단순 구현이 목표라면 오픈소스 쓰시는게 좋을 것 같습니다.
다음에는 이 삼각분할을 이용해서 절차적 맵 생성을 구현해보도록 하겠습니다.
참고자료
https://www.reddit.com/r/gamedev/comments/1dlwc4/procedural_dungeon_generation_algorithm_explained/
https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm
https://en.wikipedia.org/wiki/Circumcircle
