📝 배운 것들
🏷️ 절차적 생성
https://www.youtube.com/watch?v=l6i0oBXYmXI
MapMagic2 라는 애셋 쓰고 거기에 조금 더 커스터마이징한듯. devlog라 절차적 생성 내용은 적다.
https://www.youtube.com/watch?v=TPvxWIKHE6Q
방 여러개를 소환한다. 겹치면 무게중심 기준으로 서로 밀어낸다.
방들이 서로 겹치지 않을때까지 반복한다. 계속 해도 안되면 다른 배치로 다시 시도.'
그리고 나서 길찾기 알고리즘으로 문들을 연결하면 됨.
필수 문과 서브 문이 있고 필수 문은 반드시 연결해야 됨.
그 후엔 모든 방이 닿을 수 있는지 확인해야 하는데,
유니온 파인드 알고리즘을 사용한다.
그래프끼리 합치면 가장 낮은 값을 가진 노드가 공통 부모가 되는 알고리즘.
3D도 비슷하게 유니온 파인드로 해결.
같은 층에 있는 방들 연결할 땐 2D 때랑 똑같이 해결.
https://www.youtube.com/watch?v=dFYMOzoSDNE
원래는 노이즈로 맵 생성했는데, 지역 사이 경계가 부자연스러워 보이는 단점이 있었다.
그래서 wave function collapse (파동 함수 붕괴) 알고리즘을 사용했다.
맵 조각 주면 비슷한 거 생성하는 알고리즘이라고 함.
숲, 산, 해변, 물 이라는 타일이 있을 때
해변은 물 옆에, 숲은 해변 옆에, 산은 숲 옆에만
이런 식의 규칙을 정해놓고
랜덤하게 하나 정한 뒤에 규칙에 따라 다음 타일도 랜덤하게 결정한다.
스도쿠랑 비슷.
규칙을 직접 지정해주는게 아니라 input만 주고 규칙을 알아서 생성해줄 수도 있음.
근데 그냥 쓰면 뭔가 이상한 결과물이 나올 수 있다.
그래서 자신은 타일을 섹터로 만든 뒤에 경계면은 stitch 섹터를 삽입해줌.
근데 문제가 있음. 너무 느림.
Boris the Brave's Things라는 디스코드 채널에 가서 Boris한테 물어봄.
유니티의 Burst Compiler를 써보라고 조언받음.
Burst Compiler는 뭐냐?
C#은 생산성은 좋지만 속도가 느림.
Unity는 C#애서 속도 느린 기능들을 빼고 컴파일해줄 수 있음.
그리고 Job System을 사용해서 작업을 한 번에 하나씩 수행하는 대신 병렬로 수행하게 해줌.
단점 : 편리한 기능 없이 코드들을 작성해야 함.
그 뒤엔 애셋들 만든 뒤에 perlin 노이즈 써서 맵 만들고 (만들었던 알고리즘 적용한듯? 해당 언급 x)
https://www.youtube.com/watch?v=rBY2Dzej03A
여기에서 설명 보고 만듦.
이 문서는 게임 TinyKeep의 개발자가 설명하는 랜덤 절차적 던전 생성 방식에 관한 기술적인 내용을 다루고 있습니다. 그는 던전 레이아웃을 생성하기 위해 여러 단계를 거치며, 이를 통해 독창적이고 흥미로운 던전 구조를 만들어냅니다. 각 단계를 요약하며 해석해 보겠습니다.
1. 셀 수 설정
먼저, 생성할 셀의 수를 설정합니다. 예를 들어 150개 정도로 설정할 수 있으며, 셀의 수가 많을수록 던전의 크기와 복잡성이 커집니다.
2. 랜덤한 크기의 직사각형 생성
각 셀은 랜덤한 너비와 길이를 가진 직사각형으로 생성됩니다. 이때, 직사각형의 크기를 정할 때 Math.random 대신 Park-Miller 정규분포를 사용하여 주로 작은 셀들이 많이 나오도록 만듭니다. 또한, 셀의 너비와 길이의 비율이 너무 크지 않도록 조정하여 길쭉하거나 정사각형에 가까운 형태가 나오지 않게 합니다.
3. 셀 간의 충돌 해결
초기에는 150개의 셀이 겹쳐 있을 가능성이 큽니다. 이를 해결하기 위해 분리 스티어링 기법을 사용하여 각 직사각형이 서로 겹치지 않도록 배치합니다. 이 기법을 통해 셀들이 겹치지 않으면서도 서로 밀집된 상태를 유지할 수 있습니다.
4. 빈 공간 채우기
모든 셀들이 겹치지 않도록 배치한 후, 남은 빈 공간은 1x1 크기의 작은 셀로 채워서 전체를 정사각형 그리드 형태로 만듭니다.
5. 방(rooms) 선정
이제 그리드의 셀 중에서 크기가 일정 이상인 셀을 방으로 지정합니다. Park-Miller 분포를 사용했기 때문에 방으로 지정되는 셀은 많지 않고, 대부분 작은 셀들이 남게 되어 방 사이에 여유 공간이 생깁니다.
6. 방을 연결하기 위한 그래프 생성
각 방의 중심점을 연결하는 델로네 삼각분할(Delaunay Triangulation) 알고리즘을 사용해 그래프를 만듭니다. 이 그래프는 각 방을 다른 방과 연결하지만, 방 간의 선이 교차하지 않도록 만들어 줍니다.
7. 최소 신장 트리(MST) 구성
모든 방을 서로 연결하는 복잡한 그래프는 혼란스러운 레이아웃을 만들기 때문에, 각 방을 최소한으로 연결하는 최소 신장 트리(Minimal Spanning Tree)를 구성합니다. 이를 통해 모든 방이 연결되면서도 간결한 구조를 가질 수 있습니다.
8. 루프 추가
최소 신장 트리만으로는 던전이 너무 단순해지기 때문에, 원래의 델로네 그래프의 일부 연결선을 다시 추가하여 루프를 생성합니다. 예를 들어, 남은 연결선 중 약 15%를 다시 추가하여 던전에 다양성을 부여합니다.
9. 그래프를 통로로 변환
각 연결선을 따라 L자 모양의 직선 통로를 생성합니다. 이때, 방이 아닌 셀들은 통로 타일로 변환되어 던전의 복잡한 벽과 구조를 만듭니다. 다양한 크기의 셀을 사용하여 통로가 구불구불하고 불규칙하게 만들어지므로, 던전의 느낌이 더욱 살아납니다.
랜덤 크기랑 위치 가진 박스들 배치
각 방을 정점으로 하는 델라니 삼각분할 그래프를 만든다
(보이어 왓슨 알고리즘 사용)
만든 그래프로 최소 신장 트리 만든다 (Prim's 알고리즘 사용)
델라니 삼각분할로 만들었던 그래프에서 12.5%만 남긴다.
모든 방에 대해 길찾기 알고리즘 (A* 알고리즘 사용) 으로 두 방 사이의 경로 찾음
3D 버전은 각 알고리즘들을 3D 버전으로 실행하면 됨
배치는 그냥 하면 되고
델라니 삼각분할을 3D로 하는게 힘들었다. 논문은 있는데 소스코드가 없음.
그래서 보이어 왓슨 알고리즘 공부해서 직접 바꿈.
외접원이 아니라 외접구로 바꿨더니 3D에서도 잘 작동 함.
그 후에 최소 신장 트리랑 나머지 그래프 추가하는 것도 쉬움.
근데 길찾기 알고리즘이 어려움. (뭐라 막 설명하는데 바로 이해는 못하겠)
나머지 링크들 (아직 안 봄)
https://www.youtube.com/watch?v=VnqN0v95jtU&list=PLcRSafycjWFfEPbSSjGMNY-goOZTuBPMW
https://www.youtube.com/watch?v=4ddbnQIuwAM
https://www.youtube.com/watch?v=wbpMiKiSKm8&list=PLFt_AvWsXl0eBW2EiBtl_sxmDtSgZBxB3
https://www.youtube.com/watch?v=O9J_Cfl6HzE
https://www.youtube.com/watch?v=K_643wa9GSw&list=PLu2uAkIZ4shpPdCTIjEpvhD8U-RRM3Y2F
