Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 19
Чем-то напоминает плитки (домино) Вана или решение/построение Судоку :)
В подобных алгоритмах у меня всегда возникает вопрос: каким требованиям должны соответствовать исходные правила, чтобы алгоритм
1) Гарантированно сошелся?
2) Гарантированно сошелся не более чем за M шагов?
1) Гарантированно сошелся?
2) Гарантированно сошелся не более чем за M шагов?
Возможность противоречия портит всю малину, ведь иначе этот алгоритм можно было бы применять для генерации бесконечных карт. А так придётся либо добавлять тайл, который может встречаться где угодно (и как следствие, будет встречаться постоянно, а не только в точках противоречия), либо прикручивать какой-то другой костыль, реализуемый в случае конфликта.
Тут недавно была статья, где коллапс волновой функции применялся для генерации бесконечного трёхмерного города. Если не ошибаюсь, автор использовал откат на несколько итераций в случае противоречия, что теоретически могло приводить к перерисовке куска мира который был уже виден игроку, но такое происходило редко.
А разве в случаях конфликтов нельзя применить откат назад? Подбор же случайный. Не заметил, выше уже написали
Какой-то ёперный театр…
Зачем менять одно всем понятное слово «перебор» на кучу никому непонятных фраз про функцию, волну, коллапс, суперпозицию?
В общем, дети, это был взгляд физика-теоретика на разбросанные вами на полу игрушки, которые нужно сложить в шкаф в определённой последовательности (иначе они не влезут). Понимаете, дети? Стоит назвать ваши игрушки по умному, найти для них волновую функцию, начать с состояния суперпозиции, а потом инициировать коллапс волновой функции, как сразу все ваши игрушки улягутся спать в ваш любимый шкаф!
Хотя да, принцип работы квантового компьютера теперь знаком каждому малышу из нашего детского сада. Ура, товарищи малыши!
Зачем менять одно всем понятное слово «перебор» на кучу никому непонятных фраз про функцию, волну, коллапс, суперпозицию?
В общем, дети, это был взгляд физика-теоретика на разбросанные вами на полу игрушки, которые нужно сложить в шкаф в определённой последовательности (иначе они не влезут). Понимаете, дети? Стоит назвать ваши игрушки по умному, найти для них волновую функцию, начать с состояния суперпозиции, а потом инициировать коллапс волновой функции, как сразу все ваши игрушки улягутся спать в ваш любимый шкаф!
Хотя да, принцип работы квантового компьютера теперь знаком каждому малышу из нашего детского сада. Ура, товарищи малыши!
Если кто-то играл в TIS-100, ближе к последним уровням названия становятся всё более и более харакетрными — SPATIAL PATH FINDER, и конечно же, WAVE FUNCTION COLLAPSE SUPERVISOR.
steamcommunity.com/sharedfiles/filedetails/?id=1312967423
Уже тут многие подумали, что всё не так просто :)
А описание бесспорно хорошее. Как и подход. Порассуждать о высоком на кубиках зачастую делает это высокое не заумной хренью, а чем-то, к чему можно подступиться.
Так что и физику полезны игрушки и кубики:)
steamcommunity.com/sharedfiles/filedetails/?id=1312967423
Уже тут многие подумали, что всё не так просто :)
А описание бесспорно хорошее. Как и подход. Порассуждать о высоком на кубиках зачастую делает это высокое не заумной хренью, а чем-то, к чему можно подступиться.
Так что и физику полезны игрушки и кубики:)
принцип работы квантового компьютера теперь знаком каждому малышу из нашего детского сада
А что плохого в знании редукции фон Неймана с детского сада?
Некоторые концепции проще воспринимать как можно раньше, тем более что квантовые компьютеры уже существуют и считаются довольно перспективными.
игрушки, которые нужно сложить в шкаф в определённой последовательности— это несколько другая задача, т.к. тут число «игрушек» не ограничено, а ещё они волшебным образом превращаются в конкретную игрушку только при помещении в шкаф o_O
>> А что плохого в знании редукции фон Неймана с детского сада?
Было бы ничего, если бы детям более совсем нечем было бы заняться.
Или вы за отказ от всего ради величия физики?
>> это несколько другая задача
Не понял ваших намёков.
Было бы ничего, если бы детям более совсем нечем было бы заняться.
Или вы за отказ от всего ради величия физики?
>> это несколько другая задача
Не понял ваших намёков.
вы за отказ от всего ради величия физики?
Нет, это какие-то крайности. Но из перечня занятий физика не настолько плохая, чтобы заниматься ей только когда совсем нечем.
Не понял ваших намёков.
Основное применение алгоритма для процедурной генерации карт и текстур.
В статье использовался пример со свадьбой (не особо удачный), который действительно сводится к вашей формулировке разбросанных игрушек — но это лишь частный случай (для которого есть и более эффективные алгоритмы, чем коллапс волновой функции). Да, алгоритм решает и эту задачу, но он предназначен для решения другой.
>> Основное применение алгоритма для процедурной генерации карт и текстур
Возможно. Но я не уловил разницу. Может недостаточно внимательно читал.
Вообще, переборные алгоритмы конечно же можно оптимизировать под те или иные задачи путём отсечения заведомо бесполезных ветвей перебора, но какие конкретно ветви отсекаются в данном случае, а так же чем они принципиально отличаются от других вариантов перебора — вот этого я как раз и не уловил.
Возможно. Но я не уловил разницу. Может недостаточно внимательно читал.
Вообще, переборные алгоритмы конечно же можно оптимизировать под те или иные задачи путём отсечения заведомо бесполезных ветвей перебора, но какие конкретно ветви отсекаются в данном случае, а так же чем они принципиально отличаются от других вариантов перебора — вот этого я как раз и не уловил.
Статью нужно назвать «Максимально запутанное объяснение алгоритма ...». В статье показано как объяснить простые вещи максимально недоступно.
По-моему, волновые функции с коллапсами тут вообще ни при чём. Коллапс он на то и коллапс, что всё состояние схлопывается сразу и целиком. А механизм последовательной фильтрации допустимых вариантов мне всегда казался совершенно очевидным; я его ещё 15 лет назад реализовывал для своей задачки, не выдумывая никаких волновых функций.
Люди, пишущие на императивных языках, столкнулись с задачами декларативных языков, взяли из них кусочек алгоритма решения и сразу «Вааааау!». Ждём проникновения декларативных возможностей во все популярные ЯП, как это сейчас было (и всё ещё продолжается) с проникновением функционального программирования.
Всё это дико напоминает алгоритм поиска решения в Прологе с бэктрекингом. Единственное добавление это выбор начального узла, что делается в Прологе вручную несложно.
Советую добавить в статью ссылку сюда: https://github.com/mxgmn/WaveFunctionCollapse — куча крышесносных примеров. Там же есть веб-версия: http://www.kchapelier.com/wfc-example/simple-tiled-model-animated.html
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Доступное объяснение алгоритма коллапса волновой функции