미로를 만드는 알고리즘

만약 어렸을 때 미로찾기를 해보고

또 직접 미로를 그려보려한 경험이 있다면

미로를 만드는 게 생각보다 쉽지 않다는 걸 느껴봤을 거야

위 짤처럼 100*100정도의 미로야 대충 어떻게 만들 수도 있겠지만

많은 미로를 만들어야 할 경우나 미로 빠돌이들을 위해 더 복잡한 미로가  필요한 경우엔

시간과 노오력밖에 없는 컴퓨터가 만들어

컴퓨터가 미로를 만드는 방법,

즉 미로 생성의 알고리즘은 여러가지가 있는데 그 중에 몇 개만 간단히 소개할게

- Prim's Algorithm

미로를 만드는 가장 간단하고 직관적인 방법 중 하나야

그 과정을 살펴보면,

(1) 기초가 되는 칸을 랜덤으로 하나 선택한다. 

저 흰색 칸 하나가 지금의 새끼미로라고 할 수 있어

흰색이 선택된 칸, 붉은 색으로 칠해진 인접한 칸에 주목해봐.

(2)  미로에 인접한 칸들 중 랜덤한 칸 하나를 선택하여 확장한다

아까 붉은색이었던 칸이 미로칸으로 된 게 보이지?

이제 저 두 칸이 미로라고 할 수 있어.

사실상 이제 (2)번 과정만 무한 반복하여 미로를 랜덤으로 증식시키는 게 프림 알고리즘의 전부야.

 

그리고 확장되는 칸의 주변엔 벽을 세우는 거야.

이때 오른쪽 짤처럼 미로칸 사이에 생긴 벽이  자연스럽게 생기는 게 보이지?

저 벽이 미로를 어렵게 하는 속임수 역할을 하게 돼

-Hunt-and-Kill Algorithm

이 알고리즘 이름이 왜 'hunt and kill'일까 생각을 해봤는데

아마 아직 미로가 아닌 칸을 추적해서 없앤다는 정도의 뜻인 것 같아

알고리즘을 한 번 살펴보자

(1)  랜덤으로 미로 칸을 하나 선택한다.

시작은 프림알고리즘과 같아

(2) 사방이 막힐 때까지 랜덤으로 이동하며 길을 만든다

여기서 좀 유의할 점은 갈 수 있는 곳이 있다면 반드시 간다 '란 규칙이야

(3) 미로와 맞닿아있는 곳을 찾는다.

 

 위에서 아래로, 왼쪽에서 오른쪽으로 훑으면서 미로와 닿아있는 칸을 찾아

이 경우엔 맨 윗 줄에 4번째 칸이 지금 찾는 칸이 되겠지

(4) (2),(3)번을 남는 칸이 없을 때까지 반복한다.

hunt and kill이란 이름이 붙여진 이유같아.

남는 칸이 있다면 다시 길을 쭉 만들고, 다시 남는 칸을 찾고 무한 반복이야

-Aldous Broder Algorithm

내 생각엔 이 알고리즘이 가장 랜덤의 성질을 잘 이용한 알고리즘 같아

칸 하나로 시작해서

랜덤하게 움직이며 남기는 흔적을 최대한 이용한 게

이 알고리즘의 특징이야.

하지만 작은 규모에서는 복잡하고, 큰 규모에서는 비교적 간단하다는 단점이 있어

알고리즘을 살펴보면

(1) 랜덤하게 미로 칸을 하나 선택한다.

(2) 랜덤하게 움직여서 새로운 미로칸을 만든다.

처음에 선택했던 초록색 칸이 움직이면서 남기는 자취가 바로 미로가 되는 식이야

다만 

미로 칸에서 미로가 아닌 칸으로 움직일 때만

새로운 칸 주변에 벽을 쌓는다는 점에 유의해야해.

   예를 들면 이런 식이지

Aldous Border Algorithm 으로 미로를 생성하는 과정 

5*5 미로

그런데 과정을 보다보면 이 알고리즘을 조금의 단점이 있음을 알 수 있는데

바로 미로를 만드는 과정이 오래 걸린다는 거야.

5*5같은 경우는 초록색 칸이 25구역만 방문하면 되지만

500*500 미로만 되더라도 '랜덤으로 움직이는 칸이 25만 구역을 방문' 해야해

게다가 큰 미로에선 비교적 단순한 구조를 보이므로 작은 미로에만 쓰여

-Wilson's Algorithm

이 알고리즘은 약간 이해하기 어려울 수도 있어. 하지만 상당한 난이도의 미로를 생성하는  알고리즘이고

큰 규모든 작은 규모든 좋은 미로를 만들어내는 알고리즘이야. 

알고리즘을 살펴보면

(1) 기초가 되는 미로를 한 칸 만든다.

(2) 미로가 아닌 칸 하나를 랜덤하게 선택한다.

(3) 미로에 닿을 때까지 랜덤하게 움진인다.

여기서 초록색 칸은 이동하면서 방문했던 칸에 '방향성'을 남겨

이게 무슨 말인지는 다음 순서에서 설명할게

(4)  초록색 칸이 방문했던 칸에 남긴 방향성대로 미로까지 이동하며 칸을 만든다.

초록칸이 방문했던 수많은 곳을 두고

왜 초록칸은 하필 저 경로를 통해 미로까지 갈까?

또 경로는 어떻게 정해지는 걸까?

경로를 정하는 건 방문했던 칸들의 방향성이야.

그냥 그림을 잘 보면서 이해하는 게 빠를 것 같아

위 그림은 랜덤하게 움직이며 방문했던 칸에 방향을 남기는 규칙을 설명한 짤이야

잘보면 노란색칸( gif짤의 초록)이 랜덤하게 움직이면서 지나갔던 방향으로 화살표를 남기지?

노란색 칸이 지나간 방향이 그 칸의 방향성이 되는 거야.

또, 만약 이미 한 번 지나가서 방향성이 있는 곳이라해도

다시 지나가면 원래의 방향성은 사라지고 새로운 방향성이 생겨.

그래서 노란색 칸이 미로에 도달하여 방향성이 완전히 정해지고 난 뒤에

노란색(초록색)의 시작부분에서 미로까지 방향성을 따라 이동하며 길을 만드는 거야

이해가 안 간다면 넘어가도 좋아

요지는 " 랜덤한 곳에서부터 미로까지의 경로를 만든다" 야

(5) 남는 칸이 없을 때까지 (2)~(4)를 반복한다

말 그대로 저 짓을 계속 반복하는 거야.

Willson's Algorithm으로 미로를 생성하는 과정

직접 코딩한 200*200 미로(사람이 만드는 것과 가장 흡사한 모습을 보임)

내가 소개한 것 말고도 더 많은 알고리즘들이 있어

미로를 만드는 알고리즘은 여러가지가 있고, 또 알고리즘마다 특성이 있어서

미로를 조금 풀다보면 대충 어떤 방식으로 만들었는 지 감이 와