랜덤 미로 생성 알고리즘 정리

이전 포스팅에서는 경어체를 사용했지만 긴 글을 쓰기에는 불편해서 낮춤말로 쓰려고 합니다. 이 점 양해 바랍니다.

 

 

동아리에서 미로에 관한 이야기를 하다가 동아리 선배가 미로를 생성하는 데에는 많은 알고리즘이 있다고 이야기했다. 나는 또 그런 이야기를 들으면 못 참는 성격이라서 직접 자료를 찾아보니, 당장 인터넷에만 해도 무려 한글(!) 미로 생성 알고리즘도 많아 놀라웠다.

참고할 만한 자료도 적당히 있어서 가볍게 공부하기에 적당한 주제인 데다가 도전 욕구를 자극하는 소재였다.

그래서 간단하게 유니티를 랜덤 미로 생성을 만들어보기로 했다.

 

http://www.jamisbuck.org/mazes/

Maze Algorithms

 

이번 글에서는 유니티 프로젝트에 앞서 랜덤 미로 생성 알고리즘들을 이해하기 쉽게 정리하려고 한다. 미로 생성 알고리즘의 종류와 그 설명은 위 링크를 번역하여 가져왔다. 이번 포스팅에서 공부한 내용을 기반으로 유니티 프로젝트에 직접 적용해볼 것이다.

 

1. 재귀적 백트래킹 알고리즘 (Recursive Backtracking)

1-1. 백트래킹

백트래킹을 우리말로 쓰려고 했는데, 우리말로는 퇴각 탐색이라고 하더라. 직관적이지 않은 점에서는 영단어나 우리말이나 비슷해서 여기서는 백트래킹이라 칭하기로 했다.

 

백트래킹(Backtracking) 알고리즘은 조건을 만족하는 모든 조합을 찾아내어 해를 찾아내는 알고리즘을 말한다.

답이 될 만한 모든 조합을 하나 하나 찾다가, 이게 문제의 해가 될 것 같지 않다고 판단되면 이전 과정으로 돌아가는 과정을 반복해서 해를 얻어내는 것이다.

 

예를 들어서 고등학교 확률과 통계 과목에는 경우의 수를 찾을 때에 가지치기를 하며 모든 경우의 수를 세아린다. 아래와 같이, 모자, 상의, 하의를 입는 모든 경우의 수를 찾아낸다고 해보자.

 

즉석으로 그려낸 모자, 상, 하의

 

 

DFS 방식으로 가지치기하는 그림

 

모자를 쓰는 경우에서 두 개의 가지로 나뉘고, 상의를 입는 과정에서 가지가 더 나누어지고, 마침내 마지막에는 하의를 입는 과정에서 가지를 또 나눌 수 있다.

 

우리는 위와 같이 가지치기를 하면서 모든 경우의 수를 중복 없이 쉽게 구할 수 있다. 가지치기는 컴퓨터과학 분야에서는 트리에 해당하는데, 가지를 하나 하나 치는 과정이 트리에서는 새로운 경우의 노드를 방문하는 것에 해당한다고 볼 수 있겠다.

 

즉, 이 이야기대로라면 경우의 수를 나타내는 트리를 모두 방문할 수만 있다면 모든 경우의 수를 찾아낼 수 있다는 것이다.

 

백트래킹은 이러한 방식으로 문제를 해결해 간다.

백트래킹은 모든 경우를 찾아가며 해를 찾기 때문에 트리에 적합한 알고리즘이다. 트리 혹은 그래프에서는 BFS와 DFS를 통해 모든 노드를 방문할 수 있는데, 그중에서도 백트래킹에서는 DFS 방식을 사용한다.

 

위 그림에서는 DFS 방식으로 트리(가지)를 방문하고 있다.

A->A1->A1-1까지 탐색을 한 후 더 이상 선택할 것이 없으니 이전 항목인 A1으로 돌아간다.

A1->A1-2 과정을 거쳐 두 번째 항목인 A1-2를 찾아낸다. 또 선택할 것이 없으니 A1->A로 돌아간다.

이 과정을 반복해서 더 이상 선택할 경우가 없을 때까지 진행하면 모든 경우의 수를 찾아낼 수 있다.

 

1-2. 재귀적 백트래킹을 이용한 미로 생성

미로를 생성할 때에는 재귀적 백트래킹 방식을 자주 사용한다고 한다. 특징은 다음과 같다.

 

장점 : 다른 알고리즘보다 직관적이고 이해하기 쉬우며 구현하기도 쉽다.

단점 : 메모리 공간을 많이 사용한다. 미로의 크기에 따라 스택 사이즈가 커져서 큰 미로 생성에 부적합하다.

(다만 대부분은 크게 신경쓸 정도가 아니니 해당 알고리즘으로도 충분하다)

 

백트래킹 알고리즘을 이용한 미로는 다음과 같은 과정으로 만드는데, 방법 자체는 의외로 간단했다.

 

1. 미로 맵에서 시작점을 정한다.

2. 랜덤하게 해당 노드에서 깎을 벽(4방향이라면 동서남북 중 한 방향) 하나를 골라서, 해당 방향의 인접한 칸을 아직 방문한 적이 없다면 그 칸으로 이동한다.

3. 모든 인접한 칸을 이미 방문했었다면, 깎을 벽이 남아 있는 가장 최근 칸으로 돌아가서 2번 과정부터 다시 반복한다.

(간단하게 말해서, 주변 칸 중 갈 수 있는 칸이 없다면 이전 칸으로 돌아가는 것이다. 그 칸에서 깎을 벽이 남아 있다면 깎으면 되고, 깎을 벽이 남아 있지 않다면(즉 갈 수 있는 칸이 없다면) 그 전 칸으로 다시 돌아가는 것이다. 그렇게 깎을 벽을 찾을 때까지 이전의 칸으로 돌아간다.)

4. 그렇게 시작 지점까지 돌아가면 해당 알고리즘을 종료한다.

 

요약하자면 계속 랜덤한 방향으로 길을 만들어내다가 미로 벽 끝에 도달하거나 이전에 만든 길과 마주치게 되면, 공터를 찾아서 되돌아가는 것이다. 시작 지점까지 돌아갔다는 건 더 만들 수 있는 길이 없다는 뜻이므로 미로는 완성이다.

 

 

2. 엘러의 알고리즘(Eller's Algorithm)

엘러 알고리즘은 가장 빠른 미로 생성 알고리즘 중 하나이고 무한한 크기의 미로를 선형 시간에 생성할 수 있는 유일한 알고리즘이다. 즉, 미로의 크기가 n이라 치면 O(n)의 시간에 계산할 수 있다는 것이다. 저자 말대로 엄청난 성능을 갖지만 그 방법 또한 그 성능만큼이나 처음 들으면 이해가 잘 안 되는 알고리즘이다.

 

엘러의 알고리즘에서는 미로를 생성하는 과정에서, 집합을 이용해서 궁극적으로 두 열이 같은 공간에 있는지를 계속 추적한다. 무슨 말이냐 하면 같은 집합에 속한 칸끼리는 연결된 부분으로 보겠다는 것이다. 같은 집합끼리는 좀 길을 돌아서 가더라도 두 칸 사이에 길이 이어져 있고, 다른 집합끼리는 연결된 길이 존재하지 않는 것이다.

 

엘러의 알고리즘은 한 번에 미로의 행 하나를 생성한다. 각 미로 행을 두 번 이상 볼 필요는 없다. 모든 행을 생성하고 나면 엘러의 알고리즘은 언제나 완벽한 미로, 어디로든 이어지는 미로가 완성된다.

 

각 행을 여러 번 볼 필요가 없기 때문에 O(n)의 선형 시간을 갖는다고 보면 되겠다.

아래엔 엘러의 알고리즘을 이용해 미로를 생성하는 과정을 정리해놓았다.

 

 

1번 과정 : 새로운 집합 할당하기

1. 첫 번째 행의 칸들이 각각의 집합에 속하도록 초기화한다.

위의 칸들이 첫 번째 행이라고 하면 각각 1번 집합, 2번 집합, 3번 집합, 4번 집합, 5번 집합에 할당한다.

실제로 칸에다가 숫자가 들어가는 건 아니고, 예시에서 서로 속한 집합이 어디인지를 보이는 수단으로 숫자를 사용하는 거다. 서로 다른 집합에 들어간다고 보면 된다.

 

 

2번 과정 : "랜덤하게" 합치기

2. 랜덤하게 인접한 칸들을 골라서 같은 집합 내에 없다면 이를 연결한다. 그리고 인접한 칸이 속한 집합들을 하나의 집합으로 합쳐서 그 집합들에 있는 모든 칸이 연결되어 있다고 표시해준다.

여기서 연결되어 있다는 것은 그 집합의 두 칸 사이에 연결된 길(path)이 존재한다는 뜻이다.

1번에서는 서로 벽으로 연결되어 있던 칸들이 집합이 합쳐지면서 같은 집합끼리는 벽을 허물고 영역을 합치게 되었다. 이에 따라 같은 집합끼리는 서로 연결되게 되었다.

 

3번 과정 : 수직으로 내리기

3. 각 집합마다 랜덤하게 수직 아래 방향으로 다음 행으로 가는 연결을 만든다. 남아있는 모든 집합은 최소 하나 이상의 수직 연결을 만들어서 미로가 연결되게 해야 한다.

 

 

4번 과정 : 새로운 집합 할당하기

4. 다음 행에서 남은 칸들을 각각 새로운 집합에 넣어준다. 단 기존에 존재하는 집합과는 다른 집합이어야 한다.

1번 과정과 유사하게 집합을 초기화하는 셈이다.

 

5. 마지막 행에 도달할 때까지 위 과정을 반복한다.

 

6. 마지막 행의 경우, 집합을 공유하지 않는 모든 인접 셀을 연결한다. 이미 마지막 행이므로 수직 방향으로 길을 연결하지 않고 끝내면 된다.

 

마지막 행을 추가한 직후

 

 

마지막 행에 있는 모든 인접칸이 집합이 다르므로 같은 집합으로 통합하면서 모두 연결시킨다. 만약 인접 칸이 같은 집합이면 이미 연결되어 있으므로 따로 작업을 수행하지 않는다.

 

여기까지 하면 미로가 모두 생성된 것이고 과정도 끝이다!

 

이 과정이 언제나 완전한 미로를 생성하는 것에 관한 증명은 원문의 Analysis 파트에서 확인할 수 있다. 그래프와 관련된 지식을 선행하므로 이를 모른다면 이해하기 어려울 수 있다.

밑에 원문의 링크를 달아놨으니 필요하다면 참고하자.

(Maze Generation: Eller's Algorithm - http://weblog.jamisbuck.org/2010/12/29/maze-generation-eller-s-algorithm)

 

 

 

최소 신장 트리(MST; Minimal Spanning Tree)를 이용한 알고리즘(크루스칼 알고리즘, 프림 알고리즘)은 나중에 생각나면 올릴 예정이다. 언제 올릴지는 모르겠다...