Occam's Razor - Random Map Generation

자동 지형 맵 생성 기법

디아블로 같은 게임을 보면 게임을 새로 시작하면 전혀 다른 지형의 게임이 펼쳐집니다. 프로그램이 던젼 맵을 자동으로 랜덤하게 생성시키는거지요. 이번에 이야기할 기법은 던젼 맵이 아니라 지형 맵을 자동으로 생성하는데 쓰이는 기법입니다.

심시티에서 사용자 맵을 만들때 사용하는 것과 기본적으로 동일합니다. (알고리즘 자체가 동일하다는 것은 아닙니다.)

지형 맵은 다시 말하면 산, 평야, 강, 호수, 바다 등이 있는 맵으로, 인공적인 직각이 없어야 합니다. 이에 비해 던젼 맵은 기본적으로 미로 생성 기법과 비슷할겁니다. 던젼 맵 자동 생성에 대해서 좋은 의견이나 아이디어가 있으면 메일을 보내 주세요. 이번 기법의 기본적인 아이디어 역시 인터넷에서 얻었습니다. 바탕에 깔린 개념은 프랙탈 이론으로 유명한 '만델브로트'의 프랙탈 기하학입니다. 그럼 개략적인 단계를 설명하지요.

직사각형의 2차원 맵 상에 한 점을 난수로 결정한다.
그리고 각도를 난수로 결정한다.
점을 지나며 2에서 결정한 난수의 각도를 가지는 가상 선을 긋는다.
선으로 나뉘어진 두 부분 중 한 부분은 맵 데이터를 하나 증가하고, 나머지 부분은 하나 감소시킨다. (어느 부분을 증가시키는지는 역시 난수로 결정)
1에서 4까지의 과정을 충분히 반복(100000번 정도)한다. (10만번! 이에 대해서는 글 뒷부분의 '구현시 고려해 볼 점'를 보세요.)
맵 데이터를 해석해서 타일 번호로 변환한다.

실제로 코딩해서 실행해보지 않고는 개념이 잘 안잡힐 수도 있습니다. 뭐 대충 이런것입니다. 처음 루프를 돌면 맵의 반은 바다, 반은 평야입니다. 두번째 턴에서는 그 모양이 조금 더 복잡해 지겠지요. 이런 과정을 10만번 정도 반복하면 아주 사실적인 지형이 생긴다고 합니다.

구현시 고려해 볼 점

펜티엄 90에서 델파이 3.0으로 간단하게 구현해 보았는데, 조만간 자료실에 올리죠. 위의 원래 알고리즘을 참조해서, 몇가지 변화를 주었습니다. 그럼 구현시 고려해 볼 점, 또 제가 고려했던 점들을 쓰겠습니다.

위의 1-3 단계에서 점 하나와 각도(말하자면 기울기)로 선을 긋는 것도 좋지만 두 점을 난수로 정해서 두 점을 잇는 선을 그어도 좋을 것입니다. (1차 함수의 공식만 있으면 됩니다.) 기울기와 y절편을 난수로 정하는 것은 좀 문제가 있더군요. 맵이 한쪽으로 몰리는 경향이 있습니다. (난수의 문제?) 또, 난수을 생성할때 예를 들면 100x100의 맵에서 x,y의 값을 10에서 90 사이의 수로 생성하면, 가운데는 복잡하고 바깥쪽은 덜 복잡한 모양이 나오는데, 이게 더 사실적이었습니다.

6번의 맵 데이터 분석이 사실 문제입니다. 하나의 아이디어는, 맵 데이터를 지형의 높이라고 생각하는 것입니다. 어떤 수치(예를 들면 0)을 해수면이라고 생각하면, 0 보다 작은 부분은 물입니다. 또 어느 범위 까지는 평야, 어느 범위 까지는 숲, 어느 범위 이상은 산, 더 높은 곳은 눈덮인 산 등으로 해석해서 타일 그래픽과 연결시키면 되지 않을까요. 그리고 복셀 스페이스 등 3차원 맵으로 변환한다면 그냥 높이 데이터를 그대로 써도 되겠지요.

아니면 이런 방법도 있습니다. 타일의 종류가 5가지라고 한다면, 맵 데이터를 5로 나눈 나머지를 사용하는 것입니다. (음수는 적절히 양수로 바꿔 줘야겠지요) 제 프로그램에서는 두 가지 다 해 볼 수 있습니다. 높이로 한 경우 좀 사실적이긴 하지만, 강은 잘 나타나지 않습니다. (강이란 물이 가늘게 이어지는 현상이지요.) 또 산 속에 호수가 있는 현상도 나타나지 않더군요. 나머지로 한 경우에는 높이를 고려하지 않은 것이니 산 속에 호수가 있거나 평야에서 바로 산이 솟거나 하는데, 어떨때는 이게 더 사실적으로 보이기도 합니다.

알고리즘을 보면 선으로 나눈 두 부분 중 한 부분은 1을 더하고 한 부분은 1을 뺀다고 했습니다. 그런데 이렇게 하면 맵의 값들이 항상 2씩 차이가 납니다. 즉 짝수번 루프에서는 짝수만, 홀수번 루프에서는 홀수만 나타나지요. 높이로 해석하면 상관없겠지만, 나머지로 해석하면 나타나지 않는 타일 종류도 생깁니다. (특히 나누는 수가 짝수인 경우) 따라서 나머지 기법을 사용하려면 선으로 나눈 두 부분 중 한 부분만 선택해서 1 을 더하거나 빼는 것으로 알고리즘을 수정해야 합니다.

이 기법의 원 저자의 말로는, 컴파일러의 난수 발생 루틴에 따라 결과가 틀리다고 합니다. Ansi C의 rnd나 lrnd는 별로라고 하더군요(컴파일러 제품에 따라 틀리겠지만..). 난수 발생루틴이 시원챦으면 맵의 한쪽은 산만, 한쪽은 바다만 나올 수 있다고 합니다. 10만번 정도 난수를 발생시키면 일정한 패턴이 생기기 마련이겠지요. 10만번 정도 돌려도 난수 다운 난수가 나오는 루틴이 필요하다고. 제 경우 나머지로 해석할때에는 100x100에서 200-300 정도만 돌리면 그럴듯하게 나오며 그 이상은 너무 지저분해집니다. 높이로 해석하는 경우는 많이 돌릴수록 좋은 것 같습니다. 델파이의 난수 루틴은 뭐 별 문제 없는 것 같더군요

속도 면에서, 펜티엄 90에서 델파이 3.0으로 만든 제 프로그램의 경우 100x100맵을 1000번 돌리는데 한 7-8초 걸립니다. 높이로 해석하는 경우 적어도 5000번 이상은 돌려야 하니 시간이 좀 걸리는 편이지요. 나머지로 해석하는 경우는 200-300번만 돌리면 되니 별 문제 없을 것입니다.

최종적으로 생긴 맵 데이터(타일 번호로 변환된) 를 블러링 또는 잡음제거 기법으로 수정하는 것도 고려해볼만 합니다. 이미지 프로세싱 분야의 공부를 하면 도움이 될 것입니다. 지형이 너무 복잡하게 나온다면, 다음과 같은 알고리즘을 적용해 보는 것도 좋습니다.

맵 데이터를 임시 맵 배열에 복사
임시 맵의 각 타일마다, 자신과 주변 여덟개의 타일 중에서 가장 많이 있는 타일을 선택해서 그 타일로 바꿔줌.(참조는 원래 맵을, 변경은 임시 맵에서 해야 병렬 처리가 됩니다.)
임시 맵을 원래 맵에 복사하고 1-3을 적당히 반복.

이렇게 하면 맵이 좀 평준화되서 단순하게 됩니다. (즉 타일이 점점이 흩어져 있는 현상이 사라지지요.) 높이 데이터인 경우 자신을 포함한 주변 타일들의 값의 평균을 사용해도 될 것입니다.

맵 데이터를 타일 번호로 해석할때 타일이 나타나는 비율을 조정할 수 있으면가장 적합한 지형을 쉽게 만들어 낼 수 있을 것입니다. 그러면 여러가지로 실험해 보기가 편합니다. 실제 게임에 넣을 경우 사용자가 직접 조정할 수 있게 할 수 있어야 합니다. 아마 심시티가 그랬던 것 같은데, 별로 어려운 일은 아닙니다.

스크린샷

다음은 제가 간단하게 만든 프로그램을 이용해서, 100x100 맵에서 800번 루프를 돌린 후의 결과들입니다. 클릭하면 큰 그림이 나옵니다.

타일 출현 비율을 적용한 경우

그냥 나머지로 해석한 경우(평준화시켰음)

높이를 색상 스케일로 변환한 경우(해수면이라는 경계치를 적용)

에필로그

이 기법에서 가장 아쉬운 것은 '강'이 잘 나타지 않는다는 것입니다. 전체적으로 보면 다도해 주변 같은 모습이나 산악 지방에 분지가 있고 분지 안에 호수나 늪이 흩어져 있는 모습이 가장 잘 나옵니다. 강이 나타나게 하는 새로운 기법이 있다면 연락해 주세요.