[Перевод] Алгоритм генерации тайловых карт Model Synthesis | DevsDay.ru

IT-блоги [Перевод] Алгоритм генерации тайловых карт Model Synthesis

habr.com 10 ноября 2021 г. PatientZero


image

Я много писал об алгоритме коллапса волновой функции (Wave Function Collapse). Этот алгоритм, разработанный Максимом Гуминым в 2016 году, генерирует тайловые карты и пиксельные текстуры на основании удовлетворения ограничениям с дополнительной рандомизацией [перевод на Хабре]. Но знали ли вы, что большинство основных идей для него взято из статьи, написанной больше десятка лет назад? Сегодня мы рассмотрим диссертацию 2007 года на степень PhD Пола Меррела Model Synthesis и некоторые из разработанных им расширений алгоритма, в частности, Modifying in Blocks.

Model Synthesis


Идея Model Synthesis очень похожа на WFC, по которому я написал целый туториал. Но в этой статье мы опишем идею с нуля.

Model Synthesis начинает с передачи примера тайловой карты, которая используется алгоритмом для того, чтобы учиться, какие тайлы могут располагаться друг рядом с другом при построении модели. Затем для выходного результата инициализируется пустая сетка ячеек. Каждая ячейка имеет список «потенциальных» тайлов, которые могут её заполнить.

Изначально допустим любой тайл. Основной цикл выбирает ячейку и выбирает для неё заданный тайл, помечая все остальные как недопустимые. Затем он распространяет последствия этого выбора при помощи алгоритма AC4, то есть помечает тайл как недопустимый для текущей ячейки, если все его валидные смежные ячейки уже недопустимы. После распространения цикл сбрасывается и мы выбираем другую ячейку, для которой нужно выбрать тайл.
Читать дальше →

Источник: habr.com

Наш сайт является информационным посредником. Сообщить о нарушении авторских прав.

Разработка игр Алгоритмы Дизайн игр процедурная генерация wave function collapse model synthesis коллапс волновой функции тайлы процедурная генерация карт