ThreeJS簡易魔方自動還原實現（一）層先法

來自專欄 NewbieWeb

? Young 2018-04-29 21:08

Welcome to My GitHub

在ThreeJS四步製作一個簡易魔方中介紹了怎麼實現一個可以轉動的簡易魔方，接來下準備介紹下怎麼讓這個簡易魔方具備自動還原的功能。

例子如下：

可以掃描以下二維碼體驗：

https://newbieyoung.github.io/Threejs_rubik/step5.html (二維碼自動識別)

或者訪問鏈接https://newbieyoung.github.io/Threejs_rubik/step5.html；

代碼在https://github.com/newbieYoung/Threejs_rubik項目中：

step1.html、step2.html、step3.html、step4.html為ThreeJS四步製作一個簡易魔方的相關代碼；

wegame文件夾為簡易魔方的小遊戲代碼，目前只包含前四步功能；

step5.html為簡易魔方層先法自動還原的代碼，也就是上述例子的代碼，後續會進行簡單說明；

auto-reset-v1-test.js為上述例子的測試用例代碼，在測試用例中會把相關日誌信息（比如還原所需步數以及時長）輸出到auto-reset-v1-log.txt文件中，方便後續分析；

analyze.js為上述例子的日誌分析代碼，會計算所有樣本數據的平均時長和平均步數並把結果輸出到auto-reset-v1-analyze.txt文件中。

在210次自動測試中，平均步數為197步，平均時長為44秒，和代碼中設定的0.2秒一步基本吻合，從自動測試數據來看，目前的實現還沒有達到該演算法的最優，估計可以優化到平均步數150的樣子（旋轉90度即算一步）。

需要注意的是三階魔方有8!×3^7×12!×2^11/2 = 43252003274489856000種情形，因此雖然我對例子代碼進行了上千測試，但是依然不能百分百保證實現的還原演算法可以處理所有情況，因此希望大家在體驗的過程中如果遇到的異常情況能反饋給我（最好是六個面都截圖）。

層先法是指將魔方分為三層：底層、中層、頂層，分層復原；仔細留意上述例子就可以發現復原過程是從底層開始慢慢到頂層的，如圖：

層先法只需要記憶幾個簡單的公式就可以完成，因此適合魔方初學者使用，但是效率較差。

該怎麼實現呢？以第一步小白花來說：

首先得確定當前模型中上表面中心顏色的對應顏色；

小白花要求上表面中心顏色四周為其對應顏色；

所幸我們在ThreeJS中根據顏色數組構建正方體時其規律就已經確定了；

當我們依次給六個面賦值時，其固定順序為右、左、上、下、前、後，也就意味著根據顏色序號獲取初始化時其對面顏色序號的方法如下：

這是層先法實現過程中的第一個基本方法。

因為魔方轉動時使用的是ThreeJS提供軌道控制器OrbitControls，視角變動的原因在於攝像機位置的變化，魔方本身並沒有轉動；再加上轉動某一層之後會更新小方塊序號，使其永遠保持初始序號不變；

那麼上表面中心小方塊序號則為10，與此同時我們需要一個方法來根據序號選取小方塊：

rotateNum表示小方塊繞世界坐標系的Y軸旋轉逆時針旋轉90度的次數，比如getCubeByIndex(2,1)實際獲取的小方塊序號為20；

之所以會這樣是因為層先法中每一種情況實際還有三個等效的情形，因為魔方的上下關係確定後就固定了，但是左右前後卻是可以變化的；

這是層先法實現過程中的第二個基本方法。

選取到具體小方塊之後我們還需要獲得小方塊中法向量和世界坐標系Y軸平行的平面的序號然後根據該平面的序號獲取對應顏色，因此我們還需要一個方法來獲取某個小方塊中法向量和已知向量方向相同的面的顏色序號：

這個方法裡邊需要注意兩點：

其一：判斷兩個向量平行時不能判斷其夾角是否等於0，因為浮點數運算存在誤差，實際情況可能是其夾角是個很小很小的數但是就是不等於0，得改成判斷最小值的方法；

其二：cube.faces[i].normal獲取的法向量是在小方塊自身坐標系中的，所幸ThreeJS需要進行光線相關的運算，因此小方塊對象中存儲了法向量矩陣cube.normalMatrix，自身坐標系的法向量乘以法向量矩陣即可得到視圖坐標系中的法向量；但是因為我們傳入這個方法的坐標軸向量在世界坐標系中，因此不能拿來直接計算，需要轉換到視圖坐標系中去，轉換方法就是乘以視圖矩陣的逆反矩陣；

因為使用的是透視投影相機 THREE.PerspectiveCamera因此視圖矩陣可以這麼求：

直接調用THREE.Matrix4的靜態方法getInverse即可求得某個矩陣的逆反矩陣；

這是層先法實現過程中的第三個基本方法。

到此我們就可以實現首先得確定當前模型中上表面中心顏色的對應顏色這一步驟了：

然後判斷小白花是否完成，如果完成則進入第二步；

小白花的判斷很簡單，只需要判斷序號為1、9、11、19的小方塊的上表面顏色是否為中心小方塊上表面顏色的對應色即可：

然後得處理小白花的各種情況；

以第一種舉例來說：

如圖3號小方塊Z軸表面為底色時，如果9號小方塊Y軸表面也為底色，則需要逆時針轉動頂層；反之則需要逆時針轉動左側：

上述代碼有兩個需要注意的地方：

其一：rotateAxisByYLine方法是用於處理各種等效情況中各坐標軸的變化情況的，比如Z軸在逆時針繞Y軸旋轉90度之後就變成了X軸；

這是層先法實現過程中的第四個基本方法。

其二：逆時針轉動頂層的邏輯被u方法所封裝；逆時針轉動左側的邏輯被l方法所封裝；原因在於層先法還原魔方的各種轉動最終都可以被封裝為12基本轉動，如下：

在代碼中分別封裝如下：

這是層先法實現過程中的其它基本方法了。

後續按照教程一步步實現即可，基本都是上述基本方法的應用了。

層先法雖然理解起來簡單，但是因為步驟較多，實現起來容易出錯，寫代碼的時候最好仔細點！

另外想做一個基於微信小遊戲的魔方，前期主要想復刻好魔方體驗並結合一些方便的小功能比如標記某一狀態，後續操作有問題立刻回歸標記狀態，以及操作歷史，信息統計等；歡迎有興趣的同學一起來玩（在我博客留言留下聯繫方式即可）。

最後列一篇有趣的科普文章魔方與 「上帝之數」感受魔方的魅力。