글에 앞서, 본 글은 인프런의 강좌 'C#과 유니티로 만드는 MMORPG 게임 개발 시리즈'를 수강 후 작성한 정리글임을 밝힙니다.
이 글에서는?
2차원 배열에서의 미로를 자동으로 만드는 알고리즘, 그 중 Binary Tree Algorithm에 대해 알아볼 것 입니다. 우리가 아는 자료구조, 이진 트리와는 큰 관계가 없습니다.
Binary Tree Algorithm?
n by n의 이차원 배열에서 자동으로 미로를 생성하는 알고리즘 중 하나인데, 전처리를 해서 만든 맵에서 오른쪽 혹은 아래로만 길을 뚫어 각각의 빈칸이 오른쪽 혹은 아래라는 두 자식 중 하나를 선택하게 하는 느낌의 미로 생성 알고리즘이다. 말로만 해서는 무슨 이야기인지 잘 이해가 되지 않을텐데, 한번 순차적으로 설명해보겠다.
전처리
먼저, 이 알고리즘을 쓰려면 n by n의 2차원 배열을 만든 뒤, 인덱스에 짝수가 있는 칸을 모두 못지나가도록 막아야한다. 이 과정을 처리한 맵은 다음과 같다.
빨간색은 못지나가는 벽, 그리고 푸른색은 지나갈 수 있는 칸이다. 이와 같이 x와 y가 모두 홀수 일때만 지나갈 수 있도록 전처리를 해두는 것이다.
여기서, x와 y가 모두 '홀수' 이어야한다는 점 때문에 n by n에서 n이 홀수인 경우엔 쓸 수 없는 알고리즘이다...
위와 같은 전처리를 하는 코드를 보도록 하자.
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (j % 2 == 0 || i % 2 == 0)
tile[i, j] = TileType.Wall;
else
tile[i, j] = TileType.Empty;
}
}쉬운 이해를 위해서, 최대한 변수명 등을 보기만 해도 알 수 있도록 코드를 짰다.
TileType 은 맵에 들어갈 수 있는 요소를 정의해둔 enum 인데, 굳이 저 형태를 이해하려고 하진 않아도 된다. 그냥 저 조건에서는 Wall 을 넣었고, 아니라면 Emtpy 를 넣어줬다는 것만 봐도 대충 여러분이 직접 코드를 짤 때 어떻게 해야할지 알 것이라고 믿는다.
아무튼 위 코드를 이용해서 우리가 미로로 쓸 맵을 전처리를 해준다. 이제부터, 저 '푸른색' 칸을 가지고 오른쪽을 뚫을지- 혹은 아래로 뚫을지, 다시 배열을 순회할 것이다.
자세한 구현
기본적으로, 나는 반반의 확률로 뚫도록 만들었다. C#에서는 다음과 같은 코드를 통해 한줄로 반반 확률로 bool 값을 리턴하는 메소드를 만들 수 있다.
private static Random rand = new Random();
private bool GetRandomBoolean()
{
return rand.NextDouble() < 0.5;
}C#의 Random 클래스에서는 NextDouble() 이라는 메소드를 제공하는데, 이 메소드는 0.0부터 1.0까지의 랜덤한 double 값을 리턴한다. 따라서, 저런식으로 코드를 짜두면 반반 확률로 true 와 false 를 받아낼 수 있다.
제,,, 간단한 팁입니다,,,
어쨌거나, 이제 저 반반의 확률로 아까 만든 푸른색 칸에서 오른쪽을 뚫거나 아래를 뚫을 것이다.
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (i % 2 == 0 || j % 2 == 0)
continue;
if (GetRandomBoolean())
{
tile[i, j + 1] = (int) TileType.Empty;
}
else
{
tile[i + 1, j] = (int) TileType.Empty;
}
}
}짜잔. 반반의 확률로 true 일 때는 오른쪽을 뚫어줬고, false 일 때는 아래를 뚫어줬다.
위에 있는 if문이 무엇인가, 하는 사람이 있을 것이다. 별건 아니고, 그냥 아까 벽으로 막아뒀던 부분은 그냥 처리하지 않고 스킵을 한 것이다.
이제 이 결과물을 한번 보도록 하자.
미로가 나오긴 했는데, 뭔가 조금 엉성한 느낌이 든다. 빈칸이 여러 곳으로 나가기도 하고, 난 뭔가... 왼쪽이랑 위쪽 벽처럼 오른쪽 벽과 아래쪽 벽도 막혀있으면 좋겠다. 그래서 다음과 같은 처리를 추가 할 것이다.
if (i == size - 2)
{
tile[i, j + 1] = (int) TileType.Empty;
continue;
}
if (j == size - 2)
{
tile[i + 1, j] = (int) TileType.Empty;
continue;
}짜잔. 얘네를 GetRandomBoolean() 을 이용하는 부분 위에다 넣을건데, size - 1은 벽 부분이고, size - 2는 벽에 붙어있는 그 옆 칸이다. 그 칸에서 옆이나 아래를 뚫어버리면 벽 부분을 뚫게 되는거니까, 만약 내가 오른쪽 벽에 붙어있는 칸이라면 아래로 뚫고, 아래쪽 벽에 붙어있는 칸이라면 오른쪽으로 뚫는 것이다.
그럼 이 결과물은 어떻게 될까?
짜잔. 아래쪽과 오른쪽 벽 옆에 일자로 긴 빈칸이 생겼다. 하지만 아무튼... 아래쪽과 오른쪽 벽도 막았다. 근데 오른쪽 구석에 빈칸이 생겼는데, 이거는 사람마다 막는 사람의 자유 아닐까? 아무튼 난 막아줬다.
if ((i % 2 == 0 || j % 2 == 0) || (i == size - 2 && i == j))
continue;if문의 왼쪽 괄호는 아까 말해줬던, 짝수 인덱스가 있던 칸을 패스하는 것이고- 오른쪽 괄호가 현재 추가된 조건인데, x값이 끄트머리 옆 칸이고, y값 또한 x값과 같은 상태.
즉, x값과 y값이 다 끄트머리 옆 칸일 때 스킵해준다. 이로써 오른쪽 끄트머리에 구멍을 안낼 수 있다. 이 결과물을 보자.
구멍을 막았다. 짜잔!
우리는 이처럼 미로를 만들어보았다. 간단한 미로를 만드는데는 이정도 알고리즘을 쓸 수 있다는 것, 알게 되었길 바랍니다.
총정리
- Binary Tree Algorithm은 x와 y가 모두 홀수인 칸에서 오른쪽 혹은 아래 둘 중 하나를 뚫는 간단한 미로 생성 알고리즘이다.
- 모든 벽면을 막으려고 할 때, 아래쪽과 오른쪽 벽 옆 칸들이 쭉 비어버리는 문제가 생긴다. 개발자의 재량에 따라 어찌저찌 해결할 수는 있다.
n by n의 2차원 배열에서, n이 홀수일 때는 이용할 수 없다.- 이진트리와는 큰 관련이 없다.
오늘도 부족한 설명, 부족하고 긴 글 읽어주셔 감사합니다. 언제나 피드백과 질문은 환영하고 있으며, 다음에는 더 나은 퀄리티의 글로 찾아뵙겠습니다.
고등학생 게임 개발자 김선민이었습니다.
