헌트 앤 킬 미로 생성기

헌트 앤 킬 알고리즘은 실제로 재귀 백트래커의 수정된 버전입니다. 이 수정은 더 이상 갈 수 없을 때 계속할 새 셀을 체계적으로 스캔(또는 "사냥")하는 것으로 구성되며, 이는 항상 스택의 이전 셀로 돌아가는 진정한 재귀 검색과 대조됩니다.

이 때문에 이 알고리즘은 "사냥" 모드에 더 자주 들어가거나 특정 규칙에 따라 들어가기로 선택하는 것만으로도 다른 모양과 느낌의 미로를 생성하는 데 쉽게 적용할 수 있습니다. 여기에 구현된 버전은 현재 셀에서 더 이상 갈 수 없을 때만 "사냥" 모드로 들어갑니다.

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

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

헌트 앤 킬 알고리즘에 대하여

헌트 앤 킬 알고리즘은 미로를 생성하는 간단하면서도 효과적인 방법입니다. 깊이 우선 탐색(즉, 재귀적 백트래커 알고리즘)과 다소 유사하지만, 현재 위치에서 더 이상 갈 수 없을 때 체계적으로 미로를 스캔(또는 "헌트")하여 진행할 새 셀을 찾습니다. 이 알고리즘은 걷기와 헌팅이라는 두 가지 주요 단계로 구성됩니다.

미로 생성을 위한 헌트 앤 킬 알고리즘의 작동 방식

1단계: 임의의 셀에서 시작

• 그리드에서 임의의 셀을 찾아 방문한 것으로 표시하세요.

2단계: 걷기 단계(무작위 걷기)

• 방문하지 않은 이웃을 무작위로 선택하세요.
• 이웃으로 이동하여 방문한 것으로 표시하고 이전 셀과 새 셀 사이에 경로를 만듭니다.
• 방문하지 않은 이웃이 더 이상 없을 때까지 반복합니다.

3단계: 사냥 단계(스캐닝을 통한 백트래킹)

• 격자를 행별로(또는 열별로) 검토합니다.
• 적어도 하나의 방문된 이웃이 있는, 방문되지 않은 첫 번째 셀을 찾으세요.
• 방문한 이웃에게 해당 셀을 연결하여 걷기 단계를 다시 시작합니다.
• 모든 셀을 방문할 때까지 반복합니다.