NetHack 노움 광산의 던전 생성

요약

NetHack 노움 광산은 무작위로 채운 지도에 셀룰러 오토마타를 네 번 돌려 동굴을 만듭니다.

절차적 생성을 다루는 블로거 보리스 더 브레이브가 노움 광산 층의 생성 과정을 직접 돌려 볼 수 있는 시각화 도구와 함께 풀었습니다. 게임의 다른 구역은 대부분 네모난 방이지만, 광산만은 셀룰러 오토마타(이웃 칸의 상태에 따라 각 칸을 바꾸는 규칙)로 동굴 모양을 냅니다.

왜 중요한가

간단한 규칙 몇 개만으로 방 위주의 다른 구역과 확연히 다른 동굴 느낌이 난다는 점을 보여 줍니다.
단계마다 지도가 어떻게 바뀌는지 볼 수 있어 규칙 하나하나의 역할을 눈으로 확인할 수 있습니다.

핵심 내용

먼저 전체 칸의 40%를 무작위로 바닥으로 정하고, 규칙을 네 번 적용한 뒤 끊어진 동굴은 통로를 더 뚫어 잇습니다.
1단계는 이웃 8칸 중 바닥이 2개 이하면 바위, 5개 이상이면 바닥으로 바꿔 비슷한 칸끼리 뭉치게 합니다.
3·4단계는 바닥 이웃이 2개 이하인 칸을 바위로 바꾸는 침식 단계로, 모서리를 다듬고 작은 바닥 조각을 없앱니다.
2단계는 바닥 이웃이 정확히 5개인 칸만 바위로 바꾸는데, 글쓴이도 목적을 몰라 독자 의견을 구했습니다.
1단계만 바뀐 칸을 곧바로 반영하고, 나머지 단계는 모든 칸을 계산한 뒤 한꺼번에 바꿉니다.

HN 반응

2단계를 두고 일부 이용자는 곧은 경계에 오목한 곳을 더해 동굴을 둥근 거품보다 가시처럼 뾰족하게 만든다고 해석했습니다.
RogueBasin에 소개된 셀룰러 오토마타 동굴 생성법과 같다는 지적과 함께, 직접 만져 볼 도구를 곁들인 글 형식을 반기는 댓글이 이어졌습니다.

14개 표시 · 전체 15개

shoo1시간 전 HN

멋지네요. 인터랙티브 시각화가 설명하기에 아주 좋은 방법입니다.

비슷한 발상을 격자 없이 연속적인 2차원 공간에서, 2D 계산기하 연산으로 구현해 볼 수도 있을 것 같습니다(예: GEOS [1]의 buffer 연산으로 도형을 주어진 반지름만큼 키우는 식으로요).

각 구성 요소는 점 집합, 즉 우리가 작업하는 2차원 공간의 점들 가운데 일부입니다.

  1. 어떤 분포에서 시드 점을 잔뜩 뽑는다. 이 점들이 처음의 연결된 구성 요소가 된다
  2a. 각 구성 요소를 반지름 r만큼 키운다. 서로 닿는 구성 요소는 합친다
  2b. 각 구성 요소를 반지름 r + delta만큼 줄인다. 점이 하나도 남지 않은 구성 요소는 삭제한다
  3. '너무 작은' 구성 요소를 삭제한다: 각 구성 요소를 r_min만큼 줄이고, 점이 하나도 남지 않은 것은 삭제한 다음, 살아남은 구성 요소를 다시 r_min만큼 키운다
  4. 살아남은 연결 구성 요소들을 어떻게든 이어 준다:
  4a. 서로 인접한 구성 요소 쌍을 찾는다 (예: 점 대신 구성 요소를 시드로 삼아 보로노이 '삼각분할'을 계산하고, 결과로 나온 삼각형 두 개가 맞닿으면 그 구성 요소들은 이웃이다)
  4b. 인접한 구성 요소 쌍마다 서로 가장 가까운 점끼리 잇는 통로 후보를 제안한다
  4c. 통로 길이를 간선 가중치로 삼아, 구성 요소-통로 그래프에서 최소(혹은 흥미로운) 신장 트리를 찾는다
  4d. 선택된 통로를 선 기준으로 일정 반지름만큼 키워 파낸다
  4e. 결과는 하나의 커다란 연결 구성 요소가 되어야 한다
  5. 플레이할 만한 결과가 나왔는지 점검한다 (면적 등으로). 너무 작거나 재미없으면 버리고 1단계부터 다시 시도한다

4a 단계를 평면에서 효율적이고 합리적으로 하는 방법은 잘 모르겠습니다. 그래프에서라면 간단하고 효율적일 텐데요. 그래프를 보로노이 삼각분할하는 비용은 어떤 출발점에서 모든 최단 경로를 찾는 비용과 비슷합니다. 가장 가까운 시작점까지의 최단 경로를 복원하기 위한 기록과 약간의 논리가 더 붙는, 다중 시작점 BFS 같은 것이죠.

작은 격자에서 돌아가는 NetHack의 셀룰러 오토마타 방식 그노미시 광산 알고리즘이, GEOS의 Buffer와 Union 호출을 잔뜩 끌어다 쓰며 씨름하는 것보다 당연히 훨씬 빠르겠지만, 이 발상이 어디까지 확장되는지 따져 보는 것도 재미있습니다.

[1] https://libgeos.org/

OkayPhysicist8시간 전 HN

제 생각에 두 번째 패스는 오목한 영역을 더 만들어 내려는 겁니다. 주로 직선을 대체하는 방식으로요. 그러면 변곡점이 잔뜩 생기고, "방울방울한" 느낌 대신 유기적이고 "가시 같은" 느낌이 나게 됩니다. 이 패스가 없으면 생성된 동굴은 왁스 칠한 표면에 액체를 쏟은 것처럼 보이고, 가시덤불 같은 느낌은 줄어듭니다.

자바스크립트에서 "for(let p=0;p<3;p++)"를 "for(let p=1;p<3;p++)"로 바꾼 다음 콘솔에서 그 블록을 다시 실행하면, 2단계 없이 여러 세대를 돌려 볼 수 있습니다.
omoikane2시간 전 HN

여기 설명된 알고리즘과 똑같은 것 같네요.

https://www.roguebasin.com/index.php/Cellular_Automata_Method_for_Generating_Random_Cave-Like_Levels
bovermyer8시간 전 HN

제가 제일 좋아하는 종류의 절차적 생성 블로그 글입니다. 우리가 이렇게 했다고 설명하고, 어떻게 돌아가는지 직접 만져 볼 수 있는 작은 위젯까지 붙여 주는 글이요.
munificent3시간 전 HN

제가 예전에 쓴 이 글도 마음에 드실 겁니다.

https://journal.stuffwithstuff.com/2014/12/21/rooms-and-mazes/
Rooster619시간 전 HN

와, 이게 셀룰러 오토마타 기반인 줄은 전혀 몰랐어요. 던전의 다른 구역들과는 느낌이 완전히 다른 게 정말 그래서였네요.
ImJasonH5시간 전 HN

그 많은 공을 들여 만들어 놨더니, 곡괭이 든 불한당 드워프 고고학자(접니다)가 나타나서 쓸모없는 유리 쪼가리 몇 개 얻겠다고 다 파헤쳐 버리죠.
jmclnx8시간 전 HN

관련된 소식인데, TNNT가 9일 뒤(11월 1일)에 시작합니다. 누구나 토너먼트에 참가할 수 있습니다.

https://tnnt.org/
schoen1시간 전 HN

기대되네요! 연습 좀 하려고 방금 생애 첫 NetHack 5.0 게임을 시작했어요.
juancn7시간 전 HN
이웃 타일 번호 매기는 방식이 이해가 안 됩니다. 이런 식입니까?
```
    0 1 2
    3 4 5
    6 7 8
```
그럼 현재 셀은 어디입니까?

그림이 있으면 도움이 되겠습니다.
gjm117시간 전 HN

설명 어디에도 이웃 셀을 하나하나 가리키는 내용은 없어요. 저 숫자들은 전부 개수예요. 이웃 셀 중 0~2개가 바위면 이렇게 하고, 하는 식이죠.
card_zero7시간 전 HN

글 얘기를 하시는 건가요, 아니면 소스 코드에 있는 걸 말씀하시는 건가요?

글에서는 8개 타일 중 바닥이 몇 개인지 세기만 해요(그래서 하나도 없는 경우까지 9가지가 나옵니다). 인덱스 번호는 붙지 않아요.

추가: ㅋㅋ, 다들 한꺼번에 달려들었네요. 덕분에 같은 설명이 세 가지 방식으로 나왔어요.
Luc7시간 전 HN

번호 매기기는 없고, 그냥 이웃의 수를 세는 겁니다. '0-2'는 이웃이 0개, 1개, 2개라는 뜻이에요.
jdw648시간 전 HN

절차적 생성을 정말 잘하는 분들에게는 늘 큰 존경심이 듭니다.

Hacker News에서 보기 ↗