- PVSM.RU - https://www.pvsm.ru -
Алгоритм Wave Function Collapse генерирует битовые изображения, локально подобные входному битовому изображению.
Локальное подобие означает, что
В примерах стандартным значением N является 3.
Алгоритм WaveFunctionCollapse (WFC) инициализирует выходное битовое изображение как полностью ненаблюдаемое состояние, в котором значение каждого пикселя является суперпозицией цветов входного битового изображения (поэтому если входное изображение чёрно-белое, то ненаблюдаемые состояния отображаются как различные оттенки серого). Коэффициентами этих суперпозиций являются вещественные, а не мнимые числа, поэтому в алгоритме не используется настоящая квантовая механика, скорее он был ею вдохновлён. Затем программа переходит в цикл наблюдения-распространения:
На каждом этапе общая энтропия уменьшается, и в конце концов мы получаем полностью наблюдаемое состояние, коллапс волновой функции завершается.
Может случиться так, что в процессе распространения все коэффициенты для определённого пикселя становятся равными нулю. Это означает, что алгоритм пришёл к противоречию и не может выполняться дальше. Задача определения того, обеспечивает ли заданное битовое изображение другие нетривиальные битовые изображения, удовлетворяющие условию (C1), является NP-трудной, поэтому невозможно создать быстрое решение, всегда завершающее алгоритм. Однако на практике алгоритм сталкивается с противоречиями на удивление редко.
Алгоритм коллапса волновой функции реализован на C++ [1], Python [2], Kotlin [3], Rust [4], Julia [5], Haxe [6], JavaScript [7] и адаптирован под Unity [8]. Официальные исполняемые файлы можно скачать с itch.io [9] или запустить в браузере [10]. WFC генерирует уровни в Bad North [11], Caves of Qud [12], нескольких [13] более [14] мелких [15] играх, а также во множестве прототипов. Его создание привело к новому [16] исследованию [17]. Другие [18] связанные [19] работы [20], объяснения [21], интерактивные демо [22], руководства [23], туториалы [24] и примеры [25] см. в разделе про порты, форки и спин-оффы [26].
Посмотрите демонстрацию алгоритма WFC на YouTube: https://youtu.be/DOQTr2Xmlz0 [27]
Простейший нетривиальный случай алгоритма — это паттерн NxN=1x2 (точнее NxM). Если мы ещё больше упростим его, сохраняя не вероятности пар цветов, а вероятности самих цветов, то получим то, что называется «простой тайловой моделью». Фаза распространения в этой модели — это просто распространение зависимости соседства. Удобно инициализировать простую тайловую модель списком тайлов и данными об их соседстве (данные о соседстве можно рассматривать как большое множество очень маленьких сэмплов), а не сэмплируемым битовым изображением.
Списки всех возможных пар соседних тайлов в практических тайлсетах могут быть достаточно длинными, поэтому чтобы укоротить перечисление, я реализовал для тайлов систему симметрии. В этой системе каждому тайлу должен назначаться его тип симметрии.
Заметьте, что тайлы имеют ту же симметрию, что и назначенные им буквы (другими словами, действия диэдральной группы D4 изометричны для тайлов и соответствующих букв). Благодаря этой системе достаточно перечислить пары соседних тайлов только до их симметрии, в несколько раз укорачивает список соседей для тайлсетов со множеством симметричных тайлов (даже в тайлсете рельефа Summer, несмотря на то, что рисунки не являются симметричными, система считает такие тайлы симметричными).
Заметьте, что неограниченный тайлсет из узлов (в котором допустимы все 5 тайлов) неинтересен для алгоритма WFC, потому что нельзя попасть в ситуацию, когда невозможно разместить тайл. Мы называем тайлсеты с таким свойством «простыми». Без сложных эвристик простые тайлсеты не создают интересных глобальных структур, потому что корреляции в простых тайлсетах на расстоянии быстро снижаются. Множество простых тайлетов можно найти на сайте cr31 [30]. Посмотрите там на двухсторонний тайлсет «Dual». Как он может создавать узлы (без Т-образных соединений, то есть непростые), в то же время будучи простым? Ответ заключается в том, что он может генерировать только узкий тип узлов и не может создавать произвольный узел.
Стоит также заметить, что тайлсеты Circuit, Summer и Rooms не являются плитками Вана. То есть данные их соседства нельзя породить из расцветки краёв. Например, в тайлсете Circuit (интегральная схема) два уголка (Corner) не могут быть соседними, хотя и могут соединяться тайлом (Connection), а диагональные дорожки не могут менять направления.
Алгоритм WFC в более высоких размерностях работает совершенно так же, как и в двух измерениях, однако здесь проблемой становится производительность. Эти воксельные модели генерировались при N=2 в тайловой модели с перекрытием при помощи блоков 5x5x5 и 5x5x2 и дополнительных эвристик (высоты, плотности, кривизны...).
Скриншоты более высоких размерностей: 1 [31], 2 [32], 3 [33].
Сгенерированные с помощью WFC и других алгоритмов воксельные модели будут находиться в отдельном репозитории.
Алгоритм WFC поддерживает ограничения. Поэтому его с лёгкостью можно комбинировать с другими генеративными алгоритмами или ручным созданием.
Вот, как WFC автоматически завершает уровень, начатый человеком:
Алгоритм ConvChain [36] удовлетворяет строгой версии условия (C2): создаваемое им распределение пределов паттернов NxN в выходных данных точно такое же, как распределение паттернов во входных данных. Однако ConvChain не удовлетворяет (C1): часто он создаёт заметные артефакты. Логично сначала запускать ConvChain, чтобы получать хорошо сэмплированную конфигурацию, а затем WFC для коррекции локальных артефактов. Это похоже на распространённую в оптимизации стратегию: сначала выполняем метод Монте-Карло для нахождения точки. близкой к глобальному оптимуму, а затем выполняем из этой точки градиентный спуск для большей точности.
Алгоритм синтеза текстур [37] П. Ф. Харрисона значительно быстрее, чем WFC, но у него возникают проблемы с длинными корреляциями (например, этому алгоритму сложно синтезировать текстуры кирпичных стен с правильно выстроенными кирпичами). Именно в таких случаях WFC демонстрирует своё превосходство, а алгоритм Харрисона поддерживает ограничения. Имеет смысл сначала сгенерировать с помощью WFC идеальную схему кирпичной стены, а затем выполнить для этой схемы алгоритм ограниченного синтеза текстур.
Почему используется эвристика минимальной энтропии? Я заметил, что когда люди что-то рисуют, они часто сами следуют эвристике минимальной энтропии. Именно поэтому за алгоритмом так интересно наблюдать.
Модель с перекрытием соотносится с простой моделью так же, как цепи Маркова высокого порядка соотносятся с цепями Маркова первого порядка.
Нужно учесть, что энтропия любого узла не может увеличиваться на этапе распространения, т.е. вероятности не повышаются, но могут быть обнулены. Когда этап распространения не может дальше уменьшать энтропию, мы активируем этап наблюдения. Если этап наблюдения не может уменьшить энтропию, это значит, что алгоритм закончил работу.
Этап распространения в алгоритме WFC очень похож на цикличный алгоритм передачи сообщений (loopy belief propagation algorithm). На самом деле, я изначально программировал belief propagation (BP), но затем перешёл к распространению с ограничениями с сохраненённым стационарным распределением, потому что BP значительно медленнее без массивной параллелизации (в ЦП) и он не создавал значительно лучших результатов для моих задач.
Заметьте, что сэмплы «Simple Knot» и «Trick Knot» имеют не 2, а 3 цвета.
Одним из измерений может быть время. В частности, d-мерный WFC отображает поведение любого (d-1)-мерного клеточного автомата.
Этот проект основан на работе Пола Меррелла по синтезу моделей, в частности, на главе о дискретном синтезе моделей из его диссертации [38]. Пол распространяет ограничения соседства в том, что мы назвали простой тайловой моделью, с эвристикой, стремящейся вычислить распространение в небольшой подвижной области.
Также на мой проект сильно повлияла глава о декларативном синтезе текстур из диссертации Пола Ф. Харрисона [39]. Пол задаёт данные о соседстве тайлов, помечая их границы и используя поиск в возвратом для заполнения тайловой карты.
WFC — это консольное приложение, зависящее только от стандартной библиотеки. Скачайте .NET Core [40] для Windows, Linux или macOS и выполните
dotnet run WaveFunctionCollapse.csproj
Или же можно использовать инструкции сообщества по сборке для разных платформ в соответствующем issue [41]. Кейси Маршалл создал pull request [42], который упрощает использование программы с командной строкой и включает пакет snap.
Часть примеров взята из игр Ultima IV и Dungeon Crawl [157]. Тайлсет Circles взят у Марио Клингеманна [158]. Идея генерации интегральных схем была предложена Moonasaur [159], а их стиль был взять из игры Ruckingenur II [160] компании Zachtronics. Пример с перекрытием Cat взят из видео Nyan Cat, пример Qud был создан Брайаном Баклью [76], примеры Magic Office + Spirals — rid5x, примеры с перекрытием Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City — Арви Теикари. Тайлсет Summer был создан Германном Хиллманном. Воксельные модели отрендерены в MagicaVoxel [161].
Автор: PatientZero
Источник [162]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/algoritmy/306987
Ссылки в тексте:
[1] C++: https://github.com/math-fehr/fast-wfc
[2] Python: https://github.com/ikarth/wfc_python
[3] Kotlin: https://github.com/j-roskopf/WFC
[4] Rust: https://github.com/sdleffler/collapse
[5] Julia: https://github.com/roberthoenig/WaveFunctionCollapse.jl
[6] Haxe: https://github.com/Mitim-84/WFC-Gen
[7] JavaScript: https://github.com/kchapelier/wavefunctioncollapse
[8] Unity: https://selfsame.itch.io/unitywfc
[9] itch.io: https://exutumno.itch.io/wavefunctioncollapse
[10] запустить в браузере: http://www.kchapelier.com/wfc-example/overlapping-model.html
[11] Bad North: https://www.badnorth.com/
[12] Caves of Qud: https://store.steampowered.com/app/333640/Caves_of_Qud/
[13] нескольких: https://arcadia-clojure.itch.io/proc-skater-2016
[14] более: https://arcadia-clojure.itch.io/swapland
[15] мелких: https://marian42.itch.io/wfc
[16] новому: https://adamsmith.as/papers/wfc_is_constraint_solving_in_the_wild.pdf
[17] исследованию: https://hal.inria.fr/hal-01706539v3/document
[18] Другие: https://twitter.com/OskSta/status/784847588893814785
[19] связанные: https://twitter.com/dwtw/status/810166761270243328
[20] работы: https://github.com/mewo2/oisin
[21] объяснения: https://trasevol.dog/2017/09/01/di19/
[22] интерактивные демо: http://oskarstalberg.com/game/wave/wave.html
[23] руководства: https://www.dropbox.com/s/zeiat1w8zre9ro8/Knots%20breakdown.png?dl=0
[24] туториалы: http://www.procjam.com/tutorials/wfc/
[25] примеры: https://twitter.com/ExUtumno/status/895684431477747715
[26] порты, форки и спин-оффы: https://github.com/mxgmn/WaveFunctionCollapse#notable-ports-forks-and-spinoffs
[27] https://youtu.be/DOQTr2Xmlz0: https://youtu.be/DOQTr2Xmlz0
[28] GIF: http://i.imgur.com/jIctSoT.gif
[29] GIFV: http://i.imgur.com/jIctSoT.gifv
[30] сайте cr31: http://cr31.co.uk/stagecast/wang/tiles_e.html
[31] 1: http://i.imgur.com/0bsjlBY.png
[32] 2: http://i.imgur.com/GduN0Vr.png
[33] 3: http://i.imgur.com/IEOsbIy.png
[34] GIF: http://i.imgur.com/X3aNDUv.gif
[35] GIFV: http://i.imgur.com/X3aNDUv.gifv
[36] ConvChain: https://github.com/mxgmn/ConvChain
[37] синтеза текстур: https://github.com/mxgmn/SynTex
[38] его диссертации: http://graphics.stanford.edu/~pmerrell/thesis.pdf
[39] диссертации Пола Ф. Харрисона: http://logarithmic.net/pfh-files/thesis/dissertation.pdf
[40] .NET Core: https://www.microsoft.com/net/download
[41] соответствующем issue: https://github.com/mxgmn/WaveFunctionCollapse/issues/3
[42] pull request: https://github.com/mxgmn/WaveFunctionCollapse/pull/18
[43] порт на C++: https://github.com/emilk/wfc
[44] Макс Эллер: https://github.com/nanodeath
[45] Kollapse: https://gitlab.com/nanodeath/kollapse
[46] библиотеку Kotlin: https://github.com/edwinRNDR/wfc
[47] Кевин Чапельер: https://github.com/kchapelier
[48] 1: https://twitter.com/OskSta/status/787319655648100352
[49] 3: https://twitter.com/OskSta/status/784847933686575104
[50] 4: https://twitter.com/OskSta/status/784848286272327680
[51] 5: https://twitter.com/OskSta/status/793545297376972801
[52] 6: https://twitter.com/OskSta/status/793806535898136576
[53] 7: https://twitter.com/OskSta/status/802496920790777856
[54] 8: https://twitter.com/OskSta/status/804291629561577472
[55] 9: https://twitter.com/OskSta/status/806856212260278272
[56] 10: https://twitter.com/OskSta/status/806904557502464000
[57] 11: https://twitter.com/OskSta/status/818857408848130048
[58] 12: https://twitter.com/OskSta/status/832633189277409280
[59] 13: https://twitter.com/OskSta/status/851170356530475008
[60] 14: https://twitter.com/OskSta/status/858301207936458752
[61] 15: https://twitter.com/OskSta/status/863019585162932224
[62] Джозеф Паркер: https://github.com/selfsame
[63] фантастических плато в : https://twitter.com/jplur_/status/929482200034226176
[64] платформенных уровней: https://twitter.com/jplur_/status/1053458654454865921
[65] Bug with a Gun: https://selfsame.itch.io/bug-with-a-gun
[66] Мартин О'Лири: https://github.com/mewo2
[67] 1: https://twitter.com/mewo2/status/789167437518217216
[68] 2: https://twitter.com/mewo2/status/789177702620114945
[69] 3: https://twitter.com/mewo2/status/789187174683987968
[70] 4: https://twitter.com/mewo2/status/789897712372183041
[71] Ник Ненов: https://github.com/NNNenov
[72] трёхмерный воксельный тайлсет: https://twitter.com/NNNenov/status/789903180226301953
[73] версию WFC на OCaml: https://twitter.com/rid5x/status/782442620459114496
[74] трёхмерную тайловую модель: https://bitbucket.org/mxgmn/basic3dwfc/overview
[75] интерактивную модель : https://twitter.com/ExUtumno/status/798571284342837249
[76] Брайан Баклью: https://github.com/unormal
[77] Caves of Qud: http://store.steampowered.com/app/333640
[78] 1: https://twitter.com/unormal/status/805987523596091392
[79] 2: https://twitter.com/unormal/status/808566029387448320
[80] 3: https://twitter.com/unormal/status/808523056259993601
[81] 4: https://twitter.com/unormal/status/808523493994364928
[82] 5: https://twitter.com/unormal/status/808519575264497666
[83] 6: https://twitter.com/unormal/status/808519216185876480
[84] 7: https://twitter.com/unormal/status/808795396508123136
[85] 8: https://twitter.com/unormal/status/808860105093632001
[86] 9: https://twitter.com/unormal/status/809637856432033792
[87] 10: https://twitter.com/unormal/status/810239794433425408
[88] 11: https://twitter.com/unormal/status/811034574973243393
[89] 12: https://twitter.com/unormal/status/811720423419314176
[90] 13: https://twitter.com/unormal/status/811034037259276290
[91] 14: https://twitter.com/unormal/status/810971337309224960
[92] 15: https://twitter.com/unormal/status/811405368777723909
[93] 16: https://twitter.com/ptychomancer/status/812053801544757248
[94] 17: https://twitter.com/unormal/status/812159308263788544
[95] 18: https://twitter.com/unormal/status/812158749838340096
[96] 19: https://twitter.com/unormal/status/814569437181476864
[97] 20: https://twitter.com/unormal/status/814570383189876738
[98] 21: https://twitter.com/unormal/status/819725864623603712
[99] Дэнни Уайн: https://github.com/dannywynne
[100] алгоритм синтеза текстур с энтропийной эвристикой: http://www.hempuli.com/blogblog/archives/1598
[101] портировал: https://github.com/headchant/iga
[102] Мэтт Рикс: https://github.com/MattRix
[103] 1: https://twitter.com/MattRix/status/869403586664570880
[104] 2: https://twitter.com/MattRix/status/870999185167962113
[105] 3: https://twitter.com/MattRix/status/871054734018453505
[106] 4: https://twitter.com/MattRix/status/871056805761359872
[107] 1: https://twitter.com/MattRix/status/872674537799913472
[108] 2: https://twitter.com/MattRix/status/872648369625325568
[109] 3: https://twitter.com/MattRix/status/872645716660891648
[110] 4: https://twitter.com/MattRix/status/872641331956518914
[111] 5: https://twitter.com/MattRix/status/979020989181890560
[112] Айзек Кэрт: https://github.com/ikarth
[113] Адам М. Смит: https://github.com/rndmcnlly
[114] clingo: https://github.com/potassco/clingo
[115] реализацию на C++: https://github.com/sylefeb/VoxModSynth
[116] визуализирую: https://twitter.com/ExUtumno/status/900395635412787202
[117] использует: https://twitter.com/OskSta/status/917405214638006273
[118] реализовал: https://github.com/heyx3/easywfc
[119] Джозеф Паркер: https://gist.github.com/selfsame
[120] Аман Тивари: https://github.com/aman-tiwari
[121] ASP-задачу: https://gist.github.com/aman-tiwari/8a7b874cb1fd1270adc203b2af293f4c
[122] трёхмерную модель с перекрытием: https://github.com/MatveyK/Kazimir
[123] Силвэн Лефевр: https://github.com/sylefeb
[124] Ли Ю Вей: https://github.com/1iyiwei
[125] Коннелли Барнс: https://github.com/connellybarnes
[126] исследуют: https://hal.archives-ouvertes.fr/hal-01706539/
[127] инструмент: https://members.loria.fr/Sylvain.Lefebvre/infotexsyn/
[128] Матьё Фер: https://github.com/math-fehr
[129] Натаниэль Куран: https://github.com/Ekdohibs
[130] интегрировал: https://github.com/mxgmn/WaveFunctionCollapse/commit/fad1066b5000f7e9fbda0ef81bbea56799686670
[131] портировал: https://github.com/vasumahesh1/WFC_WebGL
[132] визуализировал: https://vasumahesh1.github.io/WFC_WebGL
[133] Ким Хуанхи: https://github.com/greentec
[134] 1: https://twitter.com/greentecq/status/1025348928634408960
[135] 2: https://twitter.com/greentecq/status/1004068394553913344
[136] 3: https://twitter.com/greentecq/status/1005835830802305024
[137] 4: https://twitter.com/greentecq/status/1022851327041265664
[138] 5: https://twitter.com/greentecq/status/1011351814216736769
[139] 6: https://twitter.com/greentecq/status/1008210550944387077
[140] 7: https://twitter.com/greentecq/status/1006390606875070464
[141] 8: https://twitter.com/greentecq/status/1015182718810841088
[142] докладом: https://www.youtube.com/watch?v=0bcZb-SsnrA
[143] написал: https://twitter.com/ExUtumno/status/1024314661951467521
[144] препринт: https://arxiv.org/abs/1809.04432
[145] использует: https://steamcommunity.com/games/314230/announcements/detail/3369147113795750369
[146] Rodina: https://store.steampowered.com/app/314230/Rodina/
[147] метод рыхления (chiseling method): https://www.boristhebrave.com/2018/04/28/random-paths-via-chiseling
[148] библиотеку: https://boristhebrave.github.io/DeBroglie
[149] Мариан Кляйнеберг: https://github.com/marian42
[150] создал: https://twitter.com/marian42_/status/1061785383057440768
[151] статью: https://marian42.de/article/wfc
[152] запрограммировал: https://github.com/s-ol/gpWFC
[153] реализовал: https://github.com/aardappel/lobster/commit/703f67472bfd80c26bb626e1d5c22ec91047da98
[154] Эдвин Джейкобс: https://github.com/edwinRNDR
[155] переносу стиля: https://twitter.com/voorbeeld/status/1073874337248239616
[156] дизерингу: https://twitter.com/voorbeeld/status/1073875725499985926
[157] Dungeon Crawl: https://github.com/crawl/crawl
[158] Марио Клингеманна: https://twitter.com/quasimondo/status/778196128957403136
[159] Moonasaur: https://twitter.com/Moonasaur/status/759890746350731264
[160] Ruckingenur II: http://www.zachtronics.com/ruckingenur-ii/
[161] MagicaVoxel: http://ephtracy.github.io/
[162] Источник: https://habr.com/ru/post/437604/?utm_campaign=437604
Нажмите здесь для печати.