[C++] 미로게임

미로는 SideWinder 알고리즘을 사용해서 미로를 만들었습니다.

 

[사진 1] SideWinder 코드

[사진 2] 사진 1 출력 코드

 

[사진 1]은 SideWinder 알고리즘을 구현한 코드이고,

[사진 2]는 [사진 1]에서 구현한 미로를 콘솔창에 출력하기 위한 코드입니다.

 

[사진 3] 미로 출력 결과

 

[사진 1]과 [사진 2]의 결과로 [사진 3]이 나왔습니다.

 

[사진 3]을 보시면 빈 네모가 보이실텐데요. 빈 네모는 탈출구입니다.

빈 네모도 랜덤한 위치에 생성이 됩니다.

출구와 가까운 위치에 생성이 되면 게임이 금방 끝나기 때문에,

최소 시도 횟수 이상인 위치에 랜덤으로 생성하도록 만들어 줬습니다.

 

우선 (0,0)과 (0,1)은 시작 지점으로 무조건 길을 열어줍니다.

 

[사진 4] 시작 지점

 

isWall[i][j] = false;면 (i,j)는 이동할 수 있는 길입니다.

즉, [사진 4]의 코드는 (0,0)과 (0,1)을 이동할 수 있는 길로 만들어줬습니다.

 

[사진 5] 랜덤으로 탈출구 만들기

 

endRow와 endCol은 탈출구 위치를 저장할 행열입니다.

bfs(false)는 탈출구까지 걸리는 최단거리를 반환하는 메소드로, BFS 알고리즘을 사용했습니다.

_size는 미로 맵의 크기입니다.

 

76,77 - 미로 맵의 사이즈보다 작은 수를 랜덤으로 넣어줍니다.

79 - 탈출구가 들어갈 공간이 벽이 아니고, bfs(false)의 결과가 _size보다 크면 반복문을 종료합니다.

 

지금까지 미로를 생성하고 탈출구를 만드는 코드까지 완성했습니다.

 

---

 

저는 프로젝트에 4가지 기능을 넣었습니다.

1. 미로 게임 시작

2. 최단거리 확인

3. 미로 확인

4. 최단 경로 확인

이렇게 4가지 기능을 넣었습니다.

 

1번부터 확인하겠습니다.

 

---

 

[사진 6] 1번 코드(1)

 

69줄의 Path는 구조체입니다. new Path(행, 열, 왔던 방향) 입니다.

왔던 방향은 0이면 아래서 온 것이고, 1이면 위에서 온 것입니다.

2이면 오른쪽에서 온 것이고, 3이면 왼쪽에서 온 것입니다.

(0 : 아래에서 옴, 1 : 위에서 옴, 2 : 오른쪽에서 옴, 3 : 왼쪽에서 옴)이라고 생각하면 될 것 같습니다.

 

[사진 7] 이동 코드(1)

[사진 8] 이동 코드(2)

 

[사진 7]과 [사진 8]이 이동하기 위한 코드로,

(0 : 아래에서 옴, 1 : 위에서 옴, 2 : 오른쪽에서 옴, 3 : 왼쪽에서 옴)를 만족시키면서 이동하게 됩니다.

 

여기서 order과 헷갈리면 안됩니다.

order은 플레이어가 내리는 명령으로,

(0 : 위로 이동, 1 : 아래로 이동, 2 : 왼쪽으로 이동, 3 : 오른쪽으로 이동) 입니다.

즉, 왔던 방향과 반대라 생각하면 됩니다.

 

pathCount는 갈림길을 마주했을 때를 위한 변수입니다.

저는 미로 게임 진행하다가 벽을 마주하면(더 이상 나아갈 길이 없을 때) 한번에 갈림길로 돌아가는 방법을 구현하고자 했습니다.

[사진 3]으로 설명을 드리면,

 

[사진 3] 미로 출력 결과

 

1. 3행 3열은 갈림길 입니다.

2. 3행 3열에서 오른쪽으로 진행해서 나아가다 보면 1행 9열에서 벽을 마주합니다.

3. 갈림길은 3행 3열로 다시 돌아와 길을 다시 선택합니다.

4. 이때 돌아온 길을 알 수 있습니다.

 

이 방법으로 구현한 이유는 현실에서 미로를 탈출하다 보면, 벽을 마주할 때가 있습니다.

이때, 갈림길로 다시 돌아와 어느 길로 갈지 선택하게 됩니다.

그래서 저는 벽을 마주했을 때 바로 갈림길로 돌아가고,

나머지 길 중 하나를 선택할 수 있도록 돌아온 길만 표시합니다.

 

코드를 보겠습니다.

 

85~86 - 지나온 길이 아니라면 pathCount++를 해줍니다.

90~95 - pathCount가 0이라는 것은 막다른 길이라는 것 입니다.

이때, (0,0)이라면 시작 지점이기 때문에, 좌측은 어차피 (0,-1)이기 때문에 갈 일이 없으니 지나온 길을 좌측으로 설정해주고 반복문을 다시 실행합니다.

(0,0)이 아니라면 P 변수에 저장된 정보를 가져오고 반복문을 다시 실행합니다.

124 - 나아갈 길이 2개 이상이라면 P 변수를 현재 갈림길 정보로 변경합니다.

 

이렇게 1번의 큰 틀을 정리했습니다.

 

---

 

2번 최단거리 확인은 BFS 알고리즘으로 구현했고,

3번은 [사진 2]를 다시 호출해줬습니다.

4번은 백트래킹 알고리즘을 활용해서 구현했습니다.

 

저는 모든 코드를 파일 분리를 했습니다.

Board 클래스와 StartGame 클래스로 나눴고,

Main.cpp 파일에서 각 클래스를 객체화해서 관리했습니다.

모든 코드를 보여드리겠습니다.

 

---

 

Main.cpp

[사진 9] Main.cpp

 

Board 클래스

[사진 10] Board.h

 

[사진 11] Board.cpp(1)

[사진 12] Board.cpp(2)

[사진 13] Board.cpp(3)

[사진 14] Board.cpp(4)

[사진 15] Board.cpp(5)

 

StartGame 클래스

[사진 16] StartGame.h

 

[사진 17] StartGame.cpp(1)

[사진 18] StartGame.cpp(2)

[사진 19] StartGame.cpp(3)

 

실행 영상

[영상 1] 실행 영상

 

---

 

제가 공부한 부분을 정리한 내용이기 때문에 틀린 부분 있을 수 있습니다!!

혹시 틀린 부분이 있으면 알려주세요!!