윌슨 알고리즘 미로 생성기

윌슨 알고리즘은 미로 생성을 위해 균일한 스패닝 트리를 생성하는 루프 삭제 랜덤 워크 방법입니다. 즉, 주어진 크기의 모든 가능한 미로가 생성될 가능성이 동일하므로 편향되지 않은 미로 생성 기술입니다. 윌슨 알고리즘은 동일한 특성을 가진 미로를 생성하기 때문에 Aldous-Broder 알고리즘의 개선된 버전으로 간주될 수 있지만 훨씬 더 빠르게 실행되므로 여기서 Aldous-Broder 알고리즘을 구현하는 데 신경 쓰지 않았습니다.

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

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

윌슨 알고리즘에 대하여

루프가 지워진 무작위 벽을 사용하여 균일 스패닝 트리를 생성하는 윌슨 알고리즘은 데이비드 브루스 윌슨이 만들었습니다.

윌슨은 원래 1996년에 확률 이론에서 랜덤 스패닝 트리와 마르코프 체인을 연구하면서 이 알고리즘을 소개했습니다. 그의 연구는 주로 수학과 통계 물리학이었지만, 이 알고리즘은 완벽하게 균일한 미로를 생성할 수 있는 능력 덕분에 미로 생성에 널리 채택되었습니다.

미로 생성을 위한 윌슨 알고리즘의 작동 방식

윌슨의 알고리즘은 무작위 탐색을 사용하여 방문하지 않은 셀에서 반복적으로 경로를 조각함으로써 최종 미로가 루프 없이 완전히 연결되도록 보장합니다.

1단계: 초기화

• 벽으로 채워진 격자로 시작하세요.
• 가능한 모든 통로 셀의 목록을 정의합니다.

2단계: 무작위 시작 셀 선택

• 임의의 셀을 선택하여 방문한 것으로 표시합니다. 이는 생성 중 미로의 시작점으로 사용됩니다.

3단계: 루프 지우기를 사용한 랜덤 워크

• 방문하지 않은 셀을 골라 무작위로 걷기(무작위적인 방향으로 이동)를 시작합니다.
• 산책이 이미 방문한 셀에 도달하면 경로에 있는 모든 루프를 지웁니다.
• 산책로가 방문한 지역과 연결되면 경로에 있는 모든 셀을 방문한 것으로 표시합니다.

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

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