Posted June 23, 2021 by concode
The P3 (code-name, no name yet) is a game in the genre of rogue-like dungeon crawler. Due to the nature of the genre, dungeons must be recreated for every play. There is a way to create a lot of presets, but I want to implement a method that automatically creates dungeons to reduce the effort of human editing. The 'Procedural map generation' is a long-standing topic in game dev, and there are many ways to do it. The P3's dungeons are mostly caves. In this post, I will talk about how to automatically create a cave-type dungeon with good quality.
A cave can be represented as a combination of rooms and corridors. A cave with a complex shape can be modeled as a set of corridors connecting several rooms and rooms. So you can create a cave in a very simple two-step method:
The rooms should not be too far apart and the areas should not overlap. There are many solutions, but I've used a simple way of arranging the rooms along a spiral. Pick a point a distance r from the center. Let v be the vector from the center to this point. Rotate v a little to create a new room. Each time v is rotated, we increase r a little
The spiral is not important. You can also use any other method that allows you to properly place the room in a 2d space.
Now it's time to decide which rooms to connect to.
The blue line below indicates that the two rooms are connected.
Now it's time to connect the rooms.
It's time to smooth out the overly complex parts. For this, I use the Cellular Automata algorithm. This algorithm behaves like a planer. Get rid of the protruding and angular parts. Iteratively applies the algorithm 4 to 5 times to remove angular parts. The blue part below is the part smoothed by this algorithm.
Now all that remains is to paint the generated map with tiles and place the objects. Since this part has nothing to do with creation, I will omit the description. Below is what it looks like after tile painting and object placement in the P3.
Conclusion
So far we have seen how to automatically create caves. The advantage of this approach is that you can naturally create a different map each time you play. However, the disadvantage is that it is somewhat difficult to implement. Hope this helps.
+ This article was written using a translator. There may be some awkward sentences. Let me know how you can fix it in the comments.
Korean
게임 P3(코드네임, 아직 이름 없음)는 로그라이크 던전 크롤러 장르의 게임입니다. 장르의 특성상 던전은 매 플레이마다 매번 새로 만들어져야 합니다. 프리셋을 많이 만드는 방법도 있겠지만, 사람이 편집하는 수고를 덜게 자동으로 던전을 생성하는 방법을 구현하고자 합니다. 던전 자동 생성은 게임 제작 분야에서 오랫동안 노력해왔던 주제로 다양한 방법이 있습니다. P3의 던전은 주로 동굴 형태입니다. 이 포스트에서는 동굴 형태의 던전을 괜찮은 퀄리티로 자동 생성하는 방법에 대해 이야기 해보겠습니다.
동굴은 방(Room)과 복도(Corridor)의 조합으로 표현될 수 있습니다. 복잡한 형태의 동굴도 여러개의 방과 방사이를 잇는 복도의 집합으로 모델링 될 수 있습니다. 따라서 다음과 같이 두단계의 아주 단순한 방식으로 동굴을 만들어 낼 수 있습니다.
방과 방은 너무 멀지 않아야 하고 영역이 겹치면 안됩니다. 여러가지 솔루션들이 있겠지만 저는 나선을 따라 방을 배치하는 단순한 방법을 이용했습니다. 중점에서 거리 r 만큼 되는 점을 선택합니다. 중점에서 이 점까지 이어지는 vector를 v라고 하겠습니다. v를 조금씩 회전시키면서 새로운 방을 생성합니다. v가 회전될때마다 r을 조금씩 늘립니다.
나선이 중요한 것은 아닙니다. 공간상에 방들을 적절히 배치할수 있는 다른 방법을 사용하셔도 됩니다.
이제 어떤 방과 어떤 방을 이어줘야 할지 정해야 할 단계 입니다.
아래의 푸른색 선이 연결된 방과 방의 정보입니다.
위에서 어떤 방과 어떤 방을 이어야 하는지 까지 정했습니다. 이 단계에서는 실제로 방과 방을 잇습니다.
너무 복잡한 부분들을 부드럽게 할 차례 입니다. Cellular Automata 알고리즘을 이용합니다. 이 알고리즘은 마치 대패질을 하는 것과 비슷하게 동작합니다. 튀어나오고 각진 부분을 없애 버립니다. 4~5번 반복적으로 알고리즘을 적용시켜서 각진 부분을 제거합니다. 아래 파란색 부분이 이 알고리즘에 의해 Smoothing 된 부분입니다.
다 되었습니다. 이제 생성된 맵을 타일들로 잘 칠해주고 오브젝트들을 배치하는 일만 남았습니다. 이 부분은 생성과는 상관 없는 부분이라 설명을 생략하겠습니다. 아래는 P3에서 타일 페인팅과 오브젝트 배치가 끝난 후의 모습입니다.
지금까지 동굴을 자동으로 생성하는 방법에 대해 알아봤습니다. 이 방식은 플레이마다 매번 다른 맵을 자연스럽게 만들 수 있다는 것이 장점입니다. 다만 구현에 다소 난이도가 있는 것이 단점입니다. 도움이 되었길 바랍니다.