절차적 지형 생성의 정수: 파동 함수 붕괴(WFC) 알고리즘 분석

서론: 왜 WFC인가?

로그라이크나 오픈월드 게임에서 '절차적 생성(Procedural Generation)'은 필수적인 기술입니다. 과거에는 Perlin Noise나 Cellular Automata가 주로 쓰였지만, 이들은 타일 간의 정교한 연결 규칙을 표현하는 데 한계가 있었습니다. 2016년 Maxim Gumin이 발표한 'Wave Function Collapse(WFC)' 알고리즘은 양자 역학의 개념을 차용하여, 주어진 인접 규칙(Constraints)을 완벽하게 준수하면서도 유기적이고 복잡한 패턴을 생성해냅니다. 이는 단순한 무작위 생성을 넘어, '말이 되는' 구조를 만드는 데 탁월합니다.

알고리즘의 핵심 원리: 중첩과 붕괴

WFC의 작동 방식은 크게 세 단계로 나뉩니다.

1. 초기화 (Superposition): 모든 그리드 칸은 가능한 모든 타일 후보를 가지고 있는 '중첩 상태'입니다.
2. 선택과 붕괴 (Observation & Collapse): 엔트로피(가능한 후보 수)가 가장 낮은 칸을 하나 선택하여, 하나의 타일로 확정(붕괴)시킵니다.
3. 전파 (Propagation): 확정된 칸의 정보가 주변 칸에 영향을 미쳐, 인접할 수 없는 타일 후보들을 제거합니다. 이 과정이 연쇄적으로 일어납니다.

이 과정을 모든 칸이 결정될 때까지 반복하며, 만약 규칙 위반으로 인해 후보가 하나도 남지 않는 '모순(Contradiction)'이 발생하면 해당 지점에서 다시 생성하거나 백트래킹을 수행합니다.

구현을 위한 데이터 구조 설계

C#에서 WFC를 구현하기 위해 가장 먼저 필요한 것은 타일 간의 인접 정보를 담는 'Adjacency Rule'입니다.

public class Tile {
    public string Name;
    // 상, 하, 좌, 우 순서로 인접 가능한 타일의 ID들
    public List[] AdjacencyRules = new List[4];
}

public class Cell {
    public List PossibleTileIds; // 현재 칸의 후보들
    public bool IsCollapsed => PossibleTileIds.Count == 1;
    
    // 샤넌 엔트로피 계산 (간소화 버전)
    public float GetEntropy() {
        if (IsCollapsed) return float.MaxValue;
        return PossibleTileIds.Count + UnityEngine.Random.Range(0f, 0.1f); // Noise for tie-breaking
    }
}

핵심 로직: 전파(Propagation) 알고리즘

WFC에서 가장 복잡하고 중요한 부분은 한 칸의 붕괴가 주변으로 퍼져나가는 과정입니다. 이는 보통 스택이나 큐를 이용한 BFS 방식으로 구현됩니다.

private void Propagate(int startX, int startY) {
    Stack stack = new Stack();
    stack.Push(new Vector2Int(startX, startY));

    while (stack.Count > 0) {
        Vector2Int current = stack.Pop();

        foreach (Vector2Int dir in directions) { // 상하좌우 탐색
            Vector2Int neighbor = current + dir;
            if (!IsValidPos(neighbor)) continue;

            Cell neighborCell = grid[neighbor.x, neighbor.y];
            if (neighborCell.IsCollapsed) continue;

            // 현재 칸의 남은 후보들로부터 이웃 칸이 가질 수 있는 유효한 타일 목록 계산
            HashSet validNeighbors = new HashSet();
            foreach (int currentTileId in grid[current.x, current.y].PossibleTileIds) {
                var rules = allTiles[currentTileId].AdjacencyRules[GetDirIndex(dir)];
                foreach (int r in rules) validNeighbors.Add(r);
            }

            // 이웃 칸의 후보 중 유효하지 않은 것들을 제거
            int removedCount = neighborCell.PossibleTileIds.RemoveAll(id => !validNeighbors.Contains(id));
            
            if (removedCount > 0) {
                if (neighborCell.PossibleTileIds.Count == 0) {
                    throw new Exception("Contradiction reached!");
                }
                stack.Push(neighbor); // 변화가 생겼으므로 이웃의 이웃도 검사
            }
        }
    }
}

실무에서의 응용과 최적화

단순한 타일 맵을 넘어 3D 구조물 생성이나 레벨 디자인에 WFC를 적용할 때 고려해야 할 점들입니다.

• 회전과 대칭 (Symmetry): 타일 하나를 정의할 때 회전된 버전들도 자동으로 생성하여 규칙에 포함시키면 더 다양한 결과물을 얻을 수 있습니다.
• 가중치 (Weights): 특정 타일(예: 평지)이 더 자주 나오게 하려면 후보 선택 단계에서 확률 가중치를 적용합니다.
• 백트래킹 (Backtracking): 모순이 발생했을 때 전체를 새로 만드는 대신, 최근 몇 단계만 되돌리는 기능을 구현하면 대규모 맵 생성 속도가 비약적으로 향상됩니다.

심화 분석: 기술적 도전과 해결책

기술적 구현의 디테일

저는 이번 개발 과정에서 모든 기능을 모듈화하여 독립적으로 테스트할 수 있는 환경을 구축했습니다. 이는 추후 기능 확장이나 버그 수정 시 발생할 수 있는 사이드 이펙트를 최소화하는 데 큰 역할을 했습니다. 또한 문서화를 병행하여 기술 부채가 쌓이는 것을 방지했습니다.

프로젝트의 성공은 기술력뿐만 아니라 팀 내 원활한 커뮤니케이션과 체계적인 파이프라인 구축에 달려 있습니다. 자동화된 빌드 시스템과 코드 리뷰 프로세스는 개발 속도를 비약적으로 높여줍니다.

성능 벤치마크 및 최적화 지표

협업 툴 도입 이후 작업 히스토리 추적 시간이 50% 단축되었으며, 휴먼 에러로 인한 빌드 실패율이 눈에 띄게 줄어들었습니다.

실무 적용 시 주의사항

완벽한 설계를 추구하기보다 빠르게 프로토타입을 만들고 피드백을 수용하는 애자일(Agile)한 자세가 1인 개발자에게는 특히 중요합니다.

결론: 무한한 가능성의 도구

WFC는 구현 난도가 조금 높지만, 한 번 완성하면 던전 생성, 도시 구획 설계, 심지어 음악 작곡에 이르기까지 정해진 규칙이 있는 모든 창작 영역에서 강력한 힘을 발휘합니다. 유니티의 타일맵 시스템과 연동하거나 언리얼의 PCG(Procedural Content Generation) 프레임워크와 결합하여 여러분만의 독창적인 세계를 자동으로 생성해 보시기 바랍니다.

LYSC Studio

1인 게임 개발과 웹 기술에 관심이 많은 개발자입니다. 경험을 통해 배운 것을 공유하고, 함께 성장하는 것을 즐깁니다.