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

성장 트리 알고리즘은 생성 과정에서 다음 셀을 선택하는 방식에 따라 여러 다른 알고리즘의 동작을 모방할 수 있다는 점에서 흥미롭습니다. 이 페이지의 구현은 너비 우선 탐색 방식의 큐형 접근법을 사용합니다.

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

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

성장 트리 알고리즘에 대하여

성장 트리 알고리즘은 완벽한 미로를 생성하는 유연하고 강력한 방법입니다. 이 알고리즘은 다음에 처리할 셀을 선택하는 방식에 따라 프림 알고리즘, 재귀적 백트래킹, 재귀적 나눗셈 등 여러 다른 미로 생성 알고리즘의 동작을 모방할 수 있다는 점에서 흥미롭습니다.

성장 트리 알고리즘의 작동 방식

1단계: 초기화

• 방문하지 않은 셀들로 이루어진 격자부터 시작하세요.
• 임의의 시작 셀을 선택하고 이를 목록에 추가합니다.

2단계: 미로 생성 루프

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

3단계: 종료

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

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

성장 트리 알고리즘의 핵심 특징은 다음에 처리할 셀을 선택하는 방식입니다. 이 선택은 미로의 모양에 큰 영향을 미칩니다.

최신 셀(스택과 유사한 동작) – 재귀적 백트래커:

• 항상 가장 최근에 추가된 셀을 선택하십시오.
• 길고 구불구불한 통로와 많은 막다른 길을 생성합니다(깊이 우선 탐색 미로와 유사).
• 미로는 보통 긴 통로로 이루어져 있고 풀기 쉽습니다.

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

• 매번 목록에서 임의의 셀을 선택합니다.
• 복잡하고 얽힌 경로로 이루어진, 보다 고르게 분포된 미로를 만듭니다.
• 긴 복도형 구조는 줄이고, 분기형 구조를 늘린다.

가장 오래된 셀(대기열과 유사한 동작):

• 항상 목록에서 가장 오래된 셀을 선택하십시오.
• 너비 우선 탐색 패턴처럼 보다 균일하게 분포된 미로를 생성합니다.
• 짧고 덤불이 우거진 통로들이 촘촘하게 연결되어 있다.
• (여기에 구현된 버전은 다음과 같습니다.)

하이브리드 접근법:

다양한 미로 특성에 맞춰 전략을 조합하세요. 예를 들면 다음과 같습니다.

• 90%는 최신 콘텐츠, 10%는 무작위 콘텐츠: 대부분 되돌아가는 미로처럼 보이지만, 긴 복도를 끊어주는 분기점이 간간이 나타납니다.
• 최신 식재 비율 50%, 오래된 식재 비율 50%: 긴 통로와 무성한 수목의 균형을 맞춥니다.

추가 자료

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

• 재귀적 백트래커 미로 생성기
• 윌슨 알고리즘 미로 생성기
• 엘러의 알고리즘 미로 생성기