Начало:
В предыдущем выпуске я описал алгоритм коллапса волновой функции. Вообще говоря, оригинальный алгоритм устроен значительно сложнее, но мне хотелось как раз уйти от сложности и выделить самую суть в минимальном количестве кода.
Тем не менее, реализация даже упрощённого алгоритма оказывается довольно сложна, или точнее сказать, громоздка.
Так что я буду двигаться потихоньку и укладывать всё как кубики.
Данные
У нас очевидно есть некая матрица и нужно кодировать состояния её ячеек. Причём эти состояния могут находиться в суперпозиции.
Отдельных, базовых состояний всего 9 шт.
Исходя из того, в какой стороне клетки находится красный блок, их можно условно назвать "верх", "низ", "лево", "право", "верх-лево", "верх-право" и т.д. Названия можно преобразовать в коды: L – левый, R – правый, UL – верхний левый и т.д.
Я буду писать на языке JavaScript. Он позволяет делать онлайн-демонстрации прямо в браузере.
Для кодирования суперпозиции воспользуемся множеством.
Как инициализируется множество? Сначала нужно инициализировать массив элементов:
['n', 'u', 'd', 'l', 'r', 'ul', 'ur', 'dl', 'dr']
А затем передать его в конструктор множества, то есть класса Set().
Теперь наше множество содержит все возможные коды состояний ячеек.
Далее в каждую клетку матрицы надо поместить по множеству. Но чтобы не создавать новые множества, я буду просто хранить в клетках null.
Если я встречу в клетке null, то буду заменять это значение на множество superposition.
Матрица будет размером 20 * 20 клеток.
А точнее, это не двумерная матрица 20*20, а линейный массив длиной 400 элементов. Двумерность существует только в голове, а необходимые преобразования координат уже неоднократно описывались, например, в игре Robots.
Получение контента клетки я инкапсулировал в отдельную функцию:
Процесс схлопывания
Каждая клетка матрицы будет содержать множество, представляющее текущую суперпозицию элементов. Чтобы схлопнуть суперпозицию, нужно из множества удалить ненужные элементы. Это делается с помощью метода delete().
Например, чтобы удалить из множества state состояние с кодом 'r', я напишу:
state.delete('r');
Однако по факту эта операция у меня не используется, так как оказалась не нужна.
Когда нужно схлопнуть случайную клетку до единственного состояния, то предположительно мы должны выбрать одно из состояний, а затем удалить все остальные с помощью delete().
Но это очевидно порождает неудобства в виде обхода множества циклом и т.п.
Поэтому вместо этого я выбираю случайный элемент множества и помещаю его в новое множество, а старое просто выбрасывается. Эффективность данного процесса меня пока не волнует.
Я написал функцию для выбора случайного элемента из множества:
Нужно сначала получить из множества массив, затем выбрать случайный индекс в массиве, и затем взять элемент по этому индексу.
Множество возвращает свои элементы через метод keys(). Но этот метод возвращает не массив, а итератор для обхода циклом. Чтобы превратить его в массив, мы вынуждены воспользоваться конструкцией Array.from(setObj.keys()).
Функцию randint() для выбора целого числа из диапазона я также взял из проекта Robots.
Теперь можно написать схлопывание суперпозиции до одного состояния:
Как видите, вместо удаления ненужных элементов из множества я просто делаю новое множество с нужным элементом.
Уменьшение количества состояний
Схлопнутая клетка должна влиять на соседние клетки, уменьшая количество их возможных состояний. Для этого мы должны знать, какое конкретное состояние совместимо с каким множеством других состояний.
Эту совместимость мы будем задавать отдельно в виде правил, а пока задача сводится к тому, чтобы построить пересечение множеств. Нужно взять множество совместимых состояний и наложить его на множество состояний, хранящихся в клетке. Пересечение этих множеств даст нам оставшиеся возможные состояния.
В JavaScript нет готового метода для пересечения множеств, поэтому его надо написать:
Здесь pool это множество совместимых состояний, а state это множество состояний клетки.
Мы проходим по всем элементам pool и проверяем, есть ли такой элемент в state. Если есть, мы добавляем его в результирующее множество intersect.
Обратите внимание, что для обхода элементов множества используется конструкция
for (let k of pool)
а не
for (let k in pool)
Абсолютно непонятно, по каким причинам надо было так делать, но что имеем, то имеем. Теперь кроме in у нас есть ещё и of.
Инструментарий для работы готов. В следующих выпусках оформим графический вывод, определим правила совместимости и запрограммируем алгоритм.
Читайте дальше: