대표적인 미로 생성 알고리즘 2가지
미로 생성 알고리즘은 컴퓨터 그래픽스, 게임 개발, 데이터 시각화 등에서 다양하게 활용되는 기술이다. 특히, 알고리즘에 따라 미로의 형태와 특징이 달라지기 때문에 그 원리를 이해하는 것이 중요하다. 이번 포스팅에서는 대표적인 미로 생성 알고리즘 중 두 가지인 Binary Tree와 Sidewinder를 소개하며, 각 알고리즘의 동작 방식과 구현 아이디어를 간략히 살펴보겠다.
Binary Tree 알고리즘
Binary Tree 알고리즘은 가장 간단한 미로 생성 알고리즘 중 하나로, 그리드 기반의 미로를 생성한다. 미로의 모양이 단조롭다는 단점이 있고, 이는 아래의 SideWinder 알고리즘으로 보완할 수 있다.
단계는 다음과 같다.
초기화
홀수 행과 홀수 열을 빈 공간으로 설정하고, 짝수 행과 짝수 열은 벽으로 설정한다. 격자 무늬의 맵이 생성된다.벽 뚫기 시작
홀수 행과 홀수 열에 위치한 셀에서만 벽 뚫기를 진행한다. 도착지가 위치한 행과 열은 모두 뚫어 길을 만든다.
벽 뚫기 방향은 [ 아래 ] 와 [ 오른쪽 ] 두 가지 이고, Random 클래스를 이용하여 각각 50% 확률로 뚫는다.
생성된 미로 예시
C# 코드
void BinaryTree()
{
// 1. 짝수 행과 짝수 열은 모두 막는다
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (y % 2 == 0 || x % 2 == 0)
Tile[y, x] = TileType.Wall;
else
Tile[y, x] = TileType.Empty;
}
}
// 2. 벽을 뚫기 시작한다
// 벽은 아래/오른쪽 중 랜덤으로 뚫는다
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
// 벽 뚫기 작업은 빈 공간에서만 진행한다
// 짝수 행과 짝수 열은 벽이므로 진행 불가하다
if (y % 2 == 0 || x % 2 == 0)
continue;
// 도착지인 경우
if (y == DestY && x == DestX)
continue;
// 도착지와 행이 일치하는 경우
// 이 행의 벽을 전부 뚫어야 미로 완성
if (y == DestY)
{
Tile[y, x + 1] = TileType.Empty;
continue;
}
// 도착지와 열이 일치하는 경우
// 이 열의 벽을 전부 뚫어야 미로 완성
if (x == DestX)
{
Tile[y + 1, x] = TileType.Empty;
continue;
}
// 각 0.5의 확률로 빈 공간에서 아래 or 오른쪽으로 벽을 뚫는다
Random rand = new Random();
if (rand.Next(0, 2) == 0)
{
// 오른쪽 벽을 뚫기
Tile[y, x + 1] = TileType.Empty;
}
else
{
// 왼쪽 벽을 뚫기
Tile[y + 1, x] = TileType.Empty;
}
}
}
}SideWinder 알고리즘
Binary Tree 알고리즘보다 더 복잡한 미로를 생성한다. 경로가 랜덤하게 오른쪽으로 이어지거나 아래쪽으로 내려가면서, 균형 잡힌 미로 구조를 만들 수 있다.
단계는 다음과 같다.
-
초기화
홀수 행과 홀수 열을 빈 공간으로 설정하고, 짝수 행과 짝수 열은 벽으로 설정한다. 격자 무늬의 맵이 생성된다. -
벽 뚫기 시작
마찬가지로, 홀수 행과 홀수 열에 위치한 셀에서만 벽 뚫기를 진행한다. 도착지가 위치한 행과 열은 모두 뚫어 길을 만든다. 벽 뚫기 방향은 [ 아래 ] 와 [ 오른쪽 ] 두 가지 이고, Random 클래스를 이용하여 각각 50% 확률로 뚫는다.
차이점은, 오른쪽으로 벽을 뚫다가 지금까지 뚫어온 벽 중 하나를 랜덤하게 선택하여 해당 위치에서 아래쪽 벽을 뚫는다.
미로 생성 예시
C# 코드
void GenerateBySideWinder()
{
// 1. 짝수 행과 짝수 열은 모두 막는다
for (int y = 0; y < Size; y++)
{
for (int x = 0; x < Size; x++)
{
if (y % 2 == 0 || x % 2 == 0)
Tile[y, x] = TileType.Wall;
else
Tile[y, x] = TileType.Empty;
}
}
// 2. 벽을 뚫기 시작한다
// 벽은 아래/오른쪽 중 랜덤으로 뚫는다
for (int y = 0; y < Size; y++)
{
// count는 반드시 x for 문 바깥에 선언되어야 한다 - out of range 오류
int count = 1;
for (int x = 0; x < Size; x++)
{
// 벽 뚫기 작업은 빈 공간에서만 진행한다
// 짝수 행과 짝수 열은 벽이므로 진행 불가하다
if (y % 2 == 0 || x % 2 == 0)
continue;
// 도착지인 경우
if (y == DestY && x == DestX)
continue;
// 도착지와 행이 일치하는 경우
// 이 행의 벽을 전부 뚫어야 미로 완성
if (y == DestY)
{
Tile[y, x + 1] = TileType.Empty;
continue;
}
// 도착지와 열이 일치하는 경우
// 이 열의 벽을 전부 뚫어야 미로 완성
if (x == DestX)
{
Tile[y + 1, x] = TileType.Empty;
continue;
}
Random rand = new Random();
// 각 0.5의 확률로 아래 or 우측 벽을 뚫는다
if (rand.Next(0, 2) == 0)
{
// 우측 벽을 뚫는다
Tile[y, x + 1] = TileType.Empty;
// 뚫은 우측 벽의 개수
count++;
}
else
{
// 뚫어온 우측 벽들 중 한 위치를 선택하여 아래로 뚫는다
int randIdx = rand.Next(0, count);
Tile[y + 1, x - randIdx * 2] = TileType.Empty;
// count는 rand 사용을 위해 1이어야 한다
count = 1;
}
}
}
}[ 참고한 강의 ] Rookiss - MMORPG Part2
