절차적 생성 알고리즘 완전 가이드: Perlin Noise부터 L-System까지
게임 개발과 그래픽스 분야에서 핵심적인 절차적 생성 알고리즘의 원리와 구현 방법을 상세히 알아보자.
Photo by Shubham Dhage
on
Unsplash
들어가며
게임을 플레이하다 보면 끝없이 펼쳐지는 지형이나 자연스럽게 생성되는 던전을 마주할 때가 있다. 이런 콘텐츠들은 사람이 직접 만든 것이 아니라 절차적 생성(Procedural Generation) 알고리즘을 통해 자동으로 만들어진다.
절차적 생성은 단순한 규칙이나 수학적 공식을 바탕으로 복잡하고 다양한 콘텐츠를 자동으로 생성하는 기술이다. 이 기술을 통해 개발자는 제한된 시간과 자원으로도 방대한 양의 콘텐츠를 만들어낼 수 있다. 오늘은 절차적 생성의 핵심 알고리즘들을 살펴보고 실제로 어떻게 구현할 수 있는지 알아보자.
절차적 생성의 기본 개념
절차적 생성이란?
절차적 생성은 알고리즘을 사용하여 데이터를 자동으로 생성하는 방법이다. 미리 정의된 규칙과 매개변수를 바탕으로 무작위성을 제어하면서 원하는 특성을 가진 콘텐츠를 만들어낸다.
// 간단한 절차적 생성 예시
class TerrainGenerator {
private seed: number;
constructor(seed: number) {
this.seed = seed;
}
generateHeightMap(width: number, height: number): number[][] {
const heightMap: number[][] = [];
const random = this.createSeededRandom(this.seed);
for (let y = 0; y < height; y++) {
heightMap[y] = [];
for (let x = 0; x < width; x++) {
// 기본적인 랜덤 높이 생성
heightMap[y][x] = random() * 100;
}
}
return heightMap;
}
private createSeededRandom(seed: number) {
return () => {
seed = (seed * 9301 + 49297) % 233280;
return seed / 233280;
};
}
}절차적 생성의 장점과 활용 분야
절차적 생성은 다음과 같은 장점을 갖는다:
- 효율성: 적은 데이터로 방대한 콘텐츠 생성
- 다양성: 매번 다른 결과물 생성 가능
- 재현성: 같은 시드값으로 동일한 결과 보장
- 확장성: 무한히 확장 가능한 콘텐츠
주요 활용 분야로는 게임 개발(지형, 던전, 텍스처), 그래픽스(자연 현상 시뮬레이션), 건축 시각화, 예술 작품 생성 등이 있다.
Perlin Noise 알고리즘
Perlin Noise의 개념과 원리
Perlin Noise는 1983년 Ken Perlin이 개발한 그래디언트 노이즈 함수다. 자연스러운 텍스처와 지형을 만들기 위해 고안되었으며, 컴퓨터 그래픽스 분야에서 가장 널리 사용되는 노이즈 함수 중 하나다.
핵심 원리는 격자점에서 랜덤한 그래디언트 벡터를 생성하고, 이들을 부드럽게 보간하여 연속적이고 자연스러운 노이즈를 만드는 것이다.
Perlin Noise 구현
class PerlinNoise {
private permutation: number[] = [];
private gradients: number[][] = [
[1, 1], [-1, 1], [1, -1], [-1, -1],
[1, 0], [-1, 0], [0, 1], [0, -1]
];
constructor(seed: number = 0) {
this.initializePermutation(seed);
}
private initializePermutation(seed: number) {
// 0-255 순열 생성
for (let i = 0; i < 256; i++) {
this.permutation[i] = i;
}
// Fisher-Yates 셔플
const random = this.createSeededRandom(seed);
for (let i = 255; i > 0; i--) {
const j = Math.floor(random() * (i + 1));
[this.permutation[i], this.permutation[j]] =
[this.permutation[j], this.permutation[i]];
}
// 배열을 두 배로 확장 (모듈러 연산 최적화)
this.permutation = [...this.permutation, ...this.permutation];
}
noise(x: number, y: number): number {
// 격자 좌표
const X = Math.floor(x) & 255;
const Y = Math.floor(y) & 255;
// 격자 내 상대 좌표
const fx = x - Math.floor(x);
const fy = y - Math.floor(y);
// 페이드 함수 적용
const u = this.fade(fx);
const v = this.fade(fy);
// 격자점 해시값
const aa = this.permutation[this.permutation[X] + Y];
const ab = this.permutation[this.permutation[X] + Y + 1];
const ba = this.permutation[this.permutation[X + 1] + Y];
const bb = this.permutation[this.permutation[X + 1] + Y + 1];
// 그래디언트 벡터와 거리 벡터의 내적
const grad1 = this.grad(aa, fx, fy);
const grad2 = this.grad(ba, fx - 1, fy);
const grad3 = this.grad(ab, fx, fy - 1);
const grad4 = this.grad(bb, fx - 1, fy - 1);
// 이중 선형 보간
const lerp1 = this.lerp(u, grad1, grad2);
const lerp2 = this.lerp(u, grad3, grad4);
return this.lerp(v, lerp1, lerp2);
}
private fade(t: number): number {
// 5차 에르미트 보간 (6t^5 - 15t^4 + 10t^3)
return t * t * t * (t * (t * 6 - 15) + 10);
}
private grad(hash: number, x: number, y: number): number {
const gradient = this.gradients[hash & 7];
return gradient[0] * x + gradient[1] * y;
}
private lerp(t: number, a: number, b: number): number {
return a + t * (b - a);
}
private createSeededRandom(seed: number) {
return () => {
seed = (seed * 9301 + 49297) % 233280;
return seed / 233280;
};
}
}실제 활용 예시
// 지형 생성 예시
function generateTerrain(width: number, height: number, scale: number = 0.1): number[][] {
const noise = new PerlinNoise(12345);
const terrain: number[][] = [];
for (let y = 0; y < height; y++) {
terrain[y] = [];
for (let x = 0; x < width; x++) {
// 여러 옥타브를 합성하여 더 복잡한 지형 생성
let value = 0;
let amplitude = 1;
let frequency = scale;
for (let octave = 0; octave < 4; octave++) {
value += noise.noise(x * frequency, y * frequency) * amplitude;
amplitude *= 0.5;
frequency *= 2;
}
terrain[y][x] = value;
}
}
return terrain;
}Diamond-Square 알고리즘
Diamond-Square의 개념과 특징
Diamond-Square 알고리즘은 프랙탈 기반의 높이맵 생성 알고리즘이다. 정사각형 격자에서 시작하여 다이아몬드 단계와 스퀘어 단계를 반복적으로 수행하면서 세부 사항을 추가해 나간다.
이 알고리즘의 핵심 특징은 분할 정복(Divide and Conquer) 방식으로 동작한다는 점이다. 큰 영역을 작은 영역으로 나누면서 각 단계에서 무작위성을 추가하여 자연스러운 높이맵을 생성한다.
Diamond-Square 구현
class DiamondSquare {
private heightMap: number[][];
private size: number;
private roughness: number;
constructor(size: number, roughness: number = 0.5) {
// 크기는 2^n + 1 이어야 함
this.size = size;
this.roughness = roughness;
this.heightMap = Array(size).fill(null).map(() => Array(size).fill(0));
}
generate(seed: number = 0): number[][] {
const random = this.createSeededRandom(seed);
// 네 모서리 초기화
this.heightMap[0][0] = random() * 100;
this.heightMap[0][this.size - 1] = random() * 100;
this.heightMap[this.size - 1][0] = random() * 100;
this.heightMap[this.size - 1][this.size - 1] = random() * 100;
let stepSize = this.size - 1;
let scale = 100;
while (stepSize > 1) {
// Diamond 단계
this.diamondStep(stepSize, scale, random);
// Square 단계
this.squareStep(stepSize, scale, random);
stepSize /= 2;
scale *= this.roughness;
}
return this.heightMap;
}
private diamondStep(stepSize: number, scale: number, random: () => number) {
const halfStep = stepSize / 2;
for (let y = halfStep; y < this.size; y += stepSize) {
for (let x = halfStep; x < this.size; x += stepSize) {
const avg = (
this.heightMap[y - halfStep][x - halfStep] +
this.heightMap[y - halfStep][x + halfStep] +
this.heightMap[y + halfStep][x - halfStep] +
this.heightMap[y + halfStep][x + halfStep]
) / 4;
this.heightMap[y][x] = avg + (random() - 0.5) * scale;
}
}
}
private squareStep(stepSize: number, scale: number, random: () => number) {
const halfStep = stepSize / 2;
for (let y = 0; y < this.size; y += halfStep) {
for (let x = (y + halfStep) % stepSize; x < this.size; x += stepSize) {
const neighbors = this.getSquareNeighbors(x, y, halfStep);
const avg = neighbors.reduce((sum, val) => sum + val, 0) / neighbors.length;
this.heightMap[y][x] = avg + (random() - 0.5) * scale;
}
}
}
private getSquareNeighbors(x: number, y: number, halfStep: number): number[] {
const neighbors: number[] = [];
// 상하좌우 이웃 검사
const positions = [
[x, y - halfStep],
[x, y + halfStep],
[x - halfStep, y],
[x + halfStep, y]
];
for (const [nx, ny] of positions) {
if (nx >= 0 && nx < this.size && ny >= 0 && ny < this.size) {
neighbors.push(this.heightMap[ny][nx]);
}
}
return neighbors;
}
private createSeededRandom(seed: number) {
return () => {
seed = (seed * 9301 + 49297) % 233280;
return seed / 233280;
};
}
}Diamond-Square의 장단점
장점:
- 빠른 실행 속도
- 메모리 효율성
- 자연스러운 프랙탈 특성
단점:
- 방향성 편향 (인공적인 패턴 생성)
- 제한된 해상도 (2^n + 1)
- 테두리 효과 문제
L-System 알고리즘
L-System의 개념과 문법
L-System(Lindenmayer System)은 1968년 생물학자 Aristid Lindenmayer가 개발한 문법 기반 재작성 시스템이다. 간단한 규칙을 반복 적용하여 복잡한 구조를 생성하는 방식으로, 특히 식물의 성장 패턴을 모델링하는 데 뛰어난 성능을 보인다.
L-System의 핵심 요소는 다음과 같다:
- 알파벳(Alphabet): 사용할 기호들의 집합
- 공리(Axiom): 시작 문자열
- 생성 규칙(Production Rules): 문자 치환 규칙
- 반복 횟수(Iterations): 규칙 적용 횟수
L-System 구현
interface LSystemRule {
symbol: string;
replacement: string;
probability?: number;
}
class LSystem {
private alphabet: string[];
private axiom: string;
private rules: Map<string, LSystemRule[]>;
constructor(alphabet: string[], axiom: string) {
this.alphabet = alphabet;
this.axiom = axiom;
this.rules = new Map();
}
addRule(symbol: string, replacement: string, probability: number = 1.0) {
if (!this.rules.has(symbol)) {
this.rules.set(symbol, []);
}
this.rules.get(symbol)!.push({ symbol, replacement, probability });
}
generate(iterations: number, seed: number = 0): string {
const random = this.createSeededRandom(seed);
let current = this.axiom;
for (let i = 0; i < iterations; i++) {
current = this.applyRules(current, random);
}
return current;
}
private applyRules(input: string, random: () => number): string {
let result = '';
for (const symbol of input) {
const applicableRules = this.rules.get(symbol);
if (applicableRules && applicableRules.length > 0) {
const selectedRule = this.selectRule(applicableRules, random);
result += selectedRule.replacement;
} else {
result += symbol;
}
}
return result;
}
private selectRule(rules: LSystemRule[], random: () => number): LSystemRule {
// 확률 기반 규칙 선택
const totalProbability = rules.reduce((sum, rule) => sum + (rule.probability || 1), 0);
let randomValue = random() * totalProbability;
for (const rule of rules) {
randomValue -= rule.probability || 1;
if (randomValue <= 0) {
return rule;
}
}
return rules[0]; // 기본값
}
private createSeededRandom(seed: number) {
return () => {
seed = (seed * 9301 + 49297) % 233280;
return seed / 233280;
};
}
}터틀 그래픽스를 이용한 시각화
interface Point {
x: number;
y: number;
}
interface TurtleState {
position: Point;
angle: number;
penDown: boolean;
}
class TurtleGraphics {
private canvas: HTMLCanvasElement;
private ctx: CanvasRenderingContext2D;
private state: TurtleState;
private stateStack: TurtleState[] = [];
constructor(canvas: HTMLCanvasElement) {
this.canvas = canvas;
this.ctx = canvas.getContext('2d')!;
this.state = {
position: { x: canvas.width / 2, y: canvas.height - 10 },
angle: -Math.PI / 2, // 위쪽 방향
penDown: true
};
}
drawLSystem(lSystemString: string, stepSize: number = 5, angleStep: number = 25) {
this.ctx.clearRect(0, 0, this.canvas.width, this.canvas.height);
this.ctx.strokeStyle = 'green';
this.ctx.lineWidth = 1;
for (const command of lSystemString) {
switch (command) {
case 'F': // 앞으로 이동하며 선 그리기
this.forward(stepSize);
break;
case 'f': // 앞으로 이동 (선 그리지 않음)
this.move(stepSize);
break;
case '+': // 왼쪽으로 회전
this.rotate(-angleStep * Math.PI / 180);
break;
case '-': // 오른쪽으로 회전
this.rotate(angleStep * Math.PI / 180);
break;
case '[': // 현재 상태 저장
this.pushState();
break;
case ']': // 저장된 상태 복원
this.popState();
break;
}
}
}
private forward(distance: number) {
const newX = this.state.position.x + Math.cos(this.state.angle) * distance;
const newY = this.state.position.y + Math.sin(this.state.angle) * distance;
if (this.state.penDown) {
this.ctx.beginPath();
this.ctx.moveTo(this.state.position.x, this.state.position.y);
this.ctx.lineTo(newX, newY);
this.ctx.stroke();
}
this.state.position = { x: newX, y: newY };
}
private move(distance: number) {
this.state.position.x += Math.cos(this.state.angle) * distance;
this.state.position.y += Math.sin(this.state.angle) * distance;
}
private rotate(angle: number) {
this.state.angle += angle;
}
private pushState() {
this.stateStack.push({ ...this.state });
}
private popState() {
if (this.stateStack.length > 0) {
this.state = this.stateStack.pop()!;
}
}
}L-System 식물 생성 예시
// 고사리 패턴 생성
function createFernPattern(): string {
const lSystem = new LSystem(['F', '+', '-', '[', ']'], 'F');
// 고사리 생성 규칙
lSystem.addRule('F', 'F[+F]F[-F]F');
return lSystem.generate(4);
}
// 나무 패턴 생성
function createTreePattern(): string {
const lSystem = new LSystem(['F', '+', '-', '[', ']'], 'F');
// 나무 생성 규칙
lSystem.addRule('F', 'FF+[+F-F-F]-[-F+F+F]');
return lSystem.generate(3);
}
// 사용 예시
const canvas = document.getElementById('canvas') as HTMLCanvasElement;
const turtle = new TurtleGraphics(canvas);
const fernPattern = createFernPattern();
turtle.drawLSystem(fernPattern, 3, 25);알고리즘 비교와 선택 기준
성능 비교
각 알고리즘의 시간 복잡도와 메모리 사용량을 비교해보자:
| 알고리즘 | 시간 복잡도 | 메모리 복잡도 | 최적 사용 사례 |
|---|---|---|---|
| Perlin Noise | O(n) | O(1) | 자연스러운 텍스처, 지형 |
| Diamond-Square | O(n) | O(n) | 빠른 지형 생성 |
| L-System | O(k^n) | O(k^n) | 식물, 프랙탈 구조 |
사용 사례별 선택 기준
지형 생성:
- 자연스러운 지형: Perlin Noise
- 빠른 프로토타이핑: Diamond-Square
- 섬세한 제어: Perlin Noise + 후처리
식물 생성:
- 사실적인 식물: L-System
- 간단한 식생: Perlin Noise 기반 분포
텍스처 생성:
- 자연 텍스처: Perlin Noise
- 프랙탈 패턴: Diamond-Square 또는 L-System
실전 활용 사례
게임 개발에서의 활용
class WorldGenerator {
private perlinNoise: PerlinNoise;
private diamondSquare: DiamondSquare;
constructor(seed: number) {
this.perlinNoise = new PerlinNoise(seed);
this.diamondSquare = new DiamondSquare(513, 0.7);
}
generateWorld(width: number, height: number) {
// 기본 지형 생성 (Diamond-Square)
const baseHeight = this.diamondSquare.generate();
// 세부 노이즈 추가 (Perlin Noise)
const detailNoise = this.generateDetailNoise(width, height);
// 생물군계 분포 (Perlin Noise)
const biomeMap = this.generateBiomeMap(width, height);
// 식물 배치 (L-System)
const vegetation = this.generateVegetation(biomeMap);
return {
terrain: this.combineHeightMaps(baseHeight, detailNoise),
biomes: biomeMap,
vegetation: vegetation
};
}
private generateDetailNoise(width: number, height: number): number[][] {
const noise: number[][] = [];
for (let y = 0; y < height; y++) {
noise[y] = [];
for (let x = 0; x < width; x++) {
noise[y][x] = this.perlinNoise.noise(x * 0.05, y * 0.05);
}
}
return noise;
}
private generateBiomeMap(width: number, height: number): string[][] {
const biomes: string[][] = [];
for (let y = 0; y < height; y++) {
biomes[y] = [];
for (let x = 0; x < width; x++) {
const temperature = this.perlinNoise.noise(x * 0.01, y * 0.01);
const humidity = this.perlinNoise.noise(x * 0.01 + 1000, y * 0.01 + 1000);
biomes[y][x] = this.determineBiome(temperature, humidity);
}
}
return biomes;
}
private determineBiome(temperature: number, humidity: number): string {
if (temperature < -0.3) return 'tundra';
if (temperature > 0.3 && humidity > 0.3) return 'jungle';
if (temperature > 0.3 && humidity < -0.3) return 'desert';
if (humidity > 0.3) return 'forest';
return 'grassland';
}
private generateVegetation(biomeMap: string[][]): any[] {
const vegetation: any[] = [];
// 각 생물군계에 따른 식물 생성 로직
// L-System을 사용한 나무 생성 등
return vegetation;
}
private combineHeightMaps(base: number[][], detail: number[][]): number[][] {
const combined: number[][] = [];
for (let y = 0; y < base.length; y++) {
combined[y] = [];
for (let x = 0; x < base[0].length; x++) {
combined[y][x] = base[y][x] + detail[y][x] * 0.2;
}
}
return combined;
}
}최적화 기법
메모리 최적화:
class OptimizedGenerator {
// 청크 기반 생성으로 메모리 사용량 제한
generateChunk(chunkX: number, chunkY: number, chunkSize: number): number[][] {
const chunk: number[][] = [];
for (let y = 0; y < chunkSize; y++) {
chunk[y] = [];
for (let x = 0; x < chunkSize; x++) {
const worldX = chunkX * chunkSize + x;
const worldY = chunkY * chunkSize + y;
chunk[y][x] = this.generateHeightAt(worldX, worldY);
}
}
return chunk;
}
private generateHeightAt(x: number, y: number): number {
// 필요할 때만 계산하는 방식
return this.perlinNoise.noise(x * 0.01, y * 0.01);
}
}마무리
절차적 생성 알고리즘은 제한된 자원으로 무한한 가능성을 만들어내는 강력한 도구다. Perlin Noise는 자연스러운 텍스처와 지형 생성에, Diamond-Square는 빠른 프로토타이핑과 기본 지형 생성에, L-System은 복잡한 생물학적 구조 생성에 각각 최적화되어 있다.
실제 프로젝트에서는 단일 알고리즘보다는 여러 알고리즘을 조합하여 사용하는 것이 일반적이다. 기본 구조는 Diamond-Square로 빠르게 생성하고, Perlin Noise로 세부 사항을 추가하며, L-System으로 식물이나 건축물 같은 복잡한 구조를 배치하는 식으로 말이다.
각 알고리즘의 특성을 이해하고 프로젝트의 요구사항에 맞게 적절히 선택하여 사용한다면, 사용자에게 매번 새로운 경험을 제공하는 동적인 콘텐츠를 만들 수 있을 것이다.
참고
- Perlin Noise 원본 논문
- Diamond-Square 알고리즘 상세 설명
- L-System 기본 이론
- Procedural Generation 게임 개발 가이드
- Ken Perlin 공식 웹사이트