절차적 맵 생성(Procedural Map Generation)

안녕하세요. 어느덧 새해가 밝았네요. 지난번에 절차적 생성에 대해서 잠깐 글을 썼었는데 의외로 많은 분들이 관심을 가져주셔서 좀 더 내용을 보충해보려고 합니다. 사실 그동안 절차적 생성을 사용하는 제 개인 프로젝트도 계속 휴면 상태였는데 신년도 되었고 겸사겸사 다시 재개해보려고 생각중이네요. 오늘은 RPG 게임의 던전과 같은 맵에 대해서 몇가지 이야기해보려고 합니다. 부족한 부분이나 잘못된 내용이 있다면 얼마든지 지적해주시기 바랍니다. 1. BSP (Binary Space Partitioning) 한국어로는 이진 공간 분할법이라고 하는, BSP 트리를 이용하는 방법입니다. 알고리즘에 대해서 서술해보면 재귀적으로 공간을 반으로 n번 나누어 작은 공간(잎)으로 만들고, 나누어진 부분공간 안에 일정한 크기의 방을 만듭니다. 이후 나누었던 트리의 잎에서부터 다시 위로 올라가면서 (병합하면서) 통로를 잇는 방법입니다. 한가지 팁을 더 드리자면 위 데모에서는 마지막에 통로를 건설할때 직선으로 잇고 있는데 공간을 나눌때 사용했던 선을 활용하면 좀 더 자연스러운 (구불거리는) 통로를 만들 수 있습니다. (통로 건설의 예시) 2. Cellular Automata 한국어로는 세포 자동자라고 되어 있는데 절차적 생성만큼이나 알아먹기 힘든 말이네요. 저는 한국어 용어를 사용하는걸 좋아하긴 하지만, 그냥 셀룰러 오토마타라고 하겠습니다... 제 경우에는 인공지능을 공부하던 시절에 몇번 들어본 내용이네요. 그래서 이름만 압니다... 절차적 생성 분야에서도 꽤 빈번하게 언급되는 기술입니다. 셀룰러 오토마타는 주로 자연스러운 동굴 모양의 던전을 만들 때 사용되는데요. 한가지 문제가 있다면 난수에 굉장히 의존적이기 때문에 어떤 형태의 동굴이 만들어질지 예측하기가 어렵습니다. 그렇기 때문에 하나의 거대한 동굴이 만들어질 수도 있고, 작고 연결되지 않은 공간이 여러개 만들어질 수도 있습니다. 물론 매개변수를 조절함으로써 빈도를 어느정도는 한쪽으로 몰아줄 수는 있지만 완전하게 하기 위해서는 후처리 작업이 필요하죠. 알고리즘은 간단한데 먼저 맵을 랜덤하게 벽으로 채우고, 특정 알고리즘을 n회 정도 반복 수행하면 됩니다. 예시를 하나 들면 먼저 45% 비율로 맵을 벽으로 채우고, 타일 하나를 선택하여 자기자신을 포함한 주변 타일 9칸 중 5칸 이상이 벽일 경우 해당 타일을 벽으로 바꾸는 알고리즘을 4회 수행합니다. 결과물은 다음과 같습니다. 매개변수나 알고리즘을 조율해보면 여러가지 형태의 재미있는 동굴맵이 나옵니다. 이후 모든 공간을 연결하기 위해 분리된 공간을 찾아 통로를 건설하여 연결하기도 하지만 제 경우에는 그냥 두는 것이 더 자연스럽더군요. 제가 과거에 만들었던 것들 중 두가지인데 첫번째는 전형적인 셀룰러 오토마타를 이용한 동굴맵이고, 두번째는 로이드(Lloyd) 알고리즘을 이용한 숲인데 이 방법도 지금보니 괜찮네요. 자료는 둘 다 이미 폐기되었지만... 3. Herringbone Wang tiles 먼저 왕 타일은 상하좌우가 다른 색으로 칠해져있고 타일을 조립할때 반드시 같은 색의 부분이 서로 마주하도록 만들어진 타일입니다. 비트연산을 이용한 타일맵을 만드는 방식과도 거의 유사합니다. 요런 타일을 가지고 요런식으로 조립하는 거죠. (왕 타일을 이용한 맵 예시) 보면 아시겠지만 알고리즘 보다는 패턴 안에 채워넣는 맵(레벨 디자이너)이 중요한 방식입니다만 결과물은 참 흥미롭습니다. 아무튼 왕 타일은 그렇고, 헤링본 왕 타일은 정사각형이 아닌 직사각형(헤링본 패턴)을 활용하는 방식인데 헤링본(청어뼈) 패턴이라는 건 요런 모양입니다. 그래서 아래의 패턴 블럭을 가지고 조립하면 이런 결과물이 나오는 것이죠. 저도 헤링본은 아직 직접 구현해본적은 없는데 원저자가 오픈소스 라이브러리를 만들어두었으니 그쪽을 참고하시면 구현하는 것도 크게 어렵지는 않을 것으로 생각됩니다. 사실 헤링본 쪽은 시간이 없어서 아직 덜 읽어본터라 내용이 부실합니다. 관심있는 분들은 원출처로... http://nothings.org/gamedev/herringbone/ . . . 그래프에 대한 내용도 추가하려고 했는데 뜻밖의 님이 몇번 글을 써주셨기 때문에 그 부분은 생략하고 기초적인 알고리즘 두개와 제가 근래에 흥미를 가지고 있는 알고리즘 하나에 대해 적어봤습니다. 적고 싶은 내용이 더 많이 있지만 쓰다보면 끝이 없을 것 같기도 하고 귀차니즘이 또... 아무튼 부족한 내용을 읽어주셔서 감사합니다. + 추가 TinyKeep의 그래프를 이용한 던전 생성 알고리즘의 보충설명이 될만한 레퍼런스입니다. https://github.com/adonaac/blog/issues/7

펌 : http://www.gamecodi.com/board/zboard.php?id=GAMECODI_Talkdev&page=1&sn1=&divpage=1&sn=off&ss=on&sc=on&select_arrange=headnum&desc=asc&no=3763