Процедурная генерация: коллапс волновой функции

1. Тайловая генерация и наивный генератор

Тайловая генерация — метод создания сцен или объектов комбинированием заранее подготовленных модульных элементов — тайлов (плиток). Подход автоматизирует сборку больших сцен, обеспечивая и разнообразие, и повторяемость: художник делает десяток модулей, генератор собирает из них сотни комнат.

Первая мысль — расставить тайлы случайно. Зная размер площадки, генерируем сетку клеток и в каждую ставим случайный тайл; чтобы пустоты встречались чаще, «пустой» тайл добавляется в список выбора несколько раз (взвешивание повторением). На C# такой генератор — десяток строк:

using UnityEngine;

public class RandomTileGenerator : MonoBehaviour
{
    [SerializeField] private GameObject[] tilePrefabs; // набор тайлов; нулевой — «пусто»
    [SerializeField] private int roomSize = 8;         // сторона сетки
    [SerializeField] private int whiteSpace = 3;       // сколько раз продублировать «пусто»
    [SerializeField] private float cellSize = 2f;

    void Start()
    {
        for (int x = 0; x < roomSize; x++)
        for (int y = 0; y < roomSize; y++)
        {
            // индекс 0 попадает в розыгрыш (1 + whiteSpace) раз — пустоты чаще
            int i = Random.Range(0, tilePrefabs.Length + whiteSpace);
            if (i >= tilePrefabs.Length) i = 0;

            Vector3 pos = new Vector3(
                (x - roomSize / 2f) * cellSize + cellSize / 2f,
                0,
                (y - roomSize / 2f) * cellSize + cellSize / 2f);

            Instantiate(tilePrefabs[i], pos, Quaternion.identity, transform);
        }
    }
}

Приём с сеткой и взвешенным случайным выбором стоит запомнить — он ещё пригодится. Но результат хаотичен: коридор обрывается в стену, дверь ведёт в никуда. Случайности не хватает правил сочетания — и здесь начинается WFC.

2. Алгоритм коллапса волновой функции

Задача WFC — заполнить клетки плитками так, чтобы изображения на плитках сочетались друг с другом. В терминах задач удовлетворения ограничений: каждая плитка — значение, каждая клетка — переменная, а правила размещения — ограничения.

Для каждой клетки создаётся булев массив — домен переменной: по одной записи на каждую плитку, все изначально true («в этой клетке ещё возможна любая плитка»). Дальше крутится основной цикл:

Распространение ограничений выполняется многократно: сузив домен одной клетки, мы могли сделать невозможными какие-то плитки у её соседей, те — у своих соседей, и так далее, пока волна изменений не затухнет. Автор алгоритма обнаружил, что при разумном выборе плиток и целесообразной рандомизации перебор с возвратом (откат при противоречии) нужен редко — его можно не реализовывать и в случае тупика просто начинать заново.

Пример: сетка 3×3 и четыре вида плиток; ограничение — цвета смежных сторон должны совпадать. В начале в каждой клетке возможна любая из четырёх плиток:

2.1. Минимальная энтропия

Какую клетку коллапсировать следующей? Если выбирать наугад по всей сетке, начнут заполняться независимые области — и при стыковке может оказаться, что соединить их нечем. Надёжнее брать клетку с наименьшим числом оставшихся вариантов в домене (но не меньше двух): такие клетки обычно соседствуют с уже заполненными, и если отложить их «на потом», доступных значений может не остаться вовсе.

Подход «наименьший домен» хорош, когда все плитки равновероятны. Если же плитки выбираются из взвешенного распределения, выбирают клетку с минимальной энтропией:

— суммирование по плиткам домена, где \(p_i\) — вероятность данной плитки. Смысл тот же: чем меньше неопределённость клетки, тем раньше её нужно решить.

3. Реализация на C# для Unity

Перенесём алгоритм в Unity. Тайл описывается префабом и четырьмя «разъёмами» — кодами сторон (север, восток, юг, запад): плитки стыкуются, если разъём одной стороны равен разъёму встречной стороны соседа. Для дорог достаточно двух кодов: 0 — «края нет», 1 — «дорога». Генератор хранит домены как булевы массивы, коллапсирует клетку с наименьшим доменом и распространяет ограничения очередью:

using System.Collections.Generic;
using UnityEngine;

public class WfcGenerator : MonoBehaviour
{
    [System.Serializable]
    public class TileDef
    {
        public GameObject prefab;
        public int n, e, s, w;      // коды разъёмов сторон
        public float weight = 1f;   // вес при случайном выборе

        public int Socket(int dir) => dir == 0 ? n : dir == 1 ? e : dir == 2 ? s : w;
    }

    [SerializeField] private TileDef[] tiles;
    [SerializeField] private int width = 10, height = 8;
    [SerializeField] private float cellSize = 2f;

    // смещения соседей и встречные направления: 0 север, 1 восток, 2 юг, 3 запад
    private static readonly Vector2Int[] Dirs =
        { new(0, 1), new(1, 0), new(0, -1), new(-1, 0) };
    private static readonly int[] Opposite = { 2, 3, 0, 1 };

    private bool[,][] domain;   // domain[x, y][t] — возможна ли плитка t в клетке

    void Start()
    {
        for (int attempt = 0; attempt < 20; attempt++)
        {
            if (TryGenerate()) { Build(); return; }
        }
        Debug.LogError("WFC: не удалось сгенерировать без противоречий");
    }

    private bool TryGenerate()
    {
        domain = new bool[width, height][];
        for (int x = 0; x < width; x++)
        for (int y = 0; y < height; y++)
        {
            domain[x, y] = new bool[tiles.Length];
            for (int t = 0; t < tiles.Length; t++) domain[x, y][t] = true;
        }

        while (true)
        {
            // клетка с минимальным доменом размера ≥ 2
            int bx = -1, by = -1, best = int.MaxValue;
            for (int x = 0; x < width; x++)
            for (int y = 0; y < height; y++)
            {
                int c = CountOptions(x, y);
                if (c == 0) return false;              // противоречие — начать заново
                if (c > 1 && c < best) { best = c; bx = x; by = y; }
            }
            if (bx < 0) return true;                    // все клетки решены

            Collapse(bx, by);
            if (!Propagate(bx, by)) return false;
        }
    }

    private int CountOptions(int x, int y)
    {
        int c = 0;
        foreach (bool b in domain[x, y]) if (b) c++;
        return c;
    }

    private void Collapse(int x, int y)
    {
        // взвешенный случайный выбор плитки из домена
        float total = 0f;
        for (int t = 0; t < tiles.Length; t++)
            if (domain[x, y][t]) total += tiles[t].weight;

        float r = Random.value * total;
        int chosen = -1;
        for (int t = 0; t < tiles.Length; t++)
        {
            if (!domain[x, y][t]) continue;
            r -= tiles[t].weight;
            if (r <= 0f) { chosen = t; break; }
            chosen = t;                              // страховка от округления
        }

        for (int t = 0; t < tiles.Length; t++)
            domain[x, y][t] = t == chosen;
    }

    private bool Propagate(int sx, int sy)
    {
        var queue = new Queue<Vector2Int>();
        queue.Enqueue(new Vector2Int(sx, sy));

        while (queue.Count > 0)
        {
            Vector2Int cell = queue.Dequeue();
            for (int dir = 0; dir < 4; dir++)
            {
                Vector2Int nb = cell + Dirs[dir];
                if (nb.x < 0 || nb.y < 0 || nb.x >= width || nb.y >= height) continue;

                // какие разъёмы клетка может показать соседу в направлении dir
                var sockets = new HashSet<int>();
                for (int t = 0; t < tiles.Length; t++)
                    if (domain[cell.x, cell.y][t]) sockets.Add(tiles[t].Socket(dir));

                // сужаем домен соседа: его встречная сторона должна совпасть
                bool changed = false;
                for (int t = 0; t < tiles.Length; t++)
                {
                    if (!domain[nb.x, nb.y][t]) continue;
                    if (!sockets.Contains(tiles[t].Socket(Opposite[dir])))
                    {
                        domain[nb.x, nb.y][t] = false;
                        changed = true;
                    }
                }

                if (changed)
                {
                    if (CountOptions(nb.x, nb.y) == 0) return false; // тупик
                    queue.Enqueue(nb);                               // волна идёт дальше
                }
            }
        }
        return true;
    }

    private void Build()
    {
        for (int x = 0; x < width; x++)
        for (int y = 0; y < height; y++)
        for (int t = 0; t < tiles.Length; t++)
        {
            if (!domain[x, y][t]) continue;
            Vector3 pos = new Vector3(x * cellSize, 0, y * cellSize);
            Instantiate(tiles[t].prefab, pos, Quaternion.identity, transform);
            break;
        }
    }
}

Что здесь важно. Домены — bool[width, height][], ровно как в описании алгоритма. Выбор клетки — минимальный домен (для равных весов это и есть минимальная энтропия). Коллапс — взвешенный случайный выбор. Распространение — очередь: изменённая клетка кладётся в очередь, и волна бежит, пока домены меняются; пустой домен означает противоречие, и Start просто пробует ещё раз — до 20 попыток. Сборка — знакомый по A08 Instantiate префабов; при желании её легко вынести в фабрику из A10.

4. Практические рекомендации

Рекомендации к набору тайлов для курсового проекта:

• Найти или создать собственный набор тайлов; хорошая цель — «красивое и солидное число»: 50–100 штук. Тайлы «проходов» могут отличаться формой двери (арка или обычная дверь), видом лестницы (прямая или винтовая).
• Продумывать в правилах сочетания «доступность» — возможность облёта сцены камерой.
• Помнить, что к каждому тайлу позже генерируются текстуры (стык с линией B: процедурные текстуры в Blender, конспект B06) — геометрия тайла должна это позволять.

Источник вдохновения — сообщество Backrooms: оно любит зацикленные бесконечные помещения, оформленные по правилам «лиминального» пространства, и среди его участников много программистов и дизайнеров, создающих процедурные пространства от простых до весьма сложных (пример — procedural backrooms, см. «Источники»). Разбор реального проекта на сто тайлов и историю оптимизации алгоритма также можно найти по ссылкам в «Источниках».

Контрольные вопросы

• Что такое тайловая генерация и в чём её преимущество?
  Метод создания сцен комбинированием заранее подготовленных модульных элементов — тайлов. Автоматизирует сборку больших сцен: художник делает ограниченный набор модулей, генератор собирает из них сколько угодно разнообразных уровней.
• Сопоставьте термины WFC с терминами задач удовлетворения ограничений.
  Клетка — переменная; плитка — значение переменной; правила размещения (сочетания сторон) — ограничения; домен клетки — булев массив «какие плитки здесь ещё возможны».
• Из каких трёх шагов состоит основной цикл WFC?
  Выбор клетки эвристикой минимальной энтропии (среди клеток с доменом ≥ 2); коллапс — случайный выбор плитки из домена и удаление остальных; распространение ограничений — многократное обновление доменов соседей волной, пока изменения не затухнут.
• Почему клетку для коллапса выбирают по минимальной энтропии, а не случайно?
  Случайный выбор порождает независимые заполненные области, которые потом может быть нечем соединить, — противоречия. Клетки с наименьшим доменом (обычно у фронта заполнения) нужно решать первыми: отложенные, они рискуют остаться без допустимых плиток вовсе.
• Что означает пустой домен клетки и как с этим бороться?
  Противоречие: ни одна плитка не удовлетворяет ограничениям. Строгое решение — перебор с возвратом, но автор WFC показал, что при разумном наборе плиток тупики редки, поэтому проще перезапустить генерацию заново (в реализации конспекта — до 20 попыток).
• Почему распространение ограничений делается очередью, а не одним проходом по соседям?
  Сужение домена соседа может делать невозможными плитки у его собственных соседей — изменения распространяются дальше одной клетки. Изменённые клетки кладутся в очередь, и волна бежит, пока домены перестают меняться.
• Как в реализации учитываются веса плиток?
  При коллапсе плитка выбирается взвешенным случайным розыгрышем: суммируются веса плиток домена, разыгрывается число от 0 до суммы, и выбор падает на плитку, на интервале которой оно оказалось. При выборе клетки веса учитываются формулой энтропии −Σ p·log p.

Источники

1. Коллапс волновой функции: алгоритм, вдохновлённый квантовой механикой // Хабр : [сайт]. — URL: https://habr.com/ru/companies/piter/articles/455004/ (дата обращения: 08.07.2026).
2. Алгоритм коллапса волновой функции // PVSM.RU : [сайт]. — URL: https://www.pvsm.ru/algoritmy/306987 (дата обращения: 08.07.2026).
3. Пример разработки процедурной генерации на 100 тайлов // PVSM.RU : [сайт]. — URL: https://www.pvsm.ru/razrabotka-igr/340622 (дата обращения: 08.07.2026).
4. Делаем аддон в Blender // Хабр : [сайт]. — URL: https://habr.com/ru/articles/787622/ (дата обращения: 08.07.2026).
5. Gumin, M. WaveFunctionCollapse : [репозиторий алгоритма] // GitHub : [сайт]. — URL: https://github.com/mxgmn/WaveFunctionCollapse (дата обращения: 08.07.2026).
6. Procedural backrooms : [видеопример] // YouTube : [сайт]. — URL: https://www.youtube.com/watch?v=8jzfw_buKzA (дата обращения: 08.07.2026).