미로를 생성하는 좋은 알고리즘은 무엇입니까?
https://stackoverflow.com/questions/38502
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
하나의 경로와 많은 수의 막다른 골목이 있는 N x M 그리드의 간단한 미로를 원하지만 "올바른" 것처럼 보입니다(예:마치 누군가가 손으로 만든 것처럼 아주 작은 막다른 골목이 없이 말이죠.)이를 수행하는 알려진 방법이 있습니까?
해결책
에서 http://www.astrolog.org/labyrnth/algrithm.htm
재귀 역추적기:이는 아래에 설명된 재귀적 역추적 해결 방법과 다소 관련이 있으며, 미로 크기만큼의 스택이 필요합니다.조각할 때는 최대한 욕심을 내고, 현재 셀 옆에 아직 만들어지지 않은 부분이 있으면 항상 조각하십시오.새 셀로 이동할 때마다 이전 셀을 스택에 밀어 넣습니다.현재 위치 옆에 만들어지지 않은 셀이 없으면 스택을 이전 위치로 팝합니다.스택에서 모든 것을 꺼내면 미로가 완성됩니다.이 알고리즘을 사용하면 "강" 요소가 최대한 높고, 막다른 골목이 적지만 길며, 일반적으로 매우 길고 구불구불한 해를 갖는 미로가 생성됩니다.Prim의 알고리즘이 조금 더 빠르지만 꽤 빠르게 실행됩니다.재귀 역추적은 벽 추가기로 작동하지 않습니다. 그렇게 하면 미로의 전체 내부가 단일 줄기로 경계에 연결되는 외부 가장자리를 따르는 솔루션 경로가 발생하는 경향이 있기 때문입니다.
그들은 단지 10%의 막다른 골목을 만들어낸다.
는 해당 방법으로 생성된 미로의 예입니다.
다른 팁
매우 간단한 해결책은 그래프 가장자리에 임의의 가중치를 할당하고 적용하는 것입니다. 크루스칼의 알고리즘 최소 스패닝 트리를 찾는다.
미로 생성 알고리즘에 관한 최고의 토론: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (며칠 전에 HN에 있었습니다).
이상하게도 '표준' 규칙을 약간 변경하고 임의의 구성에서 시작하면 콘웨이의 인생 게임 꽤 멋진 미로를 생성하는 것 같습니다!
(정확한 규칙은 기억나지 않지만, 세포 집단을 '밀도화'하는 경향이 있는 매우 간단한 변형입니다...)
내가 가장 좋아하는 방법은 Kruskal의 알고리즘을 사용하는 것이지만 가장자리를 무작위로 선택하고 제거할 때 연결된 가장자리 유형에 따라 선택에 가중치를 부여합니다.
다양한 가장자리 유형에 대한 가중치를 변경하여 고유한 특성 또는 "개성"이 많은 미로를 생성할 수 있습니다.여기에서 내 예를 참조하세요.
미로를 생성하는 방법 중 하나는 Prim 알고리즘의 무작위 버전입니다.
벽으로 가득 찬 그리드로 시작하세요.셀을 선택하고 미로의 일부로 표시하세요.벽 목록에 셀의 벽을 추가합니다.목록에 벽이 있는 동안:
목록에서 임의의 벽을 선택하세요.반대쪽에 있는 셀이 아직 미로에 있지 않은 경우:
(i) 벽을 통로로 만들고 반대쪽에 있는 셀을 미로의 일부로 표시합니다.
(ii) 셀의 인접한 벽을 벽 목록에 추가합니다.
반대편 셀이 이미 미로에 있었다면 목록에서 벽을 제거하세요.
더 많은 이해를 원하시면 클릭하세요 여기
의사 코드로 작성된 DFS 알고리즘은 다음과 같습니다.
셀 위치 목록을 보관하기 위해 CellStack(LIFO)을 생성합니다.
TotalCells = 그리드의 셀 수 설정
무작위로 셀을 선택하고 이를 CurrentCell이라고 부릅니다.
VisitedCells = 1로 설정
방문하는 동안 <TotalCells는 모든 벽이있는 모든 CurrentCell의 모든 이웃을 찾습니다.
하나 이상의 발견 된 경우 무작위로 하나를 선택하십시오
그것과 CurrentCell 사이의 벽을 허물다
CellStack에서 CurrentCell 위치 푸시
새 셀을 CurrentCell로 만듭니다.
visitedcells에 1을 추가하십시오. 그렇지 않으면 셀 스택에서 가장 최근의 셀 항목을 팝하십시오.
결국에 셀로 셀로 셀러로 만드십시오
