Тайловая модель что это
Что такое тайловое текстурирование — общие принципы и использование Статьи редакции
Как создавать тайлы и зачем это нужно.
Этот обучающий материал посвящён тайловому текстурированию: как создаются и применяются тайлы и почему это одна из важных основ в геймдеве — акцент будет на применение в разработке игр.
Не стану детально описывать пайплайн в конкретных программах, а сосредоточимся на общих принципах работы и ответах на возможные вопросы.
В одном из своих обучающих материалов я уже упоминал метод тайлового текстурирования, но рассказал о нём поверхностно — тогда основная тема касалась оптимизации UV-развертки.
Tile — произносится как «тайл», переводится как «плитка», а означает повторение. Повторяющуюся текстуру используют для текстурирования больших поверхностей: грунта, стен, домов, модулей и иногда мелких объектов. Такой вид текстур позволяет добиться высокого качества и при этом уменьшить количество применяемых материалов в игровой сцене.
Бесшовные текстуры — это и есть тайлы, но иногда их так называют. Паттерны на краях текстуры продолжают друг друга, чтобы избавиться от швов и сделать повторяемость менее заметной.
Tile Atlas или атлас тайлов — несколько тайлов на одной текстуре. При использовании атласов приходится жертвовать числом полигонов, чтобы использовать оверлапинг — наложение UV-островов на один участок текстуры. Атласы создают ради того, чтобы снизить количество материалов, чаще всего используются в мобильных играх, где требования к оптимизации более высокие.
Tileset или тайл сет — подразумевается сет модулей, из которых делают уровни. Эти модули используют общие тайловые материалы или тримы, поэтому их можно назвать сетом одного тайла.
Оптимизация. Известно, что файлы игр состоят примерно на 60-80% из текстур, а возможно и на 95% — всё зависит от конкретного проекта. Однотипные, бесшовные текстуры часто используются повторно на различных моделях, тем самым позволяя экономить место на жёстком диске, снижать время загрузки и обращение к видеопамяти. Повторное использование материала в сцене вместо создания нового снижает количество Draw Calls — вызовов отрисовки.
Сокращение времени на разработку. Опытный левелдизайнер может создавать новые и уникальные локации, используя одни и те же модели и текстуры. Разумеется, это занимает меньше времени нежели создание каждой сцены с нуля.
Повторяемость ассетов. Если в игре часто использовать ассеты повторно, то через несколько часов геймплея визуально игра станет скучной. Этим особенно страдают игры с большим миром, например TESO, да и вообще вся серия «Свитков». После нескольких походов по пещерами можно увидеть все возможные тайлсеты, и новые локации не вызовут никаких впечатлений, так как они почти идентичны во всём, кроме проектировки уровня.
Зато большая часть Тамриеля (Мира вселенной The Elder Scrolls) умещается в 95 гигабайт, что по сравнению с новыми играми не так уж и много.
Сложный пайплайн для инди и новичков. При создании своего примера, я потратил больше дня на подбор скачанных текстур для одной очень простой модельки, при этом получилось так себе.
Основная трудность для меня была в том, что я не знал, что хочу визуализировать, не хватало предварительных артов или референсов, а если я и знал, что мне нужно, то нужных текстур не находил. Потратить ещё кучу времени на создание своих текстур исключительно для примера я не решился.
А теперь представьте те же сложности в масштабах игрового проекта или большого ассета. Для реализации качественных тайл сетов понадобится хоть какой-то опыт, время или деньги на покупку готовых.
Обработка фотографий в 2D редакторе — в Photoshop или в специализированных программах. Для создания полноценного PBR-материала не достаточно одной текстуры цвета — необходимы маски метала, шероховатости и карта рельефа (Metallic, Roughness, Normal Map). Всё это нужно либо рисовать вручную, либо генерировать из той же фотографии, что, конечно, даст результат, но не лучшего качества. По этой причине способ считается устаревшим.
Для генерации существуют отдельные программы — например бесплатный materialize или Bitmap2Material — который по сути является набором нод из Substance Designer. Ещё есть онлайн-сервис NormalMap-Online, он может создать Normal, AO, Sepcular из любого изображения. У всех этих генераторов похожий принцип, цвет используется как маска, карта нормалей получается вдавленной в тёмных местах и выдавленной на светлых, в некоторых случаях из этого можно получить приемлемое качество.
Моделирование и запекание. Художник создаёт геометрию на прямой плоскости при помощи скульптинга или моделирования. Геометрию окрашивают ID-материалами или через Vertex Paint. Далее это запекается на обычный плейн в текстуры: Normal, ID map, Curvature, Ambient Occlusion.
Остальное создаётся вручную. ID Map помогает отделять друг от друга элементы на плоской текстуре. Metallic, roughness и базовый цвет можно создать в Substance painter, в Blender через нодовый редактор, в Photoshop или даже внутри игрового движка, смешивая текстуры по ID-маске.
Hand Paint — создание текстур вручную, рисование в Photoshop или в других 2D-редакторах. Как правило, этот метод подходит для стилизованной графики, так как добиться реализма мазками кисти крайне сложно, если вообще возможно. Для создания стилизованной графики с PBR можно комбинировать с методом запекания.
Процедурные редакторы. Благодаря нодовым редакторам можно создать, а затем в любой момент отредактировать, что угодно, изменять не только цвета, но и каждый паттерн в отдельности, создавать множество вариаций одного материала.
Ноды — это что-то вроде визуального программирования. В каждой программе они реализованы по-разному, но суть везде похожая: первая нода создает простой паттерн или шум, вторая нода его редактирует, а третья — добавляет цвета. Конечно, при создании реалистичного материала тремя-четырьмя нодами не обойтись.
Лучшей нодовой программой для создания тайлов и не только, считается Substance Designer, так как она, её инструментарий и библиотека нодов были созданы для этой задачи.
«Охота на тайл» — тайлящаяся текстура за 5 минут на базе фотографии (цикл: Работа с текстурами и изображениями)
Вступление
Чтобы уравновесить кислотно-щелочной баланс после моей предыдущей, скорей всего неудачной, с точки зрения зрительских симпатий, публикации и чтобы принести ресурсу больше пользы, чем вреда – я публикую новый туториал. В отличие от всех предыдущих уроков он будет короче и будет напоминать по длине вот эту статью. Скажу даже более, он будет ей вторить, словно подпевая вполголоса. Надеюсь нам удастся спеться и вместе мы выдадим слаженный дует. Там речь шла о блендинге тайлов – здесь же речь пойдет о самих тайлах. О создании тайлящейся текстуры на базе любой фотографии. Это базовые знания, еще базовей чем это может быть только изучение интерфейса пакета Photoshop. В случае если мой тенор будет фальшивить — гоните его долой.
Итак, главный вопрос сегодняшней ночи – как сделать качественную тайл-текстуру за 5 минут? Хороший вопрос я думаю, и на него вполне можно потратить 5-10 минут вашего времени. Возможно после этого для ваших собственных прототипов вы будете использовать оригинальные тайлы, созданные вашими руками, не тратя времени на поиск художника или текстурщика, который смог бы вам помочь. Заманчиво?
Первым делом находим удовлетворяющую вас фотографию из тех, что не имеет копирайта (как правило на полях или по центру изображения). Внимательно следите за этим, потому что игровая индустрия богата курьезными ситуациями и эта далеко не последняя из могущих произойти с вами. Хотя. Что может быть веселее забыть в пред-релизной версии текстурной даты текстуру от игры Unreal Tournament? И такое случалось. Правда я не видел на лицах людей улыбок и не слышал их радостного смеха.
Приступим. 5 минут. Все по честному. Ваш процесс обучения займет немногим больше. Вы получите из фотографии слева — тайловую текстуру справа. Уже классически все это будет подано с соусом из юмора и маленькими мини-индустриальными-историями.
Я взял эту фотографию из реферата Ольги Васильевны Кузьминой. Не слишком большая и содержит все грядущие проблемы с которыми может столкнуться человек изготовляющий тайл-текстуры (или тайловые текстуры, или просто «тайлы»). Во-первых, она маленькая. Во-вторых – есть небо. В третьих, фактура не равномерна, что может привести к возникновению периодического рисунка при многократном повторе.
Нормализация текстуры (Texture Normalize)
И если с первым – мы смиримся, то второе требует некоего разрешения. Давайте приведем будущий тайл к удобоваримому виду. Хотя бы избавимся от неба, чтобы почва была более или менее равномерной. Это можно сделать двумя способами. Классическим выделением через рамку с помощью инструмента Rectangular Marquee Tool (M) или с помощью клавиши М. После того как вы выделили нужный объем, нажмите стандартную для большинства пакетов операцию копирования-вставки – Ctrl + C и Ctrl + V. Полученный лоскуток перетащите в нужное место (с помощью мыши) и повторите операцию, чтобы больше никогда в жизни этого тайла не видеть неба. Если что-то не заладилось и вы не доверяете вашим рукам – переключитесь в режим Move Tool (V) и перетащите объекты с помощью курсорных клавиш (стрелочек). Такой способ бывает важен при необходимости точного позиционирования элемента.
Примечание: Небо моего тайла на иллюстрации красное. И это не потому, что я сделал хитрое или применил «маску», а потому что я хотел явно выразить проблему. Повторив тоже что и я — вы получите такой же результат. Никаких хитростей.
Также операция клонирования может быть выполнена с зажатой клавишей Alt при включенном инструменте Move Tool (V), он используется для перемещения любых объектов (слои, группы). То есть вы выделяете нужный вам объем, зажимаете клавишу Alt и тащите выделенное куда вам нужно. Выделение может быть любым. Сделанным с помощью Magic Wand, Lasso Tool – словом так можно копировать все возможные выделения и их содержимое. Если при этом зажать Shift, то ваш объект-клон будет двигаться по прямой, либо налево, либо направо, либо вверх, либо вниз, не сбиваясь при этом с выбранного направления.
Первые швы (Patсh Tool)
— У нас проблема кэп. Появились Швы! Свистать мистера Патча на мостик!
Иными словами вызываем инструмент Patсh Tool (J) с той же панели инструментов (слева от рабочего полотна).
Важное примечание: По умолчанию этот инструмент может быть закрыт другими. В Фотошопе под одной иконкой может скрывать и три. Появятся они если нажать на иконку, что для махрового новичка (нас с вами) может быть не очевидно. Если вам лень тащить до них указатель мыши – пощелкайте на клавиатуре комбинацией Shift + J. Практически все важные операции, как и в стратегиях реального времени зашиты на short-cat’ы. Прошивок как в StarCraft вы здесь не увидите, но ускорить рабочий процесс на порядки – будет можно. Со временем это дойдет до автоматизма.
С помощь Patсh Tool (J) мы выделяем проблемную зону шва, для того чтобы потом ее перетащить на то место откуда будет снята та фактура которая не содержит дефектов и других артефактов. По мне сравнение с пластическим хирургом – гораздо интереснее. Если считать, что швы это опаленная кожа, ну… или морщины, то чистой, хорошей кожей будет фактура не содержащая проблем находящаяся по соседству. Ее-то мы и берем за сэмпл.
Итого… уже получилась неплохая текстурка. За то время пока я писал этот текст (см. выше) можно было бы протайлить десяток подобных текстур. Если не более. Однако нас сейчас не интересует скорость моего набора, а в большей степени интересует что делать с краями этой фотографии. Этого нашего тайла.
В давние времена…
…в общем я мог бы рассказать вам байки о том, что когда-то нужных инструментов не было и мы проходили через ад. А потом привыкнув проходить через ад я еще пару лет как макака это проделывал, игнорируя удобный инструмент Offset.
Корчуем швы со сдвигом (Filter Offset)
Этот чудесный фильтр позволяет избавить вас от рутинных операций. Нужно открыть проблемную текстуру, желательно после всех операций пост-обработки, выбрать пункт Filter/Other/Offset и задать в пикселях необходимое смещение. Если ваша текстура, как в нашем случае 512х512 то наиболее удобный Offset составит 256 пикселей. Таким образом мы не ставим крест на этой текстуре, но убираем его с помощью уже знакомого инструмента Path Tool (J).
Далее снова возвращаем значения Offset обратно. И… текстура готова. Если попробовать выложить ее словно плитку станет заметно, что возникает некий периодический рисунок в определенных местах. Ваша задача – быстро его устранить.
На следующем рисунке я указал зону этих неприятностей белесым цветом. Именно на эти зоны мы и поставим заплатки. Заодно сделаем это не с помощью Patсh Tool (J), а с помощью Lasso Tool (L). Почему так, а не наоборот я расскажу в советах, в конце урока.
Ловим багги лассо (Lasso Tool)
Берем лассо Lasso Tool (L) и выделяем землю, которая ляжет поверх прессованной земли, которая чертовски нам мешает. Потом через Ctrl + C и Ctrl + V переносим их в нужные места. Задача примерно на глаз избавиться от явных теней и явных элементов текстуры которые присутствуют в едином числе и при повторении будут заметными. Да, безусловно, это сделает текстуру менее уникальной. Но нам тут надо целый овраг покрыть, и никуда не годиться повторяющееся по всему периметру какое-либо черное пятно.
Теперь наша текстура выглядит так.
А при выкладывании ее в виде плитки – выглядит много лучше. В наше время используются такие вещи как бленды, декали, детальные текстуры и бог знает что еще. Но до сих пор основной фактурой является фото-текстура. И до тех пор, пока это будет происходить – мы будем работать с растровыми изображениями.
Что можно добавить? Вроде как ничего, но… постойте. Вам не надоело выкладывать ваши текстуры плиткой в файле большего разрешения? Если надоело прошу проследовать в предпоследний раздел нашего скоростного урока.
Делаем паттерн (Define Patern)
Выделите текстуру с помощью Rectangular Marquee Tool (M) или с помощью искрометной комбинации Ctrl + A. Затем перейдите во вкладку Edit. Вторая вкладка после пункта File. Выберете там Define Pattern. Напишите для паттерна любое удобное вам имя.
Теперь, при создании любого файла любого размера вы можете воспользоваться операцией Fill из того же подпункта Edit, либо нажав комбинацию клавиш Shift + F5. Выбрав там свой паттерн вы сможете залить им любую поверхность избавив тем самым себя от рутинных операций проверки файлов.
Эпилог
Сложно поверить, но каждое из этих микро-знаний приходило постепенно. К примеру вы узнали это за 5 минут. Я узнал за 5 месяцев потому, что копался самостоятельно, и потому что когда-то давно никто не любил делиться. Чтобы с вами случилось, если бы вы узнали, что весь процесс обучения этой простейшей операции пришелся на отрезок в 5 лет? Я не так далек от истины. Потому что каждым элементом этого маленького уравнения я занимался в разные годы. И фильтр Offset в нем стал последним неизвестным.
Бонус для терпеливых
Для тех кто смог выдержать пять минут чтения и еще две на эпилог. Существует очень важный фильтр. Который может превратить ваше изображение в как бы рисованное. Это секрет, и никому его не открывайте. Т.к. грамотное использование этого фильтра позволяет добиться удивительных результатов. Но тут как и в любом кулинарном процессе нужна очень точная рецептура. Маслин должно быть не более десяти, кружочков лука диаметром семи сантиметров можно положить побольше, не забывая про толщину нарезки… чувствуете? Ну… наверное ничего кроме слез. Если отвлечься от лука — пропорции, проценты, и очередность наложения изображений — очень важна. Дойти до этого сразу не может никто. Все это путь экспериментов. Для многих зачастую многолетних. Причем Level Up’ы будут случаться и по прошествии десятка лет. Я серьезно. Не только у такого лодыря как я.
Так вот. Наша цель — фильтр Filter/Atistic/Cutout. Посмотрите что он сделает с текстурой.
Теперь еще один важный пункт. Всему важна своя мера. Просто как фильтр — он не нужен никому. Но если изменить уровень процентности слоя с ним лежащий поверх нашей оригинальной текстуры на 37%, то будет видна и та текстура что снизу (сохраняя нам фото-текстуру), и та текстура что сверху (нивелируя черные фрагменты фото-текстуры). Вместе они дополняют друг друга. Текстура уже не такая фото, и как бы с легкой претензией на артовость. Чувствуете как я говорю о них? Как о вкусе вина.
Признаться я никогда не понимал вин, и не понимал все богатство их вкуса. Увы, в этом деле я не образован. Но меня всегда трогали фильмы о виноделах влюбленных в свое дело. То как они описывали напиток. Его вкус. То как он впитывает эмоции. Не думайте что текстура чем-то отличается. Во все что мы делаем — мы вкладываем толику своих эмоций. Что мы получили с нашими процентами?
А теперь добавим нашу текстуру еще раз сверху. В стиле на авось. С уровнем процента прозрачности 37% но изменив наложение текстуры на Overlay. Методы наложения это свойства слоя с которыми текстура (или изображение на нем, или маска) накладывается на тот слой, что лежит под ним. Можно было бы сделать это десятком других способов — но я предпочитаю этот. Быстрая цвето-коррекция и усиление контраста. Одним лишь продублированным слоем.
Вы знаете. Скорее всего вам трудно будет в это поверить, и возможно вы сочтете меня сумасшедшим, но я верю в две вещи. То что какая-то толика нашей души переходит в душевно сделанный объект. И в то что существует магия цифр. Эти значения для себя я подбирал давным давно. Кое-какие прохвосты врачи усмотрели у меня… как это бишь называется? Да, ограниченный дальтонизм. У нас, мужиков, это часто бывает. И так уж получилось что я вижу мир чуть иначе. Мне удалось подобрать такие цифры которые позволяют мне рисовать в привычном для меня контрасте и даже в привычной гамме. А затем я подкручиваю изображение. Частенько это не спасает от ядерных цветов, но решает ряд других проблем.
Маленький GIF пример. Это незначительные на первый взгляд изменения. Пустяковые. Но в комплексе они могут дать удивительный результат. Все в этом мире состоит из мелочей.
При дополнительной получасовой работе с текстурой из нее может получиться конфетка. Но я не располагаю этими 20-30 минутами. Нам нужно было быстро.
Ну и конечно если вдуматься это хохма. Дальтоник работает коцепт-артистом в индустрии, главным художником и бог знает кем еще. Правда и врачи сказали — ограниченный. Так что… все относительно. Пусть те кто смеются — смеются и дальше. Главное что и вы теперь знаете что есть некие числа и некая магия. И возможно я не одинок в своих мыслях.
Теперь я думаю любой программист, да и вообще кто угодно сможет быстро изготовить себе тестовый материал не прибегая при этом к помощи художника… кто бы меня так научил программировать.
Наблюдения
Идеальный растровый тайл. Идеального растрового тайла на базе фотографий в природе не существует. Он как «неуловимый Джо», помните о таком? Не пытайтесь его отыскать. Идеальный тайл — это цветовая заливка, фрактальный тайл, программно генерируемый тайл, и вряд ли они устроят ваше начальство.
Всегда будут какие-то огрехи, и что-то будет не нравится. Подобных вещей можно избегнуть в случае pixel-art’а или полностью рисованных текстур. Там периодические элементы будут сведены к минимуму за счет мастерства и опыта художника. Частенько «идеальный» тайл будучи идеальным совсем не радует глаз, т.к. многие элементы превращаются в некую «шахматную доску» от которой либо рябит в глазах, либо она не привлекает.
Время работы. Да, я сделал его за пять минут. Но в случае других, более сложных тайлов время может сильно растягиваться. Иные текстуры можно обрабатывать часами. Так и скажите вашему начальству, которое прочитав этот микро-урок, предложит вам «протайлить» 12 текстур за час. Это не конвейер, даже в этой рутинной работе есть творческое звено. Необходимо минимальное чувство вкуса. Ну и сноровка конечно же.
Забавный факт. Помимо того что тайл — это плиточная или «кафельная» структура состоящая из повторяющихся фрагментов изображения, тайлом же называют периодичный рисунок возникающий при многократном повторении тайла. «Мне не нравится явный тайл» — фраза говорящая о возникновении хорошо читающегося периодического рисунка, а не о качестве проработки тайла. Говоря кратко и понятно — «то чертово пятно видно и повторяется повсюду, когда ты его, наконец, уберешь?».
Алгоритм генерации тайловых карт Model Synthesis
Я много писал об алгоритме коллапса волновой функции (Wave Function Collapse). Этот алгоритм, разработанный Максимом Гуминым в 2016 году, генерирует тайловые карты и пиксельные текстуры на основании удовлетворения ограничениям с дополнительной рандомизацией [перевод на Хабре]. Но знали ли вы, что большинство основных идей для него взято из статьи, написанной больше десятка лет назад? Сегодня мы рассмотрим диссертацию 2007 года на степень PhD Пола Меррела Model Synthesis и некоторые из разработанных им расширений алгоритма, в частности, Modifying in Blocks.
Model Synthesis
Идея Model Synthesis очень похожа на WFC, по которому я написал целый туториал. Но в этой статье мы опишем идею с нуля.
Model Synthesis начинает с передачи примера тайловой карты, которая используется алгоритмом для того, чтобы учиться, какие тайлы могут располагаться друг рядом с другом при построении модели. Затем для выходного результата инициализируется пустая сетка ячеек. Каждая ячейка имеет список «потенциальных» тайлов, которые могут её заполнить.
Изначально допустим любой тайл. Основной цикл выбирает ячейку и выбирает для неё заданный тайл, помечая все остальные как недопустимые. Затем он распространяет последствия этого выбора при помощи алгоритма AC4, то есть помечает тайл как недопустимый для текущей ячейки, если все его валидные смежные ячейки уже недопустимы. После распространения цикл сбрасывается и мы выбираем другую ячейку, для которой нужно выбрать тайл.
Рано или поздно у каждой ячейки останется только один возможный тайл, после чего генерируется карта. В случае сложных наборов тайлов могут возникать противоречия (ячейки, в которых невозможен ни один из тайлов), и для их решения требуется более сложный подход под названием Modifying in Blocks, описанный ниже.
Эта процедура очень похожа на простой солвер ограничений, за исключением способа выбора ячеек и тайлов. Model Synthesis описывает то, что, по моему мнению, является фундаментальной особенностью подобной генерации: любой солвер на основании ограничений может быть при помощи случайного выбора преобразован в генератор на основе ограничений. Похоже, такой подход впервые был использован именно в этой статье — предыдущие решениях задачи синтеза текстур были по своей природе более статистическими.
Иллюстрация из статьи, при помощи добавления внешних ограничений демонстрирующая, что Model Synthesis по своей природе является солвером ограничений
Разница между Model Synthesis и Wave Function Collapse
Типичный пример MS
Типичный пример WFC
Пол Меррелл написал статью о конкретных различиях между ModelSynthesis и WFC. Также мне нравится заметка @expad.
Почему про Model Synthesis забыли?
По моему опыту, добавленные в WFC особенности приятны, но не уникальны. Мы по-прежнем можем получать очень хорошие результаты при помощи Model Synthesis, а их базовые концепции одинаковы. Так почему же эта идея прозябала десять лет, прежде чем Максим не увидел её потенциал и не создал репозиторий?
В Model Synthesis используются 3D-тайлы, которые довольно сложно проектировать, и код на C++, который сложно заставить работать. В WFC появился большой набор примеров, и все они были простыми изображениями. Благодаря переходу на 2D-изображения использование и поведение проекта мгновенно становится намного понятнее, и этому он обязан анимациям, демонстрирующим множество возможных тайлов, обновляемое в процессе анимации. Когда я пишу туториалы, именно по этой причине я сначала знакомлю с идеями в 2D и добавляю анимации.
Или же причина может быть более скучной. Веб-сайт Model Synthesis был недоступен в течение нескольких лет, а Wave Function Collapse — гораздо более интересное название, напоминающее о квантовой физике.
Modifying in Blocks
Синтез на основе ограничений, будь то Model Synthesis или Wave Function Collapse, страдает от одного сложного аспекта: мы можем прийти к противоречиям — ситуациям, когда решение невозможно и никак нельзя продвинуться дальше. Подобные трудности являются неотъемлемой частью солверов ограничений, так как пространство задачи в целом является NP-полным.
Чтобы проиллюстрировать эту проблему, я воспользовался одним из примеров Пола Меррелла — Escheresque (с его разрешения). Escheresque — это 3D-набор тайлов, намеренно сделанный сложным; многие тайлы имеют довольно далеко распространяющиеся связи друг с другом, а пустое пространство имеет низкий вес, что вынуждает к максимальной заполненности сцены. Поэтому противоречия возникают достаточно часто.
Типичная сцена, сгенерированная на основе сэмпла Escheresque
Для устранения противоречий WFC использует чрезвычайно простой подход. Если противоречие возникает, он просто перезапускает процесс сначала. Если противоречия редки, решение будет найдено после нескольких перезапусков. К сожалению, такой подход не масштабируется — если нужно генерировать результаты всё большего размера, вероятности противоречий растут, пока не станет совершенно невозможно получить успешный результат, сколько бы раз вы ни перезапускали алгоритм.
Вот стандартный WFC с сэмплом Escheresque. Как видите, противоречия достаточно часты и WFC постоянно выполняет перезапуск. Шансы заполнения всего объёма 30x30x10 крайне малы.
Альтернативный подход, который я использую в Tessera, стандартный для многих солверов ограничений — это поиск с возвратом. Вместо того, чтобы при возникновении противоречия начинать с нуля, поиск с возвратом откатывается к последнему хорошему состоянию и записывает дополнительную информацию, чтобы мы не пробовали одно действие дважды. Поиск с возвратом решает проблему противоречий, но заменяет её возможностью захождения алгоритма в тупик.
Захождение в тупик происходит, когда частичное решение неразрешимо, но алгоритм не знает, как вернуться из него и вместо этого многократно исследует вариации этого частичного решения. Для большинства наборов тайлов такие кроличьи норы встречаются реже, чем явные противоречия, поэтому можно получить более впечатляющие результаты, но в конечном итоге такой подход всё равно не масштабируется: при необходимости достаточно объёмного результата он зайдёт в тупик и застрянет.
После включения поиска с возвратом для сэмпла Escheresque результаты становятся лучше, но рано или поздно он находит какую-нибудь слишком сложную область и застревает, пытаясь её исправить.
Поэтому вместо этого Меррелл использовал другой подход под названием Modifying In Blocks (также называемый «модификацией по частям»). Когда алгоритму нужно сгенерировать большую площадь, он решает её не как одну большую задачу, а разбивает её на несколько задач поменьше. Область результата разбивается на несколько пересекающихся блоков. После чего происходит солвинг отдельных блоков. Если достигнуто противоречие, перезапуск требуется только для одного блока, а не всего решения. Таким образом, это компромисс между полными перезапусками и поиском с возвратом. Мы надеемся, что перезапуски устранят противоречия, а блоки достаточно велики, чтобы избежать кроличьих нор, поэтому мы можем генерировать чрезвычайно большие результаты без увеличения общего количества неудач.
Запустив этот алгоритм с сэмплом Escheresque, мы увидим, что он успешно генерирует всю область, однако он потребовал тщательной настройки и обработки ошибок, которая не видна в анимации.
Подробности
Очевидно, что если мы просто будем оценивать каждый блок по отдельности, то результат не будет целостным. Весь смысл ограничений соседних ячеек в том, чтобы тайлы соединялись друг с другом. Но как оказывается, выбор способа оценки блоков очень широк.
Очевидным решением было бы разбиение всего пространства на граничащие друг с другом блоки, чтобы каждая ячейка принадлежала только одному блоку. Затем мы генерируем по одному блоку за раз, начав с одного угла и используя уже сгенерированные соседние блоки в качестве входных ограничений для общих границ текущего блока. Во многих случаях такой подход сработает.
Блоки без пересечений с простым набором тайлов из травы и дорожек
Однако в генерировании WFC мешает то, что солвер ограничений рассматривает в качестве релевантных только тайлы внутри области генерации. Это значит, что для некоторых наборов тайлов он может генерировать результаты, которые невозможно расширить без создания противоречия. Чтобы избежать этого, Пол Меррелл использует немного иную схему.
При генерации каждого блока он ограничивает все границы блока. Некоторые из этих ограничений берутся из ранее сгенерированных блоков, но для других сторон блока, которые пока открыты, он фиксирует границу на гарантированно хорошем наборе тайлов. В сэмпле Escheresque (см. видео выше) используется поверхность из плоского основания, над которым нет ничего, кроме воздуха, а в наборе тайлов с травой и дорожками используется сплошной зелёный фон (см. анимацию ниже).
Зафиксировав все границы, мы гарантируем, что каждый блок более автономен и его проще расширять. Блоки выстроены так, что накладываются друг на друга, поэтому все эти фиксированные границы постепенно перезаписываются, но они сильно повышают вероятность успеха, поскольку мы уже знаем хотя бы одну структуру тайлов, которая подходит. Если возникнет слишком много противоречий/перезапусков, всегда можно просто сдаться и откатиться к гарантированно хорошим тайлам.
Блоки намеренно наложены друг на друга и мы начинаем с «гарантированно хорошего» сплошного зелёного фона. После оценки каждого блока у нас получается полностью непротиворечивый набор тайлов.
Оценка
Я поэкспериментировал с сэмплом Escheresque. Как уже говорилось, это очень сложный для правильной генерации набор тайлов. Я выяснил, что он очень чувствителен к порядку генерации и предпочитает определённые линейные сканы для min-энтропии. Ни WFC с перезапусками, ни мой собственный код поиска с возвратом не имел бы ни малейшего шанса масштабирования до результата объёмом 30x30x10. Алгоритм Modifying by Blocks смог добиться гораздо больших объёмов, однако ему всё равно требуются достаточно щедные настройки перезапуска блоков и обработка ошибок.
Производительность тоже не особо велика, так как из-за наложения блоков приходится делать много избыточной работы. Но алгоритм масштабируется немного лучше — наивный WFC может столкнуться с проблемами больших результатов, поскольку для генерации следующей ячейки ему нужно многократно сканировать для минимальной энтропии, а эту проблему мы избегаем благодаря линейному сканированию.
В целом, этот инструмент показался мне интересным. Большое количество параметров настройи и необходимость предварительного указания гарантированно хорошей схемы тайлов ограничивает обобщённость методики. Тем не менее, я нашёл интересные способы применения Modifying in Blocks, о которых я подробно расскажу в следующей статье.