성장하는 나무 알고리즘 미로 생성기

Growing Tree 알고리즘은 흥미로운데, 생성 중에 다음 셀이 어떻게 선택되는지에 따라 여러 다른 알고리즘의 동작을 에뮬레이트할 수 있기 때문입니다. 이 페이지의 구현은 너비 우선, 큐와 같은 접근 방식을 사용합니다.

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

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

성장하는 나무 알고리즘에 대하여

Growing Tree 알고리즘은 완벽한 미로를 생성하는 유연하고 강력한 방법입니다. 이 알고리즘은 Prim 알고리즘, 재귀적 백트래킹, 재귀적 분할과 같은 다른 여러 미로 생성 알고리즘의 동작을 에뮬레이트할 수 있기 때문에 흥미롭습니다. 이는 처리할 다음 셀을 선택하는 방법에 따라 달라집니다.

성장하는 나무 알고리즘의 작동 방식

1단계: 초기화

• 방문하지 않은 셀의 그리드로 시작합니다.
• 무작위로 시작 셀을 선택하여 목록에 추가합니다.

2단계: 미로 생성 루프

• 셀 목록이 비어 있지 않은 경우:
  • 특정 전략에 따라 목록에서 셀을 선택합니다(아래 설명).
  • 선택한 셀에서 방문하지 않은 이웃(무작위로 선택) 중 하나까지 통로를 만듭니다.
  • 이웃은 이제 미로의 일부가 되었으므로 목록에 추가하세요.
  • 선택한 셀에 방문하지 않은 이웃이 없으면 목록에서 제거합니다.

3단계: 종료

• 목록에 더 이상 셀이 없으면 알고리즘이 종료되고, 이는 미로 전체가 완성되었음을 의미합니다.

셀 선택 전략(알고리즘의 유연성)

Growing Tree 알고리즘의 결정적 특징은 다음에 어떤 셀을 처리할지 선택하는 방법입니다. 이 선택은 미로의 모양에 극적인 영향을 미칩니다.

최신 셀(스택과 같은 동작) – 재귀적 백트래커:

• 항상 가장 최근에 추가된 셀을 선택하세요.
• 많은 막다른 길이 있는 길고 구불구불한 복도를 생성합니다(깊이 우선 탐색 미로와 같음).
• 미로는 통로가 길고 풀기 쉬운 편입니다.

랜덤 셀(랜덤화된 Prim 알고리즘):

• 매번 목록에서 무작위로 셀을 선택합니다.
• 복잡하고 뒤엉킨 경로가 더욱 균등하게 분포된 미로를 만듭니다.
• 긴 복도는 줄어들고, 갈림길은 늘어났습니다.

가장 오래된 셀(대기열과 같은 동작):

• 항상 목록에서 가장 오래된 셀을 선택하세요.
• 너비 우선 탐색 패턴처럼 더 균일한 분포의 미로를 생성합니다.
• 짧고 울창한 통로와 빽빽하게 연결된 연결 통로.
• (여기에 구현된 버전입니다)

하이브리드 접근 방식:

다양한 미로 특성에 대한 전략을 결합합니다. 예를 들어:

• 90% 최신, 10% 무작위: 대체로 재귀적 백트래커 미로처럼 보이지만 가끔 긴 복도를 나누는 분기가 있습니다.
• 50%는 최신식, 50%는 가장 오래된 식재: 긴 복도와 무성한 초목의 균형을 맞춥니다.