Procedural Generation(절차적 생성)
랜덤 맵을 구현해야 하는 상황이 생겨서 얼마전 부터 간단한 절차적 생성 알고리즘들을 공부해 보고 있다. 처음에는 일정 크기의 방들을 맵툴로 찍어낸 후 생성된 방들을 알고리즘을 통해 섞어낼려고 했었다. 그러다가 이왕 만들어보는 절차적 생성이니 만큼 별도의 맵툴없이 구현해 보고 싶어졌다.
처음에는 셀룰러 오토마타 방식으로 구현을 해보았는데 마음에 드는 모양을 만드는게 너무 어려웠다.
셀룰러 오토마타 알고리즘은 매우 간단한데 각 타일마다 주변 타일을 검사해서 자신의 상태를 결정하는 알고리즘이다. 많은 부분이 난수에 의존하기 때문에 어느정도 원하는 모양의 동굴을 만들어 내기가 힘들다.
그래서 다른 방식을 써서구현을 하게 되었는데 순서는 다음과 같다.
1. 랜덤한 크기의 방들을 일정기준안에서 난수로 생성한다.
2. 다음으로 생성된 방들을 전부 충돌처리해서 밀어내게 한다.
3. 생성된 방들의 중심점을 기준으로 삼각형 리스트를 만든다. 이때 삼각형들은 들로네 삼각분할 알고리즘을 이용해서 생성한다.
4. 생성된 삼각형 리스트들을 기반으로 최소 스패닝트리를 이루는 선들만 추려낸다. 추려낸 후에는 루트를 추가적으로 생성해준다.
5. 연결된 선을 직각을 이루는 선으로 분할한다.
6. 해당 선을 기준으로 통로를 건설한 후 통로가 지나는 방을 전부 빈공간으로 만든다. 이외의 공간은 전부 벽으로 설정해준다.
이제 이 데이터를 기반으로 타일을 구축하면 된다. 막상 만들어보니 이 던전도 내가 원하는 모양이 잘 안나오고 있다.
이래저래 결론은 내가 알고리즘에 약하다는 뜻이다. . .
Youtube 링크 : https://www.youtube.com/watch?v=hx_y4BhdXo8