헌트 앤 킬 미로 생성기

헌트 앤 킬 알고리즘은 본질적으로 재귀적 백트래커의 변형된 버전입니다. 변형된 부분은 스택에서 더 이상 진행할 수 없을 때 새로운 셀을 체계적으로 탐색(또는 "탐색")하는 데 있으며, 이는 항상 스택의 이전 셀로 되돌아가는 진정한 재귀적 탐색과는 대조적입니다.

이러한 이유로, 이 알고리즘은 "탐색" 모드 진입 빈도를 높이거나 특정 규칙에 따라 진입하도록 설정하는 것만으로도 다양한 모양과 느낌의 미로를 생성하도록 쉽게 조정할 수 있습니다. 여기에 구현된 버전은 현재 위치에서 더 이상 진행할 수 없을 때만 "탐색" 모드에 진입합니다.

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

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

사냥 및 사살 알고리즘에 대하여

헌트 앤 킬(Hunt and Kill) 알고리즘은 간단하면서도 효과적인 미로 생성 방법입니다. 이 알고리즘은 깊이 우선 탐색(예: 재귀적 백트래커 알고리즘)과 다소 유사하지만, 현재 위치에서 더 이상 진행할 수 없을 때 미로 전체를 체계적으로 탐색(또는 "탐색")하여 다음 진행 지점을 찾는다는 점이 다릅니다. 이 알고리즘은 크게 두 단계, 즉 탐색과 사냥으로 구성됩니다.

미로 생성에서 사냥 및 제거 알고리즘은 어떻게 작동하는가?

1단계: 임의의 셀에서 시작합니다.

• 격자에서 임의의 칸을 찾아 방문한 칸으로 표시하세요.

2단계: 걷기 단계 (랜덤 워크)

• 방문하지 않은 이웃 중 한 명을 무작위로 선택하세요.
• 이웃 셀로 이동하여 방문한 것으로 표시하고 이전 셀과 새 셀 사이에 경로를 만드세요.
• 방문하지 않은 이웃이 모두 없어질 때까지 반복하세요.

3단계: 탐색 단계 (스캔을 통한 역추적)

• 그리드를 행별로 (또는 열별로) 스캔합니다.
• 적어도 하나의 방문한 이웃 셀을 가진 첫 번째 방문하지 않은 셀을 찾습니다.
• 해당 셀을 방문한 이웃 셀에 연결하여 걷기 단계를 재개하십시오.
• 모든 셀을 방문할 때까지 반복합니다.

추가 자료

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

• 엘러의 알고리즘 미로 생성기
• 재귀적 백트래커 미로 생성기
• 크루스칼 알고리즘 미로 생성기