![image](https://webcf.waybackmachine.org/web/20211110080256im_/https://habrastorage.org/getpro/habr/post_images/733/fc9/8a1/733fc98a11984a6ed00e3c42971a595a.jpg)
Я много писал об алгоритме коллапса волновой функции (Wave Function Collapse). Этот алгоритм, разработанный Максимом Гуминым в 2016 году, генерирует тайловые карты и пиксельные текстуры на основании удовлетворения ограничениям с дополнительной рандомизацией [перевод на Хабре]. Но знали ли вы, что большинство основных идей для него взято из статьи, написанной больше десятка лет назад? Сегодня мы рассмотрим диссертацию 2007 года на степень PhD Пола Меррела Model Synthesis и некоторые из разработанных им расширений алгоритма, в частности, Modifying in Blocks.
Model Synthesis
Идея Model Synthesis очень похожа на WFC, по которому я написал целый туториал. Но в этой статье мы опишем идею с нуля.
Model Synthesis начинает с передачи примера тайловой карты, которая используется алгоритмом для того, чтобы учиться, какие тайлы могут располагаться друг рядом с другом при построении модели. Затем для выходного результата инициализируется пустая сетка ячеек. Каждая ячейка имеет список «потенциальных» тайлов, которые могут её заполнить.
Изначально допустим любой тайл. Основной цикл выбирает ячейку и выбирает для неё заданный тайл, помечая все остальные как недопустимые. Затем он распространяет последствия этого выбора при помощи алгоритма AC4, то есть помечает тайл как недопустимый для текущей ячейки, если все его валидные смежные ячейки уже недопустимы. После распространения цикл сбрасывается и мы выбираем другую ячейку, для которой нужно выбрать тайл.