윌슨 알고리즘 미로 생성기

윌슨 알고리즘은 루프 제거 방식의 랜덤 워크 기법으로, 미로 생성 시 균일한 신장 트리를 생성합니다. 즉, 주어진 크기의 모든 가능한 미로가 생성될 확률이 동일하므로 편향되지 않은 미로 생성 기법입니다. 윌슨 알고리즘은 동일한 특성을 가진 미로를 생성한다는 점에서 알더스-브로더 알고리즘의 개선된 버전으로 볼 수 있지만, 실행 속도가 훨씬 빠르기 때문에 여기서는 알더스-브로더 알고리즘을 구현하지 않았습니다.

완벽한 미로는 미로의 어느 지점에서 다른 지점까지 정확히 하나의 경로가 있는 미로입니다. 즉, 빙글빙글 돌다가 막다른 골목에 부딪혀 돌아서서 되돌아가야 하는 경우가 종종 있습니다.

여기에서 생성된 미로 지도에는 시작과 끝 위치가 없는 기본 버전이 포함되어 있으므로 미로의 어느 지점에서든 다른 지점으로 가는 해답을 직접 결정할 수 있습니다. 영감을 얻고 싶다면 제안된 시작 및 종료 위치를 활성화하고 두 위치 사이의 해법도 확인할 수 있습니다.

윌슨 알고리즘에 대하여

루프 제거된 무작위 벽을 사용하여 균일한 신장 트리를 생성하는 윌슨 알고리즘은 데이비드 브루스 윌슨이 개발했습니다.

윌슨은 확률 이론에서 무작위 신장 트리와 마르코프 체인을 연구하던 중 1996년에 이 알고리즘을 처음 소개했습니다. 그의 연구는 주로 수학과 통계 물리학 분야에 집중되었지만, 이 알고리즘은 완벽하게 균일한 미로를 생성하는 능력 덕분에 이후 미로 생성 분야에 널리 채택되었습니다.

윌슨 알고리즘을 이용한 미로 생성 방법

윌슨의 알고리즘은 무작위 보행을 이용하여 방문하지 않은 셀로부터 경로를 반복적으로 만들어 최종 미로가 루프 없이 완전히 연결되도록 보장합니다.

1단계: 초기화

• 벽으로 채워진 격자부터 시작하세요.
• 가능한 모든 통로 세포 목록을 정의하십시오.

2단계: 임의의 시작 셀을 선택합니다.

• 임의의 셀을 선택하고 방문한 셀로 표시하세요. 이 셀이 미로 생성 시 시작점이 됩니다.

3단계: 루프 제거를 사용한 무작위 보행

• 방문하지 않은 셀을 선택하고 무작위 방향으로 이동하는 무작위 보행을 시작합니다.
• 만약 이동 경로가 이미 방문한 셀에 도달하면, 경로상의 모든 루프를 삭제합니다.
• 도보 경로가 방문한 지역과 연결되면 경로상의 모든 셀을 방문한 것으로 표시하세요.

4단계: 모든 셀을 방문할 때까지 반복합니다.

• 방문하지 않은 셀을 계속 선택하고 무작위 이동을 수행하여 모든 셀이 미로의 일부가 될 때까지 진행합니다.

추가 자료

이 글이 마음에 드셨다면 다음 제안도 마음에 드실 겁니다.

• 크루스칼 알고리즘 미로 생성기
• 성장하는 나무 알고리즘 미로 생성기
• 헌트 앤 킬 미로 생성기