엘러의 알고리즘 미로 생성기

엘러 알고리즘은 행별 접근 방식을 사용하여 완벽한 미로(루프가 없고 두 지점 사이에 단일 경로가 있는 미로)를 효율적으로 생성하는 미로 생성 알고리즘입니다. 크루스칼 알고리즘과 유사한 미로를 생성하지만, 전체 미로를 메모리에 저장할 필요 없이 한 번에 한 행만 생성하여 이를 수행합니다. 따라서 매우 제한된 시스템에서 매우 큰 미로를 생성하고 절차적 콘텐츠를 생성하는 데 유용합니다.

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

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

엘러 알고리즘에 대하여

엘러 알고리즘은 데이비드 엘러가 소개했습니다.

이 알고리즘은 미로 생성에 대한 효율적인 행별 접근 방식으로 유명하여 무한 미로나 실시간으로 생성된 미로에 이상적입니다. 절차적 콘텐츠 생성 및 미로 생성 문헌에서 흔히 인용되지만, 원래 출판에 대한 자세한 내용을 설명하는 기본 출처를 찾을 수 없었습니다.

엘러 알고리즘이 미로 생성에 어떻게 적용되는가

엘러 알고리즘은 한 번에 한 행씩 처리하여 연결된 셀 세트를 유지하고 수정합니다. 루프를 피하면서 연결성을 보장하고 미로를 아래로 효율적으로 확장합니다.

이론적으로는 무한한 미로를 생성하는 데 사용할 수 있지만, 생성된 미로가 실제로 풀릴 수 있도록 하려면 어느 시점에서 "마지막 행" 논리로 전환하여 미로를 완료해야 합니다.

1단계: 첫 번째 행 초기화

• 행의 각 셀에 고유한 세트 ID를 할당합니다.

2단계: 인접한 셀을 수평으로 결합

• 인접한 셀을 동일한 세트 ID로 설정하여 무작위로 병합합니다. 이렇게 하면 수평 통로가 있는지 확인할 수 있습니다.

3단계: 다음 행에 대한 수직 연결 만들기

• 행에 나타나는 각 세트에 대해 적어도 하나의 셀이 아래로 연결되어야 합니다(연결성을 보장하기 위해).
• 각 집합에서 무작위로 하나 이상의 셀을 선택하여 다음 행에 연결합니다.

4단계: 다음 행으로 이동

• 동일한 세트 ID를 아래의 해당 셀에 할당하여 수직 연결을 이어갑니다.
• 할당되지 않은 셀에 새로운 세트 ID를 할당합니다.

5단계: 마지막 행에 도달할 때까지 2~4단계를 반복합니다.

• 행별로 처리를 계속합니다.

6단계: 최종 행 처리

• 나머지 별도 세트를 병합하여 마지막 행의 모든 셀이 동일한 세트에 속하도록 합니다.