미로 생성

그래프로 본 미로

미로는 칸으로 이루어진 격자이고 인접한 두 칸 사이에는 항상 벽이 있다. 이 격자를 그래프로 보면 칸은 노드가 되고 벽이 없는 두 칸 사이의 연결은 엣지가 된다.

모든 칸이 하나로 이어져 있으면서 두 칸을 잇는 경로가 오직 하나뿐인 미로를 완전 미로(Perfect maze)라고 부른다. 그래프 용어로는 격자의 모든 노드를 포함하는 신장 트리를 만드는 것과 같다. 트리이므로 순환이 없고 신장하므로 모든 칸에 닿는다.

재귀적 백트래커

신장 트리를 만드는 방법 중 하나가 재귀적 백트래커다. 스도쿠 백트래킹과 같은 모양으로 움직인다.

1. 선택: 현재 칸에서 아직 방문하지 않은 이웃 칸 하나를 무작위로 선택
2. 탐색: 선택한 이웃과 사이의 벽을 뚫고 그 칸으로 이동
3. 되돌아가기: 이웃이 전부 방문된 칸에 갇히면 이전 칸으로 되돌아가 남은 이웃을 다시 살핀다

방문하지 않은 이웃이 하나도 남지 않을 때까지 파고들었다가, 막히면 되돌아가 다른 갈림길을 여는 과정을 모든 칸이 방문될 때까지 반복한다. 이동한 칸을 스택에 쌓고 막히면 스택에서 꺼내는 식으로 구현하면, 이 과정 전체가 격자 그래프 위의 깊이 우선 탐색과 정확히 같은 모양이 된다.

결과물의 특징

한 칸에서 갈 수 있는 한 계속 파고드는 방식이라 갈림길보다 긴 통로가 많이 생긴다. 되돌아가는 지점에서만 새로운 갈림길이 열리기 때문에, 완성된 미로는 구불구불하게 이어지는 좁은 복도가 특징이다.

시각화

무작위 칸에서 시작해 재귀적 백트래커가 미로를 파 나가는 과정을 지켜본다. 진한 칸은 현재 파고들고 있는 칸, 옅은 칸은 이미 방문한 칸이다.

현재 칸방문한 칸

다시 생성×1정지

여기서 만들어지는 격자는 A* 길찾기가 시작점과 도착점 사이의 최단 경로를 탐색하는 대상과 같은 구조다.