# 魔術方塊的資料結構設計
應徵助教時遇到了這個題目，解完以後發現過程很有趣，於是記錄下來
## 需求分析
魔術方塊在xyz三個軸上都有三層可以旋轉，旋轉又分順逆時鐘
3 X 3 X 2 = 18
共有18種操作
## 結構分割策略
### 切三片
只有其中一個軸的旋轉是在同一片結構中搬動資料，另外兩軸上的旋轉要各自設計並且三片都會讀寫到，不夠優雅
### 整個魔術方塊
欄位過多，不好管理
### 切成小方塊
總共有 3 X 3 X 3 - 1(中心) = 26 個小方塊結構
再用上層的魔術方塊結構包含26個小方塊結構
每次旋轉都可看作是對九個小方塊各自做旋轉
## 選擇小方塊分割法
### 顏色訊息
小方塊的結構需要儲存顏色資訊
角:3種顏色
邊:2種顏色
中:1種顏色
因此至少要有三個欄位
為了未來支援多種不同的顏色效果，選擇 32 bit 的 RGBA 顏色編碼格式，以 uint32_t 儲存
```cpp
typedef struct cubie {
uint32_t color_1;
uint32_t color_2;
uint32_t color_3;
}cubie_t;
```
### 位置訊息
每次旋轉會改變小方塊的位置，因此需要儲存位置訊息，將26個位置分別編號
```cpp
typedef struct cubie {
uint32_t color_1;
uint32_t color_2;
uint32_t color_3;
int location;
}cubie_t;
```
但是這樣的設計會引來複雜性，因為需要對26個位置分別設計18種操作的變換
### 顏色朝向
旋轉時顏色的朝向會改變，是否可用位置回推朝向？
跟同學借了魔術方塊來實驗，發現不可，因為小方塊在同一個位置可以有不同方向，無法用位置一對一映射朝向，需要在每次旋轉時也儲存顏色的朝向資訊。
### 改變顏色儲存方式
小方塊的顏色資訊從3欄改為6欄，分別紀錄東南西北上下的顏色，當該面是在魔術方塊的內部不被看見時，顏色值會設為0
```cpp
typedef struct cubie {
uint32_t t; // 上 top
uint32_t w; // 西 west
uint32_t n; // 北 north
uint32_t e; // 東 east
uint32_t s; // 南 south
uint32_t b; // 下 bottom
int location;
}cubie_t;
```
在三個軸上的順逆時針旋轉操作，六個欄位間的顏色值按照方向搬動輪換
```cpp
void rotate_cubie_x(cubie_t* cubie, bool clockwise) {
if (clockwise) {
// 順時針：上 -> 北 -> 下 -> 南
uint32_t temp = cubie->t;
cubie->t = cubie->s;
cubie->s = cubie->b;
cubie->b = cubie->n;
cubie->n = temp;
} else {
// 逆時針：上 -> 南 -> 下 -> 北
uint32_t temp = cubie->t;
cubie->t = cubie->n;
cubie->n = cubie->b;
cubie->b = cubie->s;
cubie->s = temp;
}
}
void rotate_cubie_y(cubie_t* cubie, bool clockwise) {
if (clockwise) {
// 順時針：西 -> 下 -> 東 -> 上
uint32_t temp = cubie->w;
cubie->w = cubie->t;
cubie->t = cubie->e;
cubie->e = cubie->b;
cubie->b = temp;
} else {
// 逆時針：西 -> 上 -> 東 -> 下
uint32_t temp = cubie->w;
cubie->w = cubie->b;
cubie->b = cubie->e;
cubie->e = cubie->t;
cubie->t = temp;
}
}
void rotate_cubie_z(cubie_t* cubie, bool clockwise) {
if (clockwise) {
// 順時針：南 -> 西 -> 北 -> 東
uint32_t temp = cubie->s;
cubie->s = cubie->e;
cubie->e = cubie->n;
cubie->n = cubie->w;
cubie->w = temp;
} else {
// 逆時針：南 -> 東 -> 北 -> 西
uint32_t temp = cubie->s;
cubie->s = cubie->w;
cubie->w = cubie->n;
cubie->n = cubie->e;
cubie->e = temp;
}
}
```
## 發現編碼唯一性
就在我胡思亂想時，突然發現26塊小方塊各自具有的顏色面方向組合，在同一時間點下具有唯一性，也許可以省略位置資訊？
> "天傾西北，地陷東南"
> ——《山海經》
### 二轉十進制換算表
|天 |西 |北 |東 |南 |地 |
|:------:|:------:|:------:|:------:|:------:|:------:|
|32 |16 |8 |4 |2 |1 |
### 三色塊（角）
|天 |西 |北 |東 |南 |地 |換為十進制|
|:------:|:------:|:------:|:------:|:------:|:------:|:------:|
|1 |1 | | |1 | |50 |
|1 | | |1 |1 | |38 |
|1 | |1 |1 | | |44 |
|1 |1 |1 | | | |56 |
| | | |1 |1 |1 |7 |
| | |1 |1 | |1 |13 |
| |1 |1 | | |1 |25 |
| |1 | | |1 |1 |19 |
### 雙色塊（邊）
|天 |西 |北 |東 |南 |地 |換為十進制|
|:------:|:------:|:------:|:------:|:------:|:------:|:------:|
|1 |1 | | | | |48 |
|1 | |1 | | | |40 |
|1 | | |1 | | |36 |
|1 | | | |1 | |34 |
| |1 |1 | | | |24 |
| | |1 |1 | | |12 |
| | | |1 |1 | |6 |
| |1 | | |1 | |18 |
| |1 | | | |1 |17 |
| | |1 | | |1 |9 |
| | | |1 | |1 |5 |
| | | | |1 |1 |3 |
### 單色塊（中）
|天 |西 |北 |東 |南 |地 |換為十進制|
|:------:|:------:|:------:|:------:|:------:|:------:|:------:|
|1 | | | | | |32 |
| |1 | | | | |16 |
| | |1 | | | |8 |
| | | |1 | | |4 |
| | | | |1 | |2 |
| | | | | |1 |1 |
## 省略小方塊資料結構中的位置欄位
因為顏色方向組合具有唯一性，足以代表空間位置，因此省略位置欄位
```cpp
typedef struct cubie {
uint32_t t; // 上 top
uint32_t w; // 西 west
uint32_t n; // 北 north
uint32_t e; // 東 east
uint32_t s; // 南 south
uint32_t b; // 下 bottom
}cubie_t;
```
## 上層大結構
整個魔術方塊的資料結構，由26個 cubie 組成
```cpp
typedef struct cube {
cubie_t cubie[26];
}cube_t;
```
## 操作方法
使用者將魔術方塊初始化後，根據想要操作的面或中間層，以及順逆時針，填入操作參數。
函數遍歷26個小方塊，根據操作選取該位置具有顏色的cubie各自做旋轉。
exp1:操作南面，則對南面顏色不為0的cubie操作
exp2:操作x軸中間層，則對東西兩面顏色為0的cubie操作
```cpp
#define SOUTH 1 // 南面旋轉
#define NORTH 2 // 北面旋轉
#define EAST 3 // 東面旋轉
#define WEST 4 // 西面旋轉
#define TOP 5 // 上面旋轉
#define BOTTOM 6 // 下面旋轉
#define X_MIDDLE 7 // X 軸中間層旋轉
#define Y_MIDDLE 8 // Y 軸中間層旋轉
#define Z_MIDDLE 9 // Z 軸中間層旋轉
void perform_rotation(cube_t* cube, int operation, bool clockwise) {
for (int i = 0; i < 26; i++) {
cubie_t* cubie = &cube->cubie[i];
switch (operation) {
case SOUTH: // 南面旋轉
if (cubie->s != 0) {
rotate_cubie_y(cubie, clockwise);
}
break;
case NORTH: // 北面旋轉
if (cubie->n != 0) {
rotate_cubie_y(cubie, clockwise);
}
break;
case EAST: // 東面旋轉
if (cubie->e != 0) {
rotate_cubie_x(cubie, clockwise);
}
break;
case WEST: // 西面旋轉
if (cubie->w != 0) {
rotate_cubie_x(cubie, clockwise);
}
break;
case TOP: // 上面旋轉
if (cubie->t != 0) {
rotate_cubie_z(cubie, clockwise);
}
break;
case BOTTOM: // 下面旋轉
if (cubie->b != 0) {
rotate_cubie_z(cubie, clockwise);
}
break;
case X_MIDDLE: // X 軸中間層旋轉
if (cubie->e == 0 && cubie->w == 0) {
rotate_cubie_x(cubie, clockwise);
}
break;
case Y_MIDDLE: // Y 軸中間層旋轉
if (cubie->s == 0 && cubie->n == 0) {
rotate_cubie_y(cubie, clockwise);
}
break;
case Z_MIDDLE: // Z 軸中間層旋轉
if (cubie->t == 0 && cubie->b == 0) {
rotate_cubie_z(cubie, clockwise);
}
break;
}
}
}
```
## 顯示時要注意
這個儲存方法無法直接表達小方塊的具體位置或小方塊間的相對關係。
在使用 openGL 、 Vulkan 等圖形api繪製時，必須利用小方塊顏色方向組合，換算回小方塊的具體位置
Sign in with Wallet
Connect another wallet