타일맵 길찾기.

원래 블로그에는 평소에 공부했던 걸 저장하고 나중에 찾아서 참고하는 용도로 쓰고 있었는데, 최근 바빠서 그럴 시간이 없었다. 특히 NDC2016 발표를 준비하는 시간은 정말 지옥같았기 때문에(결과값이.. 결과값이 나와야 했다), 발표를 준비하면서 공부했던 내용, 그리고 발표 보충 자료를 올린다고 말해놓고 올리지 않은 채 반 년이 지나버렸다. 최근에 타일 맵을 다시 쓸 일이 생겨서 예전 자료를 참조하다가 NDC2016 발표에 썼던 기법이 기억이 나지 않는 걸 깨닫고, 시간이 나는 김에 하나씩 정리해 놓아야겠다고 생각했다.

타일 맵은 컴퓨터 게임의 초창기부터 지금까지 쓰여온 견고한 기법이다. 보통 균일한 이미지 조각인 타일(Tile) 을 이어붙여서 맵의 형태를 만든다. 보통 이렇게 만든 맵은 보기에 자연스럽고 타일 간의 이음새가 크게 눈에 띄지 않는 것이 좋다. 이렇게 만든 맵은 보통 주인공 캐릭터나 다른 오브젝트들의 활동 무대로 쓰인다.

타일 맵은 RPG Maker 같은 툴에서도 쉽게 찾아볼 수 있다. 타일을 선택하고 색칠하듯 마우스로 드래그하면 맵이 생성된다. 이렇게 생성된 맵은 자연스럽게 보인다. 즉 타일과 타일 간의 이음새가 분리되는 느낌이 아니라 부드럽게 연결된다. 이렇게 만들려면 어떻게 해야 할까?

링크

애초에 이 고민을 했던 것은 고전 게임인 <삼국지 영걸전>의 맵 파일을 누군가 뜯어놓은 것을 살펴볼 때였다. 맵 조각은 아래처럼 구성되어 있었다.

그에 비해 우리가 보통 알고 있는 맵은 아래와 같다.

이미지를 보면 금방 둘의 연관성을 알 수 있다. 실제의 맵을 구성하는 타일 조각의 최소 단위는 보통 플레이어가 “한 칸”이라고 인지하는 유닛이나 성채, 보물창고의 크기에 비해 가로, 세로가 각각 1/2 작은, 1/4 크기였다. 영걸전에서는 한 칸이 32 x 32 픽셀, 타일 하나는 16 x 16 픽셀이다.

예를 들어 위의 맵은 아래처럼 하얀 네모가 하나의 이미지 조각(타일)로, 그것이 모여서 우리가 인지할 수 있는 맵의 형태가 된다.

영걸전에서는 유닛이 이보다 가로 세로 2배 큰 단위로 배치된다. 물론 게임에 따라 맵 타일과 유닛 타일이 같은 단위일수도 있다.

이음새가 자연스럽게 보이기 위해서는 우리가 한 칸의 타일이라고 인식하는 것의 절반 정도의 스케일로 타일을 준비해야 한다. 이 페이지에 따르면 보통 RPG에서 많이 사용되는 타일 종류를 2-corner 타일이라고 부른다. 타일의 corner 부분이 변하기 때문이다. 땅과 물처럼 대비되는 두 가지의 지형이 자연스럽게 이어지도록 하는 것이다.

링크

영걸전에서는 대각선을 연결할 필요가 없었는지 아래 그림에서 빨간 네모로 표시한 이런 타일들은 쓰이지 않았다.

대신에 표현을 풍부하게 하기 위해서인지 연결 타일 일부가 2가지로 쓰였다(이음새와 면적이 차지하는 부분에 차이 있음).
영걸전의 초원 – 물 연결 부분을 정의하는 2-corner 타일은 아래와 같다.

다음 글에서는 내가 RPG 게임의 타일 맵을 어떻게 만들었는지를 보여줄 예정이다.출처:NDC2016 보충자료 – 1. 타일 맵 구현 기본

읽어볼만한 좋은 글
——————
1. http://chulin28ho.egloos.com/5097822 – 워크래프트3에서 사용된 타일 구조 연구

참고자료
——–
2. http://www.codeproject.com/Articles/106884/Implementing-Auto-tiling-Functionality-in-a-Tile-M – 2D 타일 맵의 구현 설명

3. http://s358455341.websitehome.co.uk/stagecast/wang/2corn.html – 보통 RPG 맵을 만들 때 사용하는 2-corner 타일에 대한 설명신고출처:NDC2016 보충자료 – 1. 타일 맵 구현 기본

지난 글에 이에 이번에는 실제 NDC2016 발표에서 타일 맵을 어떻게 구현했는지에 대해서 살펴보겠다. 타일 리소스는 게임업계의 저명한 인사인 Daniel Cook 이 무료로 공개한 타일셋을 가져왔다. 게임에 사용하는 무료 리소스가 올라오는 opengameart.org 에는 이 타일셋을 32 x 32 크기로 수정한 버전이 있는데 이것도 참고했다.

일단 내가 사용할 타일셋을 만들었는데 아래 그림과 같다. 가운데에 있는 벽돌은 이 예제에 사용한 유닛들과 느낌이 어울리지 않아서 결국 사용하지 않았기 때문에 기본 타일 종류는 풀(초원), 길, 물의 3종류다.

풀과 길은 이전 글에서 설명한 2-corner 타일로 서로 경계면이 부드럽게 연결되는 타일 조각들로 이루어져 있다. 하지만 물은 물과 다른 영역의 경계가 투명하게 처리되어 있는데, 이는 먼저 풀과 길을 정리한 다음에 물을 그 위에 덮어씌우기 위해서다. 풀이든 길이든 물을 그 위에 얹으면 자연스럽게 보인다. 3가지 타일이 만나는 경우의 수를 다 계산하는 것보다 이쪽이 간단하고 편하다.

간단히 생성해 본 맵은 아래와 같다.

길을 만드는 과정은 복잡하기 때문에 다음 글에 설명하기로 하고, 여기서는 물을 얹는 방법부터 설명하려고 한다. 맵의 어떤 장소에 물을 배치하기로 결정하면, 상하좌우, 좌상, 좌하, 우상, 우하의 8개 셀에 대해서 랜덤함수를 돌려서 75%의 확률로 물을 배치한다.

물을 배치한 후에는 Cellular Automata 기법을 이용해서 각 셀의 상하좌우 4방향 이웃을 체크, 물의 모양을 자연스럽게 만들어준다.
물 타일이 아닐 경우 상하좌우 이웃에 물 타일이 2개 이상 있으면 물 타일이 된다.

그 다음에는 물의 클러스터가 충분히 가깝지만 이어져 있지 않아서 어색해보이는 경우를 방지하기 위해서 1타일 떨어진 물의 경우 합쳐주는 작업을 한다.

이제 이 맵을 타일맵으로 바꿔줄 때가 왔다. 영역간의 연결을 생각하지 않는다면 아래와 같은 타일맵도 가능할 것이다.

하지만 연결을 생각하면 계산은 조금 복잡해진다. 아까의 타일셋을 살펴보면 각 타일은 4개의 corner에 물타일이 있는 경우와 그렇지 않은 경우로 나눌 수 있다(물 = w, 다른 타일 = o 로 표시).

맵의 타일 결정 방법은, 먼저 물 타일 각각에 대해서 8방향에 어떤 타일이 있는지 검사한다. 그리고 물 타일이 아니면 가중치를 둔다.

타일이 되는 빨간 타일을 확대해서 살펴보면 4개의 corner로 나눌 수 있는데, 어느 한쪽에서 영향을 받으면 인접한 영역에 1을 더해주게 된다.

예를 들어서 왼쪽 상단에 물 타일이 아닌 것이 있으면 왼쪽 위 코너에 1이 더해지고, 오른쪽에 물 타일이 아닌 것이 있으면 오른쪽 상단, 오른쪽 하단 코너에 1을 더한다.

이렇게 계산하면 위 맵의 타일에는 아래처럼 점수가 쌓이고, 그 중 1 이상인 값만 o(other) 타일로 치환하면 알맞은 타일을 찾을 수 있다. 4개의 corner가 모두 o 타일일 때는 이미 물 타일이 아니라고 판단하고 그리지 않는다.

최종적으로는 아래처럼 타일을 찾게 된다. 위와 비교하면 꽤 큰 차이다.

이렇게 타일맵의 실제 구현에 대한 내용을 살펴보았다. 다음 글에서는 위에서 약간 두리뭉실하게 넘어갔던 “어떤 장소에 물을 배치할지” 결정하는 문제에 대한 내용, 즉 맵의 노드와 경로를 정하는 기법에 대해 다룰 예정이다.출처:NDC2016 보충자료 – 2. 타일 맵 구현 실제

이번에는 지난 NDC2016 발표의 “맵 생성 절차”(59~69p.)에 대해서 좀 더 자세한 글을 써보려고 한다. 59페이지를 그대로 가져와보면 다음과 같다.

이 단계들에 대해 차례대로 설명하려고 한다.

1. Poisson Disc Sampling

맵에서 비교적 균일한 간격으로 노드를 선택하기 위한 방법이다. 완전한 랜덤이 아닌 이 방법으로 선택한 노드는 보기에도 좋고 활용도 편리하다. 하나하나의 노드가 도시나 별이라고 하면 서로 너무 멀거나 너무 가깝지 않은 적당한 거리를 유지할 수 있기 때문에 자연스럽기도 하다. 아래 그림에서 가장 오른쪽이 Poisson Disc Sampling 으로 생성한 노드들이다.

이미지 링크

Disc Sampling 이라는 이름대로 이 방법은 대기열에 속한 점(=노드) 주변에 있는 원형(Disc)의 영역에 다른 점을 추가할 수 있는지 검사한다.

새로 추가하는 점 주변에 다른 이웃이 없다면 그 점을 추가하고, 그 점을 대기열에 넣는다.
미리 정해진 tryCount 만큼 탐색하여 점을 여러 개 추가한다. 나는 tryCount를 30으로 설정했다.

tryCount 가 끝나면 대기열에 있던 점을 빼고 새로 추가된 점 중 하나를 대기열에 집어넣고 다음 탐색을 반복한다. 이때 주변에 다른 이웃이 없는지 체크해서 이웃이 있다면 그 점은 추가될 수 없다.

탐색을 빠르게 하기 위해 전체 맵을 그리드로 나누고, 그리드 안에는 하나의 점만 들어갈 수 있도록 제한한다. 따라서 원이 겹치는 영역에 있는 모든 점을 검사할 필요 없이, 원이 걸치는 그리드에 있는 점들만 검사하면 되기 때문에 탐색 시간이 줄어든다.

이해를 돕기 위해 예전에 만들었던 Poisson Disc Sampling 예제 링크를 올린다. 예제에서는 1프레임당 1개의 점을 탐색하도록 했기 때문에 점이 천천히 검색되는 것이지, 실제 검색 속도는 빠르다.

http://wonderfl.net/c/MMGa

2. Minimal Spanning Tree

트리란 두 개의 노드가 하나의 간선(edge)으로만 연결된 그래프를 말한다.

신장 트리(Spanning Tree)는 사이클(루프)가 없이 모든 노드를 연결하는 트리이다. 최소 신장 트리(Minimal Spanning Tree)는 이 중 모든 노드를 연결하면서 경로의 합이 가장 짧은 신장 트리를 말한다.

위에서 만든 노드들을 연결해서 그래프를 만드는데, 복잡한 계산을 줄이기 위해 일정 길이 이하의 간선만 남긴다. 그리고 여기서 최소 신장 트리를 찾는다.

3. 지형 배치

이렇게 최소 신장 트리를 찾은 다음에는 간선 연결이 하나뿐인 터미널 노드(terminal node)를 찾는데, 이곳에 물과 절벽을 배치한다. 터미널 노드에는 물이나 절벽 중 하나를 배치한다.

아래 그림에서 검은색으로 표시된 노드가 터미널 노드이다. 두번째 글에서 설명했던 Cellular Automata 기법으로 인접한 물, 인접한 절벽끼리는 서로 합쳐진 것을 확인할 수 있다.

이제 각 타일이 어느 지형에 속하는지 결정을 해야 한다. 어떤 타일은 풀이 먼저 그려진 다음 위에 물이 그려지고, 또 절벽까지 겹쳐져 있다. 일단 절벽(검은색)을 최우선으로 찾은 다음 물(파란색)을 찾고, 마지막으로 절벽과 물에 속하지 않은 곳을 이동 가능한 타일(하얀색)로 지정한다.

또한 경로에는 랜덤하게 길 타일을 배치해서 사실감을 높인다. 길 타일 역시 Cellular Automata 기법으로 너무 뚜렷하지 않게 자연스러운 모양을 유지하도록 했다.

4. 다시 Poisson Disc Sampling – 메인 경로 추출

지금까지의 작업이 그럴듯해 보이는 지형을 만들기 위한 것이었다면 이번 단계는 유닛들이 이동할 수 있는 메인 경로를 만드는 작업이다. 다시 Poisson Disc Sampling 을 이동 가능한 타일(하얀색)에 대해서만 수행한다. 그리고 경로는 이동 가능한 타일을 지나는 것만 인정하고, 중간에 절벽이나 물과 겹치는 경로는 제외한다.

5. 메인 노드 정하기 & 유닛 배치

그럼 이제 1:1 대결을 상정한 맵이기 때문에 각 팀의 유닛을 배치할 메인 노드를 결정한다. 메인 노드 2개는 서로 연결되어야 하고, 그 거리는 맵의 가로 길이 + 맵의 세로 길이의 40% 에서 100% 사이의 값이 되어야 한다. 적당한 메인 노드 2개를 발견하지 못했을 경우 맵 전체를 다시 생성한다.

메인 노드에는 각 팀이 지켜야 할 타워를 생성하고 그 주위에 유닛을 배치한다. 이제 양 팀은 서로의 타워를 파괴하기 위해 서로 대결을 펼치게 된다. 참고로 타워가 구석에 있을수록 유리한데, 보병과 기병은 인접해야만 타워에 공격이 가능하기 때문이다. 이 맵에서 Blue Team의 승률은 300번의 전투 시뮬레이션을 돌렸을 때 85.0%가 나왔다.

약간 길었지만 발표 중에 가장 정리하고 싶었던 부분인 맵 생성 절차를 정리해 보았다. 다음에는 시간이 된다면 딥러닝 실행 부분을 정리해보려고 한다. 양이 많아서 아마 글 하나로는 안될 것 같다.출처:NDC2016 보충자료 – 3. 맵 생성 절차

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다