Unity에서 Wave Function Collapse로 타일 맵 절차적 자동 생성하기

핵심 요약

Wave Function Collapse(WFC)는 각 셀에 가능한 타일 후보 집합을 두고 가장 불확실성이 낮은 셀을 하나 확정한 뒤 인접 셀의 후보를 제거하는 제약 만족 알고리즘이다. 타일의 상하좌우 연결 규칙을 비트마스크로 정의하면 Unity에서 도로, 방, 벽, 지형 타일 맵을 일관되게 자동 생성할 수 있다. 핵심은 무작위 선택 자체가 아니라 Collapse → Propagate → Contradiction 처리 루프다.

Wave Function Collapse 타일 맵 생성기란 무엇인가?

WFC는 이미지 압축 알고리즘에서 출발했지만 게임에서는 보통 타일 배치 제약을 만족하는 맵 생성기로 사용한다. 예를 들어 도로 타일의 오른쪽이 열려 있다면 오른쪽 셀에는 왼쪽 연결부가 열린 도로 타일만 놓일 수 있다.

항목	일반 랜덤 타일 배치	WFC 기반 배치
타일 선택	각 셀을 독립적으로 선택	인접 규칙을 고려해 선택
연결성	끊긴 도로와 벽 틈이 생기기 쉬움	규칙 범위 안에서 연결 보장
결과 다양성	높지만 품질 편차가 큼	규칙을 지키며 다양성 확보
실패 처리	별도 검증 필요	전파 중 모순을 감지

각 셀의 상태는 가능한 타일 집합인 도메인(domain)이다. 타일 종류가 4개라면 초기 도메인은 1111이고 한 타일을 확정하면 해당 셀의 도메인은 예를 들어 0100이 된다.

후보 수가 n개인 셀의 단순 엔트로피는 다음처럼 둘 수 있다.

H = \log(n)

가중치를 적용하는 WFC에서는 다음 식을 사용한다.

H = \log(W) - \frac{\sum_i w_i \log(w_i)}{W}, \quad W = \sum_i w_i

다만 첫 구현에서는 후보 수가 가장 적은 셀을 선택하는 방식만으로도 충분하다.

WFC에서 타일 후보가 확정되고 인접 셀로 제약이 전파되는 과정

Unity WFC 타일 맵은 어떻게 구현할까?

1. 타일과 인접 규칙을 데이터로 정의한다

타일마다 방향별로 허용되는 이웃 타일 집합을 정의한다. allowed[tile, direction]은 해당 타일의 특정 방향에 놓일 수 있는 모든 타일을 비트로 표현한 값이다.

예를 들어 타일 ID가 0~3이고 0번 타일의 오른쪽에 1번과 3번만 올 수 있다면 오른쪽 마스크는 0b1010이다. 규칙은 코드에 하드코딩하기보다 ScriptableObject에 저장하면 디자이너가 타일을 추가하기 쉽다.

2. 가장 적은 후보를 가진 셀을 확정한다

후보가 2개 이상인 셀 중 후보 수가 가장 작은 셀을 고른다. 같은 후보 수라면 난수를 사용해 결과 반복을 줄인다. 확정할 타일은 단순 균등 선택보다 타일별 가중치에 따라 선택하는 편이 자연스럽다.

3. 인접 셀에 제약을 전파한다

확정 또는 후보 감소가 발생한 셀을 큐에 넣고 상하좌우 이웃의 도메인을 다시 계산한다. 이웃 도메인이 비어 있으면 모순이다. 작은 맵은 전체 생성을 다시 시작하는 방식이 가장 단순하고 큰 맵이나 실패 비용이 큰 맵에서는 변경 이력을 저장한 백트래킹이 필요하다.

C# 비트마스크 기반 WFC 핵심 코드

아래 코드는 타일 수가 64개 이하인 경우 ulong 도메인을 사용하는 최소 구현이다. allowed[tile, direction]과 weights는 타일 데이터에서 채워 넣는 값이다.

using System;
using System.Collections.Generic;

public sealed class WfcSolver
{
    private readonly int width;
    private readonly int height;
    private readonly int tileCount;
    private readonly ulong[,] allowed;
    private readonly float[] weights;
    private readonly ulong[] domains;
    private readonly Random random = new();

    private static readonly (int x, int y)[] Offsets =
    {
        (0, -1), (1, 0), (0, 1), (-1, 0)
    };

    public WfcSolver(int width, int height, int tileCount, ulong[,] allowed, float[] weights)
    {
        if (tileCount < 1 || tileCount > 64)
            throw new ArgumentOutOfRangeException(nameof(tileCount));

        this.width = width;
        this.height = height;
        this.tileCount = tileCount;
        this.allowed = allowed;
        this.weights = weights;
        domains = new ulong[width * height];
    }

    public int[] Generate()
    {
        ulong allTiles = tileCount == 64 ? ulong.MaxValue : (1UL << tileCount) - 1;
        Array.Fill(domains, allTiles);

        while (TryGetLowestEntropyCell(out int cell))
        {
            domains[cell] = PickWeightedTile(domains[cell]);
            if (!Propagate(cell))
                return null;
        }

        var result = new int[domains.Length];
        for (int i = 0; i < result.Length; i++)
            result[i] = FirstSetBit(domains[i]);
        return result;
    }

    private bool Propagate(int startCell)
    {
        var queue = new Queue<int>();
        queue.Enqueue(startCell);

        while (queue.Count > 0)
        {
            int cell = queue.Dequeue();
            int x = cell % width;
            int y = cell / width;

            for (int direction = 0; direction < 4; direction++)
            {
                int nx = x + Offsets[direction].x;
                int ny = y + Offsets[direction].y;
                if (nx < 0 || nx >= width || ny < 0 || ny >= height)
                    continue;

                int neighbor = ny * width + nx;
                ulong nextDomain = Filter(domains[cell], domains[neighbor], direction);
                if (nextDomain == domains[neighbor])
                    continue;

                if (nextDomain == 0)
                    return false;

                domains[neighbor] = nextDomain;
                queue.Enqueue(neighbor);
            }
        }

        return true;
    }

    private ulong Filter(ulong source, ulong target, int direction)
    {
        ulong supported = 0;
        for (int tile = 0; tile < tileCount; tile++)
        {
            ulong bit = 1UL << tile;
            if ((source & bit) != 0)
                supported |= allowed[tile, direction];
        }
        return target & supported;
    }

    private bool TryGetLowestEntropyCell(out int selected)
    {
        selected = -1;
        int lowest = int.MaxValue;

        for (int i = 0; i < domains.Length; i++)
        {
            int count = CountBits(domains[i]);
            if (count > 1 && count < lowest)
            {
                lowest = count;
                selected = i;
            }
        }
        return selected >= 0;
    }

    private ulong PickWeightedTile(ulong domain)
    {
        float total = 0;
        for (int i = 0; i < tileCount; i++)
            if ((domain & (1UL << i)) != 0) total += weights[i];

        float point = (float)(random.NextDouble() * total);
        for (int i = 0; i < tileCount; i++)
        {
            if ((domain & (1UL << i)) == 0) continue;
            point -= weights[i];
            if (point <= 0) return 1UL << i;
        }
        return domain & (~domain + 1);
    }

    private static int CountBits(ulong value)
    {
        int count = 0;
        while (value != 0) { value &= value - 1; count++; }
        return count;
    }

    private static int FirstSetBit(ulong value)
    {
        int index = 0;
        while ((value & 1) == 0) { value >>= 1; index++; }
        return index;
    }
}

Generate()가 null을 반환하면 해당 시도는 모순으로 실패한 것이다. 호출부에서 시드 또는 난수를 바꿔 3~10회 재시도하면 소규모 맵 생성기에는 충분한 경우가 많다.

WFC 알고리즘에서 모순은 왜 발생하는가?

모순은 어떤 셀의 도메인이 0이 되었을 때 발생한다. 대체로 다음 셋 중 하나다.

타일 규칙이 비대칭이다. A의 오른쪽에 B를 허용했는데 B의 왼쪽에 A를 허용하지 않은 경우다.
경계 조건이 빠졌다. 맵 외곽에 놓일 수 없는 연결 타일이 초기 후보에 포함된 경우다.
너무 좁은 공간에 서로 양립할 수 없는 제약을 강제했다. 시작 방과 출구 위치를 고정한 경우가 대표적이다.

규칙을 만들 때는 방향 반대편 규칙이 항상 대칭인지 검증하는 에디터 도구를 추가하는 것이 효과적이다. 예를 들어 Right 규칙은 이웃 타일의 Left 규칙과 호환되어야 한다.

Unity 성능 최적화는 어디부터 해야 할까?

맵이 커질수록 전체 셀을 매 반복 탐색하는 비용과 전파 횟수가 늘어난다. 먼저 아래 순서로 최적화한다.

우선순위	방법	효과
1	도메인을 `ulong` 비트마스크로 저장	할당과 집합 연산 감소
2	변경된 셀만 큐에 넣어 전파	불필요한 재검사 감소
3	생성은 로딩 화면 또는 비동기 작업에서 수행	프레임 끊김 완화
4	후보 수 우선순위 큐 사용	대형 맵의 셀 탐색 비용 감소

Unity 타일 렌더링은 생성 알고리즘과 분리한다. 생성 완료 후 Tilemap.SetTilesBlock()으로 결과를 한 번에 반영하면 셀마다 SetTile()을 호출하는 비용을 줄일 수 있다. 실시간 생성이 필요하면 맵을 청크로 나누고 청크 경계 타일을 고정 조건으로 전달한다.

자주 묻는 질문 (FAQ)

WFC는 던전 생성에만 적합한가?

아니다. 도로망, 실내 배치, 오토타일 지형, 장식물 배치에도 쓸 수 있다. 단, 반드시 연결되어야 하는 시작점과 목표점이 있다면 WFC 결과 뒤에 경로 검증을 추가해야 한다.

타일 종류가 64개를 넘으면 어떻게 해야 하나?

ulong 하나로는 부족하다. BitArray 또는 여러 개의 ulong 배열로 도메인을 확장할 수 있지만 먼저 회전·반전 타일을 별도 타입으로 둘 필요가 있는지 점검하는 편이 낫다.

백트래킹과 재시도 중 무엇을 선택해야 하나?

작은 맵과 오프라인 생성은 재시도가 구현 대비 효율적이다. 플레이 중 생성하거나 실패가 허용되지 않는 큰 맵은 선택 이력과 변경 도메인을 저장하는 백트래킹이 적합하다.

정리

Unity WFC 타일 맵 생성기의 품질은 복잡한 랜덤 함수보다 타일 인접 규칙의 정확성에 달려 있다. 먼저 비트마스크 도메인, 최소 후보 셀 선택, 큐 기반 전파, 재시도만 구현하고 실제 프로파일링에서 병목이 확인될 때 우선순위 큐나 백트래킹을 추가하자.