魔方是个结构简单而变化无穷的神奇玩具。那么如何在万能的浏览器里模拟出魔方的无尽变换，又如何将其还原呢？下面让我们一步步地来一探究竟吧。
魔方的抽象拆解过魔方的同学可能知道，现实中魔方的内部结构包含了中轴、弹簧、螺丝等机械装置。但当我们只是想要「模拟」它的时候，我们只需抓住它最显著的性质即可——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 次操作，如果我们约定蓝色一面为 Front，其旋转序列就是 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
}
复制代码
这个实现的效率应该不差：在笔者的浏览器里，上面的代码可以支持每秒 30 万次的旋转变换。为什么在这里我们需要在意性能呢？在魔方的场景下，有一个非常不同的地方，即状态的有效性与校验。
熟悉魔方的同学应该知道，并不是随便给每块涂上不同颜色的魔方都是可以还原的。在普通的业务开发领域，数据的有效性和校验常常可以通过类型系统来保证。但对于一个打乱的魔方，保证它的可解性则是一个困难的数学问题。故而我们在保存魔方状态时，只有保存从六面同色的初始状态到当前状态下的所有变换步骤，才能保证这个状态一定是可解的。这样一来，反序列化一个魔方状态的开销就与操作步骤数量之间有了 O(N) 的关联。好在一个实际把玩中的魔方状态一般只会在 100 步之内，故而上面以牺牲时间复杂度换取数据有效性的代价应当是值得的。另外，这个方式可以非常简单地实现魔方任意状态之间的时间旅行：从初始状态走到任意一步的历史状态，都只需要叠加上它们之间一系列的旋转 diff 操作即可。这是一个很可靠的思维模型。
上面的实现中有一个特别之处：当坐标轴是 y 轴时，我们为旋转方向进行了一次取反操作。这初看起来并不符合直觉，但其背后却是坐标系定义的问题：如果你推导过每个块在顺时针变换时所处的下一个位置，那么在高中教科书和 WebGL 所用的右手坐标系中，绕 y 轴旋转时各个块的下一个位置，其交换顺序与 x 轴和 z 轴是相反的。反而在 DirectX 的左手坐标系中，旋转操作的正负能完全和坐标系的朝向一致。笔者作为区区码农，并不了解这背后的对称性是否蕴含了什么深刻的数学原理，希望数学大佬们解惑。
到此为止，我们已经基本完成了对魔方状态的抽象和变换算法的设计了。但相信很多同学可能更好奇的是这个问题：在浏览器环境下，我们该如何渲染出魔方呢？让我们来看看吧。
魔方的渲染在浏览器这个以无数的二维矩形作为排版原语的世界里，要想渲染魔方这样的三维物体并不是件查个文档写几行胶水代码就可以搞定的事情。好在我们有 WebGL 这样的三维图形库可供差遣（当然了，相信熟悉样式的同学应该是可以使用 CSS 来渲染魔方的，可惜笔者的 CSS 水平很菜）。
WebGL 渲染基础由于魔方思维模型的简单性，要渲染它并不需要使用图形学中纹理、光照和阴影等高级特性，只需要最基本的几何图形绘制特性就足够了。正因为如此，笔者在这里只使用了完全原生的 WebGL API 来绘制魔方。笼统地说，渲染魔方这样的一组立方体，所需要的步骤大致如下：
- 初始化着色器（编译供 GPU 执行的程序）
- 向缓冲区中传递顶点和颜色数据（操作显存）
- 设置用于观察的透视矩阵和模-视变换矩阵（传递变量给 GPU）
- 调用 drawElements 或 drawArray 渲染一帧
在前文中，我们设计的数据结构使用了长度为 27 的数组来存储 [-1, -1, -1] 到 [1, 1, 1] 的一系列块。在一个三重的 for 循环里，逐个将这些块绘制到屏幕上的逻辑大概就像前面看到的这张图：
