Проектирование и реализация веб-симулятора кубика Рубика

Кубик Рубика — волшебная игрушка с простой структурой и бесконечными изменениями. Так как же смоделировать бесконечную трансформацию кубика Рубика в универсальном браузере и как его восстановить? Давайте рассмотрим это шаг за шагом.

Кубик Рубика Аннотация

Учащиеся, разбиравшие кубик Рубика, могут знать, что на самом деле внутренняя структура кубика Рубика включает в себя механические устройства, такие как центральная ось, пружины и винты. Но когда мы просто хотим «симулировать» его, мы просто берем его наиболее заметное свойство — набор кубов 3x3x3:

основная концепция

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

• Блоки, расположенные по углам куба, называютсяугловой блок, каждый угловой блок имеет 3 цвета. У кубика 8 углов, поэтому у кубика Рубика тоже 8 углов.
• Блоки на каждом ребре куба называютсякраевой блок, каждое ребро имеет 2 цвета. У куба 12 ребер, поэтому у кубика Рубика тоже 12 ребер.
• Блок в центре каждой стороны кубика Рубика называетсяцентральный блок, каждый центральный блок имеет только 1 цвет. У куба 6 граней, поэтому кубик Рубика также имеет 6 центральных частей.
• Блок, расположенный в центре всего куба, не имеет цвета и не играет никакой практической роли в процессе рендеринга и реставрации, мы можем игнорировать этот блок.

Складывая числа вышеупомянутых четырех блоков, это точно3^3 = 27Кусок. Единственный способ, которым вы можете манипулировать (или преобразовывать) этими блоками, — это с разных сторон.вращать. Итак, как мы идентифицируем операцию вращения?

Представьте себе, что вы держите кубик Рубика «правильно» в руке, мы определяем сторону, обращенную к вам в это время, какFront, тыльная сторона определяется какBack. Точно так же у нас естьLeft / Right / Upper / Downопределить остальные стороны. Когда вы поворачиваете грань, мы используем сокращение для этой грани (F / B / L / R / U / D), чтобы определить время на этом лице90 градусов по часовой стрелкевращать. Для вращения против часовой стрелки мы используемF' / U'ремень вот такой'знак, чтобы выразить. Если вы повернулись на 180 градусов, вы можете использовать что-то вродеR2 / U2способ выражения. Для 5 операций, показанных на рисунке ниже, если мы согласны с тем, что синяя сторона является передней, ее последовательность вращенияF' R' L' B' F':

Достаточно знать базовую структуру и преобразование кубика Рубика. Далее нам нужно рассмотреть этот вопрос:Как разработать структуру данных для сохранения состояния кубика Рубика и использовать язык программирования для реализации определенного преобразования вращения?

структура данных

Студенты, которым нравятся абстракции, основанные на «объектно-ориентированном подходе», могут быстро понять, что мы можем спроектироватьBlockбазовый класс, затем используйте что-то вродеCornerBlockа такжеEdgeBlockкласс для абстрагирования ребер и углов, и в каждом экземпляре угла вы также можете сохранить ссылку этого угла на три его смежных ребра... такой кубик РубикаCubeОбъекты должны содержать только ссылку на центральный блок, и весь куб может быть сохранен на основе свойств смежности каждого экземпляра блока.

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

Почему это возможно? Мы знаем, что когда доступ к массиву осуществляется на основе индексов, онO(1)временная сложность. и если мыПоместите каждый блок куба в трехмерную систему координат, тогда пространственные координаты каждого блока могут быть однозначно сопоставлены с нижним индексом массива.. Далее мы можем сделатьx, y, zВзять отдельно-1, 0, 1Эти три значения выражают возможные положения блока в его направлении, когда, например, когда-то определенные ранееUВращение — это в точности вращение всех блоков, значение координаты оси Y которых равно 1. Это хорошее свойство очень полезно для реализации операции преобразования кубика Рубика.

Преобразование вращения

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

При повороте на 90 градусов каждый угловой элемент на вращающейся поверхности поворачивается в положение «следующего» углового элемента на этой грани, как и краевые элементы. Поэтому мы можем легко «переместить» блок в его новую позицию, просто циклически присваивая значения «следующей» позиции каждого блока. Но этого недостаточно: каждый блок в новом положении также должен один раз «раскрутить» цвет своих шести граней, чтобы сориентировать его в правильном положении. Это также альтернативная операция присваивания. тем самым,Операция вращения в трехмерном пространстве вокруг центра некоторой поверхности разлагается на операцию перемещения и операцию вращения вокруг центра каждого блока.. С помощью чуть более 30 строк кода мы можем реализовать основной механизм трансформации этого кубика Рубика:

rotate (center, clockwise = true) {
  const axis = center.indexOf(1) + center.indexOf(-1) + 1
  // Fix y direction in right-handed coordinate system.
  clockwise = center[1] !== 0 ? !clockwise : clockwise
  // Fix directions whose faces are opposite to axis.
  clockwise = center[axis] === 1 ? clockwise : !clockwise

  let cs = [[1, 1], [1, -1], [-1, -1], [-1, 1]] // corner coords
  let es = [[0, 1], [1, 0], [0, -1], [-1, 0]] // edge coords
  const prepareCoord = coord => coord.splice(axis, 0, center[axis])
  cs.forEach(prepareCoord); es.forEach(prepareCoord)
  if (!clockwise) { cs = cs.reverse(); es = es.reverse() }

  // 移动每个块到其新位置
  const rotateBlocks = ([a, b, c, d]) => {
    const set = (a, b) => { for (let i = 0; i < 6; i++) a[i] = b[i] }
    const tmp = []; set(tmp, a); set(a, d); set(d, c); set(c, b); set(b, tmp)
  }
  const colorsAt = coord => this.getBlock(coord).colors
  rotateBlocks(cs.map(colorsAt)); rotateBlocks(es.map(colorsAt))

  // 调整每个块的自旋朝向
  const swap = [
    [[F, U, B, D], [L, F, R, B], [L, U, R, D]],
    [[F, D, B, U], [F, L, B, R], [D, R, U, L]]
  ][clockwise ? 0 : 1][axis]
  const rotateFaces = coord => {
    const block = colorsAt(coord)
    ;[block[swap[1]], block[swap[2]], block[swap[3]], block[swap[0]]] =
    [block[swap[0]], block[swap[1]], block[swap[2]], block[swap[3]]]
  }
  cs.forEach(rotateFaces); es.forEach(rotateFaces)
  return this
}

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

Учащиеся, знакомые с кубиком Рубика, должны знать,Дело не в том, что каждый кубик Рубика, раскрашенный разными цветами, можно восстановить.. В сфере обычного развития бизнеса достоверность и проверка данных часто может быть гарантирована системой типов. Но для скремблированного кубика Рубика обеспечение его разрешимости — сложная математическая задача. Поэтому, когда мы сохраняем состояние куба,Только сохраняя все шаги преобразования из начального состояния одного цвета с шести сторон в текущее состояние, можно гарантировать, что это состояние разрешимо.. Таким образом, накладные расходы на десериализацию состояния кубика Рубика делятся на количество шагов операции.O(N)ассоциация. К счастью, фактическое состояние кубика Рубика обычно находится всего в пределах 100 шагов, поэтому стоит пожертвовать временной сложностью ради достоверности данных. Кроме того, этим методом можно очень просто добиться перехода между любым состоянием кубика Рубикапутешествие во времени: От начального состояния к историческому состоянию любого шага вам нужно всего лишь наложить между ними серию операций ротации diff. Это твердая ментальная модель.

В приведенной выше реализации есть одна особенность: когда ось является осью Y, мы делаем отрицание для направления вращения. Поначалу это может показаться нелогичным, но за этим стоит проблема определения системы координат: если вы определили, где находится следующий блок при преобразовании по часовой стрелке, правосторонняя система координат, используемая в школьных учебниках и WebGL, следующая позиция каждого блока блок при вращении вокруг оси Y, а порядок перестановки обратен для осей X и Z. Напротив, в левосторонней системе координат DirectX положительное и отрицательное значение операции вращения может полностью соответствовать ориентации системы координат. Как простой фермер, автор не знает, содержит ли стоящая за этим симметрия какие-либо глубокие математические принципы.

На данный момент мы в основном завершили абстракцию состояния куба и разработку алгоритма преобразования. Но я полагаю, что многие студенты могут быть более заинтересованы в этом вопросе: как в среде браузера мы визуализируем кубик Рубика? Давайте взглянем.

Визуализация кубика Рубика

В мире браузеров, где бесчисленные двухмерные прямоугольники используются в качестве примитивов для набора текста, рендеринг трехмерного объекта, такого как кубик Рубика, невозможно выполнить, проверив документ и написав несколько строк связующего кода. К счастью, у нас есть библиотека 3D-графики, такая как WebGL (конечно, я считаю, что студенты, знакомые со стилями, должны уметь использовать CSS для рендеринга кубика Рубика, но, к сожалению, уровень CSS у автора очень низкий).

Основы рендеринга WebGL

Из-за простоты ментальной модели кубика Рубика для его рендеринга не нужно использовать расширенные функции, такие как текстуры, освещение и тени в графике, достаточно только самых основных функций геометрического рисования. Из-за этого я использую только полностью нативный WebGL API для рисования кубика Рубика здесь. Грубо говоря, шаги, необходимые для рендеринга набора кубиков, такого как кубик Рубика, примерно следующие:

1. Инициализировать шейдеры (компилировать программы для выполнения на GPU)
2. Передать вершинные и цветовые данные в буфер (манипулировать видеопамятью)
3. Установите матрицу перспективы и матрицу преобразования по модулю для просмотра (передайте переменные в графический процессор)
4. передачаdrawElementsилиdrawArrayвизуализировать кадр

В предыдущем разделе структура данных, которую мы разработали, использовала массив длиной 27 для хранения[-1, -1, -1]прибыть[1, 1, 1]ряд блоков. в тройкеforВ цикле логика отрисовки этих блоков на экран один за другим, вероятно, похожа на картинку, которую мы видели ранее:

Следует отметить, что код ближе к низу не обязательно быстрее. Например, в самой ранней реализации автор напрямую завершал визуализацию 27 небольших блоков, вызывая процедуру 3D-куба из (или копируя) MDN в цикле. В настоящее время для 27 кубов с менее чем 1000 вершин загрузка ЦП может быть полной при отрисовке анимации в 60 кадрах. После позиционирования выяснилось, что повторное взаимодействие ЦП и ГП является большим запретом: передача данных из ЦП в ГП и, наконец, вызов API отрисовки ГП имеют большие фиксированные накладные расходы. Как правило, нам нужно контролировать количество вызовов отрисовки в кадре, чтобы оно было меньше 20. Использование 27 вызовов отрисовки для 27 кубов, очевидно, является антипаттерном. После изменения кода для пакетного прохода по всем вершинам и вызова его один разdrawElements, вы можете добиться плавной анимации со скоростью 60 кадров в секунду :)

Реализация анимации вращения

После реализации базового механизма рендеринга общий эффект вращения кубика Рубика может быть достигнут путем выполнения матричного умножения на матрице по модулю представления. Матрица по модулю представления вычисляется GPU параллельно для каждой вершины в вершинном шейдере, и получается преобразованная вершина.gl_PositionМесто нахождения. Но для поворота одной грани мы решили сначала вычислить положение вершины в процессоре, а затем передать его в буфер вершин. Это напрямую связано с принципом реализации анимации вращения кубика Рубика:

• При вращении определенной грани модель данных куба не меняется, меняется только положение затронутых вершин.
• В конце вращения мы называем описанное выше реализованнымrotateAPI для «моментального поворота» модели данных куба, а затем отрисовки еще одного кадра.

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

render (rX = 0, rY = 0, moveFace = null, moveAngle = 0) {
  if (!this.gl) throw new Error('Missing WebGL context!')
  this.buffer = getBuffer(this.gl, this.blocks, moveFace, moveAngle)
  renderFrame(this.gl, this.programInfo, this.buffer, rX, rY)
}

Для поворота одного лица мы можем использовать функцию браузера.requestAnimationFrameAPI для реализации базового контроля времени. один звонокanimateвращение возвращает обещание, которое разрешается в конце одного вращения, которое реализовано следующим образом:

animate (move = null, duration = 500) {
  if (move && move.length === 0) return Promise.resolve()
  if (!move || this.__ANIMATING) throw new Error('Unable to animate!')

  this.__ANIMATING = true
  let k = move.includes("'") ? 1 : -1
  if (/B|D|L/.test(move)) k = k * -1
  const beginTime = +new Date()
  return new Promise((resolve, reject) => {
    const tick = () => {
      const diff = +new Date() - beginTime
      const percentage = diff / duration
      const face = move.replace("'", '')
      if (percentage < 1) {
        this.render(this.rX, this.rY, face, 90 * percentage * k)
        window.requestAnimationFrame(tick)
      } else {
        this.move(move)
        this.render(this.rX, this.rY, null, 0)
        this.__ANIMATING = false
        resolve()
      }
    }
    window.requestAnimationFrame(tick)
  })
}

Реализация непрерывного вращения

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

if (Array.isArray(move) && move.length > 1) {
  const lastMove = move.pop()
  // 返回递归得到的 Promise
  return this.animate(move).then(() => this.animate(lastMove))
} else if (move.length === 1) move = move[0] // 继续已有逻辑

На данный момент кубик Рубика, который могут испытать люди, в основном может работать в браузере. Но это не наша конечная цель:Как мы можем автоматически восстановить кубик Рубика?

Реставрация кубика Рубика

Алгоритм уменьшения кубика Рубика был глубоко изучен в академическом мире.Компьютер может собрать кубик Рубика в любом состоянии за 20 шагов, а также есть зрелые колеса, которые можно вызывать напрямую. Но, как бывшего любителя кубика Рубика (в старших классах), автора больше волнует "как смоделировать работу моего собственного кубика Рубика", поэтому здесь мы собираемся представить простой и понятный Первый алгоритм уровня CFOP.

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

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

1. Восстановите четыре ребра внизу, чтобы построить «крест».
2. Восстановите все углы и края нижнего и второго слоев по группам.
3. Отрегулируйте ориентацию верхнего блока так, чтобы верхняя поверхность была того же цвета.
4. Отрегулируйте порядок блоков верхнего уровня, чтобы завершить все решение.

Давайте посмотрим, что происходит на каждом этапе по очереди.

нижний крест

Этот шаг, возможно, самый простой и самый сложный.Наша цель здесь — восстановить четыре нижних края, например:

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

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

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

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

Эта простейшая стратегия близка к алгоритму разбора, когда количество символов просмотра равно 1, но здесь не требуется обратного отслеживания. Механизм реализации можно представить следующим образом:

solveCross () {
  const clonedCube = new Cube(null, this.cube.moves)
  const moveSteps = []
  while (true) {
    const lostEdgeCoords = findCrossCoords(clonedCube)
    if (!lostEdgeCoords.length) break
    moveSteps.push(solveCrossEdge(clonedCube, lostEdgeCoords[0]))
  }
  return moveSteps
}

Принцип реализации не сложен, а цена заключается в том, что слишком маленький локальный оптимум приводит к большему количеству избыточных шагов. Если вы одновременно наблюдаете 2 или более краевых состояния и возвращаете их вместе, эффективность, очевидно, может быть повышена (сложность реализации в это время также возрастает). Для сравнения, первоклассный игрок в кубик Рубика может выполнить крест за 7 шагов, а этот алгоритм требует для реализации около 20 шагов — но смысл тут дошел, так что не судите строго судей.

два нижних слоя

Цель здесь состоит в том, чтобы завершить наведение всех блоков на два нижних слоя поверх нижней поперечной отделки. Наша цель — добиться такого состояния:

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

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

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

Верхний слой одного цвета и верхний порядок

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

а потомвысший порядоккорректирование. Этот шаг меняет порядок их расположения без изменения ориентации граней и углов и, наконец, завершает восстановление всего кубика Рубика:

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

управляемый правилами дизайн

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

В процессе того же цвета на верхней поверхности верхняя поверхность, удовлетворяющая указанному выше «шаблону», может быть пропущена черезU L U' R' U L' U' Rшаги по восстановлению. Точно так же при восстановлении порядка верхнего уровня правила сопоставляются так:

Состояния верхнего уровня, которые удовлетворяют этому правилу, могут быть решены с помощью шагов, определенных правилом:R2 U' R' U' R U R U R U' R. Таким образом,Логика правил может быть полностью отделена от логики кода только путем сопоставления и выполнения правил., который становится настраиваемыми данными в формате JSON. Формат правила для восстановления первых двух слоев следующий:

{
  match: { [E]: topEdge(COLOR_F, E), [SE]: SE_D_AS_F },
  moves: "U (R U' R')"
}

Формат правила верхнего уровня того же цвета выглядит следующим образом:

{
  match: { [NW]: L, [NE]: R, [SE]: R, [SW]: L },
  moves: "R U R' U R U' R' U R U U R'"
}

Обычный формат верхнего ордера следующий:

{
  match: { [N]: W, [W]: [E], [E]: N },
  moves: "R R U' R' U' R U R U R U' R"
}

здесьNW / E / SEЭто аббревиатура для ориентации, основанной на направлении восток-запад, север-юг Цзюгунге в авторской реализации. После реализации автоматического сопоставления и применения правил можно сказать, что реализация последних трех шагов в CFOP аналогична, и основная работа сосредоточена на некоторой обработке сопоставления, связанной с вращением.

самопроверка правил

В течение всего процесса восстановления необходимо соблюдать сотни правил. Для такого количества правил, как обеспечить их правильность? В соответствии с концепцией разработки на основе тестирования TDD разработчикам необходимо писать различные утомительные тестовые примеры для достижения покрытия логики кода. Но в области кубика Рубика я нашел гораздо более элегантное свойство:Любое правило само по себе является тестовым случаем! Как это правило:

{
  match: { [N]: W, [W]: [E], [E]: N },
  moves: "R R U' R' U' R U R U R U' R"
}

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

const flip = moves => moves.map(x => x.length > 1 ? x[0] : x + "'").reverse()

OLL.forEach(rule => {
  const rMoves = flip(rule.moves)
  const cube = new Cube(null, rMoves)
  if (
    matchOrientationRule(cube, rule) &&
    isOrientationSolved(cube.move(rule.moves))
  ) {
    console.log('OLL test pass', rule.id)
  } else console.error('Error OLL rule match', rule.id)
})

На основе этого алгоритма сопоставления правил, поддерживающего самотестирование, все шаги по сборке кубика Рубика рассчитываются так :)

Результаты и послесловие

После более чем полумесяца метания в свободное время автор реализовал очень маленький симулятор сборки кубика РубикаFreecube. Он поддерживает рендеринг и пошаговое решение состояния кубика Рубика третьего порядка, а также предоставляет API для ротации и решение для повторного использования. Поскольку он не использует никаких сторонних зависимостей и использует различные «хитрости» для стремления к простоте, его размер контролируется в пределах 10 КБ после сжатия. добро пожаловать на переездGitHubДостопримечательностиXD

Freecube реализуется автором во многих местах: кафе, поезда, автобусы и даже обеденные столы... Даже если вы не умеете писать код, вы можете использовать планшет для написания и рисования для его оформления. Он вдохновлен удивительным @youngdroСообщение в блоге об алгоритме гитарных аккордов, и спасибо за подсказки здоровяка и чей-то обзор документа README XD