Today I Learned - Day 77 [지형 절차적 생성 - 격자형]

자, 오늘은 지형의 절차적 생성 방법에 대해서 조금 더 자세하게 정리 해 보자.

---

지형의 절차적 생성 알고리즘을 분류하면 대략 5가지 조합으로 구성이 가능하다.

• 격자형
  • 특정한 간격으로 임의의 블럭을 배열하는 형태.
  • 가장 간단하고 부하가 적다.
  • 대신 정해진 형태로만 구성이 가능하다는 난점이 있다.
• 구조 선택형
  • 특정한 알고리즘을 통해서 배치 구역을 형성, 그 구역에 맞는 지형을 배치하는 구조
  • 불규칙적인 지형을 형성하는 알고리즘 중에서는 가장 간단하면서 부하가 적은 방식.
  • 다만, 형성된 구역을 어떻게 이을 것인지에 대한 알고리즘이 필요하다.
•  배치 확장형
  • 정점이나 도형 등을 배치한 다음, 그 위치관계를 이용해서 선택, 확장하는 방식.
  • 2D 필드 제작에 유용하게 쓰인다. 특히 로그라이크 게임에서 매우 유용하게 쓰이는 알고리즘.
  • 다만, 알고리즘의 특성 상 필드의 크기가 들쭉날쭉할 가능성이 높다는 문제가 있다.
• 배제형
  • 지형을 대량으로 배치한 다음 임의의 지형을 제외하고 남은 지형 끼리 연결하는 방식.
  • 복잡한 지형을 그리면서도 '특정 지형'을 반드시 배치해야 하는 경우에 사용하기 좋다.
  • 반대로 '배치', '제거', '연결'의 복수 알고리즘이 필요해서 전체적으로 다소 복잡한 편.
• 노이즈형
  • 임의의 수단으로 형성되는 '노이즈'를 이용, 지형을 생성하는 방식.
  • 복셀 스타일 같이 내부도 규격화된 경우에 사용하기 좋다.
  • 다른 방식들에 비해서 압도적으로 복잡한 방식.

이 방법들 이외에도 다른 방법들도 많이 있으나, 현재 주로 사용되는 방식은 위 5가지다.

오늘은 이 중에서 '격자형'을 정리 해 보자.

코드가 들어가는 건 아니고, 개략적인 개념 만 글로 적는 것이다.

---

격자형 절차적 생성 알고리즘

문자 그대로 '격자'에 맞춰서 지형을 배치하는 방식을 말한다.

일반적인 방식은 아래를 참고하자.

참고로, '실시간 확장'이 아닌, '계층 구조로 사전 생성' 하는 방식으로 가정한다.

[실시간 확장이면 알고리즘이 조금 바뀐다.]

 

1. 원점을 작성한다.

격자형 절차적 생성의 기본 전제는 '블록이 서로 연결되어 있을 것'이다.

그렇기 때문에 일반적으로 원점에서 시작하여 점점 확장되는 구조로 작성하편이다.

즉, 알고리즘의 기준점이 되는 원점을 작성하는 것이 격자형 절차적 생성의 시작점이라고 할 수 있다.

 

2. 반복 로직을 이용해서 방이 생성될 좌표를 형성한다.

방을 임의로 확장해서 공간을 내는 단계.

알고리즘을 통해서 임의의 좌표에서 임의의 방향으로 확장하는 방식을 사용한다.

 

보통은 다음 알고리즘 중 하나를 사용한다.

[공통적으로 '방의 개수'를 조건으로 삼는다.]

1. 현재 형성된 좌표군 중 임의의 정점에서 임의의 방향으로 확장을 시도한다.
   중복된 좌표라면 다시 뽑는다.
2. 원점에서 시작해서 임의의 방향으로 나아가는 객체를 임의의 갯수 만큼 생성한다.
   이 객체들의 이동 경로 대로 좌표를 형성한다.
3. 현재 형성된 좌표군의 모든 점정에서 모든 방향에 확률적인 확장을 일정 횟수 시행한다.
   중복된 좌표를 제거한 뒤, 모든 좌표 중 임의의 좌표를 좌표의 개수가 맞춰질 때 까지 제거한다.
   이후 원점을 기준으로 고립된 좌표군 사이에 이동 방식을 구현하거나,
   고립된 좌표가 없을 때 까지 위 알고리즘으로 확장을 시도한다.

일반적으로는 1번이나 2번을 자주 사용한다.

 

3. 좌표 간의 연결 여부를 결정한다.

간단하게, 좌표 간의 문의 여부를 형성하는 단계다.

아예 모두 연결해도 좋고, 알고리즘으로 미로를 만들어도 좋다.

다만, 구성을 잘못하면 고립된 방이 나올 수 있다는 점에는 유의하자.

 

4. 좌표에 방을 배정한다.

알고리즘에 맞춰서 방을 좌표에 배정, 생성한다.

절차적 생성의 마지막 단계로, 이 과정이 끝나면 격자형 절차적 생성이 모두 종료된다.

 

또한, 이 '방 배정'을 어떻게 하느냐 또한 본 알고리즘에서 큰 갈림길이기도 하다.

보통은 다음 알고리즘 중 하나를 사용한다.

1. 각 정점의 연결된 정점의 개수를 이용해서 방을 배정하는 방식.
2. 처음 부터 방의 위치를 정해놓고, '반드시 연결될 수 있는' 알고리즘을 사용하는 방식.
   [ex. 원점과 특수방 양쪽에서 확장.]
3. 원점 부터 시작해서 연결된 정점들의 방 배정 상태를 참고하여 방을 배정하는 방식.

일반적으로는 1번이나 3번을 자주 사용한다.

---

응용 알고리즘

내용만 보면 문자 그대로 '격자형'이라서 2D 환경에만 쓸 수 있을 거 같은 기분이 들 수도 있다.

실제로는 3D 환경에서도 충분히 활용 가능하고, 오픈월드 구성에서도 활용 가능한 게 본 방식이다.

[오픈 월드라면 상술한 플로우를 따라갈 수는 없기는 하다. 그래도 '가능 하다'는 것은 맞다.]

물론, 이 정도로 활용하려면 제대로 설계를 해야된다.

 

그럼, 간단한 방식으로 응용할 수 있는 방법은 없을까?

당연히 있다. '각 방의 크기가 다르게 구성'한다거나, '추가 좌표를 이용해서 다중 차원 구조로 만든다'거나...

이외에도 응용할 방법은 많다. 격자의 형태가 사각형이 아니어도 되고, 0.5 지점을 활용할 수 있는 구조도 가능하다.

아니면 플레이어의 이동을 기점으로 하는 실시간 확장 구조로 만들어서 무한 필드를 만들 수도 있다.

 

정말로 다양한 방식으로 응용, 변형이 가능한 셈.

---

절차적 생성의 구현 방법은 가짓수가 정말로 많다.

그 중에서도 지금 정리한 '격자형 알고리즘'은 의외로 사용 빈도가 꽤 높은 알고리즘에 해당한다.

아무래도 가장 간단하다 보니, 이래저래 변주를 주기가 좋기 때문인 것으로 보인다.

 

'시스템에서 자동으로 무작위 지형을 생성할 수 있다'라는 점 덕분에 현재 절차적 생성은 게임 개발에서 떼어놓을 수 없는 입장에 가까워 지고 있다.

다만, 앞전의 글과 본 글에서 작성했듯이, 절차적 생성은 수학적 계산이 상당히 많이 들어가는 데다가, 활용 방안이 정말로 무궁무진하다. 덕분에 '어떻게 하는지'를 공부하기 보다는 '왜 그렇게 하는지'를 분석해야 하는 분야에 해당한다.

덕분에 개인적으로는 공부하고 알아본다고 해도 이래저래 따라가기 힘들고 이해도 잘 안되는 영역이리라고 생각한다.

그래도 자주 사용하는 방식이 있기도 하고, 기존의 방식을 응용하는 경우도 잦기 때문에, 어느 정도 정리해 두면 추후 도움이 되지 않을까.

그래서 조금씩 정리해 둘 생각이다. 적어도 '기본적인 형태'의 알고리즘은 모두 곧바로 작성할 수 있게끔.