통로는 이어졌는데 출구에 갈 수 없다

문제와 원인

연결된 방 그림만으로 문을 열 수 있는지 알 수 없습니다. 문 뒤에 열쇠를 두면 문을 열기 위해 그 문을 먼저 지나야 합니다. 열쇠를 얻은 뒤 분기 A로 되돌아오는 경로도 ‘A는 이미 방문’이라며 버리면 놓칩니다.

해결 · 충분한 상태로 탐색

오른쪽은 (현재 방, 열쇠 수, 주웠는지, 열린 문 비트)를 탐색합니다. 열쇠는 최초 방문에만 얻고 소모형은 닫힌 문을 처음 열 때만 줄어듭니다. 열린 문은 왕복해도 다시 소모하지 않습니다. 높은 방으로 오를 때만 점프 조건이 적용됩니다.

상위 진행과 내부 미로

아래의 5×5 미로는 새 셀을 방문할 때만 통로를 추가하는 DFS입니다. 25개 셀의 트리는 간선 24개이며, 추가 통로를 넣으면 순환이 생깁니다. 이 성질이 열쇠를 포함한 상위 방 그래프의 진행까지 보장하지는 않습니다.

대가와 범위

방 위치가 고정된 독립 그래프와 한 종류의 열쇠 모델입니다. 상태를 많이 추가하면 탐색 공간도 커집니다. 수제 템플릿 적합성·WFC·전투 난이도·연속적인 점프 궤적은 계산하지 않습니다.

Dead Cells 개발자의 혼합 생성 방식 · 상태 공간과 행동의 선행 조건