Что такое схлопывание волновой функции

КВАНТОВАЯ МЕХАНИКА. ИНОЙ ВЗГЛЯД

А. ШИШЛОВА. по материалам журналов «Успехи физических наук» и «Scientific american».

Квантово-механическое описание физических явлений микромира считается единственно верным и наиболее полно отвечающим реальности. Объекты макромира подчиняются законам другой, классической механики. Граница между макро- и микромиром размыта, а это вызывает целый ряд парадоксов и противоречий. Попытки их ликвидировать приводят к появлению других взглядов на квантовую механику и физику микромира. Видимо, наилучшим образом выразить их удалось американскому теоретику Дэвиду Джозефу Бому (1917-1992).

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

2. Последовательное измерение двух компонент спина. Измеряется «горизонтальный» спин электрона (слева), потом «вертикальный» спин (справа), потом снова «горизонтальный» (внизу).

3А. Электроны с «правым» спином после прохождения через «вертикальный» ящик движутся в двух направлениях: вверх и вниз.

3Б. В том же эксперименте на пути одного из двух пучков поставим некую поглощающую поверхность. Далее в измерениях участвует лишь половина электронов, и на выходе половина их имеет «левый» спин, а половина — «правый».

4. Состояние любого объекта микромира описывает так называемая волновая функция.
5. Мысленный эксперимент Эрвина Шредингера.

6. Эксперимент, предложенный Д. Бомом и Я. Аароновым в 1959 году, должен был показать, что магнитное поле, недоступное для частицы, влияет на ее состояние.

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

В 1900 году появилась работа немецкого физика Макса Планка, в которой эти новые идеи и появились. Планк предположил, что излучение происходит порциями, квантами. Такое представление противоречило классическим воззрениям, но прекрасно объясняло результаты экспериментов (в 1918 году эта работа была удостоена Нобелевской премии по физике). Спустя пять лет Альберт Эйнштейн показал, что не только излучение, но и поглощение энергии должно происходить дискретно, порциями, и сумел объяснить особенности фотоэффекта (Нобелевская премия 1921 года). Световой квант — фотон, по Эйнштейну, имея волновые свойства, одновременно во многом напоминает частицу (корпускулу). В отличие от волны, например, он либо поглощается целиком, либо не поглощается вовсе. Так возник принцип корпускулярно-волнового дуализма электромагнитного излучения.

В 1924 году французский физик Луи де Бройль выдвинул достаточно «безумную» идею, предположив, что все без исключения частицы — электроны, протоны и целые атомы обладают волновыми свойствами. Год спустя Эйнштейн отозвался об этой работе: «Хотя кажется, что ее писал сумасшедший, написана она солидно», а в 1929 году де Бройль получил за нее Нобелевскую премию.

На первый взгляд, повседневный опыт гипотезу де Бройля отвергает: в окружающих нас предметах ничего «волнового» как будто нет. Расчеты, однако, показывают, что длина дебройлевской волны электрона, ускоренно го до энергии 100 электрон-вольт, равна 10 -8 сантиметра. Эту волну нетрудно обнаружить экспериментально, пропустив поток электронов сквозь кристалл. На кристаллической решетке произойдет дифракция их волн и возникнет характерная полосатая картинка. А у пылинки массой 0,001 грамма при той же скорости длина волны де Бройля будет в 10 24 раз меньше, и обнаружить ее никакими средствами нельзя.

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

Идеи де Бройля углубил и развил австрийский физик Эрвин Шредингер. В 1926 году он вывел систему уравнений — волновых функций, описывающих поведение квантовых объектов во времени в зависимости от их энергии (Нобелевская премия 1933 года). Из уравнений следует, что любое воздействие на частицу меняет ее состояние. А поскольку процесс измерения параметров частицы неизбежно связан с воздействием, возникает вопрос: что же регистрирует измерительный прибор, вносящий непредсказуемые возмущения в состояние измеряемого объекта?

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

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

Впервые к таким выводам пришли сами основоположники квантовой теории — Нильс Бор, Вернер Гейзенберг, Вольфганг Паули. Позднее данная точка зрения, получившая название Копенгагенской интерпретации квантовой механики, была принята в теоретической физике в качестве официальной, что и нашло свое отражение во всех стандартных учебниках.

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

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

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

Пытаясь объяснить полученные результаты, традиционная квантовая теория пришла к выводу, что необходимо полностью отказаться от детерминистского, то есть полностью определяющего состояние

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

Продолжим наши мысленные эксперименты. Будем теперь не только расщеплять пучки электронов, но и заставим их отражаться от неких поверхностей, пересекаться и снова соединяться в один пучок в специальном «черном ящике» (3).

Результаты этих экспериментов противоречат обычной логике. Действительно, рассмотрим поведение какого-либо электрона в случае, когда поглощающая стенка отсутствует (3 А). Куда он будет двигаться? Допустим, что вниз. Тогда, если первоначально электрон имел «правый» спин, он так и останется правым до конца эксперимента. Однако, применив к этому электрону результаты другого эксперимента (3 Б), мы увидим, что его «горизонтальный» спин на выходе должен быть в половине случаев «правым», а в половине — «левым». Явное противоречие. Мог ли электрон пойти вверх? Нет, по той же самой причине. Быть может, он двигался не вниз, не вверх, а как-то по-другому? Но, перекрыв верхний и нижний маршруты поглощающими стенками, мы на выходе не получим вообще ничего. Остается предположить, что электрон может двигаться сразу по двум направлениям. Тогда, имея возможность фиксировать его положение в разные моменты времени, в половине случаев мы находили бы его на пути вверх, а в половине — на пути вниз. Ситуация достаточно парадоксальная: материальная частица не может ни раздваиваться, ни «прыгать» с одной траектории на другую.

Что говорит в данном случае традиционная квантовая теория? Она просто объявляет все рассмотренные ситуации невозможными, а саму постановку вопроса об определенном направлении движения электрона (и соответственно о направлении его спина) — некорректной. Проявление квантовой природы электрона в том и заключается, что ответа на данный вопрос в принципе не существует. Состояние электрона представляет собой суперпозицию, то есть сумму двух состояний, каждое из которых имеет определенное значение «вертикального» спина. Понятие о суперпозиции — один из основополагающих принципов квантовой механики, с помощью которого вот уже более семидесяти лет удается успешно объяснять и предсказывать поведение всех известных квантовых систем.

Для математического описания состояний квантовых объектов используется волновая функция, которая в случае одной частицы просто определяет ее координаты. Квадрат волновой функции равен вероятности обнаружить частицу в данной точке пространства. Таким образом, если частица находится в некой области А, ее волновая функция равна нулю всюду, за исключением этой области. Аналогично частица, локализованная в области Б, имеет волновую функцию, отличную от нуля только в Б. Если же состояние частицы оказывается суперпозицией пребывания ее в А и Б, то волновая функция, описывающая такое состояние, отлична от нуля в обеих областях пространства и равна нулю всюду вне их. Однако, если мы поставим эксперимент по определению положения такой частицы, каждое измерение будет давать нам только одно значение: в половине случаев мы обнаружим частицу в области А, а в половине — в Б ( 4). Это означает, что при взаимодействии частицы с окружением, когда фиксируется только одно из состояний частицы, ее волновая функция как бы коллапсирует, «схлопывается» в точку.

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

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

Возникает естественный вопрос: как отличить условия применимости той или другой группы законов? Создатели квантовой механики указывают на необходимость четкого разделения всех физических процессов на «измерения» и «собственно физические процессы», то есть на «наблюдателей» и «наблюдаемых», или, по философской терминологии, на субъект и объект. Однако отличие между этими категориями носит не принципиальный, а чисто относительный характер. Тем самым, по мнению многих физиков и философов, квантовая теория в такой интерпретации становится неоднозначной, теряет свою объективность и фундаментальность. «Проблема измерения» стала основным камнем преткновения в квантовой механике. Ситуация несколько напоминает знаменитую апорию Зенона «Куча». Одно зерно — явно не куча, а тысяча (или, если угодно, миллион) — куча. Два зерна — тоже не куча, а 999 (или 999999) — куча. Эта цепочка рассуждений приводит к некоему количеству зерен, при котором понятия «куча — не куча» станут неопределенными. Они будут зависеть от субъективной оценки наблюдателя, то есть от способа измерений, хотя бы и на глаз.

Все окружающие нас макроскопические тела предполагаются точечными (или протяженными) объектами с фиксированными координатами, которые подчиняются законам классической механики. Но это означает, что классическое описание можно продолжить вплоть до самых малых частиц. С другой стороны, идя со стороны микромира, следует включать в волновое описание объекты все большего размера вплоть до Вселенной в целом. Граница между макро- и микромиром не определена, и попытки ее обозначить приводят к парадоксу. Наиболее четко указывает на него так называемая «задача о кошке Шредингера» — мысленный эксперимент, предложенный Эрвином Шредингером в 1935 году (5).

В закрытом ящике сидит кошка. Там же находятся флакон с ядом, источник излучения и счетчик заряженных частиц, подсоединенный к устройству, разбивающему флакон в момент регистрации частицы. Если яд разольется, кошка погибнет. Зарегистрировал счетчик частицу или нет, мы не можем знать в принципе: законы квантовой механики подчиняются законам вероятности. И с этой точки зрения, пока счетчик не произвел измерения, он находится в суперпозиции двух состояний — «регистрация — нерегистрация». Но тогда в этот момент и кошка оказывается в суперпозиции состояний жизни и смерти.

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

Итак, несмотря на несомненные успехи квантовой механики в объяснении экспериментальных фактов, в настоящий момент она едва ли может претендовать на полноту и универсальность описания физических явлений. Одной из наиболее смелых альтернатив квантовой механики и стала теория, предложенная Дэвидом Бомом.

Задавшись целью построить теорию, свободную от принципа неопределенности, Бом предложил считать микрочастицу материальной точкой, способной занимать точное положение в пространстве. Ее волновая функция получает статус не характеристики вероятности, а вполне реального физического объекта, некоего квантовомеханического поля, оказывающего мгновенное силовое воздействие. В свете этой интерпретации, например, «парадокс Эйнштейна-Подольского-Розена» (см. «Наука и жизнь» № 5, 1998 г.) перестает быть парадоксом. Все законы, управляющие физическими процессами, становятся строго детерминистскими и имеют вид линейных дифференциальных уравнений. Одна группа уравнений описывает изменение волновых функций во времени, другая — их воздействие на соответствующие частицы. Законы применимы ко всем физическим объектам без исключения — и к «наблюдателям», и к «наблюдаемым».

Таким образом, если в какой-то момент известны положение всех частиц во Вселенной и полная волновая функция каждой, то в принципе можно точно рассчитать положение частиц и их волновые функции в любой последующий момент времени. Следовательно, ни о какой случайности в физических процессах не может быть и речи. Другое дело, что мы никогда не сможем обладать всей информацией, необходимой для точных вычислений, да и сами расчеты оказываются непреодолимо сложными. Принципиальное незнание многих параметров системы приводит к тому, что на практике мы всегда оперируем некими усредненными величинами. Именно это «незнание», по мнению Бома, заставляет нас прибегать к вероятностным законам при описании явлений в микромире (подобная ситуация возникает и в классической статистической механике, например в термодинамике, которая имеет дело с огромным количеством молекул). Теория Бома предусматривает определенные правила усреднения неизвестных параметров и вычисления вероятностей.

Вернемся к экспериментам с электронами, изображенным на рис. 3 А и Б. Теория Бома дает им следующее объяснение. Направление движения электрона на выходе из «вертикального ящика» полностью определяется исходными условиями — начальным положением электрона и его волновой функцией. В то время как электрон движется либо вверх, либо вниз, его волновая функция, как это следует из дифференциальных уравнений движения, расщепится и станет распространяться сразу в двух направлениях. Таким образом, одна часть волновой функции окажется «пустой», то есть будет распространяться отдельно от электрона. Отразившись от стенок, обе части волновой функции воссоединятся в «черном ящике», и при этом электрон получит информацию о том участке пути, где его не было. Содержание этой информации, например о препятствии на пути «пустой» волновой функции, может оказать существенное воздействие на свойства электрона. Это и снимает логическое противоречие между результатами экспериментов, изображенных на рисунке. Необходимо отметить одно любопытное свойство «пустых» волновых функций: будучи реальными, они тем не менее никак не влияют на посторонние объекты и не могут быть зарегистрированы измерительными приборами. А на «свой» электрон «пустая» волновая функция оказывает силовое воздействие независимо от расстояния, причем воздействие это передается мгновенно.

Попытки «исправить» квантовую механику или объяснить возникающие в ней противоречия предпринимали многие исследователи. Построить детерминистскую теорию микромира, например, пытался де Бройль, который был согласен с Эйнштейном, что «Бог не играет в кости». А видный отечественный теоретик Д. И. Блохинцев считал, что особенности квантовой механики проистекают из-за невозможности изолировать частицу от окружающего мира. При любой температуре выше абсолютного нуля тела излучают и поглощают электромаг нитные волны. С позиций квантовой механики это означает, что их положение непрерывно «измеряется», вызывая коллапс волновых функций. «С этой точки зрения никаких изолированных, предоставленных самим себе «свободных» частиц не существует, — писал Блохинцев. — Возможно, что в этой связи частиц и cреды и скрывается природа той невозможности изолировать частицу, которая проявляется в аппарате квантовой механики».

И все-таки — почему же интепретация квантовой механики, предложенная Бомом, до сих пор не получила должного признания в научном мире? И как объяснить почти повсеместное господство традиционной теории, несмотря на все ее парадоксы и «темные места»?

Долгое время новую теорию не хотели рассматривать всерьез на основании того, что в предсказании исхода конкретных экспериментов она полностью совпадает с квантовой механикой, не приводя к существен но новым результатам. Вернер Гейзенберг, например, считал, что «для любого опыта его (Бома) результаты совпадают с копенгагенской интерпретацией. Отсюда первое следствие: интерпретацию Бома нельзя опровергнуть экспериментом. » Некоторые считают теорию ошибочной, так как в ней преимущественная роль отводится положению частицы в пространстве. По их мнению, это противоречит физической реальности, ибо явления в квантовом мире принципиально не могут быть описаны детерминистскими законами. Существует немало и других, не менее спорных аргументов против теории Бома, которые сами требуют серьезных доказательств. Во всяком случае, ее пока что действительно никому не удалось полностью опровергнуть. Более того — работу над ее совершенствованием продолжают многие, в том числе отечественные, исследователи.

Читайте в любое время

Детальное описание иллюстрации

1. Мысленный эксперимент по измерению компонент спина (собственного количества движения) электрона с помощью некоего устройства — «черного ящика». Пройдя через «горизонтальный» ящик, электроны с «левым» спином будут двигаться налево, с «правым» — направо. Аналогично работает «вертикальный» ящик.
2. Последовательное измерение двух компонент спина. Измеряется «горизонтальный» спин электрона (слева), потом «вертикальный» спин (справа), потом снова «горизонтальный» (внизу). Оказывается, что измерение «вертикального» спина разрушает значение «горизонтального» спина: половина электронов приобретает «левый» спин.
3А. Электроны с «правым» спином после прохождения через «вертикальный» ящик движутся в двух направлениях: вверх и вниз. Отражающие поверхности направляют оба пучка в «черный ящик», где они пересекаются; на выходе получаем единый пучок электронов с «правым» спином.
4. Состояние любого объекта микромира описывает так называемая волновая функция. Величина этой функции характеризует вероятность обнаружить частицу в некоторой конкретной области пространства. Если состояние частицы таково, что можно ожидать встретить ее в двух областях — А и Б, то волновая функция частицы будет равна нулю всюду, кроме этих областей.
5. Мысленный эксперимент Эрвина Шредингера. В ящик помещают кошку, флакон со смертельным ядом, источник радиоактивного излучения и счетчик заряженных частиц. Эксперимент поставлен так, что регистрация частицы может привести в действие механизм, разбивающий флакон. Что произойдет с животным с квантовой точки зрения? Теория утверждает, что кошка в ящике ни жива, ни мертва, но пребывает в суперпозиции этих двух состояний, взятых с некоторой вероятностью. Вершителем судьбы бедного животного окажется некий наблюдатель, решивший «заглянуть» в ящик. В момент наблюдения волновая функция кошки сколлапсирует в какое-то определенное состояние.
6. Эксперимент, предложенный Д. Бомом и Я. Аароновым в 1959 году, должен был показать, что магнитное поле, недоступное для частицы, влияет на ее состояние. В однородном пространстве расположен бесконечно длинный тонкий соленоид. Магнитное поле внутри соленоида имеет форму тонкой нити, как бы «выдернутой» из пространства. Когда мимо соленоида пролетает электрон, его волновая функция расщепляется на две — «пустую» и связанную с электроном. Они обходят поле с обеих сторон и воссоединяются. Если дебройлевская волна — реальность, а не просто характеристика вероятности, то при таком ее движении возникнет разность фаз, которая приведет к интерференции. Электрон как бы провзаимодействует сам с собой, и по изменению его состояния можно будет судить о препятствии на его пути. Эксперименты по наблюдению эффекта Ааронова — Бома неоднократно проводились начиная с 60-х годов, вначале на соленоиде диаметром около 14 микрон, затем — на тороидаль ных магнитах и квантовых интерферомет рах. Все они надежно подтвердили существование эффекта. Современная квантовая теория формально объясняет эффект тем, что уравнение Шредингера для волновой функции заряженной частицы во внешнем электромагнитном поле содержит потенциал этого поля. Величина потенциала определяет фазу волновой функции и приводит к возникновению интерференции даже без прямого воздействия поля на частицу.

Коллапс волновой функции: алгоритм, вдохновлённый квантовой механикой

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

Локальное подобие означает, что

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

В примерах стандартным значением N является 3.

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

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

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

Алгоритм коллапса волновой функции реализован на C++, Python, Kotlin, Rust, Julia, Haxe, JavaScript и адаптирован под Unity. Официальные исполняемые файлы можно скачать с itch.io или запустить в браузере. WFC генерирует уровни в Bad North, Caves of Qud, нескольких более мелких играх, а также во множестве прототипов. Его создание привело к новому исследованию. Другие связанные работы, объяснения, интерактивные демо, руководства, туториалы и примеры см. в разделе про порты, форки и спин-оффы.

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

Алгоритм

Считать входящее битовое изображение и подсчитать количество паттернов NxN.
1. (необязательно) Дополнить данные паттернов повёрнутыми и отражёнными паттернами.
1. Наблюдение:
  1. Найти элемент волны с минимальной ненулевой энтропией. Если таких элементов нет (если у всех элементов энтропия нулевая или неопределённая), то завершить цикл (4) и перейти к шагу (5).
  2. Коллапсировать этот элемент в состояние определённости в соответствии с его коэффициентами и распределением паттернов NxN входящих данных.
  Генерация тайловых карт
  
  Простейший нетривиальный случай алгоритма — это паттерн NxN=1×2 (точнее NxM). Если мы ещё больше упростим его, сохраняя не вероятности пар цветов, а вероятности самих цветов, то получим то, что называется «простой тайловой моделью». Фаза распространения в этой модели — это просто распространение зависимости соседства. Удобно инициализировать простую тайловую модель списком тайлов и данными об их соседстве (данные о соседстве можно рассматривать как большое множество очень маленьких сэмплов), а не сэмплируемым битовым изображением.
  
  Списки всех возможных пар соседних тайлов в практических тайлсетах могут быть достаточно длинными, поэтому чтобы укоротить перечисление, я реализовал для тайлов систему симметрии. В этой системе каждому тайлу должен назначаться его тип симметрии.
  
  Заметьте, что тайлы имеют ту же симметрию, что и назначенные им буквы (другими словами, действия диэдральной группы D4 изометричны для тайлов и соответствующих букв). Благодаря этой системе достаточно перечислить пары соседних тайлов только до их симметрии, в несколько раз укорачивает список соседей для тайлсетов со множеством симметричных тайлов (даже в тайлсете рельефа Summer, несмотря на то, что рисунки не являются симметричными, система считает такие тайлы симметричными).
  
  Заметьте, что неограниченный тайлсет из узлов (в котором допустимы все 5 тайлов) неинтересен для алгоритма WFC, потому что нельзя попасть в ситуацию, когда невозможно разместить тайл. Мы называем тайлсеты с таким свойством «простыми». Без сложных эвристик простые тайлсеты не создают интересных глобальных структур, потому что корреляции в простых тайлсетах на расстоянии быстро снижаются. Множество простых тайлетов можно найти на сайте cr31. Посмотрите там на двухсторонний тайлсет «Dual». Как он может создавать узлы (без Т-образных соединений, то есть непростые), в то же время будучи простым? Ответ заключается в том, что он может генерировать только узкий тип узлов и не может создавать произвольный узел.
  
  Стоит также заметить, что тайлсеты Circuit, Summer и Rooms не являются плитками Вана. То есть данные их соседства нельзя породить из расцветки краёв. Например, в тайлсете Circuit (интегральная схема) два уголка (Corner) не могут быть соседними, хотя и могут соединяться тайлом (Connection), а диагональные дорожки не могут менять направления.
  
  Более высокие размерности
  
  Алгоритм WFC в более высоких размерностях работает совершенно так же, как и в двух измерениях, однако здесь проблемой становится производительность. Эти воксельные модели генерировались при N=2 в тайловой модели с перекрытием при помощи блоков 5x5x5 и 5x5x2 и дополнительных эвристик (высоты, плотности, кривизны. ).
  
  Скриншоты более высоких размерностей: 1, 2, 3.
  
  Сгенерированные с помощью WFC и других алгоритмов воксельные модели будут находиться в отдельном репозитории.
  
  Синтез с ограничениями
  
  Алгоритм WFC поддерживает ограничения. Поэтому его с лёгкостью можно комбинировать с другими генеративными алгоритмами или ручным созданием.
  
  Вот, как WFC автоматически завершает уровень, начатый человеком:
  
  Алгоритм ConvChain удовлетворяет строгой версии условия (C2): создаваемое им распределение пределов паттернов NxN в выходных данных точно такое же, как распределение паттернов во входных данных. Однако ConvChain не удовлетворяет (C1): часто он создаёт заметные артефакты. Логично сначала запускать ConvChain, чтобы получать хорошо сэмплированную конфигурацию, а затем WFC для коррекции локальных артефактов. Это похоже на распространённую в оптимизации стратегию: сначала выполняем метод Монте-Карло для нахождения точки. близкой к глобальному оптимуму, а затем выполняем из этой точки градиентный спуск для большей точности.
  
  Алгоритм синтеза текстур П. Ф. Харрисона значительно быстрее, чем WFC, но у него возникают проблемы с длинными корреляциями (например, этому алгоритму сложно синтезировать текстуры кирпичных стен с правильно выстроенными кирпичами). Именно в таких случаях WFC демонстрирует своё превосходство, а алгоритм Харрисона поддерживает ограничения. Имеет смысл сначала сгенерировать с помощью WFC идеальную схему кирпичной стены, а затем выполнить для этой схемы алгоритм ограниченного синтеза текстур.
  
  Комментарии
  
  Почему используется эвристика минимальной энтропии? Я заметил, что когда люди что-то рисуют, они часто сами следуют эвристике минимальной энтропии. Именно поэтому за алгоритмом так интересно наблюдать.
  
  Модель с перекрытием соотносится с простой моделью так же, как цепи Маркова высокого порядка соотносятся с цепями Маркова первого порядка.
  
  Нужно учесть, что энтропия любого узла не может увеличиваться на этапе распространения, т.е. вероятности не повышаются, но могут быть обнулены. Когда этап распространения не может дальше уменьшать энтропию, мы активируем этап наблюдения. Если этап наблюдения не может уменьшить энтропию, это значит, что алгоритм закончил работу.
  
  Этап распространения в алгоритме WFC очень похож на цикличный алгоритм передачи сообщений (loopy belief propagation algorithm). На самом деле, я изначально программировал belief propagation (BP), но затем перешёл к распространению с ограничениями с сохраненённым стационарным распределением, потому что BP значительно медленнее без массивной параллелизации (в ЦП) и он не создавал значительно лучших результатов для моих задач.
  
  Заметьте, что сэмплы «Simple Knot» и «Trick Knot» имеют не 2, а 3 цвета.
  
  Одним из измерений может быть время. В частности, d-мерный WFC отображает поведение любого (d-1)-мерного клеточного автомата.
  
  Справочные материалы
  
  Этот проект основан на работе Пола Меррелла по синтезу моделей, в частности, на главе о дискретном синтезе моделей из его диссертации. Пол распространяет ограничения соседства в том, что мы назвали простой тайловой моделью, с эвристикой, стремящейся вычислить распространение в небольшой подвижной области.
  
  Также на мой проект сильно повлияла глава о декларативном синтезе текстур из диссертации Пола Ф. Харрисона. Пол задаёт данные о соседстве тайлов, помечая их границы и используя поиск в возвратом для заполнения тайловой карты.
  
  Сборка
  
  WFC — это консольное приложение, зависящее только от стандартной библиотеки. Скачайте .NET Core для Windows, Linux или macOS и выполните
```
dotnet run WaveFunctionCollapse.csproj
```
  Или же можно использовать инструкции сообщества по сборке для разных платформ в соответствующем issue. Кейси Маршалл создал pull request, который упрощает использование программы с командной строкой и включает пакет snap.
  
  Интересные порты, форки и спин-оффы
  - Эмиль Эрнерфельд создал порт на C++.
  - Макс Эллер создал библиотеку Kotlin (JVM) под названием Kollapse. Джозеф Роскопф создал построчный порт на Kotlin оптимизированной версии алгоритма 2018 года. Эдвин Джейкобс создал ещё одну библиотеку Kotlin.
  - Кевин Чапельер создал порт на JavaScript.
  - Оскар Сталберг запрограммировал трёхмерную тайловую модель, двухмерную тайловую модель для неравномерных сеток в сфере. Вот красивые 3D-тайлсеты для них: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15.
  - Джозеф Паркер адаптировал WFC под Unity и использовал его для генерации скейтпарков в игре Proc Skater 2016, фантастических плато в игре 2017 года Swapland и платформенных уровней в игре 2018 года Bug with a Gun.
  - Мартин О’Лири применил напоминающий WFC алгоритм для генерации поэзии: 1, 2, 3, 4.
  - Ник Ненов создал трёхмерный воксельный тайлсет, основанный на моём тайлсете Castle. Ник использует опцию текстового вывода данных в тайловую модель для воссоздания 3D-моделей в Cinema 4D.
  - Шон Лефлер реализовал модель с перекрытием на Rust.
  - rid5x создаёт версию WFC на OCaml.
  - Я опубликовал простую трёхмерную тайловую модель, чтобы люди могли создавать собственные 3D-тайлсеты, не ожидая полного репозитория трёхмерного алгоритма.
  - Я создал интерактивную модель модели с перекрытием. Исполняемый файл с GUI можно скачать страницы WFC на itch.io.
  - Брайан Баклью собрал конвейер генерации уровней для игры Caves of Qud, в нескольких проходах которого используется WFC: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21.
  - Дэнни Уайн реализовал трёхмерную тайловую модель.
  - Арви Теикари запрограммировал алгоритм синтеза текстур с энтропийной эвристикой на Lua. Headchant портировал его для работы с LÖVE.
  - Айзек Кэрт создал порт на Python модели с перекрытием.
  - Оскар Сталберг создал интерактивную версию тайловой модели, запускаемую в браузере.
  - Мэтт Рикс реализовал трёхмерную тайловую модель (1, 2, 3, 4) и создал трёхмерную тайловую модель, в которой одним из измерений является время (1, 2, 3, 4, 5).
  - Ник Ненов создал визуальное руководство по системе симметрии тайлов.
  - Айзек Кэрт и Адам М. Смит написали исследовательскую статью, в которой они формулируют WFC как ASP-задачу, используют обобщённый решатель общих ограничений clingo для генерации битовых изображений, экспериментируют с глобальными ограничениями, прослеживают историю WFC и дают подробное описание алгоритма.
  - Силвэн Лефевр создал реализацию на C++ синтеза трёхмерных моделей, описал мыслительный процесс создания сэмпла и показал пример, в котором ограничения соседства гарантируют, что выходные данные соединены (их можно обойти).
  - Я обобщил трёхмерный WFC, чтобы он работал с группой симметрии куба и создал тайлсет, генерирующий сцены в духе Эшера.
  - Существует множество способов визуализации частично наблюдаемых волновых состояний. В коде цветовые значения возможных вариантов усреднены для получения конечного цвета. Оскар Сталберг показывает частично наблюдаемые состояния как полупрозрачные прямоугольники: чем больше вариантов, тем больше прямоугольник. В воксельной схеме я визуализирую волновые состояния попиксельным голосованием.
  - Реми Дево реализовал тайловую модель в PICO-8 и написал статью о генерации когерентных данных с объяснением WFC.
  - Для своей игры Bad North Оскар Сталберг использует эвристику, которая пытается выбрать такие тайлы, чтобы на каждом этапе получившаяся наблюдаемая зона была проходимой.
  - Уильям Мэннинг реализовал модель с перекрытием на C#; в первую очередь он стремился сделать код читаемым, и дополнил WPF графическим интерфейсом.
  - Джозеф Паркер написал туториал по WFC для Procjam 2017.
  - Аман Тивари сформулировал ограничение соединения как ASP-задачу для clingo.
  - MatveyK запрограммировал трёхмерную модель с перекрытием.
  - Силвэн Лефевр, Ли Ю Вей и Коннелли Барнсисследуют возможность сокрытия информации внутри текстур. Они создали инструмент, способный кодировать текстовые сообщения как тайлы WFC и декодировать их обратно. Эта техника позволяет использовать тайлы WFC как QR-коды.
  - Матьё Фер и Натаниэль Куран значительно улучшили время выполнения WFC, для модели с перекрытием — на порядок величин. Я интегрировал их усовершенствования в код.
  - Васу Махеш портировал трёхмерную тайловую модель в TypeScript, создал новый тайлсет и визуализировал процесс генерации в WebGL.
  - Ким Хуанхи экспериментировал с трёхмерным WFC и создал/адаптировал множество воксельных тайлсетов: 1, 2, 3, 4, 5, 6, 7, 8.
  - Оскар Сталберг выступил с докладом о генерации уровней в Bad North на конференции Everything Procedural Conference 2018.
  - Я написал о том, как генерировать (приближенно) неискажённые пути между двумя точками с помощью WFC и других алгоритмов.
  - Айзер Кэрт и Адам М. Смит опубликовали препринт, в котором описывают основанную на WFC систему, которая учится на положительных и отрицательных примерах, и рассказали о ней в общем контексте диалогов с генераторами, работающими на основе примеров.
  - Брэндан Энтони использует WFC для генерации украшений стен в игре Rodina.
  - Тим Конг реализовал модель с перекрытием на Haxe.
  - Для генерации соединённых структур Boris the Brave применил к WFC метод рыхления (chiseling method). Он опубликовал библиотеку, поддерживающую сетки из шестиугольников, дополнительные ограничения и возврат назад.
  - Мариан Кляйнебергсоздал для Procjam 2018 генератор городов, основанный на тайловой модели. Он написал статью, описывающую свои подходы к заданию соседства, возврату назад и онлайн-вариации WFC.
  - Сол Бекич запрограммировал с помощью PyOpenCL тайловую модель, выполняемую на GPU. Вместо хранения очереди узлов, из которых выполняется распространение, эта модель параллельно выполняет распространение из каждого узла сетки.
  - Воутер ван Оортмерссен реализовал тайловую модель в единственной функции C++ со структурой для ускорения наблюдения, похожей на очередь с приоритетами.
  - Роберт Хёниг реализовал модель с перекрытием на Julia с опцией распространения ограничений только локально.
  - Эдвин Джейкобс применил WFC к переносу стиля и дизерингу.
  Благодарности
  
  Часть примеров взята из игр Ultima IV и Dungeon Crawl. Тайлсет Circles взят у Марио Клингеманна. Идея генерации интегральных схем была предложена Moonasaur, а их стиль был взять из игры Ruckingenur II компании Zachtronics. Пример с перекрытием Cat взят из видео Nyan Cat, пример Qud был создан Брайаном Баклью, примеры Magic Office + Spirals — rid5x, примеры с перекрытием Colored City + Link + Link 2 + Mazelike + Red Dot + Smile City — Арви Теикари. Тайлсет Summer был создан Германном Хиллманном. Воксельные модели отрендерены в MagicaVoxel.
  
  Доступное объяснение алгоритма коллапса волновой функции
  
  Алгоритм коллапса волновой функции (Wavefunction Collapse Algorithm) учит компьютер импровизировать. На входе он получает архетипичные данные и создаёт процедурно генерируемые данные, похожие на исходные.
  
  Чаще всего он используется для создания изображений, но может также строить города, скейтпарки и писать ужасные стихи.
  
  Коллапс волновой функции — это очень независимо мыслящий алгоритм, не требующий практически никакой помощи или инструкций извне. Вам нужен только пример стиля, которого нужно достичь, а всё остальное он сделает сам. Несмотря на свою самодостаточность, он на удивление прост. Он не использует никаких нейронных сетей, случайных лесов или чего-то другого, похожего на машинное обучение. Если разобраться с идеей, он станет для вас очень понятным и интуитивным.
  
  Большинство реализаций и объяснений коллапса волновой функции — это полная, оптимизированная по скорости версия алгоритма. Разумеется, все они важны и необходимы, но в них сложно разобраться с нуля. В этом посте я буду объяснять всё понятным я простым языком, сосредоточившись на версии Wavefunction с ограничениями, которую я назвал Even Simpler Tiled Model. Кроме того, я выложил пример реализации ESTM на Github. Код в нём неэффективный и медленный, но очень хорошо читаемый и подробно прокомментирован. Как только вы разберётесь в технологии, лежащей в основе 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, а более сложные модели напоминают цепи большего порядка.
  
  Wavefunction Collapse даже может учитывать дополнительные ограничения, например «этот тайл должен быть морем» или «этот пиксель должен быть красным» или «в выходных данных может быть только один монстр». Обо всё этом рассказывается README основного проекта. Также можно изучить оптимизации скорости, внесённые в полную реализацию. Необязательно повторно вычислять энторпию каждого квадрата в каждой итерации, а распространение информации по волновой функции можно сделать значительно быстрее. Эти аспекты становятся важнее при увеличении размеров выходящих изображений.
  
  Коллапс волновой функции — это красивый и мощный инструмент, который стоит освоить. Вспомните об этом, когда в следующий раз будете планировать свадьбу или генерировать процедурный мир.
  - wavefunction collapse
  - коллапс волновой функции
  - процедурная генерация
  - генерация изображений
  - Разработка игр
  - Алгоритмы
  - Обработка изображений
  - Дизайн игр
  Научный форум dxdy
  
  Квантовая механика.Коллапс волновой функции.
  
  На страницу Пред. 1 . 26 , 27 , 28 , 29 , 30 , 31 , 32 . 40 След.
  
  Re: Квантовая механика.Коллапс волновой функции.
  22.10.2014, 16:17
  
  Вот например волновая функция электрона схлопнулась в некой точке пространства-времени
  При этом определилась координата
  А что в этой точке пространства-времени происходит с импульсом? Он характеризуется величиной задающей вероятность его значения вне этой точки?
  
  Re: Квантовая механика.Коллапс волновой функции.
  22.10.2014, 16:23
  
  Заслуженный участник
  
  sdf
  Волновая функция не схлопывается в некой точке пространства-времени. Вы что, способны измерять координату с идеальной точностью? В лучшем случае, после измерения следует считать ее локализованной конфигурацией в окрестности измеренного значения. Что естественно меняет и как она выглядит в импульсном пространстве (чем точнее локализуете координату, тем больше размазываете по импульсу)
  
  Re: Квантовая механика.Коллапс волновой функции.
  22.10.2014, 16:24
  
  Заслуженный участник
  
  sdf в сообщении #921912 писал(а):
  
  Вот например волновая функция электрона схлопнулась в некой точке пространства-времени
  При этом определилась координата
  А что в этой точке пространства-времени происходит с импульсом?
  
  Слова «в этой точке пространства-времени» зачеркните, пожалуйста.
  
  Можно задать вопрос «а что происходит с импульсом электрона «. Импульс, как величина, привязан именно к электрону, а не к точке пространства-времени.
  
  Импульс тоже схлопнулся — в неопределённую величину, типа распределения
  
  На самом деле, любое реальное схлопывание координаты происходит не в одну точку, а в некоторую область конечного размера, и поэтому импульс тоже схлопывается в распределение конечного размера. Например, в гауссовский «колокольчик». По координате — очень узкий, по импульсу — очень широкий.
  
  Re: Квантовая механика.Коллапс волновой функции.
  22.10.2014, 16:33
  
  Заслуженный участник
  
  Грубо говоря, можно считать, что импульс принял все свои возможные значения сразу
  
  А вообще, интересно попытаться представить состояния в пространстве-времени как некие «пучки» существенных траекторий. Вот перед нами практически параллельный некоторому направлению набор прутиков. Но, увы, достаточно широко разбросанный. Это — состояние с хорошо определённым импульсом. А вот нечто напоминающее ежа. Торчит практически во все времениподобные напрааления сразу, но зато имеет точку пережатия. Это — состояние с определённой координатой. Ну и принцип неопребелённости сюда присовокупить. Только вместо скорости лучше использовать быстроту.
  
  Re: Квантовая механика.Коллапс волновой функции.
  23.10.2014, 00:18
  
  Последний раз редактировалось Prikol 23.10.2014, 00:19, всего редактировалось 1 раз.
  
  sdf в сообщении #921912 писал(а):
  Вот например волновая функция электрона схлопнулась в некой точке пространства-времени.
  
  Когда говорят, что «волновая функция схлопнулась», имеют ввиду, что она схлопнулась не в точку, а в очень малую область. Например, была волновая функция размазаная на несколько миллиметров, а схлопнулась до диаметра атома — порядка 1 ангстрем.
  
  sdf в сообщении #915809 писал(а):
  Почему волновая функция колапсирует именно в данной точке а не в какой либо другой?
  
  Потому что Бог играет в кости.
  Re: Квантовая механика.Коллапс волновой функции.
  23.10.2014, 00:28
  
  Заслуженный участник
  
  fizeg в сообщении #921917 писал(а):
  
  Волновая функция не схлопывается в некой точке пространства-времени. Вы что, способны измерять координату с идеальной точностью? В лучшем случае, после измерения следует считать ее локализованной конфигурацией в окрестности измеренного значения.
  
  Munin в сообщении #921918 писал(а):
  
  любое реальное схлопывание координаты происходит не в одну точку, а в некоторую область конечного размера
  
  Prikol в сообщении #922180 писал(а):
  
  Когда говорят, что «волновая функция схлопнулась», имеют ввиду, что она схлопнулась не в точку, а в очень малую область.
  
  Выключай свет! Они на свет лезут!
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 07:40
  
  Последний раз редактировалось sdf 24.10.2014, 07:58, всего редактировалось 4 раз(а).
  
  Когда я говорил об измерении электрона при котором его координаты становятся абсолютно точно определенными я имел в виду момент излучения и поглощения фотона
  Это считается измерением?
  Или и в этот момент его точное положение не определено?
  
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 12:18
  Prikol в сообщении #922180 писал(а):
  sdf в сообщении #921912 писал(а):
  Потому что Бог играет в кости.
  
  Нет.Кости играют сами.
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 17:13
  
  Разве колапс волновой функции это не мгновенная смена одной волновой функции на другую?
  И если так то разве эта смена не должна происходить в абсолютно определённой точке?
  Ничё не понимаю!
  
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 18:01
  
  Заслуженный участник
  
  sdf в сообщении #922608 писал(а):
  И если так то разве эта смена не должна происходить в абсолютно определённой точке?
  
  В какой определённой? Вот, например, была волновая функция у пары электронов $\psi(\mathbf r_1, \mathbf r_2)$ . И в некоторый момент времени — раз — и сколлапсировала в другую функцию $\varphi(\mathbf r_1, \mathbf r_2)$ . Где в этом процессе хоть какая-то выделенная чем-то точка?
  
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 19:31
  
  Заслуженный участник
  
  sdf в сообщении #922483 писал(а):
  Это считается измерением?
  Или и в этот момент его точное положение не определено?
  
  Не определено. Вот если потом кто-то определит положение фотона, то тем самым определит и место, в которой он был испущен. Опять же не точно, а только некоторую приблизительную область.
  
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 19:32
  warlock66613 в сообщении #922632 писал(а):
  
  В какой определённой? Вот, например, была волновая функция у пары электронов $\psi(\mathbf r_1, \mathbf r_2)$ . И в некоторый момент времени — раз — и сколлапсировала в другую функцию $\varphi(\mathbf r_1, \mathbf r_2)$ . Где в этом процессе хоть какая-то выделенная чем-то точка?
  
  $\psi(\mathbf r,t)$
  
  Я пологал это так: пусть есть функция , её колапс заключается в том что в какой то точке r,t она меняется на другую значение которой нужно рассматривать в этом случае толлько для t+х, где х больше или равное 0
  
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 19:48
  
  Заслуженный участник
  
  sdf в сообщении #922659 писал(а):
  
  Прекратите «пологать» и начинайте думать.
  Re: Квантовая механика.Коллапс волновой функции.
  24.10.2014, 21:13
  sdf в сообщении #922659 писал(а):
  warlock66613 в сообщении #922632 писал(а):
  
  В какой определённой? Вот, например, была волновая функция у пары электронов $\psi(\mathbf r_1, \mathbf r_2)$ . И в некоторый момент времени — раз — и сколлапсировала в другую функцию $\varphi(\mathbf r_1, \mathbf r_2)$ . Где в этом процессе хоть какая-то выделенная чем-то точка?
  
  $\psi(\mathbf r,t)$
  
  Я пологал это так: пусть есть функция , её колапс заключается в том что в какой то точке r,t она меняется на другую значение которой нужно рассматривать в этом случае толлько для t+х, где х больше или равное 0
  
  Нет я не то хотел сказать. Я имел в виду что считал что колапс это когда волновая функция зависящая от координат и времени в точке x,y,z,t заменяется на другую волновую функцию для которой x,y,z,t=0
  Похожие публикации: