Хабрахабр

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

Алгоритм коллапса волновой функции (Wavefunction Collapse Algorithm) учит компьютер импровизировать. На входе он получает архетипичные данные и создаёт процедурно генерируемые данные, похожие на исходные.

(Источник)

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

(Источник)

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

Разумеется, все они важны и необходимы, но в них сложно разобраться с нуля. Большинство реализаций и объяснений коллапса волновой функции — это полная, оптимизированная по скорости версия алгоритма. Кроме того, я выложил пример реализации ESTM на Github. В этом посте я буду объяснять всё понятным я простым языком, сосредоточившись на версии Wavefunction с ограничениями, которую я назвал Even Simpler Tiled Model. Как только вы разберётесь в технологии, лежащей в основе ESTM, то станете ближе к пониманию более сложных версий алгоритма. Код в нём неэффективный и медленный, но очень хорошо читаемый и подробно прокомментирован. Если хотите понять алгоритм коллапса волновой функции, то эта статья будет хорошим началом.
Давайте начнём с истории.

Свадьба

Представьте, что вы планируете свою свадьбу. Кроме подбора украшений и музыки вам нужно создать план рассаживания гостей для обеда. Ваша семья любит поспорить и капризничать, поэтому это может оказаться сложным. Отец не может сидеть ближе чем в двух столах от матери. Двоюродной сестре становится одиноко, если она не сидит с другой двоюродной сестрой. А дядю Роя лучше не сажать рядом с экологически настроенными членами семьи вашего партнёра. Осталось всего 5 часов до прибытия еды, поэтому вы решаете атаковать эту упрямую задачу при помощи алгоритма коллапса волновой функции.

Вы начинаете с длинного списка правил и пустого плана рассаживания гостей.

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

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

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

Этот выбор имеет последствия, распространяющиеся на волновые функции остальных стульев. Если дядя Рой будет сидеть за столом 2, то кузен Фрэнк и Мишель Обама (друг семьи вашего партнёра) точно не будут рядом с ним. А если Мишель не сядет за стол 2, то Барака за ним тоже не будет. Мы обновляем волновую функцию плана расположения, вычёркивая людей из списков возможных кандидатов.

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

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

Отбросить всю предыдущую работу, найти новый пустой план и запустить алгоритм заново, выполнив коллапс волновой функции для другого случайного стула. Если вы достигли противоречия, то проще всего будет начать сначала. Можно также реализовать систему возврата назад, позволяющую отменять отдельный выбор, а не отказываться сразу от всего («что если пересадить Шейлу на стул 54?»).

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

От свадьбы к битовым картам

Это не теоретический пример. Вы действительно можете реализовать вариант коллапса волновой функции, который будет создавать план рассаживания гостей для свадьбы. Однако в более традиционном Wavefunction Collapse мы обычно пытаемся не рассадить людей на свадьбе, а расставить пиксели на выходящем изображении. Тем не менее, процесс будет очень похожим. Мы обучаем алгоритм набору правил, которым должны удовлетворять выходные данные. Инициализируем волновую функцию. Выполняем коллапс одного элемента и распространяем последствия на остальную часть волновой функции. И продолжаем так делать, или пока волновая функция полностью не коллапсирует, или пока мы не достигнем противоречия.

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

Давайте начнём исследование реального коллапса волновой функции с рассмотрения простого особого случая, который ExUtumno (создатель алгоритма) называет простой тайловой моделью (Simple Tiled Model).

Simple Tiled Model

В модели Simple Tiled Model входящие и выходящие изображения строятся из небольшого количества заранее определённых тайлов, и каждый квадрат в выходящем изображении ограничивается только его четырьмя ближайшими соседями. Например, предположим, что мы генерируем случайные миры для двухмерной игры с видом сверху. У нас могут быть тайлы для суши, побережья и моря, а также набор правил вида «побережье может находиться рядом с морем», «суша может быть рядом с побережьем» и «море может быть рядом с другим морем».

Simple Tiled Model учитывает симметрию и поворот своих тайлов. Например, суша может находиться рядом с побережьем, но только в правильной ориентации.

Эта обработка симметрии обеспечивает более качественные выходные изображения, но усложняет код. Чтобы не усложнять, давайте рассмотрим ещё более простой вид коллапса волновой функции, который я назвал Even Simpler Tiled Model.

Even Simpler Tiled Model

Even Simpler Tiled Model («ещё более простая тайловая модель») похожа на Simple Tiled Model, но её тайлы не имеют свойств симметрии. Каждый тайл — это один пиксель одного цвета, то есть мы никак не сможем перепутать их края.

Правила Even Simpler Tiled Model определяют, какие тайлы можно размещать рядом друг с другом и в какой ориентации. Каждое правило представляет собой кортеж из трёх элементов (3-tuple): двух тайлов и направления. Например, (SEA, COAST, LEFT) означает, что тайл SEA (море) может размещаться СЛЕВА от тайла COAST (побережье). Это правило должно сопровождаться другим правилом, описывающим ситуацию с точки зрения COAST(COAST, SEA, RIGHT).

Если вы хотите, чтобы тайлы SEA могли располагаться не только СЛЕВА, но и СПРАВА от тайлов COAST. то им нужны дополнительные правила: (SEA, COAST, RIGHT) и (COAST, SEA, LEFT).

Коллапс волновой функции может создать набор правил для Even Simpler Tile Model парсингом изображения-примера и собиранием списка всех 3-tuple, которые в нём содержатся. Как я сказал выше, нам не нужно создавать список всех этих правил самостоятельно.

Исследовав показанный выше пример изображения, Even Simpler Tiled Model замечает, что тайлы моря могут быть только под или сбоку от тайлов побережья, или в любом месте рядом с другими тайлами моря. Также она замечает, что тайлы побережья могут располагаться рядом с сушей, морем или другими тайлами побережья, но только над тайлами моря и под тайлами суши. Она не пытается вывести никакие более сложные правила, например «тайлы моря должны быть рядом по крайней мере с одним тайлом моря» или «каждый остров должен содержать как минимум один тайл суши». Ни один из тайлов не может влиять на то, что какие-то типы тайлов могут или не могут располагаться в двух или более квадратах от них. Это похоже на модель плана свадьбы, в которой единственное правило: «X может сидеть рядом с Y».

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

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

Коллапс

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

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

Следовательно, он имеет очень высокую энтропию. Например, в модели Even Simpler Tile Model квадрат без информации об окружающих его квадратах ничем не ограничен и может стать любым тайлом. Но квадрат, вокруг которого уже коллапсировало несколько квадратов, может иметь на выбор всего 2 тайла.

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

Даже если вы не пользуетесь коллапсом волновой функции для создания плана размещения гостей на свадьбе и будете составлять его самостоятельно, то всё равно сосредоточитесь на тех областях плана, в которых уже есть наибольшее количество ограничений. Именно на такие ограниченные тайлы с низкой энтропией обычно и обращают внимание люди, когда вручную решают подобные задачи. Вы сначала посадите Дуэйна, потом разберётесь, кто может сидеть рядом с ним, затем кто может сидеть рядом с этим человеком, и так далее. Вы не будете сажать Дуэйна за стол 1, а затем случайным образом перепрыгивать, чтобы посадить Кэти за стол 7 (который пока пуст). Я пока не видел обоснований этого, но моя интуиция говорит, что при использовании этой эвристики минимальной энтропии скорее всего будет получаться меньше противоречий, чем при случайном выборе квадратов для коллапсирования.

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

# Sums are over the weights of each remaining
# allowed tile type for the square whose
# entropy we are calculating.
shannon_entropy_for_square = log(sum(weight)) - (sum(weight * log(weight)) / sum(weight))

Вычислив квадрат волновой функции с наименьшей энтропией, мы коллапсируем её волновую функцию. Мы делаем это, случайным образом выбирая один из тайлов, пока ещё доступных для квадрата, взвешенный на веса тайлов, которые мы спарсили из входящего изображения. Веса используются потому, что это обеспечивает более реалистичное изображение на выходе. Допустим, волновая функция квадрата сообщает, что он может быть сушей или побережьем. Мы не всегда должны выбирать один из вариантов с вероятностью 50%. Если во входящем изображении больше тайлов суши, чем побережья, то нам стоит отразить этот перевес и в выходном изображении. Реализуется это при помощи простых глобальных весов. Если в примере изображения есть 20 тайлов суши и 10 тайлов побережья, то квадрат коллапсирует в сушу с вероятностью 2/3, а в побережье — с оставшейся вероятностью 1/3.

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

В итоге мы создали мир (или ошибку).

Куда двигаться дальше

Разобравшись с моделью Even Simpler Tiled Model, вы готовы подниматься выше по лестнице мощности и сложности алгоритма. Начните с Simple Tiled Model, которую мы упоминали в начале этого поста, затем перейдите к полной Overlapping Model. В Overlapping Model тайлы или пиксели влияют друг на друга издалека. Если вы понимаете в таких вещах, то ExUtumno замечает, что Simple Tiled Model схожа с цепью Маркова порядка-1, а более сложные модели напоминают цепи большего порядка.

Обо всё этом рассказывается README основного проекта. Wavefunction Collapse даже может учитывать дополнительные ограничения, например «этот тайл должен быть морем» или «этот пиксель должен быть красным» или «в выходных данных может быть только один монстр». Необязательно повторно вычислять энторпию каждого квадрата в каждой итерации, а распространение информации по волновой функции можно сделать значительно быстрее. Также можно изучить оптимизации скорости, внесённые в полную реализацию. Эти аспекты становятся важнее при увеличении размеров выходящих изображений.

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

Теги
Показать больше

Похожие статьи

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *

Кнопка «Наверх»
Закрыть