[Unity 게임 개발을 위한 C# 공부 일지] 길찾기 - 1(미로 생성, 우수법)

본 포스팅은

'[C#과 유니티로 만드는 MMORPG 게임 개발 시리즈]' 인프런 강의를 수강 후, 개인적으로 배운 내용을 정리합니다.

코드의 경우에는 강사님의 저작권을 훼손할 염려가 있어 결과의 모습, 이론적인 내용을 중점으로 정리합니다.

 

---

게임 개발의 순서

게임 개발의 순서는 크게 3단계로 나눌 수 있다고 한다.

1. 입력 이벤트 처리
2. 로직 업데이트
3. 디스플레이 렌더링

이에 기반해서 길찾기 알고리즘을 통해 자료구조를 공부하는 방식으로 진행하려고 한다.

 

미로 생성

길을 찾는다라는 것이 무엇인가?

출발지가 있고 목적지가 있어, 출발지로부터 목적지까지의 올바른 길을 선택하여 목적지에 도달함을 말한다.

그렇다면 그 사이의 경로가 있어야 길찾기를 공부할 수 있음인데, 그 경로는 어떻게 만드는가?

 

물론, 직접 제작하는 방법도 있을것이나... 랜덤으로 생성되는 미로를 제작하는 방법도 있을 것이다.

 

그 미로를 제작하는 방법 중 간단한 2가지에 대해 이야기해보자.

 

1. Binary Tree Maze

직역하면 이진트리미로다.

우선... 이렇게 되어 있는 공간이 있다고 하자.

실선으로 되어 있는 곳은 막혀있어 진행이 불가능한 곳이다.

한마디로 지금은, 각 방 하나씩 나뉘어져 있는 공간에 불과하다. 

여기서 방에서 방끼리 연결하는 통로를 '임의'로 생성하여 미로를 생성하려고 한다.

 

방법은 여러가지가 있겠으나 Binary Tree Maze의 경우에는 간단하다.

각 방을 한 번씩 차례로 지나가면서 오른쪽으로 뚫을지, 아래로 뚫을지를 매 번 임의로 결정하여 뚫어주면 된다.

 

위의 그림을 코드로 구현하여 나타낸 그림은 아래와 같다.

(아직 방을 뚫지 않은, 각 방의 상태)

 

빨간색 원들이 검은실선이라고 생각하면 된다. 

즉, 초록색 공간을 하나씩 순회하면서 오른쪽 초록색 공간과 연결할지, 아래의 초록색 공간과 연결할지를

임의로 결정한 후, 연결해주면 미로가 생긴다는 것.

 

위의 설명에 따라 Binary Tree Maze를 생성한 모습은 아래와 같다.

위의 미로를 잘 살펴보면 알겠지만 각 기존의 방에서 오른쪽, 아래 둘 중 하나의 방향으로 뚫었다는것을 볼 수 있다.

 

2. SideWinder Maze

두번째는 SideWinder Maze이다.

이 방법은 1에서 설명한 Binary Tree Maze와 유사한 부분이 있다.

바로, '임의로 오른쪽으로 뚫을지, 아래쪽으로 뚫을지 결정한다' 라는 것이다.

어? 그럼 Binary Tree Maze와 똑같은게 아닌가 라고 생각할 수 있지만 결정적으로 이 부분이 다르다.

오른쪽으로 계속 진행을 하다가, 아래쪽으로 진행하도록 결정이 나면.

이전에 오른쪽으로 진행했던 방들 중 하나를 임의로 선택하여 그 방의 아래쪽 진행방향을 뚫는다는 것이다.

그림으로 설명하면 아래와 같다

현재 출발지 A로부터 오른쪽 진행방향으로 4개의 방이 연결되어있다.

그리고 이제 주황색(아래쪽 방향)으로 갈지, 초록색(오른쪽 방향)으로 갈지 결정해야 하는 순간인데.

주황색(아래쪽 방향)으로 가게 선택되었다고 하자.

그렇다면 이제 그동안 오른쪽 방향으로 진행되어 연결되어있는 4개의 방 중 임의로 하나가, 아래쪽 진행방향으로 연결해야한다는 것이다.

임의로 하나를 아래로 연결해보겠다.

이렇게 2번째 방이 아래로 진행되었다.

그리고 이제 다음으로 선택해야하는 진행방향은 주황색이냐 초록색이냐가 되고 선택하게 되는것이다.

이를 계속해서 모든방을 돌아가며 선택해주면 미로가 완성된다.

이렇게 해서 완성된 미로의 그림이다.

잘 보면 설명한 SideWinder Maze의 특성이 드러남을 알 수 있다.

 

이 두 개의 미로 생성 알고리즘은 만들기 정말 간단하지만 그렇기에 가지고 있는 단점이 있다.

단순하기 때문에 아무리 랜덤이라고 해도, 만들어진 모습이 비슷비슷 하다는 것이다.

 

3개의 SideWinder Maze를 생성한 모습이다.

SideWinder Maze - 1

SideWinder Maze - 2

SideWinder Maze - 3

 

이와 같이 상당히 유사한 모습을 보이고 있다.

어찌됐든 이렇게 랜덤으로 미로를 생성하였다면 길을 찾아야한다.

미로에서 길을 찾는 방법 중 하나인 '우수법'을 사용 해 보자.

 

길찾기 - '우수법'

우수법은 효율적인 길찾기 방법은 아니지만, 확실하게 길을 찾을 수 있는 방법이다.

오른쪽 벽이든, 왼쪽 벽이든 짚고 따라가면 길을 찾는다는 것.

 

이를 하기 위해서는, 진행방향을 알고 있어야 한다.

현재 좌표로 오기까지 어떤 진행방향을 갖고 진행했는가? 왜냐하면 오른쪽 벽이라는 것은

진행방향에 따라서 현재 좌표 기준 X좌표, Y좌표에서 +- 되는값이 다 다르기 때문.

 

간단하게 생각하자면 그냥 각 방을 넘어갈때마다 진행방향의 오른쪽 방부터 시작해서 반시계방향으로 진행하면 된다.

 

조잡한 그림이나마 설명해보자면 위의 그림과 같다

기존 진행방향이 빨간색 화살표라고 가정시

1, 2, 3, 4 순서대로 진행이 가능한 지 확인 후 진행 가능하다면 진행하면 된다.

 

이 우수법을 기반하여 길찾기를 한 모습은 아래와 같다.

 

다음은 그래프에 대해 공부한 것에 대해 정리하도록 하겠다.