Chapter 3-2. 미로 생성 알고리즘(Binary Tree, Side Winder)
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
Chapter 3. 미로 준비
가장 자리만 벽으로 하는 것이 아닌, 진짜 미로처럼 벽을 배치해 보자.
- 미로 생성 알고리즘
- Binary Tree
- Side Winder
- 이 두개 말고도 많지만 이 두개만 배움!
🚖 미로 만들 준비
1️⃣ 가장 자리는 벽으로
public void Initialize(int size)
{
_tile = new TileType[size, size];
_size = size;
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x == 0 || x == _size - 1 || y == 0 || y == size - 1)
_tile[y, x] = TileType.Wall;
else
_tile[y, x] = TileType.Empty;
}
}
}
- 1️⃣ 가장 자리는 모두 갈 수 없는 벽으로 지정
2️⃣ 미로를 뚫기 전, 짝수는 벽으로
public void Initialize(int size)
{
_tile = new TileType[size, size];
_size = size;
// 미로 만들기 전, 길을 다 막아버리는 작업
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0 )
_tile[y, x] = TileType.Wall;
else
_tile[y, x] = TileType.Empty;
}
}
}
- 2️⃣ 짝수번 째 타일은 모두 벽으로 만든다.
- 이렇게 하면 벽이 아닌 곳(초록 타일들)은 모두 사방의 벽으로 둘러 싸이게 된다.
- 가장 자리 1️⃣ 도 다 벽으로 막힘 (짝수니까)
- 이 상태에서 초록 타일을 기준으로 오른쪽 혹은 아래쪽으로 랜덤하게 둘 중 하나의 방향이 있는 벽을 초록색으로 만들어 뚫어 줄 것이다.
- 👉 BinaryTree 방식의 미로를 만들기 !
🚖 Binary Tree 알고리즘
갈 수 있는 타일 하나의 입장에서 오른 쪽, 아래 쪽 2 개의 벽 중 하나를 랜덤하게 선택하여 갈 수 있는 타일로서 바꿔준다.
- 즉, 랜덤하게 두 방향 중 하나를 선택해 길을 뚫어 줌
// 미로 만들기 전, 길을 다 막아버리는 작업
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0 )
_tile[y, x] = TileType.Wall;
else
_tile[y, x] = TileType.Empty;
}
}
// 길을 반반 확률로 뚫는 작업
Random rand = new Random();
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if(rand.Next(0, 2) == 0) // 0, 1 중 랜덤하게 하나를 뽑음
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽 뚫기
}
else
{
_tile[y + 1, x] = TileType.Empty; // 아래 뚫기
}
}
}
- 갈 수 있는 타일을 기준으로 하여 오른쪽 아래쪽 벽을 선택 하여 둘 중 하나를 더 이상 벽이 아닌 갈 수 있는 길로서 바꿔 줌
- 짝수 행, 짝수 열인 타일은 벽이므로
continue- 갈 수 있는 타일의 기준에서 선택해야 하므로.
- 0, 1 중 랜덤하게 0 을 뽑았다면
- 현재 타일의 기준에서 오른쪽 벽을 갈 수 있는 길로 뚫는다.
_tile[y, x + 1] = TileType.Empty;
- 현재 타일의 기준에서 오른쪽 벽을 갈 수 있는 길로 뚫는다.
- 0, 1 중 랜덤하게 1 을 뽑았다면
- 현재 타일의 기준에서 아래 쪽 벽을 갈 수 있는 길로 뚫는다.
_tile[y, x + 1] = TileType.Empty;
- 현재 타일의 기준에서 아래 쪽 벽을 갈 수 있는 길로 뚫는다.
- 짝수 행, 짝수 열인 타일은 벽이므로
완성된 미로
public void Initialize(int size)
{
if (size % 2 == 0)
return;
바이너리 한 작업이고 가장 자리는 항상 벽이어야 하므로 미로의 크기는 홀수여야 한다. 따라서 미로의 크기가 짝수로 입력 됐다면 Initialize(int size) 함수 그냥 처음부터 종료 시킴.
- 가장 자리는 항상 벽이어야 한다.
- 따라서 오른쪽 흰색 선에 위치한 길(x == _size - 2)들은 오른쪽 벽을 길로 뚫어선 안되며
- 아래쪽 흰색 선에 위치한 길 (y == _size - 2)들은 아래쪽 벽을 길로 뚫어선 안된다.
// 길을 반반 확률로 뚫는 작업
Random rand = new Random();
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if (x == _size - 2 && y == _size - 2)
continue;
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty;
continue;
}
if (x == _size - 2)
{
_tile[y + 1, x] = TileType.Empty;
continue;
}
if (rand.Next(0, 2) == 0)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽 뚫기
}
else
{
_tile[y + 1, x] = TileType.Empty; // 아래 뚫기
}
}
}
위처럼 코딩해주니 오른쪽, 아래쪽 가장자리가 이제 뚫리지 않고 전부 벽으로 막히는 것을 확인할 수 있다.
// 오른쪽 벽이 가장 자리이고 동시에 아래 쪽 벽도 가장자리일 경우엔
// 아무런 처리도 하지 않도록 continue
if (x == _size - 2 && y == _size - 2)
continue;
// 아래쪽 벽이 가장 자리인 경우엔
// 아래쪽 벽을 뚫지 않도록 오른쪽 벽을 뚫도록 한 후 continue
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty;
continue;
}
// 오른쪽 벽이 가장 자리인 경우엔
// 오른쪽 벽을 뚫지 않도록 아래쪽 벽을 뚫도록 한 후 continue
if (x == _size - 2)
{
_tile[y + 1, x] = TileType.Empty;
continue;
}
🚖 Side Winder 알고리즘
void GenerateBySideWinder()
{
// 길을 다 막아버리는 작업
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
_tile[y, x] = TileType.Wall;
else
_tile[y, x] = TileType.Empty;
}
}
// 길을 반반 확률로 뚫는 작업
Random rand = new Random();
for (int y = 0; y < _size; y++)
{
int count = 1; // 연속해서 몇 개의 오른쪽 벽을 길로 뚫었는지
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if (x == _size - 2 && y == _size - 2)
continue;
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty;
continue;
}
if (x == _size - 2)
{
_tile[y + 1, x] = TileType.Empty;
continue;
}
if (rand.Next(0, 2) == 0)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽 뚫기
count++;
}
else
{
int randomIndex = rand.Next(0, count);
_tile[y + 1, x - randomIndex * 2] = TileType.Empty; // 아래 뚫기
count = 1;
}
}
}
}
int count = 1; // 연속해서 몇 개의 오른쪽 벽을 길로 뚫었는지
// ...
if (rand.Next(0, 2) == 0)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽 뚫기
count++;
}
else
{
int randomIndex = rand.Next(0, count); // 0 ~ (count - 1) 에서 랜덤한 정수 뽑기
_tile[y + 1, x - randomIndex * 2] = TileType.Empty; // 아래 뚫기
count = 1;
}
아래를 뚫어야 하면 해당 타일의 아래 벽을 뚫는 것이 아니라, 오른쪽으로 연속되어 뚫어왔던 벽들 중에서 랜덤으로 하나를 선택한 타일의 아래 벽을 뚫는다.
- 오른쪽을 뚫기로 했을 땐
count를 증가시킨다.- 연속으로 몇 개의 오른쪽 벽을 뚫었는지를 담게 된다.
- 초기값은 1
- 아래쪽을 뚫기로 했을 땐 👉 여태까지 오른쪽 벽을 뚫기로 결정해 왔던 초록 타일 중에서 랜덤하게 하나를 선태갛여 그 타일의 아래 벽을 뚫는다.
- 미로 만들기 전부터 초록색이었던, 즉 벽을 뚫는 기준이 되는 초록 타일들은 벽 하나를 두고 띄엄 띄엄 있으므로
x - randomIndex * 2열에 위치한 타일의y + 1아래 벽을 뚫으면 된다. count는 다시 1 로 초기화. 지금부터 다시 셈.
- 미로 만들기 전부터 초록색이었던, 즉 벽을 뚫는 기준이 되는 초록 타일들은 벽 하나를 두고 띄엄 띄엄 있으므로
- 그 외의 작업은 다 Binary Tree 알고리즘과 동일
- Binary Tree 알고리즘 방식을 베이스로 하여, 아래를 뚫을 땐 랜덤하게 또 고른다는 방식이 추가된 것 같다.
🚖 두 알고리즘의 장 단점
- 장점
- 간단 하다. 그저 둘 중 하나를 선택.
- 단점
- 모양이 치우쳐진다.
- 가장 자리를 벽으로 보장하기 위하여 오른쪽 벽이 가장 자리이면 아래 쪽을 뚫고, 혹은 아래 쪽 벽이 가장자리일 경우엔 오른쪽 벽을 뚫기 때문에 x == _size - 2 혹은 y == _size - 2 에 해당하는 타일들은 항상 전부 길로 뚫리는 모양의 미로가 나오게 된다.
- 모양이 치우쳐진다.
🚖 코드 정리
public void Initialize(int size)
{
if (size % 2 == 0)
return;
_tile = new TileType[size, size];
_size = size;
// GenerateByBinaryTree();
GenerateBySideWinder();
}
void GenerateBySideWinder()
{
// 길을 다 막아버리는 작업
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
_tile[y, x] = TileType.Wall;
else
_tile[y, x] = TileType.Empty;
}
}
// 길을 반반 확률로 뚫는 작업
Random rand = new Random();
for (int y = 0; y < _size; y++)
{
int count = 1; // 연속해서 몇 개의 오른쪽 벽을 길로 뚫었는지
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if (x == _size - 2 && y == _size - 2)
continue;
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty;
continue;
}
if (x == _size - 2)
{
_tile[y + 1, x] = TileType.Empty;
continue;
}
if (rand.Next(0, 2) == 0)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽 뚫기
count++;
}
else
{
int randomIndex = rand.Next(0, count);
_tile[y + 1, x - randomIndex * 2] = TileType.Empty; // 아래 뚫기
count = 1;
}
}
}
}
void GenerateByBinaryTree()
{
// 길을 다 막아버리는 작업
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
_tile[y, x] = TileType.Wall;
else
_tile[y, x] = TileType.Empty;
}
}
// 길을 반반 확률로 뚫는 작업
Random rand = new Random();
for (int y = 0; y < _size; y++)
{
for (int x = 0; x < _size; x++)
{
if (x % 2 == 0 || y % 2 == 0)
continue;
if (x == _size - 2 && y == _size - 2)
continue;
if (y == _size - 2)
{
_tile[y, x + 1] = TileType.Empty;
continue;
}
if (x == _size - 2)
{
_tile[y + 1, x] = TileType.Empty;
continue;
}
if (rand.Next(0, 2) == 0)
{
_tile[y, x + 1] = TileType.Empty; // 오른쪽 뚫기
}
else
{
_tile[y + 1, x] = TileType.Empty; // 아래 뚫기
}
}
}
}
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기