마인크래프트 지하유적에서 포탈 방 찾는 법

최근에 새로 생긴 취미가 있는데 마인크래프트 스피드런 공부입니다.

단순히 빠르게 하는 종목인 줄 알았는데 빠르게 하기 위해서 마인크래프트와 Java 언어의 알고리즘에 대해서 굉장히 많은 연구와 자료가 있더라구요. 그 점이 흥미로워서 공부를 하다보니 외울 게 너무 많아서 기록용으로 남겨볼까 합니다.

참고로 버전은 스피드런 대표 버전인 1.16.1 버전 기준입니다.

 

특히 지하 유적Stronghold에서 포탈 방Portal Room을 찾는 것은 비단 스피드러너뿐만 아니라, 일반 마인크래프트 유저들에게도 도움이 되는 정보 중 하나라고 생각합니다.

 

실제로 엔더눈으로 유적까진 찾았는데 유적 안에서 길을 잃고 말 그대로 2시간 이상 쓰는 경우도 정말 많거든요.

 

선 요약 후 설명

1. 엔더 눈을 던져서 엔더 눈이 땅으로 들어가는 청크를 찾습니다.
2. 그 청크 내에서 청크 좌표가 (3, x, 3)인 곳을 직선으로 파면 '시작 계단'이 나옵니다.
3. 시작 계단에서 나온 '시작 방'은 항상 (최대) 5갈래로 나뉘어지는 방인데 이 방은 히든 방이 있을 수 있고, 그 히든 방을 찾아야만 포탈 룸으로 연결되는 길이 나올 수 있습니다. (시작 계단에서 문을 열고 시작 방으로 나왔을 때 바라보는 방향이 -x 방향이거나 -z방향일 때만 히든 방이 존재할 가능성이 있으며, +x 방향이거나 +z 방향일 때는 히든 방은 절대 존재하지 않습니다.)
4. 시작 방을 포함하여 10칸을 넘어가는 방들은 탐색할 필요가 없습니다. 포탈 방은 시작 방을 포함하여 10칸 이내에 대부분 스폰되기 때문입니다.

 

엔더 눈과 시작 계단Starter Stair

엔더 눈을 던지면 지하유적으로 날아갑니다.

이때 (스피드런을 시작하기 전 저를 포함하여) 많은 유저분들이 엔더 눈이 포탈 방을 향해서 날아가는 건 줄 아시는 분들이 있습니다.

하지만 엔더 눈은 포탈 방이 아니라 '시작 계단'이라고 불리는 곳을 향해 날아갑니다.

이렇게 소용돌이처럼 빙글빙글 돌며 내려가는 계단입니다. 이런 소용돌이 계단은 유적에 딱 1개만 있는 건 아닙니다. 여러 개가 있을 수 있는데 다만 시작 계단은 무조건 소용돌이 계단입니다.

엔더 눈을 던지면 이 시작 계단이 있는 곳으로 날아가는 겁니다.

이 시작 계단으로부터 먼 곳에서 엔더 눈을 던지면 보통 엔더 눈은 하늘 위쪽으로 날아갑니다.

시작 계단과 반지름 12칸 정도 이내로 가까운 곳에서 던지면 엔더 눈이 땅속으로 들어갑니다.

(반지름에서 y 높이는 빼고 x, z만 12칸 이내입니다. y는 0이든 1억이든 상관 없습니다.)

F3 + G를 누르면 청크 경계선이 노란색으로 나타납니다.

시작 계단이 있는 청크 안으로 들어가셔서 F3을 눌러서 좌표계를 띄웁니다

Chunk라고 적힌 부분에서 3 x 3이 되는 곳을 찾습니다. x는 높이니까 상관 없습니다.

이 좌표는 청크 좌표로서, 맵의 (0,0,0)을 기준으로 측정되는 일반적인 좌표와 달리 현재 내가 있는 청크를 기준으로 측정됩니다. 한 청크가 16x16이니까 이 청크 좌표는 무조건 (0, x, 0)~(15, x, 15)입니다.

 

엔더 눈이 땅으로 파고 들어간 청크에서 청크 좌표 (3, x, 3)을 찾았으면 거기를 파고 내려갑니다. 그럼 무조건 시작 계단이 나옵니다.

 

시작 방

시작 계단에서 나오는 순간 처음 보이는 방이 시작 방입니다. 시작 계단 -> 시작 방은 모든 유적이 예외 없습니다.

시작 방은 대표적으로 이렇게 생겼습니다

왼쪽 위, 왼쪽 아래, 오른쪽 위, 오른쪽 아래, 정면 지하로 가는 길이 총 5개까지 생길 수 있습니다.

사진에서 보시다시피 그 길이라는 건 나무 문으로 되어있을 수도 있고, 철문으로 되어있을 수도 있고,  사진의 오른쪽 아래처럼 그냥 뚫려있을 수도 있고, 아예 길이 없이 막혀있을 수도 있습니다.

 

이 시작 방에서부터 점점 맵이 생성되는 원리라고 생각하시면 됩니다.

컴퓨터 전공이신 분들은 DFS, BFS 생각하시면 됩니다.

얼마 전 프로그래밍 문제 풀이할 때 올린 DFS 그래프를 마인크래프트 포스팅에서 쓸 줄이야...

 

히든 방Hidden Room

문제는, 시작 방에는 눈에 보이는 방이 다가 아니라는 점입니다.

지금 보시면 이 지하유적의 시작방은 통로가 오직 1개인 것처럼 보입니다.

왼쪽위, 왼쪽 아래, 오른쪽 아래는 깔끔하게 막혀있고

오른쪽 위는 1칸 들어가있어서 사진상으로 길이 있는 것처럼 보일 수도 있긴한데

보시다시피 깔끔하게 막혀있습니다.

즉 이 시작방은 길 5개 중에 4개가 막혀있으니 지하로 가는 길 1개만 가면 포탈 방에 도달할 수 있겠네? 개꿀 ㅎㅎ이라고 생각할 수도 있습니다.

근데 그러다가 2시간을 헤매는 겁니다.

 

왜냐하면 지하길로 가는 순간 그 안에서 모든 방을 다 찾아보더라도 포탈 방은 존재하지 않기 때문입니다.

마린이분들이 지하 유적에서 몇 시간동안 포탈 방을 찾아 헤매는 경우가 이런 경우입니다.

특히 이 상황에 엔더 눈을 던져서 포탈 방을 찾으려고 하면, 아까도 말씀드렸듯이 엔더 눈은 포탈 방이 아니라 시작 계단을 향하기 때문에 결국에 왔던 길을 돌아가 가게 됩니다.

 

그럼 대체 포탈 방은 어디있을까요?

뜬금없이 시작 방의 오른쪽 아래 벽을 부쉈더니 길이 보이고, 그 길이 포탈 방으로 이어지고 있었습니다!

아까 그 사진을 이번 요새로 표현하자면 이런 느낌인 겁니다.

시작 방에서 지하 계단으로 내려가는 순간이 바로 위 그림에서 9번 노드로 가는 것과 같으며, 9번 노드 아래에 있는 그 어떤 방을 다 찾아봐도 포탈 방은 절대 안 나오는 거죠.

 

그럼 히든 방은 어떻게 찾을까요?

 

네 그림이 다 설명해서 더 설명할 필요가 없네요.

반대쪽도 마찬가지입니다.

​만약 이렇게 왼쪽 아래 벽이 움푹 파져있었으면 왼쪽 윗부분을 팠을 때 히든 방이 나올 확률이 있습니다.

이것 역시 '확률'이기 때문에 움푹 파져있다고 해서 옆 벽이 무조건 히든 방이 존재하는 건 아닙니다.

또한 히든 방이 무조건 포탈 방과 이어진 것도 아닙니다. 하지만 히든 방이 포탈 방과 이어져있을 가능성이 있을 수 있으니, 시작 방에서 움푹 파진 벽을 보면 그 옆을 반드시 파봐야합니다.

 

참고로 시작 방과 똑같이 생긴 방을 유적을 탐사하다보면 2개 이상 볼 수도 있습니다. 그 방에도 마찬가지로 히든 방 규칙이 적용됩니다.

 

참고로 시작 방에서 히든 방이 있는 경우는 시작 계단에서 시작 방으로 들어왔을 때 바라본 정면의 방향이 북쪽이거나 서쪽일 때 뿐입니다. (즉, x좌표가 마이너스 방향이거나 z좌표가 마이너스 방향이라는 거죠.)

시작 방으로 들어왔을 때 바라보는 방향이 x좌표가 플러스거나 z좌표가 플러스인 경우엔 벽이 움푹 파여있든 말든 시작방이 무조건 없기 때문에 굳이 벽을 파볼 필요가 없습니다.

하지만 이걸 외우긴 귀찮으니까 스피드런 랭킹을 세우시려는 분이 아니라면 그냥 시작방에서 벽이 움푹 파인 경우 옆을 한 번 파보면 된다라고만 외우시면 됩니다. 어차피 벽 1칸 파보는 거 뭐 몇 초 안 걸리니까요.

 

방Room이란?

유적의 모든 방을 다 탐색하는 것은 굉장히 무리가 있습니다. 방을 타고 들어가면 들어갈수록 경우의 수가 기하급수적으로 늘어나기 때문입니다.

시작 방으로부터 1~2개의 방만 생긴다고 가정해도 15번만 반복해도 1.5^15는 437개의 방이 됩니다.

물론 뭐 무조건 방이 방을 만드는 건 아니고 중간에 끊기는 길도 있으니 그걸 감안하더라도 적어도 수십 개, 많으면 수백 개의 방이 있는데 그걸 탐험하는 건 너무 시간이 많이 걸립니다.

 

다행이 제작사는 시작방과 가까울수록 포탈 방이 생길 확률이 높고, 멀수록 포탈 방이 생길 확률이 낮게 설계해두었습니다.

무슨 말이냐면 이런 구조에서 아래쪽으로 내려갈수록 포탈 방이 나올 확률이 적어진다는 것입니다.

시작 방으로부터 6칸 떨어졌을 때 확률이 가장 높고

11칸 이상 떨어졌을 때부턴 확률이 엄청 낮기 때문에 시작 방으로부터 10개의 방을 지나왔는데 포탈 방을 못 봤다? 그럼 더 이상은 안으로 들어가도 포탈 방이 사실상 없다고 생각하고, 왔던 길을 되돌아가는 게 빠릅니다.

컴퓨터공학 공부하신 분들은 방문한 노드의 수가 10이 될 때까지만 백트래킹 알고리즘을 수행한다라고 생각하시면 됩니다.

 

그런데 이 '방'이라는 게 여러분들이 상상하는 것보다 굉장히 작을 수도 있고, 애초에 '방'이 아니라 복도인데도 '방'으로 취급합니다.

 

자 시작 방? 당연히 '방'이죠. 딱봐도 방처럼 생겼으니까요.

상자 방? 방치곤 좁긴한데 그래도 방으로 볼 수 있을 거 같네요.

긴 계단? 이것도 방입니다.

복도, 계단 이런 거 전부 다 방입니다.

시작방 - 복도 - 계단 - 창고방 이렇게 되어있으면 보통은 그냥 시작방과 창고방 2개만 생각하겠지만, 맵을 생성하는 알고리즘 입장에선

'자 일단 시작방 만들었고... 시작방에서 지하 길로 가면 뭐가 나오게 만들지? 에라 모르겠다 돌려돌려 돌림판~! 복도가 나왔네? 그럼 복도 만들고, 복도 만들었으니 다음은 뭐 만들지? 또 돌림판 돌려야지' 이렇게 해서 만들기 때문에 계단 복도 전부 다 방입니다.

감옥 방? 이것도 방입니다. 근데 착각하면 안 되는게 복도까지가 세트예요.

이렇게 방 2개라고 생각할 수 있는데

그냥 이렇게가 방 1개 입니다.

왜냐하면 철장만 있는 감옥방은 없기 때문이죠. 무조건 감옥방이 만들어진다면 복도와 철창방이 한 세트이기 때문입니다.

탐색 도중에 만난 시작 방이랑 똑같이 생긴 방? 역시 당연히 방이겠죠?

지금 눈에 보이는 여기도 방입니다.

네 딱 이만큼이요. 철창 너머 돌계단 쪽은 다른 방인 거고, 문 너머도 당연히 다른 방입니다.

방이 이렇게 좁기도 해요.

사실 여긴 방이라기보단 코너에 가깝긴한데 어쨌든 생성 알고리즘 입장에서 봤을 땐 얘도 하나의 노드니까요.

네 좁고 어둡지만 당연히 방이겠죠.

막혀있네요? 길이 없는 방입니다.

창고방 1개네요? 그럼 지금 이 사진엔 방이 1개인가요? 아니요 3개입니다.

창고방(파란색) 1개, 3갈래 방(빨간색) 1개, 코너방(주황색 1개) 이렇게 입니다.

이거 그냥 창고방 1개 같은데 어떻게 구분하냐고 물으신다면 찐 창고방이랑 비교해보죠.

딱봐도 작죠. 이게 원래 창고방의 크기라는 걸 아는 경우엔 자연스럽게 아까 그 사진에서 '창고 방이 이렇게 클 리가 없는데? 복도랑 연결된 형태구나'라고 알게 되는 거죠.

그니까 결국엔 요새들을 다니다보면 자주 보이는 형태들의 최소 단위가 있어요. 그 최소 단위들을 얼마나 알고 있느냐에 따라 방을 정확히 셀 수 있냐 아니냐가 나뉩니다.

 

다만 그렇다고 방을 진짜 정확하게 세실 필요는 없어요.

아까 창고방+세갈래+코너방 3개짜리를 1개로 착각했다고 해서 뭐 큰 일이 나는 건 아니잖아요? 그냥 3개를 1개로 착각한만큼 탐색할 때 2단계 더 깊이 들어가는 노가다를 할 뿐입니다. 쓸데 없이 방을 더 들어가게 될 뿐이고 시간을 좀 더 쓰게될 뿐이죠.

 

연습법

처음에 내가 방을 몇 개 지나왔는지 세는 게 진짜 헷갈립니다.

예를 들어 제가 이 그림에서 1, 2, 3, 4번 노드를 순서대로 방문했다고 할게요.

그럼 지금까지 방문한 방의 수가 4죠?

근데 4번 노드에서 길이 막혀서 더이상 갈 곳이 없으면 3번으로 되돌아가겠죠.

그럼 다시 지금까지 방문한 방의 수가 3이죠? (3번 노드를 2번 방문했다고 5가 되는 게 아닙니다. 4번 노드로 들어갔던 기억을 지우고 되감기한다라고 생각하셔야 합니다.)

이번엔 6번방을 들어가면 방문 수가 4죠? 근데 길이 없으니 3번으로 돌아가고, 3번에서 더 이상 안 가본 길이 없으니 2번으로 돌아가고, 2번에서 7번을 방문하고... 이런 식으로 합니다.

 

그러는 중에 방문한 방의 개수가 10을 넘어가면 앞에 길이 있더라도 더 이상 들어가지 않고, 그냥 앞은 막힌 셈쳐버리고 다시 되돌아가서 아까 들어온 방의 다른 방을 들어가는 거죠.

 

방의 개수를 10개로 하면 움짤 길이가 너무 길어지니까 최대 방의 개수를 4로만 생각하고 탐색한다고 했을 때 어떤 식으로 탐색하는지 보여드릴게요.

방 1개를 지날 때마다 색깔 양털을 1개씩 설치할 겁니다.

핵심은 4번째 방을 방문했다는 증거인 하늘색 양털을 설치하는 순간 그 방앞에 있는 길은 거들떠도 안 보고 그냥 막혔다 생각하고 되돌아가는 겁니다.

물론 실제론 이걸 10번째 방까지 카운팅해야죠. 그래서 생각보다 훨씬 어렵습니다.

10번째 방까지 들어갔다가 9,8,7번 지나서 6번 방에서 다시 시작해서 7,8,9를 셌다가... 이러다보니 헷갈리기 정말 쉽습니다.

진짜 연습이 필수입니다. 별 거 아닌 거 같은데 진짜 헷갈려요.

저처럼 월드 하나 파서 인벤토리에 색깔별로 양털 1개씩 준비하셔서 방 하나 지날때마다 양털 설치하는 방식으로 연습해보셔야합니다.

 

그리고 갈림길이 나왔을 때는 왼쪽방으로 순서대로 들어갈지, 오른쪽 방부터 순서대로 들어갈지 정해놓는 게 좋습니다. 저는 무조건 왼쪽방부터 들어가는 걸로 정하고 있습니다. 오른쪽부터 하셔도 상관 없어요. 개인취향입니다.

다만 중간에 바꾸는 건 안 됩니다. 한 번 왼쪽부터로 했으면 계속 왼쪽으로만 해야하고 오른쪽은 계속 오른쪽으로만 가야합니다. 그래야 빠뜨리는 방 없이 꼼꼼히 찾아갈 수 있습니다.

 

미로 안에서 길을 잃었을 때

탐색하다보면 내가 어디까지 했는지, 어디서 왔는지 정말 헷갈립니다. 마음 같아선 누르는 순간 시작 계단으로 돌아가는 리셋 버튼이라도 있었으면 좋겠다 싶죠.

 

그런 버튼은 없지만 다행히 시작 계단으로 돌아가는 방법이 있습니다.

아까 언급한 것처럼 엔더눈은 무조건 시작 계단으로 간다는 방법을 이용하셔도 되는데 지하에서 엔더 눈 던졌다간 엔더 눈 하나 버리는 거랑 마찬가지니까 그 방법은 쓰지말고 문을 보면서 가면 됩니다.

 

마인크래프트 지하 유적 생성 알고리즘은 시작 계단 위치를 정한 다음에 하나씩 방을 만들어 가는 방식이라고 했잖아요?

그래서 문의 방향이 무조건 정해져있습니다.

 

여러분이 이렇게 된 문을 발견했다면, 여러분은 현재 시작 계단쪽에서 더 깊은 방으로 가고 있다는 뜻입니다.

이렇게 반대로 설치된(움푹 파인) 문을 발견했다면, 여러분들은 깊은 방에서 시작 계단 쪽으로 가고 있다는 뜻입니다.

그래서 이렇게 설치된 문만 찾아서 가다보면 시작 계단을 발견할 수 있습니다.

 

마치며

마인크래프트 알고리즘은 참 심오하더라구요...

어쨌든 알아두면 특히 도움이 될 거 같습니다.