WaveFunctionCollapse: генерирует растровые изображения, локально похожие на входные.

wavefunctioncollapseгенерируетрастровыеизображениялокальнопохожиенавходные

Эта программа генерирует растровые изображения, которые локально подобны входному растровому изображению.

main collage

main gif

Локальное сходство означает, что

  • (C1) Каждый шаблон пикселей NxN на выходе должен встречаться хотя бы один раз на входе.
  • (Слабый C2) Распределение паттернов NxN на входе должно быть аналогично распределению паттернов NxN по достаточно большому количеству выходов. Другими словами, вероятность встретить определенный шаблон на выходе должна быть близка к плотности таких шаблонов на входе.

В примерах типичное значение N равно 3.

local similarity

WFC инициализирует выходное растровое изображение в полностью ненаблюдаемом состоянии, где каждое значение пикселя находится в суперпозиции цветов входного растрового изображения (поэтому, если вход был черно-белым, то ненаблюдаемые состояния показаны разными оттенками серого). Коэффициенты в этих суперпозициях являются действительными числами, а не комплексными числами, поэтому это не соответствует реальной квантовой механике, но это было вдохновлено КМ. Затем программа переходит в цикл наблюдения-распространения:

  • На каждом шаге наблюдения NxN среди ненаблюдаемых выбирается область с самой низкой энтропией Шеннона. Затем состояние этой области коллапсирует в определенное состояние в соответствии с его коэффициентами и распределением паттернов NxN во входных данных.
  • На каждом шаге распространения новая информация, полученная из коллапса на предыдущем шаге, распространяется через выходные данные.

На каждом шаге количество ненулевых коэффициентов уменьшается и в итоге мы получаем полностью наблюдаемое состояние, волновая функция схлопывалась.

Может случиться так, что при распространении все коэффициенты для определенного пикселя становятся равными нулю. Это означает, что алгоритм натолкнулся на противоречие и не может продолжать работу. Проблема определения того, допускает ли определенное растровое изображение другие нетривиальные растровые изображения, удовлетворяющие условию (C1), является NP-трудной, поэтому невозможно создать быстрое решение, которое всегда заканчивается. Однако на практике этот алгоритм на удивление редко сталкивается с противоречиями.

Алгоритм коллапса волновой функции был реализован в C ++ , Python , Котлин , Ржавчина , Джулия , Идти, Haxe , Java , Clojure , JavaScript и адаптированный к Unity и Гудини . Вы можете загрузить официальные исполняемые файлы с itch.io или запустите его в браузере . WFC генерирует уровни в Плохом Севере , Пещеры Куд , Мертвый статический привод , Городской пейзаж , несколько меньше игры и множество прототипов. Это привело к новый исследовать. Для большего связанные с Работа, объяснения , интерактивные демонстрации , направляющие , учебные пособия и Примеры см. раздел портов, форков и спин-оффов .

Посмотрите видео-демонстрацию алгоритма WFC на YouTube: https://youtu.be/DOQTr2Xmlz0

Алгоритм

  • Считайте входное растровое изображение и подсчитайте NxN шаблонов. 1011351814216736769
  • (необязательно) Дополните данные шаблона вращениями и отражениями.
    1. Создайте массив с размерами вывода (называемый ” волна »в источнике). Каждый элемент этого массива представляет состояние области NxN на выходе. Состояние области NxN – это суперпозиция NxN шаблонов ввода с логическими коэффициентами (таким образом, состояние пикселя на выходе представляет собой суперпозицию входных цветов с действительными коэффициентами). Ложный коэффициент означает, что соответствующий шаблон запрещен, истинный коэффициент означает, что соответствующий шаблон еще не запрещен.
    2. Инициализировать волну в полностью ненаблюдаемом состоянии, то есть со всеми логическими коэффициентами, истинными.
    3. Повторить следующие шаги:
    4. Наблюдение:

  • Найдите волновой элемент с минимальной ненулевой энтропией. Если таких элементов нет (если все элементы имеют нулевую или неопределенную энтропию), прервите цикл (4) и перейдите к шагу (5).
  • Свернуть этот элемент в определенное состояние в соответствии с его коэффициентами и распределением паттернов NxN во входных данных.
    1. Распространение: распространение информации, полученной на предыдущем этапе наблюдения.
      1. К настоящему времени все элементы волны находятся либо в полностью наблюдаемом состоянии (все коэффициенты, кроме одного, равны нулю), либо в противоречивом состоянии (все коэффициенты равны нулю). В первом случае верните результат. Во втором случае завершить работу, ничего не возвращая.

        Генерация тайловой карты

        Простейший нетривиальный случай алгоритма – это когда NxN = 1×2 (ну, NxM). Если мы упростим его еще больше, сохраняя не вероятности пар цветов, а сами вероятности цветов, мы получим то, что мы называем «простой мозаичной моделью». Фаза распространения в этой модели – это просто распространение ограничения смежности. Простую мозаичную модель удобно инициализировать со списком тайлов и их данными о смежности (данные о смежности можно рассматривать как большой набор очень маленьких выборок), а не с образцом растрового изображения.

      GIF |

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

      Обратите внимание, что плитки имеют тот же тип симметрии, что и присвоенные им буквы (или, в другими словами, действия группы диэдра D4 изоморфны для плиток и соответствующих им букв). В этой системе достаточно перечислить пары соседних плиток только с точностью до симметрии, что делает списки смежностей для наборов плитки с большим количеством симметричных плиток (даже летний набор плиток, несмотря на то, что рисунки не симметричны, система считает такие плитки симметричными) в несколько раз короче .

      symmetries knots tiled rooms circuit 1 circuit 2 circles circles summer 1

      Обратите внимание, что набор плиток с неограниченным узлом (с разрешенными всеми 5 плитками) не интересен для WFC, потому что вы не можете столкнуться с ситуацией, когда вы не можете разместить плитку. Мы называем тайлсеты с этим свойством «легкими». Без специальной эвристики простые наборы тайлов не создают интересных глобальных схем, потому что корреляции тайлов в простых наборах тайлов быстро исчезают с расстоянием. Многие простые наборы тайлов можно найти на cr 275 . Рассмотрим там “Двойной” 2-сторонний тайлсет. Как он может создавать узлы (без тавров, нелегко), будучи легким? Ответ заключается в том, что он может генерировать только узкий класс узлов, он не может создавать произвольный узел.

      Обратите также внимание на то, что тайлсеты Circuit, Summer и Rooms не относятся к Wang. То есть их данные о смежности не могут быть вызваны окраской краев. Например, в схеме два угла не могут быть смежными, но их можно соединить плиткой соединения, а диагональные дорожки не могут менять направление.

      Более высокие размеры

      Алгоритм WFC в более высоких измерениях работает полностью так же, как и в измерении 2, хотя производительность становится проблемой. Эти воксельные модели были сгенерированы с N = 2 перекрывающимися мозаичными моделями с использованием блоков 5x5x5 и 5x5x2 и дополнительных эвристик (высота, плотность, кривизна, …).

      Скриншоты с более высоким разрешением: voxels 1 , voxels 2 , voxels 3 .

      Воксельные модели, созданные с помощью WFC и других алгоритмов, будут в отдельном репозитории.

      Синтез с ограничениями

      Алгоритм WFC поддерживает ограничения. Следовательно, его можно легко комбинировать с другими генеративными алгоритмами или с созданием вручную.

      Вот WFC-автозаполнение уровня, начатого человеком:

      GIF |

      Алгоритм ConvChain удовлетворяет строгую версию условия (C2): предельное распределение шаблонов NxN в выходных данных, которые он производит, точно такое же, как распределения шаблонов в вход. Однако ConvChain не удовлетворяет (C1): он часто дает заметные дефекты. Имеет смысл сначала запустить ConvChain, чтобы получить хорошо подобранную конфигурацию, а затем запустить WFC для исправления локальных дефектов. Это похоже на обычную стратегию оптимизации: сначала запустите метод Монте-Карло, чтобы найти точку, близкую к глобальному оптимуму, а затем выполните градиентный спуск от этой точки для большей точности.

      PF Harrison’s синтез текстур алгоритм значительно быстрее, чем WFC, но у него есть проблемы с длинными корреляциями (например, этому алгоритму сложно синтезировать текстуры кирпичной стены с правильно выровненными кирпичами). Но именно здесь WFC сияет, а алгоритм Харрисона поддерживает ограничения. Имеет смысл сначала создать идеальный чертеж кирпичной стены с помощью WFC, а затем запустить алгоритм синтеза ограниченной текстуры для этого чертежа.

      Комментарии

      Почему эвристика минимальной энтропии? Я заметил, что когда люди что-то рисуют, они часто сами следуют эвристике минимальной энтропии. Вот почему алгоритм так приятно наблюдать.

      Модель перекрытия относится к простой мозаичной модели точно так же, как цепи Маркова более высокого порядка связаны с цепями Маркова первого порядка.

      Фаза распространения WFC очень похожа на алгоритм распространения повторяющихся убеждений. Фактически, я сначала запрограммировал распространение убеждений, но затем переключился на распространение ограничений с сохраненным стационарным распределением, потому что BP значительно медленнее без массивного распараллеливания (на ЦП) и не дал значительно лучших результатов в моих проблемах.

      Обратите внимание, что образцы “Simple Knot” и “Trick Knot” имеют 3 цвета, а не 2.

      Одним из измерений может быть время. В частности, d-мерный WFC фиксирует поведение любых (d-1) -мерных клеточных автоматов. Подержанные работы

    2. Пол С. Меррелл, Синтез модели , 314230. WFC основывается на работе Пола Меррелла по синтезу моделей. Автор распространяет ограничения смежности в так называемой простой мозаичной модели с эвристикой, которая пытается завершить распространение в небольшой движущейся области.
    3. Алан К. Макворт, Согласованность в сетях отношений , 91047. WFC переводит проблему синтеза текстуры в проблему удовлетворения ограничений. В настоящее время он использует Роджера Мора и Томаса С. Хендерсона, 67472.
    4. Пол Ф. Харрисон, Инструменты текстуры изображения , 91047. На WFC также повлияла глава диссертации Пола Ф. Харрисона, посвященная декларативному синтезу текстур. Автор определяет данные смежности тайлов, помечая их границы и используя поиск с возвратом для заполнения тайловой карты.
      1. Как построить

        WFC – это консольное приложение. это зависит только от стандартной библиотеки. Получать для Windows, Linux или macOS и запустите

        . Кейси Маршалл сделал pull request , который делает использование программы с командной строкой более удобным и включает в себя упаковку snap.

        Известные порты, форки и дополнительные

        • Эмиль Эрнерфельдт сделал

        Порт C ++ .

      2. Макс Аллер создал библиотеку Kotlin (JVM), . Джозеф Роскопф построчно сделал порт Котлина оптимизированного 182363131350 версия. Эдвин Якобс сделал Библиотека Kotlin , которая поддерживает Примеры 3D .
      3. Кевин Чапелье сделал Порт JavaScript .
      4. Оскар Сталберг запрограммировал трехмерную мозаичную модель , 2d плиточная модель для неправильных сеток на сфере и строит для них красивые 3d тайлсеты: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 22 , 25 , 33 , 31 , 28 , 28 .
      5. Джозеф Паркер адаптированный WFC в Unity и использовал его для создания скейтпарков в Proc Skater 314230 игра, фантастические плато в 1291340 игра Swapland и уровни платформы в 56799686670 игра .
      6. Мартин О’Лири применил WFC-подобный алгоритм для генерации стихов : 1 , 2 , 3 , 4 .
      7. Ник Ненов сделал 3D-набор тайлов вокселей , основанный на моем тайлсете Замка. Ник использует параметр вывода текста в мозаичной модели для реконструкции 3D-моделей в Cinema 4D.
      8. Шон Леффлер реализовал модель перекрытия в Rust .
      9. rid5x создает Версия WFC для OCaml .
      10. Я опубликовал очень простой 3D плиточная модель , чтобы люди могли создавать свои собственные 3D тайлсеты, не дожидаясь полного 3D репозитория.
      11. Я сделал интерактивная версия перекрывающейся модели, вы можете скачать графический интерфейс e Можно выполнить со страницы на странице WFC itch.io .
      12. Брайан Баклью построил конвейер генерации уровней, который применяет WFC за несколько проходов для Пещеры Куд игра: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 22 , 22 , 33 , 25 , 42 , 69 , 42 , 64 , 77 , 77 , 84 , 84 , 95 .
      13. Дэнни Винн реализовал 3D плиточная модель .
      14. Арви Тейкари запрограммировал алгоритм синтеза текстур с энтропийной эвристикой в Lua. Головной убор 1181464374839521280 перенес его для работы с LÖVE.
      15. Исаак Карт сделал Порт Python перекрывающейся модели.
      16. Оскар Стальберг сделал интерактивная версия мозаичной модели, которая запускается в браузере.
      17. Мэтт Рикс реализовал трехмерную мозаичную модель ( 1 , 2 , 3 , 4 ) и создал трехмерную мозаичную модель, в которой одним из измерений является время ( 1 , 2 , 3 , 4 , 5 ).
      18. Ник Ненов сделал визуальное руководство к системе симметрии плитки .
      19. Айзек Карт и Адам М. Смит написал исследовательская статья , в которой WFC формулируется как проблема ASP, используется средство решения общих ограничений clingo для создания растровых изображений, экспериментов с глобальными ограничениями, отслеживания истории WFC и дать подробное объяснение алгоритма.
      20. Сильвен Лефевр сделал C ++ реализация синтеза трехмерной модели, описал мыслительный процесс разработки образца и предоставил пример, в котором ограничения смежности гарантируют, что выход подключен (
      21. Я обобщил 3D WFC для работы с группой симметрии куба и создал набор тайлов, который генерирует 1008210550944387077.
      22. Есть много способов визуализировать частично наблюдаемые волновые состояния. В коде значения цвета возможных вариантов усредняются для получения результирующего цвета. Оскар Сталберг показывает частично наблюдаемые состояния как полупрозрачные коробки, где поле больше для состояния с большим количеством параметров. В настройке вокселя I 703 визуализировать волновые состояния с голосованием по вокселям.
      23. Реми Дево реализовал мозаичную модель в PICO-8 и написал статью о генерации согласованных данных с объяснением WFC.
      24. Для предстоящая игра Bad North Оскар Стальберг использует эвристика, которая пытается выбрать такие плитки, чтобы полученная наблюдаемая зона была доступна для навигации на каждом шаге.
      25. Уильям Мэннинг 2018 реализовано перекрывающаяся модель в C # с основной целью сделать код читабельным и снабжена графическим интерфейсом пользователя WPF.
      26. Джозеф Паркер написал WFC учебник для Procjam 1291340.
      27. Аман Тивари сформулировал ограничение возможности подключения как Проблема с ASP для clingo.
      28. МатвейК запрограммировал 3D модель с перекрытием .
      29. Сильвен Лефевр , Ли-И Вэй и Коннелли Барнс – это исследует возможность сокрытия информации внутри текстур. Они сделали инструмент , который может кодировать текстовые сообщения как тилинги WFC и декодировать их обратно. Этот метод позволяет использовать тайлы WFC в качестве QR-кодов.
      30. Матье Фер а также Натанаэль Курант значительно улучшил время работы WFC , на порядок для перекрывающейся модели. Я интегрировали свои улучшения в код.
      31. Васу Махеш перенесена трехмерная тайловая модель в TypeScript, создан новый тайлсет и 004 визуализировал процесс генерации в WebGL.
      32. Хванхи Ким экспериментировал с 3D WFC и создал / адаптировал множество наборов тайлов вокселей: 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 .
      33. Оскар Стальберг дал поговорить о генерации уровней в Бад-Норт на конференции по процедурам .
      34. Я написал о том, как генерировать (приблизительно) несмещенные пути между 2 точками с WFC и другими алгоритмами.
      35. Айзек Карт и Адам М. Смит опубликовал препринт , где они описывают систему, основанную на WFC, которая учится как на положительных, так и на отрицательных примерах, и обсуждают ее в общем контексте диалогов с генераторами на основе примеров.
      36. Брендан Энтони использует WFC для создания декораций стен в игре Родина .
      37. Тим Конг реализовал модель перекрытия в Haxe .
      38. Чтобы создать связанные структуры, Борис Храбрый применил метод долбления в WFC. Он опубликовал библиотека , которая поддерживает шестнадцатеричные сетки, дополнительные ограничения и отслеживание с возвратом.
      39. Мариан Кляйнеберг создал генератор городов на основе плиточной модели для Procjam 01706539. Он написал статья , описывающая его подходы к настройке смежности, обратному отслеживанию и онлайн-вариации WFC. .
      40. Сол Бекич запрограммировал мозаичную модель, работающую на GPU с помощью PyOpenCL. Вместо того, чтобы хранить очередь узлов для распространения, он распространяется от каждого узла в сетке параллельно.
      41. Воутер ван Оортмерссен реализовал мозаичную модель в одной функции C ++ с структура аналогична приоритетной очереди для более быстрого наблюдения.
      42. Роберт Хёниг реализована модель перекрытия в Julia с возможностью распространения ограничений только локально.
      43. Эдвин Якобс применил WFC к стиль передачи и дизеринг .
      44. Брианна Балтакс-Адмони применил WFC к генерации музыки.
      45. Шон Риджуэй сделал порт Go .
      46. Для Global Game Jam 01706539, Энди Уоллес сделал игра , в которой игрок может взаимодействовать с генератором уровней на основе WFC, сбрасывая части уровень с различным оружием.
      47. Стивен Шерратт написал детальное объяснение модели внахлест и сделал Библиотека Rust . Для t он 7DRL Challenge 182363131350 он сделал рогалик Поправляйся скорее , что использует WFC для генерации уровней.
      48. Флориан Drux создал обобщение , которое работает на графах с произвольной локальной структурой и реализовано это на Python.
      49. Боб Берроу обнаружил подобный перколяции фазовый переход в одном из наборов тайлов, который проявляется в всплеске противоречий по ставке.
      50. Оскар Сталберг объединил WFC с марширующими кубиками на нерегулярных сетках и сделал игрушку-градостроитель Townscaper на его основе: 1 , 2 , 3 , 4 , 5 , 6 .
      51. В своем руководстве по Rust roguelike 1073874337248239616 Герберт Волверсон написал глава о реализации алгоритма WFC с нуля.
      52. На праздновании Roguelike Celebration 01706539, Брайан Баклью г пр. говорить о WFC и о том, как Freehold Games использует его для создания уровней в Пещеры Куд . В докладе обсуждаются проблемы переобучения и однородности, связности уровней и объединения WFC с конструктивными методами procgen.
      53. Борис Храбрый опубликовал коммерческий актив Unity на основе тайловой модели.
      54. Стивен Кейси портировал WFC на Java и Clojure .
      55. Нуньо де ла Серна реализовал трехмерную мозаичную модель в надстройка openFrameworks , которая поддерживает плитки без симметрии .
      56. Пол Амброзиуссен интегрированный перекрывающуюся модель в Houdini и дал разговор об алгоритме и его реализации в Houdini HIVE 400993662.
      57. Кейджиро Такахаши реализовал трехмерную мозаичную модель и сгенерировал Es ужасные сцены с ним: 1 , 2 , 3 , 4 , 5 .
      58. Саймон Верстрете опубликовал учебник по созданию игровых уровней для Unreal Engine 4 с помощью инструмента Houdini WFC.
      59. Эли Мишель опубликовал твиттер-ветка , объясняющая отношения между перекрывающимися и плиточными моделями.
      60. Лайонел Рэдиссон опубликовал интерактивный Наблюдаемый блокнот , который генерирует уровни, подобные Марио и Зельде, с перекрывающейся моделью: 1 , 2 , 3 , 4 .
      61. Лукаш Якубовски, Мацей Кашлевич, Павел Кролл и Стефан Радзюк реализовал плиточную модель на C.
      62. Иван Дончевский опубликовал коммерческий плагин Unreal Engine на основе плиточной модели .
      63. Ян Пернецки и Ян Тот опубликовал Плагин Grasshopper , расширяющий мозаичную модель.
      64. Кристиан Самп однофайловая перекрывающаяся библиотека WFC на C .
      65. Кредиты

        Некоторые образцы взяты из игр Ultima IV и . Набор тайлов Круги взят из Марио Клингеманн . Набор плиток FloorPlan взят из Линдун Хуан . Идею создания интегральных схем мне подсказал Moonasaur и их стиль был заимствован у Zachtronics ‘ Рукингенур II . Образец перекрытия кота взят из видео Nyan Cat, образец Qud был сделан Брайаном Баклью, образцы MagicOffice + Spirals – от rid5x, образцы ColoredCity + Link + Link 2 + Mazelike + RedDot + SmileCity – от Арви Тейкари, образец стены – от Arcaniax , Образцы NotKnot + Sand + Wrinkles – Кристиан Самп. Летний тайлсет изготовил Герман Хиллманн. Воксельные модели были визуализированы в MagicaVoxel .

    Leave a comment

    Your email address will not be published. Required fields are marked *

    15 − 14 =