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

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

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

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

엘러의 알고리즘에 대하여

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

이 알고리즘은 미로 생성에 있어 효율적인 행별 접근 방식을 사용하는 것이 특징이며, 무한 미로 또는 실시간 미로 생성에 이상적입니다. 절차적 콘텐츠 생성 및 미로 생성 관련 문헌에서 흔히 인용되지만, 최초 발표에 대한 자세한 내용을 담은 원문을 찾지는 못했습니다.

엘러 알고리즘을 이용한 미로 생성 방법

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

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

1단계: 첫 번째 행 초기화

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

2단계: 인접한 셀들을 가로로 연결합니다

• 인접한 셀들을 무작위로 병합하여 동일한 ID 세트를 지정합니다. 이렇게 하면 수평 통로가 생성됩니다.

3단계: 다음 행과의 세로 연결 생성

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

4단계: 다음 행으로 이동

• 수직 연결을 유지하려면 아래쪽의 해당 셀에 동일한 세트 ID를 할당하십시오.
• 할당되지 않은 셀에 새 세트 ID를 할당합니다.

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

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

6단계: 마지막 행을 처리합니다.

• 마지막 행의 모든 셀이 동일한 집합에 속하도록 남아 있는 개별 집합들을 병합하십시오.

추가 자료

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

• 윌슨 알고리즘 미로 생성기
• 재귀적 백트래커 미로 생성기
• 헌트 앤 킬 미로 생성기