초기 기획
- 신전 입구에 들어가기전에 랜덤으로 미로를 생성하고 미로 내부에 신전입구 열쇠를 배치
- 추후 다른기믹추가를 고려해서 Base클래스 생성
모든 벽을 데이터 상으로만 세우고, 경로에 따라서 벽을 지우는 방식으로 길을 생성
- 서버에서 1회 생성 -> 모든 클라이언트에게 Replicate
- 입구와 출구는 고정된 위치에 존재하며, 그 사이를 Depth-First Search (DFS) 알고리즘을 통해 연결하는 방식으로 경로를 생성
DFS 생성 방식
한 방향으로 쭉 가다가 더 이상 갈 곳이 없으면 이전으로 되돌아가서 다른 방향을 파는 방식
RuinsGimmickBase.h
- 추후 기믹추가를 고려해 Base 미리 생성
미로 설계
RuinsMazeStructs
- 방문 여부와 벽의 유무 여부를 확인하기 위한 구조체
- DFS로 경로를 연결할때 연결한 방향의 벽만 제거하기
RuinsMazeWall
- bReplicates = true로 클라이언트로 복제시킴
서버에서 생성 -> 클라이언트에 복제- LDMaxDrawDistance를 설정해서 최적화
RuinsMazeManager 주요 함수
GenerateMaze()
- MazeBounds로 미로 구역 계산
- 셀 / 벽 정보 초기화
- DFS로 경로 생성
- 벽 스폰
- 입출구 연결 유효성 검사(디버깅용)
GenerateMainPath()
- 현재 셀 방문 처리
- 방문하지 않은 이웃 방향을 랜덤하게 추출
- 이웃 셀로 이동 -> 현재 셀과의 사이 벽 제거
- 재귀로 반복
GetShuffledUnvisitedNeighbors()
- 현재 셀에서 방문하지 않은 방향을 랜덤하게 섞은 후 반환
- Fisher–Yates 방식 섞기
Fisher-Yates Shuffle
- 배열을 무작위로 섞는 알고리즘
- 편향이 없고 각 순열이 같은 확률로 나옴
- 배열에 끝에서 시작 -> 현재 위치(i)보다 작거나 같은 위치(j)를 무작위로 선택 -> i와 j의 위치를 서로 바꿈
SpawnWall()
- 각 셀의 4방향을 기준으로 ARuinsMazeWall 액터를 스폰
- 스폰 시 충돌 방지 설정 : AlwaysSpawn
IsPathToExitValid()
- 생성된 미로가 실제 입출구를 연결하는지 검사(디버깅용)
RecursiveCheckPath()
- 재귀 DFS로 실제 연결 여부를 검사하는 내부 함수
- 이미 제거된 벽 뱡향으로만 이동
구조체 적용 리팩토링
- Visited / Wall 배열을 RuinsMazeCell 구조체로 통합해서 미로 셀 데이터를 관리하기 더 용이하게 리팩토링 진행
셀 방문 여부
Visited[X][Y] -> MazeCells[X][Y].bVisited
벽 상태
Walls[X][Y]("Top")와 같은 문자열 키 -> MazeCells[X][Y].bWallTop 같은 명시적 멤버
배열 구성
2개의 분리된 배열에서 통합 구조체 배열로 변경
초기화 방식
TMap 기반 반복에서 구조체 자동 초기화
결과물
- 입 출구 테그를 붙인 후 실험 결과 경로가 생성되고 로그도 정상적으로 뜸
확장계획
- 내부에 벽에 걸치지 않고 자연스럽게 장애물이나 아이템 스폰
- 몬스터를 피할 수 있게 구멍이 나있는 벽도 넣어 여러 벽으로 생성되게 확장
