Wave Function Collapse: локальные ограничения и глобальная проходимость

Генерация по явным правилам

Wave Function Collapse полезен для размещения контента с чёткой локальной совместимостью: какие края тайлов сочетаются и какие перекрывающиеся паттерны сосуществуют. Он не заменяет определение целей уровня. Сначала отделите визуальную согласованность от требований вроде достижимого выхода или гарантированного ресурса.

Домены, энтропия и распространение

Исходная реализация хранит возможные паттерны, выбирает неразрешённое место с низкой энтропией, назначает паттерн и распространяет ограничения. Пустые множества возможностей обозначают противоречия. [1] Объяснения решения ограничений описывают backtracking как возврат к прошлому решению и проверку альтернатив. [2] Не каждая реализация WFC поддерживает возврат, а взвешенная энтропия учитывает веса вариантов, а не только их число.

Разобранный пример

Рассмотрим условный ряд из 3 клеток. Тайл RoadEW имеет дорожные соединения на востоке и западе; Grass не имеет их. Правило требует соединять дорогу с дорогой, а пустой край с пустым. Левая клетка закреплена как RoadEW, правая — Grass, средняя сначала допускает оба тайла.

Левый сосед заставляет середину стать RoadEW. Правый запрещает это. Домен середины пуст: фиксированные требования противоречат друг другу. Перезапуск с другим случайным seed не исправит именно эту фиксированную конфигурацию. Ослабьте требование, добавьте совместимый переходный тайл или сообщите о неудаче.

Теперь рассмотрим большую локально допустимую карту. Совпадающие дорожные края всё ещё способны образовывать несвязанные петли. Успешный коллапс поэтому не доказывает путь от входа до выхода. Нужны дополнительное ограничение, зарезервированная структура маршрута или отдельная проверка связности.

Процесс проектирования

Создайте небольшой каталог тайлов с явными ориентациями, метками краёв и весами. Проверьте каждое правило соседства в обоих нужных направлениях. Проверяйте границы отдельно от внутренних правил: краю мира может требоваться специальное замыкание. Добавляйте тайлы постепенно, чтобы связать противоречия с обозримым изменением.

Ограничьте число решений, работу распространения, возвраты и перезапуски. Для воспроизведения храните seed, версию каталога, фиксированные условия и место сбоя. При генерации во время игры определите, уступает ли незавершённая работа время, выдаёт запасной вариант или отклоняет запрос.

Ограничения и проверка

Веса направляют выбор, но не гарантируют точные итоговые доли тайлов. Локальная согласованность не доказывает темп, доступность, навигационную проходимость или баланс ресурсов. Проверяйте это на настоящем игровом представлении, а не только на сгенерированном изображении.

Измеряйте время генерации, частоту противоречий, число перезапусков и долю отказов на разнообразных seed. Называйте их измерениями проекта, когда они действительно собраны. Для больших миров планируйте согласование границ соседних регионов: успешные по отдельности фрагменты могут не соединиться в пригодное целое.

Источники

[1] Реализация WaveFunctionCollapse — Maxim Gumin и участники проекта.

[2] Объяснение Wave Function Collapse — Boris the Brave.