[완성] Procedural Dungeon Generation

#1 - https://atli-yeondi.tistory.com/29 

#2 - https://atli-yeondi.tistory.com/30

#3 - https://atli-yeondi.tistory.com/31

#4 - https://atli-yeondi.tistory.com/35

 

현재 로그라이트 형식의 게임을 만들고 있는데 랜덤 맵 생성 알고리즘에 대해 알아보다가 알게된 절차 생성 알고리즘.

 

이전에 개인적으로 생각했던 방식은

1. 여러가지 룸의 템플릿을 만들어서 재구성하는 방식

2. nXn 방식의 테두리만 정해놓고 알고리즘으로 맵을 재구성 하는 방식 ( ex: 스펠렁키 )

등의 방식을 고려했고

 

1번의 방식으로 구현을 했으나.. 뭔가 밋밋하고 알고리즘이라 하기엔.. 뭔가 디자인적으로 손댄 부분이 너무 많아서 조금 더 찾아보다가 알게되었다.

 

레딧의 TinyKeepDev라는 사람이 쓴 글을 토대로 짠 코드인데

처음엔 잘 이해가 안되다가 하나하나 복잡하게 생각 안하고 풀어나가니 풀려서  아직 완성은 못했지만  중도에 기록해본다.

 

대충 방식은 이러하다.

1. 반지름 값을 토대로 원을 하나 만든다.

2. 원 안에 각 다른 크기의 사각형을 여러개 만든다.

3. 서로 겹치지 않게 나눈다.

4. 메인 룸, 복도 등등 필요에 따라 나눈다.

 

대략 이정도 단계인데 현재 4단계를 하고있다.

 

글 상단에 getRandomPointInCircle 함수를 만들어서 원을 그려주고 따로 함수를 만들어 사각형을 그려준뒤 나눠주면 되는데

사실 다른것보다 사각형을 만드는게 가장 까다로웠는데 이유는

1. 사각형을 만드는게 나으려나? 바로 타일로 규칙에 따라 깔아주면 더 편하려나?

2. 사각형을 만든다는 가정을 하고 나중에 타일을 깔았을때 똑같이 작동하려나? 였는데

일단은 생각을 안하고 하기로 했다. 어떻게든 되겠지

 

사실 저 글 맨 밑에 내려보면 최하단 맨션 어딘가에 누군가 유니티로 재작업한 글이 있긴하다.

난 그중에서 일단 room.cs만 따로 빼왔다.

 

 

본문으로 돌아가서

1. 반지름 값을 토대로 원을 하나 만든다.

t,u,r값을 float로 준 후 글에 있는 랜덤값은 퍼센트라는 생각에 0.0 ~1.0으로 주었고

local r = nil 이게뭐지? 하는 마당에  바로 밑에 있는 링크

https://stackoverflow.com/questions/5837572/generate-a-random-point-within-a-circle-uniformly

이곳을 따라가서 r = if u>1 then 2-u else u 이걸 보았다.  바로 밑에 있다는걸 몰랐다..

Generate a random point within a circle (uniformly)

 

아무튼 return값으로 Vector2 or Vector3값을 주면 될것 같아서 그렇게 주었다.

 

2. 원안에 사각형을 여러개 만든다.

일단 room.cs파일을 가져왔기 때문에 조금뜯어봤는데 코드가 심플해서 읽는데 오래 걸리진 않았다.

그냥 Vector2든 3이든 알맞은 변수 선언을 해준 후 원 값에 반지름 값을 입력해서 원을 그려주는 코드를 넣어주고

사각형의 크기는 제각각이여야 하기 때문에 가로의 최소값,최대값 / 높이의 최소값,최대값을 입력받아서 그 중 랜덤으로 값을 찾아서 fWidthSize , fHeightSize에 각각 넣어주었고 room의 포지션값에 따라서 사각형을 그려주었다.

 

일단 혹시몰라서 seperate할때를 대비해 room 프리팹에 박스 콜라이더를 넣어주고 트리거를 체크해줬다.

 

인스턴스화도 했고 Add를 해서 추가를 하고 미리 입력받은 room개수에 따라 for문을 반복해주었다.

 

전부 끝난 후 3번인 나누기로 가서

 

3. 서로 겹치지 않게 나눈다.

이 부분이 참 난해했던게 글 중

I found that it's much easier to just use a physics engine. 라는 문구가 있어서

미리 추가했던 콜라이더 + 리지드바디로 z값만 잠궈봤으나 뭔가 이미지처럼 확 퍼지는 느낌이 없이 가로 또는 세로로만 퍼져서 고민 하다가

따로 값 중복 체크 함수를 만들어서 거친 후 참이면 위치 값을 판단해 서로 떨어트리는 작업을 반복하도록 했다.

 

만들면서 생각났지만 아직 안만들었던 아이디어중 단순히 맵 가운데에 있는 메인 홀 하나를 잡고 중심으로 오른쪽에 있는 사각형들은 오른쪽으로 점점 밀어내고 왼쪽에 있는 사각형들은 왼쪽으로 밀어내는 방식도 괜찮긴 할것 같다.

이건 나중에 만든 후 후술

 

4. 필요에 따라 방을 나눈다.

이건 room에 있던 설정이라 일단 메인룸,복도,비활성화 정도로 나눌건데

현재는 메인룸만 가로,세로가 일정 크기를 넘을경우 메인룸으로 설정하게 두었다.

 

빨간 사각형이 메인룸, 파란색은 아직 정해지지 않은 룸들이다.

보면 중간중간 떨어진곳이 많은데

저 사이를 적절하게 이어야하는게 우선이다.

 

2020년 7월 16일 추가

어제 조금 작업했는데

첫번째 결과물은

약 2초뒤에 실행된다. 잘못 촬영함

뭔가 엄청 화려해서 있어보인다(?)

하지만 문제점이 너무 잘 보이는게 일단 각 메인룸을 연결해주는데에 성공은 했는데

너무 많아서 문제다.

사실 이용을 해보자면 어차피 방들 사이의 실에 위치하는 메인룸이 아닌 일반 방들을 복도라던가 다른 방으로 쓸 예정이라

저런식으로 연결을 한 후 저 사이의 방들을 전부 살려둬도 괜찮겠지만

스케일이 커지면 관리하기 어렵고 쓸때없이 공간을 차지하는건 덤이니.. 

 

일단 수정을 하기로 마음을 먹었고

확실히 방들끼리 이어지는 선이 줄은 상태인데 잘보면 중앙 상단 방에 바로 오른쪽 조그마한 메인룸엔 실이 하나도 없고

오른쪽 상단 방 두개는 서로만 이어져 있다.

여기서 추측할 수 있는것은 "서로 방이 붙어있다"라는것 때문에 따로 계산을 안한것 같다.

 

그래서 기존 거리공식은 두고 실을 잇는 조건공식만 새로 엎어버리고 짰다.

 

역시나 문제점이 보이는데

첫번째로 붙어있는방은 빠로 잇는 연산을 안한다는것.

그리고 알 수 없는이유로 연산에 빠져 있는 방이 있다는것.

 

현재는 메인룸의 첫번째 배열로 접근한 변수를 i

메인룸의 i번째 +1로 접근한 변수를 j로 두고

첫번째만 i와j의 거리계산을 한 후 최단거리 변수를 만들어 넣어주었고

이후 들어오는 값에 따라 currentDistance라고 선언해 최단거리 변수와 currentDistance를 비교해서

currentDistance가 더 짧을경우  값을 교체해주는 방식으로 했는데

 

위 그림을 계속 보다보니 예상되는 오류는

첫번째 i,j의 거리계산에서 "첫번째"라는 if문때문에 연산에서 빠져버린 방이 있을수도 있다는 점이고

문제는 붙어있는 방이 왜 계산에서 빠져버렸냐인데..  디버그하기 너무 귀찮다.

 

더 좋은 방법이 있을지도 모르지만

기존에 쓰던 방식을 버렸다.

기존의 방식은 A,B를 잡고 i==0 -> true , 즉 루프문의 첫번째일 경우 A,B사이의 거리 값을 구해서 

최단거리 값에 넣어준 후  i가 1일때부터 최단거리 값과 현재 거리값을 구해서 (아마도 A,C의 거리값)

비교해준 후 최단거리 값일 경우 A에서 ?를 이어주는 작업을 했었는데

무언가 하나씩 연결이 안되는 경우가 생겨서

 

A,B -> 두개를 잡는것이 아닌 A,B,C를 잡아서 비교해주는 방식을 선택했다.

(이는 기존 코드에도 있는 방식)

비교 코드는 그대로 유지한 후 방식만 조금 바꾸는데

 

i번지 == 0으로 시작

j번지 == 1로 시작

k번지 == 2로 시작

 

각각 roomA[i] , roomB[j], roomC[k]

로 시작을 하면 된다.

 

위와 같이 사각형을 랜덤하게 그려준뒤 임의로 번지수가 들어갔을때를 가정해서 그려보았다.

0과 1사이 즉, i,j사이는 Dist1의 변수에 저장하고

0과 2사이 i,k사이는 Dist2에 저장하고

1과 2사이 j,k사이는 Dist3에 저장한다.

 

여기서 처음에 생각없이 하는 바람에 최단거리를 거르려고 여러번 if문을 썼지만

지금은 조금 수정해서

최단거리가 아닌 경우를 걸러버리면 되는데

Dist1을 잡든 2를잡든 상관은 없지만 k가 자주 바뀌기때문에

i,j를 잡은 Dist1을 기준으로 걸러버리면 된다.

 

if(Dist1 > Dist2 && Dist1 > Dist3)

이런식으로 걸러버리면 되는데

만일 위 구문이 참이라면 최단거리여야 하는 Dist1은 최단거리가 아니므로

continue로 걸러버리거나 따로 bool형 변수를 선언해서 후에 계산이 일어나지 않도록 설정해주는게 좋다.

 

그리고 만약 위 if문이 거짓이라면 Dist1이 최단거리라는 말이므로

이어주는 작업을 해주는 함수를 연결해주면 된다.

 

여기서 사용하는 Room함수안에 좌표관련 변수들이 많으니 체크하는건 필수다.

 

참고로 거리구할때 pos.center를 이용했다.

 

 

이제 완벽하게 서로를 이어주었다.

이젠 그 사이를 복도로 만들어서 이어주어야 하는데

이 역시 center를 기준으로 해주면 된다.

 

사실 이 경우는 거의 대부분을 코드를 가져와서 썼고

현재 내 방식으로 수정하는 중이다.

코드는 최상단 github페이지의 comment를 보면 나와있다.

 

기존의 코드는 막론하고

수정중인 방안은 이어주어야 할 방 두개를 잡는다.

(기존 코드를 보거나 내 방식을 따라왔다면 따로 리스트에 순서대로 저장되어있다.)

두개씩 페어로 잡은 후  4사분면으로 나누어 A를 기준으로 B의 방이 어디있는지를 계산을 하고

또 b.x - a.x  b.y - a.y 를 각각 계산해서

A를 기준으로 B가 1사분면에 있을경우 x값이 더 크면 hall.pos.x = b.pos.center로 설정해주고

hall2.pos.y = b.pos.center로  가로 세로 따로 홀을 만들어 이어줄 생각이다.

 

2사분면의 경우 x,y를 비교해 더 값이 작은쪽으로 향할 생각이다.

 

 

 

이제 쓸모없는 방을 삭제하거나 재편성 해보자.

최상단 글에도 나와있는 내용이지만 우리가 만들어준 hall은 사실 억지로 만들어준것이고,

되도록 이미 만들어놓은 room clone을 활용하는게 더 좋다. 게다가 그 방을 어떠한 목적으로 바꾸든 (예로들어 쉼터,상점등등) 기존에 단순히 직각의 기다란 복도를 만드는것보다 유저가 느끼는 재미의 폭도 다를것이다.

 

그래서 쓰이지않는 모든 방을 삭제하는선택보다 hall과 겹쳐버리는 방을 살리는 방안을 모색해보자.

일단 "겹쳐"라는 단어에 집중을 해보자.

 

일단 이전에 겹치는 것에대해 우린 방안을 모색했었다.

overlapCheck정도로 함수를 만들어서

두개의 네모를 비교해주면 된다.

 

첫번째 사각형의 좌 하단값과 두번째 사각형의 우하단 값을 비교해주면 되고

역시 첫번째 좌하단과 두번째 좌상단을 비교해주는 식으로 값을 비교하면 되는데

 

이는 https://stackoverflow.com/questions/306316/determine-if-two-rectangles-overlap-each-other

Determine if two rectangles overlap each other?

여길 참고했다.

 

여기서 굳이 size라는 변수를 어떤방식으로든 만들 필요가 전혀 없는게

우린 이미 pos.width와 pos.height값을 가지고 있고

pos1.x < pos2.x + size2.x 라는 값은 pos1.pos.x < pos2.pos.x + pos2.pos.width로 해주면 된다.

 

보면 size자체는 사각형의 우상단 - 좌하단 값인데 그건 그냥 (width,height)값이다.

 

즉 우린 이미 구해져있다.

 

저 식에 참이면 겹친다는 뜻이므로

우린 해당 hall의 isHall값을 true로 변경해주면 된다.

 

코드 방식은 대략 이러하다.

 

우선 룸의 종류는 3종류다.

mainRoom , Hall , Disabled

 

우린 아직 판정이 나지 않은 즉, Hall인지 Disabled인지는 모르지만 mainRoom이 아닌 방을 골라야 하기 때문에

일단

foreach(Room room in rooms) 혹은 for(int i=0;i<rooms.count;i++) {Room room = rooms[i];}

둘 중 하나의 방식으로 걸러주면된다. (어떤 방식이든 상관없다. 어쨋든 모든 방을 불러오면 된다.)

그리고 mainRoom을 걸러준다.

if(room.mainRoom == true) continue;

이러면 room타입이 mainRoom일경우 넘어간다.

 

그리고 우린 아까 만든 복도를 찾아야한다.

아까 홀을 잇는 코드에 halls라는 배열을 만들고 전부 대입해주는 코드를 중간에 슬쩍 넣어준 후

위 방식대로 halls를 전부 불러와주면 된다.

이번엔 halls만 따로 모아놓은 배열이기때문에 따로 걸러줄 필요가 없다.

(단, 반복문은 써야한다. 차례대로 비교해줄 예정이기때문)

 

이제 겹치는지 판단해야한다.

미리 만들어둔 overlapCheck라는 함수를 껴넣고 overlapCheck(room,halls);

를 써서 참,거짓을 판별해서 참일경우 room.isHall = true로 해주면 된다.

 

여기서 나는 바로 else를 써서 room.disabled = true로 해주었는데

그렇게 해서

이렇게 나왔다.

언뜻보면 어? 잘 된거 아냐? 싶지만 자세히 보면 임의로 만들어준 복도들만 있고 따로 분류되지 않은 후 복도로 변경해준 방들은 없다. 즉 초록색 방이 없다.

물론 이럴 가능성은 충분히 있지만 아무래도 이상하다.

 

그래서 모든 방의 disabled만 풀었는데

4개의 초록색 방이 보인다.

그리고 그 값들을보면 disabled와 hall에 모두 체크되어있다.

이런 경우가 나와버리니

 

halls의 반복문이 끝난 뒤

홀도 아니고 메인룸도 아닌 즉, 이도저도 아닌 방만 disabled로 만들어주면 깔끔해진다.

 

결과물

 

참고로 좀 더 쉽게 해보려고

모든 방들에 기본적으로 boxCollider2D와 RigidBody2D를 넣고 방을 생성할때 나온 x,y,width,height값으로 offset과 size를 계산해서 넣어준 후 trigger를 설정해주었는데

 

알수없는 이유로 전혀 붙어있지 않음에도 hall이 체크되거나 완전히 관통했는데 hall이 체크되지 않는등 알 수 없는 오류들이 많아서 결국 이와같이 바꿧다.

 

 

대충 루트 정리

1. 반지름값으로 원을 그린다.

2. 최소,최대값을 설정한 후 그려진 원안에 랜덤으로 사각형을 막 찍어낸다 rect이용

3. 겹침의 판정을 하는 함수를 만들고 x,y값의 오버랩을 구한 후 절대값으로 크고 작음을 구해서 서로 반대쪽으로 찢어준다. 이때 올림을 해야 안정적으로 찢긴다.

4. 가까이에 있는 사각형을 구한다.

5. 기즈모로 이어준 선을 토대로 사각형의 중심에서 선을 만들어 이어준다.

6. 그렇게 만들어진 복도와 겹치는 방은 전부 복도로 설정해주고 메인룸과 복도가 아닌 모든 방들은 비활성화 해준다.