整合營(yíng)銷服務(wù)商
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
電腦端+手機(jī)端+微信端=數(shù)據(jù)同步管理
免費(fèi)咨詢熱線：
方是個(gè)結(jié)構(gòu)簡(jiǎn)單而變化無窮的神奇玩具。那么如何在萬能的瀏覽器里模擬出魔方的無盡變換，又如何將其還原呢？下面讓我們一步步地來一探究竟吧。
拆解過魔方的同學(xué)可能知道，現(xiàn)實(shí)中魔方的內(nèi)部結(jié)構(gòu)包含了中軸、彈簧、螺絲等機(jī)械裝置。但當(dāng)我們只是想要「模擬」它的時(shí)候，我們只需抓住它最顯著的性質(zhì)即可——3x3x3 的一組立方體：
上圖演示了魔方最基本的思維模型。但光有這樣的感性認(rèn)識(shí)還不夠：組成魔方的每個(gè)塊并非隨意安置，它們之間有著細(xì)微的區(qū)別：
將以上四種塊的數(shù)量相加，正好是 3^3=27 塊。對(duì)這些塊，你所能使用的唯一操作（或者說變換）方式，就是在不同面上的旋轉(zhuǎn)。那么，我們?cè)撊绾螛?biāo)識(shí)出一次旋轉(zhuǎn)操作呢？
設(shè)想你的手里「端正地」拿著一個(gè)魔方，我們將此時(shí)面對(duì)你的那一面定義為 Front，背對(duì)的一面定義為 Back。類似地，我們有了 Left / Right / Upper / Down 來標(biāo)識(shí)其余各面。當(dāng)你旋轉(zhuǎn)某一面時(shí)，我們用這一面的簡(jiǎn)寫（F / B / L / R / U / D）來標(biāo)識(shí)在這一面上的一次順時(shí)針 90 度旋轉(zhuǎn)。對(duì)于一次逆時(shí)針的旋轉(zhuǎn)，我們則用 F' / U' 這樣帶 ' 的記號(hào)來表達(dá)。如果你旋轉(zhuǎn)了 180 度，那么可以用形如 R2 / U2 的方式表示。如下圖的 5 次操作，如果我們約定藍(lán)色一面為 Front，其旋轉(zhuǎn)序列就是 F' R' L' B' F'：
關(guān)于魔方的基礎(chǔ)結(jié)構(gòu)和變換方式，知道這些就足夠了。下面我們需要考慮這個(gè)問題：如何設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)來保存的魔方狀態(tài)，并使用編程語言來實(shí)現(xiàn)某個(gè)旋轉(zhuǎn)變換呢？
喜歡基于「面向?qū)ο蟆钩橄蟮耐瑢W(xué)可能很快就能想到，我們可以為每個(gè)塊設(shè)計(jì)一個(gè) Block 基類，然后用形如 CornerBlock 和 EdgeBlock 的類來抽象棱塊和角塊，在每個(gè)角塊實(shí)例中還可以保存這個(gè)角塊到它相鄰三個(gè)棱塊的引用……這樣一個(gè)魔方的 Cube 對(duì)象只需持有對(duì)中心塊的引用，就可以基于各塊實(shí)例的鄰接屬性保存整個(gè)魔方了。
上面這種實(shí)現(xiàn)很類似于鏈表，它可以 O(1) 地實(shí)現(xiàn)「給定某個(gè)塊，查找其鄰接塊」的操作，但不難發(fā)現(xiàn)，它需要 O(N) 的復(fù)雜度來實(shí)現(xiàn)形如「某個(gè)位置的塊在哪里」這樣的查找操作，基于它的旋轉(zhuǎn)操作也并不十分符合直覺。相對(duì)地，另一種顯得「過于暴力」的方式反而相當(dāng)實(shí)用：直接開辟一個(gè)長(zhǎng)度為 27 的數(shù)組，在其中存儲(chǔ)每一塊的顏色信息即可。
為什么可以這樣呢？我們知道，數(shù)組在基于下標(biāo)訪問時(shí)，具有 O(1) 的時(shí)間復(fù)雜度。而如果我們在一個(gè)三維坐標(biāo)系中定位魔方的每一個(gè)塊，那么每個(gè)塊的空間坐標(biāo)都可以唯一地映射到數(shù)組的下標(biāo)上。更進(jìn)一步地，我們可以令 x, y, z 分別取 -1, 0, 1 這三個(gè)值來表達(dá)一個(gè)塊在其方向上可能的位置，這時(shí)，例如前面所定義的一次 U 旋轉(zhuǎn)，剛好就是對(duì)所有 y 軸坐標(biāo)值為 1 的塊的旋轉(zhuǎn)。這個(gè)良好的性質(zhì)很有利于實(shí)現(xiàn)對(duì)魔方的變換操作。
在約定好數(shù)據(jù)結(jié)構(gòu)之后，我們?nèi)绾螌?shí)現(xiàn)對(duì)魔方的一次旋轉(zhuǎn)變換呢？可能有些同學(xué)會(huì)直接將這個(gè)操作與三維空間中的四階變換矩陣聯(lián)系起來。但只要注意到一次旋轉(zhuǎn)的角度都是 90 度的整數(shù)倍，我們可以利用數(shù)學(xué)性質(zhì)極大地簡(jiǎn)化這一操作：
在旋轉(zhuǎn) 90 度時(shí)，旋轉(zhuǎn)面上每個(gè)角塊都旋轉(zhuǎn)到了該面上的「下一個(gè)」角塊的位置上，棱塊也是這樣。故而，我們只需要循環(huán)交替地在每個(gè)塊的「下一個(gè)」位置賦值，就能輕松地將塊「移動(dòng)」到其新位置上。但這還不夠：每個(gè)新位置上的塊，還需要對(duì)其自身六個(gè)面的顏色做一次「自旋」，才能將它的朝向指向正確的位置。這也是一次交替的賦值操作。從而，一次三維空間繞某個(gè)面中心的旋轉(zhuǎn)操作，就被我們分解為了一次平移操作和一次繞各塊中心的旋轉(zhuǎn)操作。只需要 30 余行代碼，我們就能實(shí)現(xiàn)這一魔方最核心的變換機(jī)制：
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() }
// 移動(dòng)每個(gè)塊到其新位置
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))
// 調(diào)整每個(gè)塊的自旋朝向
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
}
復(fù)制代碼這個(gè)實(shí)現(xiàn)的效率應(yīng)該不差：在筆者的瀏覽器里，上面的代碼可以支持每秒 30 萬次的旋轉(zhuǎn)變換。為什么在這里我們需要在意性能呢？在魔方的場(chǎng)景下，有一個(gè)非常不同的地方，即狀態(tài)的有效性與校驗(yàn)。
熟悉魔方的同學(xué)應(yīng)該知道，并不是隨便給每塊涂上不同顏色的魔方都是可以還原的。在普通的業(yè)務(wù)開發(fā)領(lǐng)域，數(shù)據(jù)的有效性和校驗(yàn)常常可以通過類型系統(tǒng)來保證。但對(duì)于一個(gè)打亂的魔方，保證它的可解性則是一個(gè)困難的數(shù)學(xué)問題。故而我們?cè)诒４婺Х綘顟B(tài)時(shí)，只有保存從六面同色的初始狀態(tài)到當(dāng)前狀態(tài)下的所有變換步驟，才能保證這個(gè)狀態(tài)一定是可解的。這樣一來，反序列化一個(gè)魔方狀態(tài)的開銷就與操作步驟數(shù)量之間有了 O(N) 的關(guān)聯(lián)。好在一個(gè)實(shí)際把玩中的魔方狀態(tài)一般只會(huì)在 100 步之內(nèi)，故而上面以犧牲時(shí)間復(fù)雜度換取數(shù)據(jù)有效性的代價(jià)應(yīng)當(dāng)是值得的。另外，這個(gè)方式可以非常簡(jiǎn)單地實(shí)現(xiàn)魔方任意狀態(tài)之間的時(shí)間旅行：從初始狀態(tài)走到任意一步的歷史狀態(tài)，都只需要疊加上它們之間一系列的旋轉(zhuǎn) diff 操作即可。這是一個(gè)很可靠的思維模型。
上面的實(shí)現(xiàn)中有一個(gè)特別之處：當(dāng)坐標(biāo)軸是 y 軸時(shí)，我們?yōu)樾D(zhuǎn)方向進(jìn)行了一次取反操作。這初看起來并不符合直覺，但其背后卻是坐標(biāo)系定義的問題：如果你推導(dǎo)過每個(gè)塊在順時(shí)針變換時(shí)所處的下一個(gè)位置，那么在高中教科書和 WebGL 所用的右手坐標(biāo)系中，繞 y 軸旋轉(zhuǎn)時(shí)各個(gè)塊的下一個(gè)位置，其交換順序與 x 軸和 z 軸是相反的。反而在 DirectX 的左手坐標(biāo)系中，旋轉(zhuǎn)操作的正負(fù)能完全和坐標(biāo)系的朝向一致。筆者作為區(qū)區(qū)碼農(nóng)，并不了解這背后的對(duì)稱性是否蘊(yùn)含了什么深刻的數(shù)學(xué)原理，希望數(shù)學(xué)大佬們解惑。
到此為止，我們已經(jīng)基本完成了對(duì)魔方狀態(tài)的抽象和變換算法的設(shè)計(jì)了。但相信很多同學(xué)可能更好奇的是這個(gè)問題：在瀏覽器環(huán)境下，我們?cè)撊绾武秩境瞿Х侥兀孔屛覀儊砜纯窗伞?/p>
在瀏覽器這個(gè)以無數(shù)的二維矩形作為排版原語的世界里，要想渲染魔方這樣的三維物體并不是件查個(gè)文檔寫幾行膠水代碼就可以搞定的事情。好在我們有 WebGL 這樣的三維圖形庫可供差遣（當(dāng)然了，相信熟悉樣式的同學(xué)應(yīng)該是可以使用 CSS 來渲染魔方的，可惜筆者的 CSS 水平很菜）。
由于魔方思維模型的簡(jiǎn)單性，要渲染它并不需要使用圖形學(xué)中紋理、光照和陰影等高級(jí)特性，只需要最基本的幾何圖形繪制特性就足夠了。正因?yàn)槿绱耍P者在這里只使用了完全原生的 WebGL API 來繪制魔方。籠統(tǒng)地說，渲染魔方這樣的一組立方體，所需要的步驟大致如下：
在前文中，我們?cè)O(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)使用了長(zhǎng)度為 27 的數(shù)組來存儲(chǔ) [-1, -1, -1] 到 [1, 1, 1] 的一系列塊。在一個(gè)三重的 for 循環(huán)里，逐個(gè)將這些塊繪制到屏幕上的邏輯大概就像前面看到的這張圖：
需要注意的是，并不是越接近底層的代碼就一定越快。例如在最早的實(shí)現(xiàn)中，筆者直接通過循環(huán)調(diào)用來自（或者說抄自）MDN 的 3D 立方體例程來完成 27 個(gè)小塊的渲染。這時(shí)對(duì)于 27 個(gè)立方體區(qū)區(qū)不足千個(gè)頂點(diǎn)，60 幀繪制動(dòng)畫時(shí)的 CPU 占用率都可能跑滿。經(jīng)過定位，發(fā)現(xiàn)重復(fù)的 CPU 與 GPU 交互是一個(gè)大忌：從 CPU 向 GPU 傳遞數(shù)據(jù)，以及最終對(duì) GPU 繪圖 API 的調(diào)用，都具有較大的固定開銷。一般我們需要將一幀中 Draw Call 的數(shù)量控制在 20 個(gè)以內(nèi)，對(duì)于 27 個(gè)立方體就使用 27 次 Draw Call 的做法顯然是個(gè)反模式。在將代碼改造為一次批量傳入全部頂點(diǎn)并調(diào)用一次 drawElements 后，即可實(shí)現(xiàn)流暢的 60 幀動(dòng)畫了 :)
在實(shí)現(xiàn)基本的渲染機(jī)制后，魔方整體的旋轉(zhuǎn)效果可以通過對(duì)模-視矩陣做矩陣乘法來實(shí)現(xiàn)。模-視矩陣會(huì)在頂點(diǎn)著色器由 GPU 中對(duì)每一個(gè)頂點(diǎn)并行地計(jì)算，得到頂點(diǎn)變換后的 gl_Position 位置。但對(duì)于單個(gè)面的旋轉(zhuǎn)，我們選擇了先在 CPU 中計(jì)算好頂點(diǎn)位置，再將其傳入頂點(diǎn)緩沖區(qū)。這和魔方旋轉(zhuǎn)動(dòng)畫的實(shí)現(xiàn)原理直接相關(guān)：
我們首先需要設(shè)計(jì)用于渲染一幀的 render API。考慮到魔方在繪制時(shí)可能存在對(duì)某個(gè)面一定程度的旋轉(zhuǎn)，這個(gè)無狀態(tài)的渲染 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)
}
復(fù)制代碼而對(duì)單個(gè)面的旋轉(zhuǎn)過程中，我們可以使用瀏覽器的 requestAnimationFrame API 來實(shí)現(xiàn)基本的時(shí)序控制。一次調(diào)用 animate 的旋轉(zhuǎn)返回一個(gè)在單次旋轉(zhuǎn)結(jié)束時(shí) resolve 的 Promise，其實(shí)現(xiàn)如下：
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)
})
}
復(fù)制代碼在實(shí)現(xiàn)了單次旋轉(zhuǎn)后，如何支持連續(xù)的多次旋轉(zhuǎn)呢？本著能偷懶就偷懶的想法，筆者對(duì)上面的函數(shù)進(jìn)行了不改動(dòng)已有邏輯的遞歸化改造，只需要在原函數(shù)入口處加入如下幾行，就可以使支持傳入數(shù)組為參數(shù)來遞歸調(diào)用自身，并在傳入的連續(xù)動(dòng)畫數(shù)組長(zhǎng)度為 1 時(shí)作為遞歸的出口，從而輕松地實(shí)現(xiàn)連續(xù)的動(dòng)畫效果：
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] // 繼續(xù)已有邏輯
復(fù)制代碼到這里，一個(gè)可以供人體驗(yàn)的魔方基本就可以在瀏覽器里跑起來了。但這還不是我們最終的目標(biāo)：我們?cè)撛趺醋詣?dòng)還原一個(gè)魔方呢？
魔方的還原算法在學(xué)術(shù)界已有很深入的研究，計(jì)算機(jī)在 20 步之內(nèi)可以解出任意狀態(tài)的魔方，也有成熟的輪子可以直接調(diào)用。但作為一個(gè)（高中時(shí)）曾經(jīng)的魔方業(yè)余愛好者，筆者這里更關(guān)注的是「如何模擬出我自己還原魔方的操作」，故而在這里我們要介紹的是簡(jiǎn)單易懂的 CFOP 層先算法。
在開始前，有必要強(qiáng)調(diào)一個(gè)前文中一筆帶過的概念：在旋轉(zhuǎn)時(shí)，魔方中心塊之間的相對(duì)位置始終不會(huì)發(fā)生變化。如下圖：
因此，在魔方旋轉(zhuǎn)時(shí)，我們只需關(guān)注角塊和棱塊是否歸位即可。在 CFOP 層先法中，歸位全部角塊和棱塊的步驟，被分為了逐次遞進(jìn)的四步：
讓我們依次來看看每一步都發(fā)生了什么吧。
這一步可以說是最簡(jiǎn)單也最難的，在此我們的目標(biāo)是還原四個(gè)底部棱塊，像這樣：
對(duì)一個(gè)完全打亂的魔方，每個(gè)目標(biāo)棱塊都可能以兩種不同的朝向出現(xiàn)在任意一個(gè)棱塊的位置上。為什么有兩種朝向呢？請(qǐng)看下圖：
這是最簡(jiǎn)單的一種情形，此時(shí)直接做一次 R2 旋轉(zhuǎn)即可使紅白棱塊歸位。但下面這種情況也是完全合法的：
這時(shí)由于棱塊的朝向不同，所需的步驟就完全不同了。但總的來說，構(gòu)成十字所需的棱塊可能出現(xiàn)的位置總是有限的。拆解分類出所有可能的情形后，我們不難使用貪心策略來匹配：
這個(gè)最簡(jiǎn)單的策略很接近語法分析中向前看符號(hào)數(shù)量為 1 時(shí)的算法，不過這里不需要回溯。實(shí)現(xiàn)機(jī)制可以抽象如下：
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
}
復(fù)制代碼這個(gè)實(shí)現(xiàn)原理并不復(fù)雜，其代價(jià)就是過小的局部最優(yōu)造成了較多的冗余步驟。如果同時(shí)觀察 2 個(gè)甚至更多的棱塊狀態(tài)并將其一并歸位，其效率顯然能得到提升（這時(shí)的實(shí)現(xiàn)難度也是水漲船高）。作為對(duì)比，一流的魔方玩家可以在 7 步內(nèi)完成十字，但這個(gè)算法實(shí)現(xiàn)卻需要 20 步左右——不過這里意思已經(jīng)到了，各位看官就先不要太苛刻啦。
這里的目標(biāo)是在底部十字完成的基礎(chǔ)上，完成底部?jī)蓪铀袎K的歸位。我們的目標(biāo)是實(shí)現(xiàn)這樣的狀態(tài)：
這個(gè)步驟中，我們以 Slot 和 Pair 的概念作為還原的基本元素。相鄰的十字之間所間隔的一個(gè)棱和一個(gè)角，構(gòu)成了一個(gè) Slot，而它們所對(duì)應(yīng)的兩個(gè)目標(biāo)塊則稱為一個(gè) Pair。故而這個(gè)步驟中，我們只需要重復(fù)四次將 Pair 放入 Slot 中的操作即可。一次最簡(jiǎn)單的操作大概是這樣的：
上圖將頂層的一對(duì) Pair 放入了藍(lán)紅相間的 Slot 中。類似于之前解十字時(shí)的情形，這一步中的每個(gè)棱塊和角塊也有不同的位置和朝向。如果它們都在頂層，那么我們可以通過已有的匹配規(guī)則來實(shí)現(xiàn)匹配；如果它們?cè)谄渌?Slot 中，那么我們就遞歸地執(zhí)行「將 Pair 從其它 Slot 中旋出」的算法，直到這組 Pair 都位于頂層為止。
這一步的還原算法與下面的步驟相當(dāng)接近，稍后一并介紹。
完成了前兩層的還原后，我們最后所需要處理的就是頂層的 8 個(gè)棱塊與角塊了。首先是頂面同色的步驟，將各塊調(diào)整到正確的朝向，實(shí)現(xiàn)頂面同色（一般采用白色作為底面，此時(shí)按照約定，黃色為頂面）：
而后是頂層順序的調(diào)整。這一步在不改變棱與角朝向的前提下，改變它們的排列順序，最終完成整個(gè)魔方的還原：
從前兩層的還原到頂層的還原步驟中，都有大量的魔方公式規(guī)則可供匹配使用。如何將這些現(xiàn)成的規(guī)則應(yīng)用到還原算法中呢？我們可以使用規(guī)則驅(qū)動(dòng)的方式來使用它們。
了解編譯過程的同學(xué)應(yīng)該知道，語法分析的過程可以通過編寫一系列的語法規(guī)則來實(shí)現(xiàn)。而在魔方還原時(shí)，我們也有大量的規(guī)則可供使用。一條規(guī)則的匹配部分大概是這樣的：
在頂面同色過程中，滿足上述 "pattern" 的頂面，可以通過 U L U' R' U L' U' R 的步驟來還原。類似地，在還原頂層順序時(shí)，規(guī)則的匹配方式形如這樣：
滿足這條規(guī)則的頂層狀態(tài)可以通過該規(guī)則所定義的步驟求解：R2 U' R' U' R U R U R U' R。這樣一來，只需要實(shí)現(xiàn)對(duì)規(guī)則的匹配和執(zhí)行操作，規(guī)則的邏輯就可以完全與代碼邏輯解耦，變?yōu)榭膳渲玫?JSON 格式數(shù)據(jù)。用于還原前兩層的一條規(guī)則格式形如：
{
match: { [E]: topEdge(COLOR_F, E), [SE]: SE_D_AS_F },
moves: "U (R U' R')"
}
復(fù)制代碼頂層同色的規(guī)則格式形如：
{
match: { [NW]: L, [NE]: R, [SE]: R, [SW]: L },
moves: "R U R' U R U' R' U R U U R'"
}
復(fù)制代碼頂面順序的規(guī)則格式形如：
{
match: { [N]: W, [W]: [E], [E]: N },
moves: "R R U' R' U' R U R U R U' R"
}
復(fù)制代碼這里的 NW / E / SE 是筆者的實(shí)現(xiàn)中基于九宮格東西南北方向定位的簡(jiǎn)寫。在實(shí)現(xiàn)了對(duì)規(guī)則的自動(dòng)匹配和應(yīng)用之后，CFOP 中后面三步的實(shí)現(xiàn)方式可以說大同小異，主要的工作集中在一些與旋轉(zhuǎn)相關(guān)的 mapping 處理。
在整個(gè)還原過程中，一共有上百條規(guī)則需要匹配。對(duì)于這么多的規(guī)則，該如何保證它們的正確性呢？在 TDD 測(cè)試驅(qū)動(dòng)開發(fā)的理念中，開發(fā)者需要通過編寫各種繁冗的測(cè)試用例來實(shí)現(xiàn)對(duì)代碼邏輯的覆蓋。但在魔方領(lǐng)域，筆者發(fā)現(xiàn)了一種優(yōu)雅得多的性質(zhì)：任何一條規(guī)則本身，就是自己的測(cè)試用例！如這條規(guī)則：
{
match: { [N]: W, [W]: [E], [E]: N },
moves: "R R U' R' U' R U R U R U' R"
}
復(fù)制代碼我們只需要將 moves 中的每一步順序顛倒地輸入初始狀態(tài)的魔方，就可以用這個(gè)狀態(tài)來驗(yàn)證規(guī)則是否能夠匹配，以及魔方是否能基于該規(guī)則還原了。這個(gè)性質(zhì)使得我很容易地編寫了下面這樣簡(jiǎn)單的代碼，自動(dòng)驗(yàn)證每條輸入規(guī)則的正確性：
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)
})
復(fù)制代碼在這個(gè)支持自測(cè)試的規(guī)則匹配算法基礎(chǔ)上，求解魔方的全部步驟就這樣計(jì)算出來了 :)
經(jīng)過半個(gè)多月業(yè)余時(shí)間的折騰，筆者實(shí)現(xiàn)了一個(gè)非常小巧的魔方求解模擬器 Freecube。它支持三階魔方狀態(tài)的渲染和逐步求解，還提供了旋轉(zhuǎn)與求解的 API 可供復(fù)用。由于它沒有使用任何第三方依賴并使用了各種力求精簡(jiǎn)的「技巧」，因而它的體積被控制在了壓縮后 10KB 內(nèi)。歡迎移步 GitHub 觀光 XD
Freecube 案例地址：https://ewind.us/h5/freecube/
Freecube 是筆者在很多地方忙里偷閑地實(shí)現(xiàn)的：咖啡廳、動(dòng)車、公交車甚至飯桌上……即便寫不了代碼的場(chǎng)合，也可以拿平板寫寫畫畫來設(shè)計(jì)它。它的靈感來自于 @youngdro 神奇的吉他和弦算法博文，
https://juejin.im/post/5b2627d051882574ac7848a4
另外感謝大佬的指點(diǎn)和某人對(duì) README 文檔的審校 XD
Github地址：https://github.com/doodlewind/freecube
原地址：https://juejin.im/post/5b837c0b51882542d950efb4
久沒參與魔方的發(fā)布工作了，今天提筆，有種莫名的生疏和惶恐，從下午四點(diǎn)半一直坐到現(xiàn)在，3個(gè)小時(shí)，刪刪寫寫。千言無語，千頭萬緒，千百般滋味涌上心頭，真的很懷念那些年每個(gè)周五定期一更的日子，簡(jiǎn)單而快樂。
2006年12月Vista優(yōu)化大師發(fā)布第一個(gè)測(cè)試版，再到2009年9月發(fā)布魔方0.1，時(shí)光荏苒，便過去了9年。很多當(dāng)初最早的那批朋友，現(xiàn)在都成了老友，有時(shí)候一覺醒來，發(fā)現(xiàn)軟媒的那個(gè)最老用戶群里的消息閃爍，由衷的開心，沒有什么比熟悉的感覺更有韻味。
產(chǎn)品部的魔方一哥過來催文了，盡管他說理解我的心情啊什么的，但是為了保持一貫的不加班作風(fēng)，我得直入主題了——
魔方6.16正式版現(xiàn)在發(fā)布，“忍不住”還是讓產(chǎn)品組加了新功能，本來說好的要克制加新功能的沖動(dòng)，重點(diǎn)大幅改進(jìn)清理等原有常用功能的。
這次忍不住要加的新功能，大家在標(biāo)題里面已經(jīng)看到了，就是一鍵提取微軟官方的精美聚焦壁紙（美化大師頂部加入了“聚焦壁紙”）。熟悉微軟的朋友都知道，Win10TH2開始系統(tǒng)增加了“Windows 聚焦”壁紙，大家在系統(tǒng)設(shè)置的“個(gè)性化”-“鎖屏設(shè)置”里面可以設(shè)置鎖屏的背景壁紙為“Windows 聚焦”，如下圖所示：
這些微軟官方提供的鎖屏壁紙還是非常精美的，會(huì)自動(dòng)的下載并切換，于是魔方便加入了提取功能，需要注意的是，這兒的提取，是提取的本機(jī)已經(jīng)下載的，如果您之前沒有開啟過Windows聚焦功能，是抓不到的。這個(gè)抓取功能更方便的是讓大家隨時(shí)保存最新的。那過去的好看聚焦壁紙?jiān)趺崔k？別著急，我們?cè)谲浖缑嫣峁┝怂蠾in10歷史聚焦壁紙下載大全的鏈接，很貼心的說。
當(dāng)然，這次魔方還有其他的有愛更新，例如清理大師的重復(fù)文件查找支持了批量選擇和刪除操作，例如設(shè)置大師中加入了讓資源管理器關(guān)閉mkv文件的預(yù)覽以防止卡頓，軟媒雷達(dá)、軟媒時(shí)間、WiFi助手、軟媒壓縮等都有界面和功能修復(fù)改進(jìn)。
具體更新內(nèi)容的細(xì)節(jié)，請(qǐng)看下面的更新歷史吧！
PS：按照慣例，軟媒魔方將在發(fā)布數(shù)十分鐘后才放開自動(dòng)升級(jí)。
一、軟媒魔方更新歷史
軟媒魔方 6.1.6.0 正式版 - 2015年12月17日
魔方主程序 6.1.6.0：
新增：應(yīng)用大全 - 增加旗魚瀏覽器PC版入口
軟媒美化大師 3.6.9.0：
新增：針對(duì)Win10 TH2增加Windows聚焦壁紙一鍵提取功能
軟媒時(shí)間 3.1.3.0：
修正：界面 - 多云和陰天的小圖標(biāo)弄反的問題修正：界面 - 系統(tǒng)開啟高DPI的時(shí)候，窗口太小的問題
軟媒清理大師 3.7.3.0：
新增：隱私清理 - Office 2016打開歷史記錄清理
改進(jìn)：重復(fù)文件查找 - 支持批量操作改進(jìn)：注冊(cè)表清理 - 屏蔽注冊(cè)表清理功能
修正：隱私清理 - Office 2013打開歷史記錄清理不掉的問題
軟媒設(shè)置大師 3.6.8.0：
新增：資源管理器 - 關(guān)閉MKV視頻預(yù)覽
軟媒雷達(dá) 6.0.7.0：
修正：本機(jī)信息 - 讀取IE的Flash Player版本號(hào)錯(cuò)誤的問題修正：界面 - 系統(tǒng)開啟高DPI的時(shí)候，窗口太小的問題
軟媒IE管理大師 1.9.8.0：
修正：界面 - 系統(tǒng)開啟高DPI的時(shí)候，窗口太小的問題
軟媒WiFi助手 1.1.8.0：
修正：穩(wěn)定性 - 啟動(dòng)WiFi助手時(shí)可能發(fā)生的崩潰問題
軟媒壓縮 1.1.5.0：
修正：界面 - 系統(tǒng)開啟高DPI的時(shí)候，窗口太小的問題
二、為什么大家都在用魔方？
軟媒魔方好不好？軟媒魔方有什么用？為什么要用軟媒魔方？
先列出一些基本組件功能：
1、清理大師：一鍵清理、深度清理、注冊(cè)表清理、字體清理，還有隱私清理。。。難道你不需要？
2、美化大師：改系統(tǒng)字體、DIY win7開始按鈕、設(shè)置開機(jī)動(dòng)畫、破解系統(tǒng)主題、修改系統(tǒng)聲音。。。怎么個(gè)性怎么玩，美化大師全搞定！
3、優(yōu)化大師：一鍵加速、添加、刪除系統(tǒng)啟動(dòng)項(xiàng)，讓你輕松掌控系統(tǒng)進(jìn)程的開啟！
4、軟媒時(shí)間，軟媒全球首創(chuàng)獨(dú)創(chuàng)的創(chuàng)意，任務(wù)欄時(shí)間區(qū)加入農(nóng)歷、天氣等顯示，不占任何額外空間，超NB！
5、軟媒桌面：哈，Windows系統(tǒng)里多了類似蘋果Mac OS X的快捷欄，方便大發(fā)了。
6、軟件管家：精選裝機(jī)必備軟件大全，下載杠杠的……
7、系統(tǒng)雷達(dá)：任務(wù)欄窗口+桌面懸浮窗自由隨意選擇，實(shí)時(shí)監(jiān)控網(wǎng)絡(luò)流量、CPU、內(nèi)存占用、磁盤讀寫，簡(jiǎn)單、清晰、方便！
8、U盤啟動(dòng)：一鍵制作U盤系統(tǒng)安裝盤，裝機(jī)還是PE維護(hù)簡(jiǎn)直輕松到極點(diǎn)！
9、硬盤裝機(jī)：僅需兩步，輕松幫你重裝系統(tǒng)，win7、win8、win10，想裝什么裝什么，你肯定需要！
10、WiFi共享助手：超級(jí)簡(jiǎn)單，打開軟件，一鍵開啟熱點(diǎn)，立馬擺脫手機(jī)流量不夠用的困擾！！親，你的流量還夠用嗎？
還有啥？上面列出的連一半功能都不到，還有網(wǎng)速測(cè)試、磁盤大師、文件校驗(yàn)、文件解鎖、文件分割合并、文件粉碎……等等，還有好多功能，你能想到的基本都有！
軟媒魔方現(xiàn)在已經(jīng)有4000萬用戶下載使用，好用沒得說！
三、軟媒魔方軟件截圖
只需一鍵，智能模式讓你可以放心的把軟媒魔方介紹給你的老婆、小姨子和表妹……
右上角輕松切換到專業(yè)模式，熟悉中包含著科學(xué)改進(jìn)后的經(jīng)典布局
軟媒時(shí)間，風(fēng)云變幻-不占用任何額外空間，萬年歷天氣鬧鐘記事本在任務(wù)欄時(shí)間區(qū)完美呈現(xiàn)；
軟媒桌面，好玩好看-喜歡的鼠標(biāo)拖進(jìn)來，不愛的鼠標(biāo)拖出去，桌面干凈整潔靈動(dòng)驚艷；
軟媒雷達(dá)，實(shí)時(shí)偵探-把握您愛機(jī)的每一跳脈動(dòng)，精確掌控系統(tǒng)軟硬件的占用資源；
軟件管家，純凈精干-編輯精選裝機(jī)必備的500款最常用軟件，一鍵安裝絕無插件；
四、軟媒魔方下載信息
初級(jí)用戶解惑：安裝包和綠色版有什么不同？安裝版下載后直接雙擊運(yùn)行即可進(jìn)入向?qū)О惭b，方便快捷。綠色版是ZIP壓縮格式，直接解壓到你指定的文件夾路徑下。
軟媒 - 存在，創(chuàng)造價(jià)值。
微信搜索“IT之家”關(guān)注搶6s大禮！下載IT之家客戶端（戳這里）也可參與評(píng)論抽樓層大獎(jiǎng)！
oogle 的第一個(gè) Doodle 誕生于 1998 年 8 月 30 日。當(dāng)時(shí)，公司的兩位聯(lián)合創(chuàng)始人去內(nèi)華達(dá)參加“火人節(jié)”。他們?cè)谥黜摰?Google 后面放了一個(gè)燃火的小人，以表示自己外出旅行了。這個(gè) Doodle 非常簡(jiǎn)單，但是，把公司 Logo 與重要紀(jì)念日結(jié)合的想法就此誕生。多年以來，Doodle 已經(jīng)成為 Google 文化的一部分，傳達(dá)著科技背后的人文化精神。
如今，Google 內(nèi)部有專業(yè)的 Doodle 團(tuán)隊(duì)，擁有 10 名插畫師，4 個(gè)全職開發(fā)者和 2 個(gè)項(xiàng)目經(jīng)理。他們會(huì)收集創(chuàng)意，對(duì)其進(jìn)行定期整理，并且制定 Doodle 呈現(xiàn)計(jì)劃。Doodle 的形式也已經(jīng)豐富多彩了。除了靜態(tài)圖片之外，它也可以是動(dòng)態(tài)圖片、動(dòng)畫短片，甚至是交互性的小游戲。2010 年的吃豆人就是讓人印象深刻的一個(gè)互動(dòng) Doodle。今年的 5 月 19 日，為了紀(jì)念魔方發(fā)明 40 周年，Google 特意制作了一個(gè)交互性的小游戲：魔方 Doodle。
魔方 Doodle 看起來并不復(fù)雜，但是對(duì)于 Doodle 團(tuán)隊(duì)來說，它是極具挑戰(zhàn)性的一次嘗試。如果你玩過網(wǎng)上的魔方游戲，或許會(huì)注意到，它們基本都是使用了 Flash 技術(shù)，而且操作上很是糟糕。Google 的魔方 Doodle 使用的完全是網(wǎng)頁技術(shù)。
“魔方 Doodle 是人們多次建議過的東西，但是我們一直覺得，制作它的網(wǎng)頁技術(shù)還沒有成熟，” Doodle 的團(tuán)隊(duì)主管 Ryan Gemick 對(duì) Wired 網(wǎng)站說。 Google 創(chuàng)意實(shí)驗(yàn)室把它稱作是，“我們最具技術(shù)野心的 Doodle 之一。”
魔方 Doodle 能夠?qū)崿F(xiàn)，是因?yàn)榻鼇泶蠖鄶?shù)瀏覽器都開始支持 CSS 3-D Transforms。“CSS 3-D Transforms 可以讓我們把魔方展現(xiàn)在 3D 空間，而不是一種柵格化的 2D 體驗(yàn)，” 主工程師 Kristopher Hom 說，“這使它鮮活起來，當(dāng)你移動(dòng)鼠標(biāo)的時(shí)候，你能看到魔方在 3D 空間里轉(zhuǎn)動(dòng)。”
Ryan Germick 說，他們面臨的最大挑戰(zhàn)是，如何讓游戲體現(xiàn)出魔方設(shè)計(jì)上的簡(jiǎn)樸功能。“從設(shè)計(jì)角度來說，我們使它盡可能的簡(jiǎn)單、樸素，” Germick 解釋說，“ ‘Google’ 的拼寫是極簡(jiǎn)、抽象和幾何形式的。界面極簡(jiǎn)化，只告訴你移動(dòng)了多少步。”
對(duì)魔方Doodle 背后的技術(shù)感興趣？Google 已經(jīng)把源代碼全部開源了。任何人都可以去改進(jìn)它，去制作更好的魔方游戲。同時(shí)，Google 還與自由科學(xué)中心合作，在其舉辦的魔方 40 周年紀(jì)念展上放置了一個(gè)互動(dòng)的魔方。（魔方誕生 40 周年之際，魔方創(chuàng)始人、69 歲的匈牙利發(fā)明家 Enno Rubik 與美國(guó)新澤西州的自由科學(xué)中心合作舉辦了魔方展。在展示的魔方中，有第一個(gè)原型，制造材料是木頭和橡皮筋，還有世界上最貴的魔方，18 K 金打造，1360 塊寶石，價(jià)值估計(jì)為 150 萬英鎊。）
在 Ryan Germick 看來，Google 制作 Doodle 的目的，是為了贊賞魔方中體現(xiàn)的創(chuàng)造力。“如果你小時(shí)候得到了一個(gè)魔方，你對(duì)它感興趣的原因是因?yàn)槟闶且粋€(gè)問題解決者，或者你對(duì)那些促使你以后走向編程、工程和技術(shù)的東西感興趣。” 他說，“我認(rèn)為，我們對(duì)它感興趣的原因是，它是一個(gè)符號(hào)，一個(gè)解決問題的符號(hào)，一個(gè)簡(jiǎn)單與復(fù)雜并存的符號(hào)。這是我們真正想要慶祝的東西。”
圖片來自 florianmecl
*請(qǐng)認(rèn)真填寫需求信息，我們會(huì)在24小時(shí)內(nèi)與您取得聯(lián)系。
