Доступное объяснение алгоритма коллапса волновой функции

[GCU]

Чем-то напоминает плитки (домино) Вана или решение/построение Судоку :)

[deitry]

Последняя картинка невозбранно отдаёт Сапёром

[cadovvl]

В подобных алгоритмах у меня всегда возникает вопрос: каким требованиям должны соответствовать исходные правила, чтобы алгоритм
1) Гарантированно сошелся?
2) Гарантированно сошелся не более чем за M шагов?

[Vindicar]

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

[wladyspb]

Тут недавно была статья, где коллапс волновой функции применялся для генерации бесконечного трёхмерного города. Если не ошибаюсь, автор использовал откат на несколько итераций в случае противоречия, что теоретически могло приводить к перерисовке куска мира который был уже виден игроку, но такое происходило редко.

[neurocore]

А разве в случаях конфликтов нельзя применить откат назад? Подбор же случайный. Не заметил, выше уже написали

[user_man]

Какой-то ёперный театр…

Зачем менять одно всем понятное слово «перебор» на кучу никому непонятных фраз про функцию, волну, коллапс, суперпозицию?

В общем, дети, это был взгляд физика-теоретика на разбросанные вами на полу игрушки, которые нужно сложить в шкаф в определённой последовательности (иначе они не влезут). Понимаете, дети? Стоит назвать ваши игрушки по умному, найти для них волновую функцию, начать с состояния суперпозиции, а потом инициировать коллапс волновой функции, как сразу все ваши игрушки улягутся спать в ваш любимый шкаф!

Хотя да, принцип работы квантового компьютера теперь знаком каждому малышу из нашего детского сада. Ура, товарищи малыши!

[ipswitch]

Если кто-то играл в TIS-100, ближе к последним уровням названия становятся всё более и более харакетрными — SPATIAL PATH FINDER, и конечно же, WAVE FUNCTION COLLAPSE SUPERVISOR.
steamcommunity.com/sharedfiles/filedetails/?id=1312967423

Уже тут многие подумали, что всё не так просто :)
А описание бесспорно хорошее. Как и подход. Порассуждать о высоком на кубиках зачастую делает это высокое не заумной хренью, а чем-то, к чему можно подступиться.
Так что и физику полезны игрушки и кубики:)

[GCU]

принцип работы квантового компьютера теперь знаком каждому малышу из нашего детского сада

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

игрушки, которые нужно сложить в шкаф в определённой последовательности

— это несколько другая задача, т.к. тут число «игрушек» не ограничено, а ещё они волшебным образом превращаются в конкретную игрушку только при помещении в шкаф o_O

[user_man]

>> А что плохого в знании редукции фон Неймана с детского сада?

Было бы ничего, если бы детям более совсем нечем было бы заняться.

Или вы за отказ от всего ради величия физики?

>> это несколько другая задача

Не понял ваших намёков.

[GCU]

вы за отказ от всего ради величия физики?

Нет, это какие-то крайности. Но из перечня занятий физика не настолько плохая, чтобы заниматься ей только когда совсем нечем.

Не понял ваших намёков.

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

[user_man]

>> Основное применение алгоритма для процедурной генерации карт и текстур

Возможно. Но я не уловил разницу. Может недостаточно внимательно читал.

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

[DimPal]

Статью нужно назвать «Максимально запутанное объяснение алгоритма ...». В статье показано как объяснить простые вещи максимально недоступно.

[usdglander]

Вы и это объяснение не поняли? =)

[perfect_genius]

Простое объяснение через квантовую физику — что может быть проще?

[CaptainFlint]

По-моему, волновые функции с коллапсами тут вообще ни при чём. Коллапс он на то и коллапс, что всё состояние схлопывается сразу и целиком. А механизм последовательной фильтрации допустимых вариантов мне всегда казался совершенно очевидным; я его ещё 15 лет назад реализовывал для своей задачки, не выдумывая никаких волновых функций.

[DatUser]

Люди, пишущие на императивных языках, столкнулись с задачами декларативных языков, взяли из них кусочек алгоритма решения и сразу «Вааааау!». Ждём проникновения декларативных возможностей во все популярные ЯП, как это сейчас было (и всё ещё продолжается) с проникновением функционального программирования.

[rmrfchik]

Всё это дико напоминает алгоритм поиска решения в Прологе с бэктрекингом. Единственное добавление это выбор начального узла, что делается в Прологе вручную несложно.

[Fen1kz]

Советую добавить в статью ссылку сюда: https://github.com/mxgmn/WaveFunctionCollapse — куча крышесносных примеров. Там же есть веб-версия: http://www.kchapelier.com/wfc-example/simple-tiled-model-animated.html