Skip to content

Latest commit

 

History

History
397 lines (333 loc) · 28.4 KB

PCG.md

File metadata and controls

397 lines (333 loc) · 28.4 KB

PCG

Procedural Content Generation(PCG)은 컴퓨터 알고리즘을 사용하여 콘텐츠를 자동으로 생성하는 기법입니다. PCG는 무작위성을 도입하여 많은 변형과 다양한 콘텐츠를 생성할 수 있습니다. 이 방법은 게임, 영화, 음악, 그래픽 디자인 등 다양한 분야에서 사용될 수 있습니다.

  1. 무작위성(Randomness):
    • 무작위성은 PCG의 핵심 요소 중 하나입니다. 무작위성을 도입하여 예측 불가능하고 다양한 콘텐츠를 생성할 수 있습니다.
    • 예를 들어, 랜덤 시드(seed)를 사용하여 맵을 생성하면 같은 시드로 항상 동일한 맵을 생성할 수 있지만, 시드를 변경하면 다른 맵을 생성할 수 있습니다.
  2. 규칙 및 제약(Rules and Constraints):
    • PCG는 무작위성에만 의존하지 않습니다. 특정 규칙과 제약을 통해 생성된 콘텐츠가 논리적이고 일관성 있게 만들어집니다.
    • 예를 들어, 게임 맵에서는 벽이 방을 둘러싸야 하며, 통로는 연결되어야 하는 등의 규칙이 필요합니다.

PCG 기법으로 다음이 있습니다:

  1. 랜덤 생성(Random Generation):
    • 무작위 수 생성기를 사용하여 콘텐츠를 생성합니다. 예를 들어, 랜덤 시드를 사용하여 무작위 맵을 생성할 수 있습니다.
  2. 규칙 기반 시스템(Rule-based Systems):
    • 특정 규칙이나 조건에 따라 콘텐츠를 생성합니다. 예를 들어, 특정 패턴을 따르거나, 일정한 규칙에 따라 레벨을 생성하는 방식입니다.
  3. 프랙탈 생성(Fractal Generation):
    • 프랙탈 알고리즘을 사용하여 자연스러운 형태를 생성합니다. 예를 들어, 산, 강, 해안선 등의 지형을 생성할 때 사용됩니다.
  4. 그래머 기반 생성(Grammar-based Generation):
    • 문법 규칙을 사용하여 콘텐츠를 생성합니다. L-시스템(Lindenmayer Systems)과 같은 방법을 사용하여 식물이나 건물의 구조를 생성할 수 있습니다.
  5. 셀룰러 오토마타(Cellular Automata):
    • 셀룰러 오토마타는 격자 형태의 셀들이 일정한 규칙에 따라 상태를 변화시키는 방식입니다. 예를 들어, 던전 맵을 생성할 때 사용될 수 있습니다.
  6. 진화적 알고리즘(Evolutionary Algorithms):
    • 진화적 알고리즘을 사용하여 최적화된 콘텐츠를 생성합니다. 이는 자연 선택과 유사한 방식으로 콘텐츠를 반복적으로 개선합니다.

랜덤 생성 (Random Generation)

Procedural Content Generation(PCG) 기법에서 랜덤 생성(Random Generation)은 콘텐츠를 생성하는 과정에서 무작위성을 도입하여 다양한 결과물을 만들어내는 방법입니다. 이 기법은 게임 개발, 레벨 디자인, 맵 생성, 아이템 배치 등에 널리 사용됩니다.

  1. 무작위성(Randomness):
    • 콘텐츠 생성 과정에서 무작위성을 도입하여 각 실행마다 다른 결과를 생성합니다.
    • 동일한 규칙이나 알고리즘을 사용해도 다양한 결과물이 나올 수 있습니다.
  2. 재현성(Reproducibility):
    • 특정 시드값(Seed)을 사용하여 무작위성을 제어할 수 있습니다.
    • 동일한 시드를 사용하면 언제든지 동일한 결과물을 생성할 수 있어 테스트와 디버깅이 용이합니다.

퍼린 노이즈 (Perlin Noise)

퍼린 노이즈는 절차적 콘텐츠 생성에서 자주 사용되는 그래디언트 노이즈(Gradient Noise) 함수입니다. 퍼린 노이즈 함수는 자연스럽고 연속적인 무작위 패턴을 생성하는 데 유용하며, 지형 생성, 텍스처 생성, 애니메이션 등 다양한 분야에서 사용됩니다.

  1. 연속성(Continuity):
    • 퍼린 노이즈는 값들이 연속적으로 변하여 자연스러운 시각적 패턴을 생성합니다.
    • 인접한 좌표 간의 값들이 부드럽게 변하도록 보장하기 때문에, 거친 점진적인 변화가 없습니다.
  2. 무작위성(Randomness):
    • 무작위 요소를 포함하지만, 연속성을 유지하여 자연스러운 패턴을 생성합니다.
  3. 다중 차원(Multi-Dimensional):
    • 1차원, 2차원, 3차원 등 여러 차원에서 사용될 수 있습니다.

퍼린 노이즈의 동작 과정은 다음과 같습니다:

  1. 격자 정의 (Grid Definition)
    • 공간을 일정한 간격으로 나누어 격자를 만듭니다.
    • 각 격자 점마다 임의의 그래디언트 벡터를 할당합니다.
  2. 격자 점과의 거리 벡터 계산 (Calculating Distance Vectors)
    • 노이즈를 계산할 위치 (x, y)가 주어지면, 이 위치를 둘러싼 가장 가까운 4개의 격자 점을 찾습니다.
    • 계산할 위치 (x, y)에서 각 격자 점까지의 거리 벡터를 계산합니다.
    • 예를 들어, 계산할 위치가 (x, y)라면, 각 격자 점 (i, j)에 대해 거리 벡터는 (x - i, y - j)가 됩니다.
  3. 점곱 계산 (Calculating Dot Products)
    • 각 거리 벡터와 해당 격자 점의 그래디언트 벡터 간의 점곱을 계산합니다.
  4. 보간 (Interpolation)
    • 페이드 함수를 사용하여 거리 벡터의 각 성분에 대해 보간 계수를 계산합니다.
    • 퍼린 노이즈는 일반적으로 페이드 함수(Fade Function)를 사용하여 보간합니다.
    • 일반적으로 페이드 함수는 다음을 사용합니다: $f(t) = 6t^5 - 15t^4 + 10t^3$
  5. 값 결합 (Combining Values)
    • 계산한 점곱 값과 보간 계수를 결합합니다. 이 과정은 1D, 2D, 3D 등 차원에 따라 달라집니다.
    • 예를 들어, 2D에서는 x축과 y축을 따라 이중 보간을 수행합니다.
  6. 최종 노이즈 값 계산 (Calculating Final Noise Value)
    • 최종 보간된 값을 합산하여, 최종적인 노이즈 값을 계산합니다.
    • 이 값은 주어진 위치 (x, y)에서의 퍼린 노이즈 값이 됩니다.

심플렉스 노이즈 (Simplex Noise)

심플렉스 노이즈는 퍼린 노이즈의 단점을 개선하기 위해 개발된 노이즈 함수입니다. 심플렉스 노이즈는 퍼린 노이즈와 비슷한 목적을 가지고 있지만, 더 효율적으로 고차원 노이즈를 생성하고, 더 나은 품질을 제공합니다.

  1. 효율성(Efficiency)
    • 고차원(예: 3D, 4D)에서 계산 효율성이 높습니다.
    • 퍼린 노이즈는 고차원에서 계산 비용이 기하급수적으로 증가하는 반면, 심플렉스 노이즈는 이를 줄여줍니다.
  2. 품질(Quality)
    • 퍼린 노이즈의 시각적 인공물(artifacts)을 줄여줍니다.
    • 퍼린 노이즈는 고차원에서 격자 패턴(grid pattern)이 나타날 수 있지만, 심플렉스 노이즈는 이를 피할 수 있습니다.

심플렉스 노이즈는 퍼린 노이즈와 달리, 격자를 사용하지 않고 심플렉스(Simplex)라는 구조를 사용합니다. 심플렉스는 n차원 공간에서 가장 단순한 다면체입니다. 예를 들어, 2D에서는 정삼각형, 3D에서는 정사면체입니다.

심플렉스 노이즈의 동작 과정은 다음과 같습니다:

  1. 심플렉스 구조 정의(Simplex Structure Definition)
    • n차원 공간을 심플렉스 단위로 나눕니다.
    • 2D에서는 정삼각형, 3D에서는 정사면체 등으로 공간을 나눕니다.
  2. 거리 벡터 계산 (Calculate Distance Vectors)
    • 입력 좌표와 인접한 심플렉스의 각 꼭짓점 사이의 거리 벡터를 계산합니다.
  3. 기여도 계산 (Calculate Contributions)
    • 각 꼭짓점의 그래디언트 벡터와 거리 벡터 간의 점곱을 계산하여 기여도를 구합니다.
  4. 합산 (Accumulate Contributions)
    • 각 꼭짓점의 기여도를 가중합하여 최종 노이즈 값을 계산합니다.
    • 이 과정에서 기여도를 부드럽게 결합하기 위해 가중 함수를 사용합니다.

로지스틱 맵 (Logistic Map)

로지스틱 맵은 혼돈 이론(chaos theory)과 복잡계(complex systems) 연구에서 자주 등장하는 간단한 수학적 모델입니다. 로지스틱 맵은 인구 성장 모델을 설명하기 위해 개발되었으며, 비선형 동적 시스템의 행동을 이해하는 데 중요한 역할을 합니다. 또한 혼돈적 특성을 이용하여 예측 불가능한 난수열이나 절차적 콘텐츠 생성에 활용할 수 있습니다.

로지스틱 맵은 다음과 같은 이차 함수로 정의됩니다:

$x_{n+1} = r x_n (1 - x_n)$

  • $x_n$은 시간 $n$에서의 값입니다. (예: 인구 비율)
  • $r$은 성장률 파라미터입니다.
  • $x_{n+1}$은 다음 세대의 값입니다.

로지스틱 맵의 동작 과정은 다음과 같습니다:

  1. 초기값 설정 (Initialization)
    • 초기값 $x_0$를 [0, 1] 범위 내에서 설정합니다.
  2. 반복 계산 (Iterative Calculation)
    • 주어진 성장률 파라미터 $r$와 초기값 $x_0$를 사용하여 다음 값을 계산합니다.

로지스틱 맵은 파라미터 $r$의 값에 따라 다양한 행동을 보입니다:

  1. 0 < $r$ ≤ 1
    • 인구는 결국 멸종하여 0으로 수렴합니다.
  2. 1 < $r$ ≤ 3
    • 인구는 안정적인 특정 값에 수렴합니다.
  3. 3 < $r$ < 3.57
    • 인구는 주기적인 패턴을 보입니다.
    • 처음에는 주기 2의 주기적인 패턴을 보이다가 $r$이 증가함에 따라 주기가 4, 8, 16 등으로 증가합니다.
  4. 3.57 < $r$ ≤ 4
    • 시스템은 혼돈 상태에 빠지며, 초기 조건에 매우 민감해집니다.

규칙 기반 시스템 (Rule-based System)

규칙 기반 시스템은 명시적인 규칙과 논리적 구조에 따라 콘텐츠를 생성하는 방법을 말합니다. 이러한 시스템은 미리 정의된 규칙 집합을 기반으로 하여 게임의 레벨, 지형, 퍼즐, 캐릭터 등의 콘텐츠를 자동으로 생성합니다. 규칙 기반 시스템은 그 구조적 특성과 예측 가능성 덕분에 원하는 결과를 얻기 쉽게 만들 수 있습니다.

  1. 규칙 정의 (Rule Definition)
    • 규칙 기반 시스템의 핵심은 명확하게 정의된 규칙입니다. 규칙은 특정 조건하에서 어떤 행동이 발생할지를 명시합니다.
  2. 조건 및 행동 (Conditions and Actions)
    • 조건은 현재 상태나 입력 데이터에 기반한 논리적 판단을 의미하며, 행동은 조건이 만족될 때 수행되는 작업을 의미합니다.
  3. 추론 엔진 (Inference Engine)
    • 규칙을 평가하고 실행하는 시스템입니다. 입력 데이터를 분석하여 해당 규칙을 적용하고, 결과를 생성합니다.

다음은 규칙 기반 시스템을 사용하여 게임 레벨을 생성하는 예제입니다:

  1. 규칙 정의
    • 시작 타일은 항상 문이어야 한다.
    • 적어도 하나의 보물이 존재해야 한다.
    • 적어도 하나의 적이 존재해야 한다.
    • 보물은 문에서 두 타일 이상 떨어져 있어야 한다.
  2. 조건 및 행동
    • 현재 타일이 시작 타일인 경우, 문을 배치한다.
    • 현재 타일이 보물 타일인 경우, 두 타일 이상 떨어진 위치에 배치한다.
    • 나머지 타일은 적이나 일반 타일로 채운다.
  3. 추론 엔진
    • 시작 타일에서 규칙을 평가하여 문을 배치한다.
    • 보물 타일의 규칙을 평가하여 보물을 배치한다.
    • 나머지 타일에 적이나 일반 타일을 배치한다.

프랙탈 생성 (Fractal Generation)

프랙탈 생성은 프랙탈 기하학을 활용하여 복잡하고 자연스러운 패턴이나 구조를 생성하는 방법을 말합니다. 프랙탈은 자기유사성(self-similarity)이라는 특성을 가지며, 작은 부분이 전체 구조와 유사한 형태를 나타내는 특징이 있습니다. 이러한 프랙탈 기법은 자연 속의 다양한 형태, 예를 들어 산맥, 구름, 나무, 강 등의 복잡한 구조를 모방하는 데 유용합니다.

  1. 자기유사성(Self-similarity)
    • 프랙탈 구조는 전체와 유사한 작은 부분들로 구성되어 있습니다. 이러한 자기유사성은 반복적인 패턴 생성에 유용합니다.
  2. 반복적 과정(Iterative Process)
    • 프랙탈 생성은 보통 반복적 또는 재귀적인 과정을 통해 이루어집니다. 간단한 규칙을 반복적으로 적용하여 복잡한 구조를 만듭니다.
  3. 수학적 기반(Mathematical Basis)
    • 프랙탈은 수학적 방정식이나 알고리즘을 기반으로 생성됩니다. 이는 정확하고 복잡한 패턴을 생성하는 데 도움을 줍니다.

프랙탈 생성에는 여러 기법이 있습니다:

  1. 코흐 곡선 (Koch Curve)
    • 직선을 일정한 규칙에 따라 반복적으로 분할하여 복잡한 패턴을 만듭니다. 대표적으로 코흐 눈송이가 있습니다.
  2. 리디아의 삼각형 (Sierpinski Triangle)
    • 삼각형을 반복적으로 작은 삼각형으로 분할하여 생성됩니다. 각 단계에서 중앙의 삼각형을 제거하는 방식입니다.
  3. 카펜터 카펫 (Sierpinski Carpet)
    • 정사각형을 반복적으로 작은 정사각형으로 분할하여 중앙의 정사각형을 제거하는 방식으로 생성됩니다.
  4. 만델브로 집합 (Mandelbrot Set)
    • 복소수 평면에서 특정 반복 조건을 만족하는 점들의 집합으로, 복소수의 반복적 연산을 통해 생성됩니다.
  5. 다이아몬드-스퀘어 알고리즘 (Diamond-Square Algorithm)
    • 랜덤 변동을 더하여 지형을 생성하는 기법으로, 큰 영역을 작은 부분으로 분할하고 중앙 값을 변동시켜 생성됩니다.

그래머 기반 생성(Grammar-Based Generation)

그래머 기반 생성은 규칙 집합(문법)을 사용하여 컨텐츠를 생성하는 방법입니다. 이러한 시스템은 일반적으로 형식 문법(formal grammar)을 이용하여 콘텐츠의 구조를 정의하고, 규칙을 반복적으로 적용하여 최종 결과물을 생성합니다. 이 방법은 언어 생성, 프로시저적 맵 생성, 스토리 생성 등 다양한 분야에서 사용됩니다.

  1. 형식 문법(Formal Grammar):
    • 형식 문법은 언어의 문법 규칙을 형식적으로 정의한 것입니다.
    • 예를 들어, 프로덕션 룰(production rule)을 통해 복잡한 구조를 간단한 구성 요소로 분해합니다.
  2. 규칙(Production Rules):
    • 규칙은 하나의 심볼(symbol)을 다른 심볼의 조합으로 대체하는 방식으로 정의됩니다.
    • 예를 들어, S → A B는 심볼 S를 심볼 A와 B로 대체합니다.
  3. 재귀(Recursion):
    • 규칙은 재귀적으로 정의될 수 있으며, 이는 복잡한 구조를 생성하는 데 유용합니다.
    • 예를 들어, S → a S b는 무한히 확장될 수 있는 재귀적인 구조를 만듭니다.

다음은 간단한 문법 예제입니다:

  1. 문법 정의:
    • S → NP VP
    • NP → Det N
    • VP → V NP
    • Det → "the" | "a"
    • N → "cat" | "dog"
    • V → "chases" | "sees"
  2. 생성 과정:
    • 시작 심볼(S)에서 시작하여 규칙을 반복적으로 적용합니다.
    • 예: S → NP VP → Det N VP → "the" N VP → "the" "cat" VP → "the" "cat" V NP → "the" "cat" "chases" NP → "the" "cat" "chases" Det N → "the" "cat" "chases" "a" N → "the" "cat" "chases" "a" "dog"

이러한 규칙을 통해 "the cat chases a dog"라는 문장을 생성할 수 있습니다.

셀룰러 오토마타 (Cellular Automata)

셀룰러 오토마타는 격자 형태의 셀로 구성된 시스템에서 각 셀이 이웃한 셀들과의 상호작용을 통해 상태를 변화시키는 계산 모델입니다. 이 모델은 간단한 규칙에 따라 복잡한 패턴을 생성할 수 있으며, 다양한 과학적 및 기술적 응용 분야에서 사용됩니다.

  1. 격자(Grid)
    • 셀룰러 오토마타는 1차원, 2차원, 3차원 등 다양한 차원의 격자로 구성될 수 있습니다.
    • 가장 흔한 형태는 2차원 격자입니다.
  2. 셀(Cell)
    • 각 셀은 하나의 상태(state)를 가집니다. 상태는 일반적으로 유한한 수의 값으로 표현됩니다. (예: 0, 1)
  3. 이웃(Neighborhood)
    • 각 셀의 상태는 이웃 셀들의 상태에 따라 결정됩니다.
    • 가장 일반적인 이웃 형태는 무어 이웃(8개의 인접한 셀)과 폰 노이만 이웃(4개의 인접한 셀)입니다.
  4. 규칙(Rule)
    • 셀의 상태 변화를 결정하는 규칙 집합입니다.
    • 규칙은 현재 상태와 이웃 셀들의 상태를 기반으로 새로운 상태를 결정합니다.

게임 오브 라이프 (Game of Life)

존 호튼 콘웨이가 고안한 2차원 셀룰러 오토마타로, 간단한 규칙을 통해 복잡한 패턴을 생성합니다.

규칙:

  • 생존: 살아있는 셀은 이웃한 살아있는 셀이 2개 또는 3개일 때 살아남습니다.
  • 죽음: 살아있는 셀은 이웃한 살아있는 셀이 2개 미만이거나 4개 이상일 때 죽습니다.
  • 탄생: 죽어있는 셀은 이웃한 살아있는 셀이 정확히 3개일 때 살아납니다.

진화적 알고리즘 (Evolutionary Algorithms)

진화적 알고리즘은 생물 진화의 원리를 모방하여 콘텐츠를 생성하는 방법입니다. 이 알고리즘은 자연 선택, 돌연변이, 교배 등의 개념을 사용하여 콘텐츠를 점진적으로 개선합니다. 진화적 알고리즘은 게임 맵, 캐릭터, 퍼즐, 음악 등 다양한 형태의 콘텐츠를 생성하는 데 사용될 수 있습니다.

  1. 개체(Individual):
    • 생성할 콘텐츠의 한 예를 나타냅니다.
  2. 유전자(Genotype):
    • 개체의 특성을 코드화한 것입니다.
  3. 집단(Population):
    • 여러 개체들의 집합으로, 한 세대의 모든 가능성을 포함합니다.
  4. 적합도 함수(Fitness Function):
    • 개체의 품질을 평가하는 함수입니다.
  5. 선택(Selection):
    • 적합도가 높은 개체를 선택하여 다음 세대를 형성합니다.
  6. 교배(Crossover):
    • 두 개체의 유전자를 조합하여 새로운 개체를 생성합니다.
  7. 돌연변이(Mutation):
    • 유전자의 일부를 무작위로 변경하여 다양성을 추가합니다.

진화적 알고리즘의 동작 과정은 다음과 같습니다:

  1. 초기 집단 생성:
    • 무작위로 초기 집단을 생성합니다.
  2. 적합도 평가:
    • 각 개체에 대해 적합도 함수를 적용하여 품질을 평가합니다.
  3. 선택:
    • 적합도가 높은 개체를 선택합니다. 일반적으로 룰렛 휠 선택, 토너먼트 선택 등이 사용됩니다.
  4. 교배 및 돌연변이:
    • 선택된 개체들 사이에서 교배를 통해 새로운 개체를 생성하고, 일부 개체에 돌연변이를 적용합니다.
  5. 세대 교체:
    • 새로 생성된 개체들로 집단을 교체합니다.
  6. 종료 조건 확인:
    • 일정 세대 수에 도달하거나 적합도가 충분히 높아질 때까지 반복합니다.

아래는 게임 맵 생성을 하는 예제입니다.

  1. 유전자 표현:
    • 게임 맵을 2D 배열로 표현합니다. 각 셀은 타일 유형(예: 벽, 길, 문 등)을 나타냅니다.
  2. 적합도 함수:
    • 맵의 완성도, 플레이어의 이동 가능성, 퍼즐의 난이도 등을 평가합니다.
  3. 진화적 과정:
    • 초기 맵들을 무작위로 생성하고, 적합도에 따라 선별하여 교배 및 돌연변이를 통해 점진적으로 개선합니다.

랜덤 워크 (Random Walk)

랜덤 워크(Random Walk)는 임의의 경로를 따라 이동하는 과정을 의미하며, 통계학, 물리학, 컴퓨터 과학 등 여러 분야에서 사용되는 개념입니다. 이 알고리즘은 현재 위치에서 다음 위치로 이동할 때, 여러 가능한 방향 중 하나를 무작위로 선택하여 이동하는 방식입니다. 랜덤 워크는 단순하면서도 강력한 알고리즘으로, 복잡한 패턴을 쉽게 생성할 수 있어 게임 개발 및 기타 무작위 콘텐츠 생성에서 유용합니다.

랜덤 워크의 동작 과정은 다음과 같습니다:

  1. 초기 위치 (Starting Point):
    • 임의의 위치에서 시작합니다.
  2. 이동 규칙 (Movement Rules):
    • 각 단계에서 이동할 수 있는 방향을 결정합니다.
    • 예를 들어, 2차원 격자에서는 상하좌우 네 방향으로 이동할 수 있습니다.
  3. 반복 (Iteration):
    • 정해진 단계 수 만큼 이동을 반복합니다. 각 단계에서 이동 방향을 무작위로 선택합니다.

랜덤 워크의 종류는 다음이 있습니다.

  1. 단순 랜덤 워크 (Simple Random Walk):
    • 가장 기본적인 형태로, 각 단계에서 이동할 방향이 모두 동일한 확률로 선택됩니다.
  2. 편향 랜덤 워크 (Biased Random Walk):
    • 특정 방향으로 이동할 확률이 더 높은 랜덤 워크입니다.
  3. 반사 랜덤 워크 (Reflecting Random Walk):
    • 경계에 도달하면 반사되어 되돌아오는 랜덤 워크입니다.

L-시스템(Lindenmayer System)

L-시스템은 식물의 성장 과정과 같은 복잡한 구조를 간단한 규칙 집합으로 모델링하는 형식 문법입니다. L-시스템은 주로 식물의 가지와 잎, 나무 구조 등의 프랙탈 패턴을 생성하는 데 사용됩니다. L-시스템은 규칙 기반 생성의 일종으로, 문자열을 재귀적으로 변환하여 복잡한 구조를 만들어냅니다.

  1. 알파벳 (Alphabet):
    • 시스템에서 사용되는 문자 집합입니다. 보통 F, +, -, [, ] 등의 문자를 포함합니다.
    • 예: F (전진), + (시계 방향 회전), - (반시계 방향 회전), [ (현재 위치 저장), ] (저장된 위치로 복귀)
  2. 공리 (Axiom):
    • 문자열 변환의 시작점이 되는 초기 문자열입니다.
    • 예: "F"
  3. 생성 규칙 (Production Rules):
    • 각 문자에 대해 적용할 변환 규칙입니다. 규칙은 한 문자를 다른 문자열로 변환합니다.
    • 예: F → F+F−F−F+F
  4. 반복 단계 (Iteration):
    • 규칙을 반복적으로 적용하여 문자열을 점진적으로 발전시킵니다.

L-시스템의 동작 과정은 다음과 같습니다:

  1. 초기화:
    • 공리를 초기 문자열로 설정합니다.
  2. 규칙 적용:
    • 각 문자에 대해 생성 규칙을 적용하여 새로운 문자열을 만듭니다.
  3. 반복:
    • 원하는 횟수만큼 규칙 적용 단계를 반복합니다.
  4. 결과 해석:
    • 최종 문자열을 사용하여 그래픽이나 구조를 생성합니다.

타일 기반 알고리즘 (Tile-based Algorithms)

타일 기반 알고리즘(Tile-based Algorithms)은 미리 정의된 타일 세트를 사용하여 맵을 생성하는 방법입니다. 각 타일은 특정한 속성과 규칙을 가지며, 이 타일들을 조합하여 일관성 있고 의미 있는 맵을 생성합니다. 타일 기반 알고리즘은 다양한 게임 장르에서 맵과 레벨을 설계하는 데 널리 사용됩니다.

  1. 타일(Tile):
    • 맵을 구성하는 기본 단위로, 각 타일은 특정 속성(예: 지형, 장애물, 아이템 등)을 가집니다.
  2. 타일 세트(Tile Set):
    • 사용 가능한 타일들의 집합으로, 다양한 타일이 포함될 수 있습니다.
  3. 타일 규칙(Tile Rules):
    • 타일이 어떻게 배치될지 결정하는 규칙으로, 타일 간의 연결성과 일관성을 유지합니다.

Wave Function Collapse

Wave Function Collapse(WFC)는 주어진 타일 세트를 이용해 일관성 있고 의미 있는 패턴을 생성하는 방법입니다. 이 알고리즘은 양자역학의 Wave Function Collapse 개념에서 영감을 받아 이름 지어졌지만, 실제로는 타일 기반 맵 생성에 활용되는 기법입니다.

  1. 타일 세트(Tile Set):
    • 사용 가능한 타일들의 집합입니다.
    • 각 타일은 특정 속성과 패턴을 가집니다.
  2. 타일 제약(Tile Constraints):
    • 타일이 인접할 수 있는 규칙을 정의합니다.
    • 어떤 타일이 다른 타일 옆에 배치될 수 있는지 규칙을 통해 결정합니다.
  3. 슈퍼포지션(Superposition):
    • 각 타일의 가능한 상태를 나타내며, 초기 상태에서는 모든 타일이 모든 가능한 상태를 가질 수 있습니다.
  4. 엔트로피(Entropy):
    • 특정 타일이 가질 수 있는 상태의 수로, 엔트로피가 낮을수록 타일의 상태가 덜 불확실합니다.

작동 원리는 다음과 같습니다.

  1. 초기화(Initialization):
    • 맵의 각 위치에 대해 가능한 모든 타일 상태(슈퍼포지션)를 설정합니다.
  2. 관찰(Observation):
    • 가장 낮은 엔트로피(가장 불확실성이 적은)의 위치를 선택하여 하나의 타일 상태로 축소합니다.
    • 이 과정에서 타일 제약을 고려합니다.
  3. 프로파게이션(Propagation):
    • 선택된 타일 상태가 인접한 위치에 미치는 영향을 계산하여, 인접 위치의 가능한 타일 상태를 갱신합니다.
    • 이 과정은 주변 타일들의 엔트로피를 낮춥니다.
  4. 반복(Iteration):
    • 모든 위치의 타일 상태가 결정될 때까지 관찰과 프로파게이션 과정을 반복합니다.

Binary Space Partitioning

Binary Space Partitioning (BSP, 이진 공간 분할)은 컴퓨터 그래픽스, 게임 개발, 맵 생성 등에서 공간을 효율적으로 관리하고 구조화하기 위해 사용되는 알고리즘입니다. 특히 던전 생성과 같은 구조적 맵 생성에 많이 활용됩니다. BSP는 공간을 반복적으로 이진 분할하여 트리 구조로 표현하며, 각 분할 영역을 다양한 목적으로 사용할 수 있습니다.

  1. 분할(Partitioning):
    • 공간을 둘로 나누는 작업입니다.
    • 각 분할은 다시 하위 분할될 수 있습니다.
  2. 노드(Node):
    • 트리 구조에서 각 분할을 나타내며, 루트 노드에서 시작하여 하위 노드로 계속 분할됩니다.
  3. 리프(Leaf):
    • 더 이상 분할되지 않는 최종 노드로, 실제 방, 구역 또는 타일을 나타낼 수 있습니다.
  4. 트리(Tree):
    • 전체 공간을 표현하는 계층적 구조입니다.
    • 각 노드는 하나의 분할을 나타내며, 리프는 최종 공간을 나타냅니다.

작동 원리는 다음과 같습니다.

  1. 초기화(Initialization):
    • 전체 공간을 하나의 루트 노드로 시작합니다.
  2. 분할(Partitioning):
    • 루트 노드를 기준으로 공간을 두 개의 하위 공간으로 분할합니다.
    • 분할 방법은 수평 또는 수직으로 나눌 수 있습니다.
  3. 재귀적 분할(Recursive Partitioning):
    • 각 하위 공간을 다시 분할합니다.
    • 이 과정은 더 이상 분할할 수 없을 때까지(예: 최소 크기 도달) 반복됩니다.
  4. 리프 생성(Leaf Creation):
    • 최종 분할된 공간(리프)은 실제로 사용할 방이나 구역으로 변환됩니다.
  5. 연결(Connection):
    • 리프들을 서로 연결합니다. 던전의 경우, 방과 방을 연결하는 복도를 생성합니다.

랜덤 타일 배치 (Random Tile Placement)

랜덤 타일 배치는 타일 기반 맵 생성 방법 중 하나로, 규칙에 의한 제한 없이 타일을 무작위로 배치하는 간단한 알고리즘입니다. 이 방법은 구현이 매우 간단하고 빠르지만, 결과가 일관성 없고 무작위적일 수 있습니다. 그럼에도 불구하고, 특정 유형의 게임이나 프로토타입을 빠르게 생성해야 할 때 유용할 수 있습니다.

  1. 타일(Tile):
    • 맵을 구성하는 기본 단위로, 각 타일은 특정 속성(예: 지형, 아이템, 장애물 등)을 가집니다.
  2. 무작위 배치(Random Placement):
    • 각 타일을 아무런 규칙 없이 무작위로 배치합니다.

작동 원리는 다음과 같습니다.

  1. 타일 세트(Tile Set):
    • 사용할 타일들의 집합을 정의합니다.
  2. 무작위 배치(Random Placement):
    • 맵의 각 위치에 대해 타일 세트에서 무작위로 타일을 선택하여 배치합니다.

그래프 기반 알고리즘 (Graph-based Algorithms)

그래프 기반 알고리즘(Graph-based Algorithms)은 그래프 이론을 이용하여 맵을 생성하는 방법입니다. 그래프는 노드(정점)과 엣지(간선)으로 구성되며, 노드는 특정 위치나 타일을, 엣지는 이들 간의 연결이나 경로를 나타냅니다. 그래프 기반 알고리즘은 맵의 구조적 일관성과 연결성을 보장하며, 복잡한 레이아웃을 효율적으로 생성할 수 있습니다.

  1. 노드(Node):
    • 맵에서 특정 지점을 나타내며, 방, 구역, 또는 중요한 타일을 의미할 수 있습니다.
  2. 엣지(Edge):
    • 노드 간의 연결을 나타내며, 통로, 길, 또는 기타 연결부를 의미합니다.
  3. 그래프(Graph):
    • 노드와 엣지로 구성된 전체 구조로, 맵의 레이아웃을 형성합니다.