Cave Dungeon Generation

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.

Key Idea 

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:

1. Create rooms in a random position
2. Connect each room by corridors

Create rooms in a random position

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

1. Create K rooms including spares along the spiral
2. Among them, only N rooms are randomly selected.

The spiral is not important. You can also use any other method that allows you to properly place the room in a 2d space.

Connect rooms #1

Now it's time to decide which rooms to connect to.

1. Create a mesh with the center points of the room. By applying the Delaunay triangulation algorithm, all rooms can be meshed as shown below. Since the implementation of this algorithm is complicated, it is recommended to find the implemented code on github rather than implementing it yourself.
2. No fun when all the rooms are connected. Remove unnecessary connections. The Minimum Spanning Tree (MST) allows you to create the least costly (shortest) connection that goes through every room.
3. However, if you use only MST, the map becomes monotonous because there is no loop in the map, and it makes a loop by connecting a few more lines.

The blue line below indicates that the two rooms are connected.

Connect rooms #2

Now it's time to connect the rooms.

1. First, I add some noise to each room because it won't be natural if the rooms in the cave are square.
2. The room and the room find the path using the A* algorithm.
3. Add some noise to the path.

Smoothing

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.

Painting

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)의 조합으로 표현될 수 있습니다. 복잡한 형태의 동굴도 여러개의 방과 방사이를 잇는 복도의 집합으로 모델링 될 수 있습니다. 따라서 다음과 같이 두단계의 아주 단순한 방식으로 동굴을 만들어 낼 수 있습니다.

1. 랜덤한 위치의 방을 생성
2. 방과 방을 복도로 연결

랜덤 방의 생성

방과 방은 너무 멀지 않아야 하고 영역이 겹치면 안됩니다. 여러가지 솔루션들이 있겠지만 저는 나선을 따라 방을 배치하는 단순한 방법을 이용했습니다. 중점에서 거리 r 만큼 되는 점을 선택합니다. 중점에서 이 점까지 이어지는 vector를 v라고 하겠습니다. v를 조금씩 회전시키면서 새로운 방을 생성합니다. v가 회전될때마다 r을 조금씩 늘립니다.

1. 나선을 따라 여분을 포함한 K개의 방을 생성
2. 그중 N개의 방만을 랜덤하게 선택

나선이 중요한 것은 아닙니다. 공간상에 방들을 적절히 배치할수 있는 다른 방법을 사용하셔도 됩니다.

방과 방을 연결 #1

이제 어떤 방과 어떤 방을 이어줘야 할지 정해야 할 단계 입니다. 

1. 모든 방을 메시화 해줍니다. 방의 중앙의 점들로 Delaunay triangulation 알고리즘을 적용하면 모든 방을 아래와 같은 메시로 이어줄 수 있습니다. 이 알고리즘은 구현이 복잡해서 직접 구현하는 것 보다는 github에서 구현된 코드를 찾는것을 추천드립니다.
2. 모든 방이 연결되면 재미가 없습니다. 필요 없는 연결은 제거합니다. MST(Minimum Spanning Tree) 를 이용하면 모든 방을 지나는 최소 비용(가장 짧은)의 연결 을 만들 수 있습니다.
3. 하지만 MST만을 이용하면 맵에 루프가 없기 때문에 맵이 단조로워 져서 약간의 선을 더 이어서 루프가 있게 만들어 줍니다. 

아래의 푸른색 선이 연결된 방과 방의 정보입니다. 

방과 방을 연결 #2

위에서 어떤 방과 어떤 방을 이어야 하는지 까지 정했습니다. 이 단계에서는 실제로 방과 방을 잇습니다.  

1. 동굴의 방들이 정사각형이라면 자연스럽지가 않기 때문에 각 방에 약간의 노이즈들을 추가합니다. 
2. 방과 방은 A* 알고리즘을 이용해서 path를 구합니다. 
3. 연결된 path에 약간의 노이즈를 추가해서 복도를 구성합니다. 

부드럽게 만들기

너무 복잡한 부분들을 부드럽게 할 차례 입니다. Cellular Automata 알고리즘을 이용합니다. 이 알고리즘은 마치 대패질을 하는 것과 비슷하게 동작합니다. 튀어나오고 각진 부분을 없애 버립니다. 4~5번 반복적으로 알고리즘을 적용시켜서 각진 부분을 제거합니다. 아래 파란색 부분이 이 알고리즘에 의해 Smoothing 된 부분입니다. 

페인팅

다 되었습니다. 이제 생성된 맵을 타일들로 잘 칠해주고 오브젝트들을 배치하는 일만 남았습니다. 이 부분은 생성과는 상관 없는 부분이라 설명을 생략하겠습니다. 아래는 P3에서 타일 페인팅과 오브젝트 배치가 끝난 후의 모습입니다.

결론

지금까지 동굴을 자동으로 생성하는 방법에 대해 알아봤습니다. 이 방식은 플레이마다 매번 다른 맵을 자연스럽게 만들 수 있다는 것이 장점입니다. 다만 구현에 다소 난이도가 있는 것이 단점입니다. 도움이 되었길 바랍니다.