[Unreal Engine C++] 랜덤 맵 생성에 관한 아이디어들

이번 졸업 작품 프로젝트에서 개인적으로 꼭 구현해보고 싶었던 알고리즘 중 하나가 랜덤 맵 생성 알고리즘 이였다.
이를 생각하고, 구현해내기 전 아이디어와 과정들을 적어보고자 한다.

---

구현을 시작하기 전..

네이버 및 구글에서 언리얼 관련 내용을 검색해보았을 때, 툴 설명 및 기능들을 설명해주는 글을 어느정도 존재하지만 알고리즘을 설명하는 내용은 거의 없었다.

또한 그 것을 한국어로 검색하였을 때 나오는 건 극히 일부분이였다..

Procedural Map Generation라던가 절차적 맵 생성.. 랜덤 맵 생성... 등등을 검색하였지만 나오는 내용은 많이 없었지만 그 조금의 내용이라도 최대한 활용해서 구현해보고자 했다.

---

생각의 시작 - BSP 알고리즘

검색해보았을 때, 그 중에 가장 많이 나오는 것이 바로 BSP 알고리즘(  Binary Space Partitioning)일 것이다.

이는 재귀적으로 특정한 크기의 공간을 계속 나누고 나누어 일정 크기가 되었을 때 방을 생성시킨 후, 차례차례 돌아가면서 길을 잇는 방식으로 구현된다.

출처 : http://1st.gamecodi.com/

이 알고리즘을 구현하는 것은 생각보다 어렵지는 않았다. 특정한 공간 벡터에서 비율을 정한 뒤 그 공간의 가로길이와 세로길이를 비교하여 긴 방향과 수직으로 나누는 작업을 반복하였다.

다만, 필자의 프로젝트에서는 각각의 방의 크기는 다양하였고, 고정되어 있는 에셋이였다. 또한 각 방들은 여러 곳으로 연결되는 것이 아닌 하나의 문만 존재하였기 때문에 BSP를 사용하게 되면 복도를 어떻게 이을까 하는 문제가 발생하였다.

결론적으로 이 알고리즘은 공부 및 구현만 직접 해보고, 폐기하는 절차를 밟게 되었다...

---

따라해볼까? - MST 알고리즘

첫 알고리즘을 폐기하는 절차를 밟고, 어떻게 구현할까 고민하던 도중 한 포트폴리오 블로그를 찾게 되었다.

MST알고리즘을 사용한 랜덤 맵 생성 알고리즘이였고, 이를 간략하게 설명해 주고 코드를 제공해주었다.

대략 설명하자면 캐릭터를 중심으로 한 일정 크기의 원을 스폰시킨 뒤 그 안에 랜덤한 위치에 방을 스폰, 안겹치게 펼친 뒤 랜덤으로 액터들을 지워준다.
그 뒤 각각의 방들을 알고리즘을 이용해 최적 거리를 계산하고 그 곳에 복도를 스폰하는 방식이였다.

출처 : rohanpatel1899.wixsite.com

이 방식을 처음 찾았을 때에는 엄청 획기적으로 보였고 배웠던 알고리즘을 게임에 직접 사용해볼 수 있는 기회라고 생각하여서 클론 코딩을 해보면서 내 게임에 맞춰 수정해보고 적용해보고 구현해보았다.

흩뿌리는 것은 같지만 가운데에 일정한 크기의 메인룸을 생성하고, 메인룸에서 특정 거리 안에 있는 액터들은 두세개만 남기고 지운 후, 다시 그 두세개 남은 방에서 일정 크기만큼 지우고... 를 반복하는 알고리즘으로 작성하고자 하였다.

하지만 이를 내 프로젝트에 직접 추가하면서 해보다 보니, 알고리즘은 둘째치고 Separating에서 서로 무한적으로 움직이거나 크기가 큰 방 안에 작은 방이 갇혀버리는 문제가 발생하였다. 이를 수정하고자 언리얼의 Collision이 작동하는 방식을 이해하는데 시간이 많이 소모되었다..

MST를 사용해 복도를 최적 길이로 만드는 방식은 BSP에서도 걱정이였던 복도 문제와 겹친다.
다만 그 문제는 완벽한 최소 신장 트리를 구현하는 것이 아닌, 구현 후 몇개는 잘라내고 몇개는 남기는 식으로 대처할 수 있다. 그러나 복도 액터는 정해진 길이를 가지고 있고, 이 에셋으로 구현한다면 복도를 잇는 액터중 몇개의 액터는 길이가 짧아지고 길어져 게임 플레이에 보기 좋지 않은 문제를 발생할 수도 있다는 염려가 생겼다.

그래서 결국 이 알고리즘도 사용하지 않기로 하였다.

---

이걸로 하자! - 청크 개념

생각했던 두 알고리즘을 사용하지 않기로 하면서 고심이 많아지던 도중... 대학교 동기의 아이디어를 듣게 되었다.

유니티에서 만드는 랜덤 맵 알고리즘에도 많이 사용하는 청크 개념 형식으로 사용해보는 것이 어떻냐는 이야기였다.

출처 : 마인크래프트 위키

이는 마인크래프트라는 게임에서도 활용되는 개념인데 플레이어의 주변 일정 거리만큼 있는 정해진 크기의 청크, 즉 하나의 큰 블럭만 스폰시켜서 보여주는 것이다.

그렇게 된다면 무한맵을 생성해도 메모리 확보가 가능한 장점이 있다.

 

이를 응용하여 청크 형식으로 이어보면 어떨까 하는 생각을 하게 되었다.

하나의 메인룸을 가운데에 두고 이동할 수 있는 위치에 똑같은 크기를 가진 복도, 방 등을 스폰시켜서 이어보면 원하는 랜덤맵과 동시에 에셋 크기에 구애받지 않고 제작할 수 있겠다 하는 자신감이 생겼다.

이를 구현해보았고, 다음 포스팅에서 차례차례 설명하면서 풀어볼 예정이다.