[Unity 2D / (1) 절차적 맵 생성] 절차적 맵 생성 알고리즘의 던전 생성 방식

절차적 맵 생성 알고리즘의 던전 생성 방식

1. Random Walk 알고리즘
2. 복도들을 생성한다.
3. 복도들에 대해, 각 복도의 끝점에 대해서 방을 생성한다.

 

1. Random Walk 알고리즘

• 말 그대로 임의의 방향으로 이동하는 방식을 뜻한다. 특정 규칙 없이 탐색을 하는 알고리즘인 것.
• 1. 시작점 설정 → 특정 좌표에서 시작
  2. 무작위 이동 → 매 이동마다, 직교 방향(상, 하, 좌, 우) 중 랜덤한 방향으로 한 칸씩 이동
  3. 저장 및 반복 → 이동한 좌표를 컨테이너에 저장하고, 1, 2를 임의의 횟수 만큼 반복
  4. 타일 배치 → 이동을 완료후, 컨테이너에 저장된 좌표들에 대해 타일을 배치
• 이 알고리즘을 이용해서 방과 복도를 생성할 수 있다.

Random Walk 과정 시각화

 

 

2. 복도들을 생성한다.

Random Walk 알고리즘 이용

1. 시작점 설정: 복도 생성을 시작할 시작점 정하기.
2. 무작위 이동: 현재 위치에서 직교 방향(상, 하, 좌, 우)를 랜덤하게 정해서, 그 방향으로 일정 거리 만큼 이동(Walk)한다.
3. 원하는 갯수 만큼 반복: 원하는 갯수만큼 반복한다. 이 때 다음 복도의 시작점은, 이전에 만든 복도의 마지막 끝 좌표이다. 그래야 복도들이 서로 이어지면서 만들어질 것이다. 
4. 타일 배치: 생성된 복도와 방의 좌표들에 대해 타일을 배치해서 시각화 한다.

Random Walk를 통해 생성된 복도들.

 

 

3. 복도들에 대해, 각 복도의 끝점에 대해서 방을 생성한다.

Random Walk 알고리즘 이용

1. 방의 시작 좌표 설정: 방의 시작 좌표는 복도별 끝 좌표이다. 이러면 모든 방들은 복도를 통해, 서로 오갈 수 있는 구조가 자동적으로 형성된다. 
2. Random Walk 수행: 방의 시작 좌표에 대해 Random Walk를 수행. 
3. 타일 배치: 생성된 좌표들에 대해 타일을 배치해서 시각화 한다.

빨간 점이 각 복도별 끝 좌표. 해당 좌표를 중심으로 방이 생성되었다.