[Unreal BP] 깊이 우선 탐색(DFS)으로 미로 생성하기

오른쪽 이미지처럼 미로를 구현해 볼 예정이다.

미로를 구성하는 방 하나를 Cell이라고 말하겠다.

 

구현되는 순서

1. Cell을 격자무늬로 생성한다.

원하는만큼. (5x5라든지 10x10이라든지)

 

2. 시작할 Cell을 기준으로 상하좌우 Cell을 검색한다.

상하좌우 벽 중에 하나라도 뚫려있으면, 방문한 것으로 친다.

방문하지 않은 Cell만 배열에 담는다.

 

CellArray의 Length가 0이라면, 갈 곳이 없으므로 끝낸다.

CellArray에 뭐라도 담겨있으면, 그 중에 랜덤으로 Cell을 정한다.

 

기준이 되는 Cell -> CurrentCell

상하좌우 Cell 중의 랜덤 Cell -> NextCell

 

3. CurrentCell과 NextCell의 사이 벽을 뚫어준다.

CurrentCell와 NextCell의 인덱스를 비교해서 상하좌우 중 어디인지 위치를 파악한 뒤, 벽을 없앤다.

 

여기까지 하면, 이렇게 방문하지 않은 Cell들이 생긴다.

 

4. 기준이 되는 CurrentCell은 계속 스택에 쌓는다. (DFS 알고리즘 사용)

2번에서 상하좌우 중 방문할 수 있는 노드가 없으면 끝내지말고,

스택에서 하나를 빼서 이전 노드로 다시 상하좌우 검색하는 걸로 바꾸자.

 

구현해보기

구현되는 순서에 맞추어서 구현해보겠다.

 

1. Cell을 격자무늬로 생성한다.

일단 블루프린트로 BP_Cell을 만들고, 모양을 잡아준다.

 

여기에는 벽을 안보이게 하는 커스텀 이벤트도 구현하자. (나는 동서남북으로 구분했다.)

안보이게 하면서 충돌체크도 끄자.

 

방문했는지 안했는지도 구분할 수 있게 하자.

 

그 다음에는 Cell을 생성할 BP_MazeGenerator를 만든다.

이거는 따로 설명안함. 반복문 돌면서 Cell 크기에 맞게 위치 조정해서 생성하자.

 

블루프린트는 2차원 배열이 없나?? 그래서 그냥 1차원 배열을 2차원처럼 쓰기로 했다.

 

2. 시작할 Cell을 기준으로 상하좌우 Cell을 검색한다.

x인덱스 -1 이면, 왼쪽 위치의 Cell을 얻어온다.

x인덱스 +1 이면, 오른쪽 위치의 Cell을 얻어온다.

이렇게 상하좌우 Cell을 검색해서 배열에 담았다.

 

3. CurrentCell과 NextCell의 사이 벽을 뚫어준다.

배열 길이가 0이면, 상하좌우에 방문하지 않은 노드가 없다는 것이므로 끝내고,

있으면 랜덤방향을 선택해서 벽을 숨긴다.

 

4. 기준이 되는 CurrentCell은 계속 스택에 쌓는다. (DFS 알고리즘 사용)

 

GetNextCell은 2번과 3번 과정을 하는 함수이다.

3번에서 배열 길이가 0일 때 끝나므로, 재귀 함수를 계속 부르고 있었다.

3번에서 배열 길이가 0일 때 끝나는 지점(반환노드 부분)을

스택에서 하나를 빼서(이전 노드로 돌아감.) 다시 GetNextCell을 부르는 것으로 바꾸었다.

 

메인 블루프린트

Create Cell Array -> 셀을 격자무늬로 만들고,

Get Cell -> 랜덤으로 시작 Cell을 뽑아서,

Get Next Cell -> 미로 생성.

 

입구 출구는 마음대로 만드삼.

나는 첫번째 Cell의 북쪽을 뚫고, 마지막 Cell의 동쪽을 뚫었다.

 

방 하나하나를 생성해서 만들었기 때문에,

방 사이의 벽이 겹치는 중이다. 이것도 고쳐보자.

동쪽 벽과 남쪽 벽을 안보이게 하고, 원래처럼 배치한다. 이후에 가장 동쪽 벽과 남쪽 벽들만 한번 더 보이도록 변경한다.

 

미로 생성을 완료했다!!

 

 

DFS라고 해서 어려울 줄 알았는데 생각보다 간단하다.

 

끝! 인줄 알았지만, 주의할 점이 있다.

블루프린트에서 재귀함수를 돌리면 약 250번 정도에서 무한루프로 인식이 되어서 에러가 뜬다.

(테스트 코딩해보니까 246번까지 괜찮던데 자세히는 모르겠음.)

 

이러한 이유로 미로 크기를 15x15로 생성해서 만들면 무한루프로 인식된다.

 

해결법은

1. 무한루프로 인식하는 것을 더 깊은 값으로 수정하는 방법.

2. 재귀함수를 반복문으로 바꾸는 방법.

3. C++로 코딩하는 방법. (C++은 무한루프 에러 안뜸.)

이 있다.

 

1번은 언리얼 소스 코드를 바꾸어야 해서 못한다고 볼 수 있다. (아직 할 줄 모름.)

2번이나 3번으로 하면 오류를 막을 수 있다.