안녕하세요. 아직 이름이 없는 인디 게임을 혼자 만들고 있는 개발자입니다. 최근에 몇몇 기술적 내용들을 글로 정리하고 있는데 이곳에도 공유드립니다. 여기엔 게임을 만드는 분들은 얼마 없는것 같지만 도움이 될 분들이 있으셨음 좋겠네요. 

내용은 자동 던전 생성에 관련된 내용입니다. 

-----

게임 P3(코드네임, 아직 이름 없음)는 로그라이크 던전 크롤러 장르의 게임입니다. 장르의 특성상 던전은 매 플레이마다 매번 새로 만들어져야 합니다. 프리셋을 많이 만드는 방법도 있겠지만, 사람이 편집하는 수고를 덜게 자동으로 던전을 생성하는 방법을 구현하고자 합니다. 던전 자동 생성은 게임 제작 분야에서 오랫동안 노력해왔던 주제로 다양한 방법이 있습니다. P3의 던전은 주로 동굴 형태입니다. 이 포스트에서는 동굴 형태의 던전을 괜찮은 퀄리티로 자동 생성하는 방법에 대해 이야기 해보겠습니다.

키 아이디어

동굴은 방(Room)과 복도(Corridor)의 조합으로 표현될 수 있습니다. 복잡한 형태의 동굴도 여러개의 방과 방사이를 잇는 복도의 집합으로 모델링 될 수 있습니다. 따라서 다음과 같이 두단계의 아주 단순한 방식으로 동굴을 만들어 낼 수 있습니다.

1. 랜덤한 위치의 방을 생성
2. 방과 방을 복도로 연결

랜덤 방의 생성

방과 방은 너무 멀지 않아야 하고 영역이 겹치면 안됩니다. 여러가지 솔루션들이 있겠지만 저는 나선을 따라 방을 배치하는 단순한 방법을 이용했습니다. 중점에서 거리 r 만큼 되는 점을 선택합니다. 중점에서 이 점까지 이어지는 vector를 v라고 하겠습니다. v를 조금씩 회전시키면서 새로운 방을 생성합니다. v가 회전될때마다 r을 조금씩 늘립니다.

1. 나선을 따라 여분을 포함한 K개의 방을 생성
2. 그중 N개의 방만을 랜덤하게 선택

나선이 중요한 것은 아닙니다. 공간상에 방들을 적절히 배치할수 있는 다른 방법을 사용하셔도 됩니다.

방과 방을 연결 #1

이제 어떤 방과 어떤 방을 이어줘야 할지 정해야 할 단계 입니다. 

1. 모든 방을 메시화 해줍니다. 방의 중앙의 점들로 Delaunay triangulation 알고리즘을 적용하면 모든 방을 아래와 같은 메시로 이어줄 수 있습니다. 이 알고리즘은 구현이 복잡해서 직접 구현하는 것 보다는 github에서 구현된 코드를 찾는것을 추천드립니다.
2. 모든 방이 연결되면 재미가 없습니다. 필요 없는 연결은 제거합니다. MST(Minimum Spanning Tree) 를 이용하면 모든 방을 지나는 최소 비용(가장 짧은)의 연결 을 만들 수 있습니다.
3. 하지만 MST만을 이용하면 맵에 루프가 없기 때문에 맵이 단조로워 져서 약간의 선을 더 이어서 루프가 있게 만들어 줍니다. 

아래의 푸른색 선이 연결된 방과 방의 정보입니다. 

방과 방을 연결 #2

위에서 어떤 방과 어떤 방을 이어야 하는지 까지 정했습니다. 이 단계에서는 실제로 방과 방을 잇습니다.  

1. 동굴의 방들이 정사각형이라면 자연스럽지가 않기 때문에 각 방에 약간의 노이즈들을 추가합니다. 
2. 방과 방은 A* 알고리즘을 이용해서 path를 구합니다. 
3. 연결된 path에 약간의 노이즈를 추가해서 복도를 구성합니다. 

부드럽게 만들기

너무 복잡한 부분들을 부드럽게 할 차례 입니다. Cellular Automata 알고리즘을 이용합니다. 이 알고리즘은 마치 대패질을 하는 것과 비슷하게 동작합니다. 튀어나오고 각진 부분을 없애 버립니다. 4~5번 반복적으로 알고리즘을 적용시켜서 각진 부분을 제거합니다. 아래 파란색 부분이 이 알고리즘에 의해 Smoothing 된 부분입니다. 

페인팅

다 되었습니다. 이제 생성된 맵을 타일들로 잘 칠해주고 오브젝트들을 배치하는 일만 남았습니다. 이 부분은 생성과는 상관 없는 부분이라 설명을 생략하겠습니다. 아래는 P3에서 타일 페인팅과 오브젝트 배치가 끝난 후의 모습입니다.

결론

지금까지 동굴을 자동으로 생성하는 방법에 대해 알아봤습니다. 이 방식은 플레이마다 매번 다른 맵을 자연스럽게 만들 수 있다는 것이 장점입니다. 다만 구현에 다소 난이도가 있는 것이 단점입니다. 도움이 되었길 바랍니다. 

---

간혹 기술적인 문서들 정리할 때마다 공유 드리겠습니다~

언제 출시할지 기약없지만(이 속도로 가능하긴 할지..) 만들고 있는 게임(https://concode-studio.itch.io/p3)도 관심 부탁드릴께요.

감사합니다.