ブラウザ上で動くルービックキューブを Elm で作った
この記事は Elm アドベントカレンダー2022 に投稿しています。
はじめに
Elm Meetup で話したネタです。イベントでは5分間でかいつまんで発表したので、この記事でそれぞれの要素についてもう少し詳しく説明します。
当日の発表資料です
作ったもの
ブラウザで動くルービックキューブを作成しました。下のリンクから実際に動かしていただけます。
動いている様子
使用した言語は Elm (v0.19.1) です。その他ライブラリとバージョンはこちらを参照してください。
注意
ルービックキューブのデータ構造は、ルービックキューブをソフトウェアで表現するための具体的な方法について述べています。 Elm を使った 3D オブジェクトの表現やアニメーションの実装方法などを知りたい場合は、3D オブジェクトの実装から読んでください。
コードは雰囲気を感じてもらうために掲載しています。厳密な定義をしていない関数が含まれています。
ルービックキューブのデータ構造
ルービックキューブを実装するためには、やはりルービックキューブの特性を知る必要があります。
今回実装する一般的な 3x3x3 のルービックキューブは、次の3種類のキューブによって構成されています。それぞれ表中の画像で明るく表示されているキューブのことです。
| コーナーキューブ | エッジキューブ | センターキューブ | |
|---|---|---|---|
| 位置 |  |
 |
 |
| 色の数 | 3色 | 2色 | 1色 |
| 個数 | 8個 | 12個 | 6個 |
これらの3種類のキューブはそれぞれ独立して回転します。言い換えると、ある面を回転させるとき、キューブは種類ごとに別々に回転しているとみなすことができます。
ルービックキューブのデータを表現するときの型を次のように定義します。キューブは種類ごとに別々に回転しているとみなせるので、3つのプロパティは互いに独立して実装を進められます。
type Cube =
{ corner: ???
, edge: ???
, center: ???
}
キューブの番号付け
便宜上、各キューブとキューブの位置に次の展開図のように番号を付けます。赤く書かれた数字がセンターキューブの番号(0~5)、黒い太字で書かれた番号がコーナーキューブの番号(0~7)、紫の斜め字で書かれたのがエッジキューブの番号(0~11)です。
たとえば、「白、青、赤」の3色を持つコーナーキューブはコーナーキューブの1番で、初期状態でコーナーキューブの1番のところにあります。また、「黄、赤」の2色をもつエッジキューブはエッジキューブの7番で、初期状態でエッジキューブの7番に置かれています。
位置に番号を付けたルービックキューブの展開図
下の図では、丸のついたコーナーキューブの1番が2番の位置に置かれています。
コーナーキューブの1番（白、青、赤）が、2番の位置（一番手前の位置）に置かれている
型の定義
コーナーキューブの型
コーナーキューブを管理するためには「Array であればいいです。
type alias Corner = Array Int;
位置だけでなく「向き」の情報も必要です。初期状態では、2番目の位置に「白、緑、赤」のキューブが白が上に来るように置かれます。その状態から「Top(CW) → Front(CW)」の順でボタンをクリックしてキューブを回転すると、同じく2番の位置に「白、緑、赤」のキューブが緑が上の状態（元から右に120度回転した状態）を作ることができます。同様に、「Top(CCW) → Right(CCW)」とすると赤が上の状態（元から左に120度回転した状態）を作ることもできます。
2の位置に「白、緑、赤」のキューブが右に120度回転して置かれている
向きは Normal、Right、 Left の三つの状態があり、次のように決めます。
- 白、黄が上面か下面にあるなら
Normal - 白、黄が上面か下面から時計回りに120度回転した位置にあるなら
Right - 白、黄が上面か下面から反時計回りに120度回転したいちにあるなら
Left
コーナーキューブは、ある位置に置かれているキューブの番号とその向き（元の状態、右に120度回転した状態、左に120度回転した状態）を使って表現する必要があるとわかりました。
よって、キューブのデータを表現する型は次のように定義できます。
type CornerOrientation
= NormalCO -- 元の回転状態
| RightCO -- 元の状態から時計回りに120度回転した状態
| LeftCO -- 元の状態から反時計回りに120度回転した状態
type alias Corner = Array ( Int, CornerOrientation )
次のように初期化できます。前述の通り、初期状態で
initCorner: () -> Corner
initCorner () =
Array.fromList <| List.map (\i -> ( i, NormalCO )) <| List.range 0 7
エッジキューブの型
エッジキューブもコーナーキューブと同様に、ある位置に置かれているキューブの番号と向きの配列で表現することができます。
初期状態で9番目の位置には「緑、赤」のエッジキューブが置かれています。「Z(CW) → Front(CW) → Front(CW)」と操作すると同じ位置に「緑、赤」のエッジキューブが反対向きで置かれた状態になります。
9の位置に「緑、赤」のキューブが反転して置かれている
エッジキューブの向きは Normal、Revered の二つの状態があり、次のように決めます。
- キューブに白、黄が含まれる場合
- 位置が 0~3, 4~7 の場合
- 白、黄が上面か下面にあるなら
Normal - 白、黄が上面か下面にないなら
Reversed
- 白、黄が上面か下面にあるなら
- 位置が 8~11 の場合
- 白、黄が前面か背面にあるなら
Normal - 白、黄が前面か背面にないなら
Reversed
- 白、黄が前面か背面にあるなら
- 位置が 0~3, 4~7 の場合
- キューブに白、黄が含まれない場合（緑、青が必ず含まれる）
- 位置が 0~3, 4~7 の場合
- 緑、青が上面か下面にあるなら
Normal - 緑、青が上面か下面にないなら
Reversed
- 緑、青が上面か下面にあるなら
- 位置が 8~11 の場合
- 緑、青が前面か背面にあるなら
Normal - 緑、青が前面か背面にないなら
Reversed
- 緑、青が前面か背面にあるなら
- 位置が 0~3, 4~7 の場合
エッジキューブのデータを表現する型とその初期状態は次のように定義できます。
type EdgeOrientation
= NormalEO -- 元の状態
| ReversedEO -- 反転した状態
type alias Edge = Array ( Int, EdgeOrientation )
initEdge () =
Array.fromList <| List.range 0 5
センターキューブの型
コーナーキューブやセンターキューブと同じように、番号をつけます。
センターキューブは1色しかなく回転で向きが変わらないため、長さ6 Array Int で表現できます。
type alias Center = Array Int
initCenter () =
Array.fromList <| List.range 0 5
型の定義のまとめ
以上より、ルービックキューブのデータは次の型で扱うことができます。
type CornerOrientation
= NormalCO
| RightCO
| LeftCO
type EdgeOrientation
= NormalEO
| ReversedEO
type Cube =
{ corner: Array ( Int, CornerOrientation )
, edge: Array ( Int, EdgeOrientation )
, center: Array Int
}
initCube: () -> Cube
initCube () =
{ corner = Array.fromList <| List.map (\i -> ( i, NormalCO )) <| List.range 0 7
, edge =
, center = Array fromList <| List.range 0 5
}
回転操作の実装
これまで定義した型で表現されたルービックキューブのデータにおいて、回転操作は「キューブの種類ごとにベクトルの順番を入れ替え、向きを切り替える操作」ということができます。
前面の回転の様子を考えています。上面の回転ではコーナーキューブとエッジキューブは影響を受けますが、センターキューブはそのままです。
前面の回転に伴うキューブの移動を追う
コーナーキューブの3番の動きを見てみます。前面の回転により、2番の位置に移動しています。また、キューブの向きは右に120度回転しています。
エッジキューブの2番の動きも見てみましょう。9番の位置に移動し、かつ向きも反転しています。
前面の回転の影響を受けるキューブの位置と向きの変化を次のように表現できます。前述のとおり、コーナーキューブとエッジキューブは独立して表現されています。
-- 先頭要素は、2の位置には3の位置にあったキューブが右に120度回転してセットされる、と読みます
cornerRotateFront = [ ( 2, 3, RightCO ), ( 6, 2, LeftCO ), ( 7, 6, RightCO ), ( 3, 7, LeftCO ) ]
edgeRotateFront = [ ( 9, 2, ReversedEO ), ( 6, 9, ReversedEO ), ( 8, 6, ReversedEO ), ( 2, 8, ReversedEO ) ]
これを6つ面すべてに対して実装すると次のようになります。これらの情報をもとに、ルービックキューブのデータの配列をうまく操作すると回転操作が実現できます。
type Side
= Top
| Left
| Front
| Right
| Back
| Bottom
rotatePattern : Side -> { edge : List ( Int, Int, EdgeOrientation ), corner : List ( Int, Int, CornerOrientation ) }
rotatePattern side =
case side of
Front ->
{ corner = [ ( 2, 3, RightCO ), ( 3, 7, LeftCO ), ( 7, 6, RightCO ), ( 6, 2, LeftCO ) ]
, edge = [ ( 9, 2, ReversedEO ), ( 2, 8, ReversedEO ), ( 8, 6, ReversedEO ), ( 6, 9, ReversedEO ) ]
}
Top ->
{ corner = [ ( 0, 3, NormalCO ), ( 1, 0, NormalCO ), ( 2, 1, NormalCO ), ( 3, 2, NormalCO ) ]
, edge = [ ( 0, 1, NormalEO ), ( 1, 2, NormalEO ), ( 2, 3, NormalEO ), ( 3, 0, NormalEO ) ]
}
Left ->
{ corner = [ ( 0, 4, LeftCO ), ( 3, 0, RightCO ), ( 7, 3, LeftCO ), ( 4, 7, RightCO ) ]
, edge = [ ( 1, 11, NormalEO ), ( 8, 1, NormalEO ), ( 5, 8, NormalEO ), ( 11, 5, NormalEO ) ]
}
Right ->
{ corner = [ ( 1, 2, RightCO ), ( 2, 6, LeftCO ), ( 6, 5, RightCO ), ( 5, 1, LeftCO ) ]
, edge = [ ( 3, 9, NormalEO ), ( 10, 3, NormalEO ), ( 7, 10, NormalEO ), ( 9, 7, NormalEO ) ]
}
Back ->
{ corner = [ ( 0, 1, RightCO ), ( 1, 5, LeftCO ), ( 5, 4, RightCO ), ( 4, 0, LeftCO ) ]
, edge = [ ( 11, 0, ReversedEO ), ( 4, 11, ReversedEO ), ( 10, 4, ReversedEO ), ( 0, 10, ReversedEO ) ]
}
Back ->
{ corner = [ ( 7, 4, NormalCO ), ( 6, 7, NormalCO ), ( 5, 6, NormalCO ), ( 4, 5, NormalCO ) ]
, edge = [ ( 6, 5, NormalEO ), ( 7, 6, NormalEO ), ( 4, 7, NormalEO ), ( 5, 4, NormalEO ) ]
}
回転と対称群
ルービックキューブの性質として、ある回転を4回連続で実行すると元の状態に戻ることが知られています。
前面の回転について見てみると、コーナーキューブの3番にいたキューブは操作ごとに次のように移動します。
- 右に120度回転して2番へ
- 左に120度回転して6番へ
- 右に120度回転して7番へ
- 左に120度回転して3番へ
結果として、4回の目の回転が終わったときには元の状態に戻っています。すべてのキューブも同様に4回の操作でもとに戻っていることが確認できます。
他のすべての回転でも同じで、ルービックキューブの回転は4次の対称群だということができます。
この性質を理解しておくと、いくらか実装でミスが無くなるかと思います。
以上で、ルービックキューブを表現するデータの型とその操作の定義が完了しました。
3D オブジェクトの実装
ライブラリを使った 3D オブジェクトの表現
3D オブジェクトの実装は ianmackenzie/elm-3d-scene を使って実装しています。このライブラリで使われる 3D 空間は手前方向が
下のようにしてブロックを表示することができます。
import Block3d
import Color as ObjColor
import Point3d
import Scene3d exposing (..)
import Scene3d.Material as Material
Scene3d.block
(Material.color ObjColor.black)
(Block3d.with
{ x1 = Length.meters 1
, x2 = Length.meters -1
, y1 = Length.meters 1
, y2 = Length.meters -1
, z1 = Length.meters 1
, z2 = Length.meters -1
}
|> Block3d.scaleAbout Point3d.origin (1 / 2)
)
単純なブロック
ここに白、緑、赤の色を付きの平面を追加してみましょう。
白い平面は、 panel_size で大きさを調整しています。 small_gap の分だけ）外側に移動させて平面がしっかり表示させます（同じ位置だとめり込んでよく見えない）。
追加した平面は
最後に Scene3d.group で1つのオブジェクトとして扱えるようにします。
panel_size = 0.9
small_gap = 0.01
cube =
[ Scene3d.block
(Material.color ObjColor.black)
(Block3d.with
{ x1 = Length.meters 1
, x2 = Length.meters -1
, y1 = Length.meters 1
, y2 = Length.meters -1
, z1 = Length.meters 1
, z2 = Length.meters -1
}
|> Block3d.scaleAbout Point3d.origin (1 / 2)
)
, Scene3d.quad
-- 白の面
(Material.color ObjColor.white)
(Point3d.meters -1 -1 0)
(Point3d.meters 1 -1 0)
(Point3d.meters 1 1 0)
(Point3d.meters -1 1 0)
|> Scene3d.scaleAbout Point3d.origin (panel_size / 2)
|> Scene3d.translateBy (Vector3d.meters 0 0 (0.5 + small_gap))
, Scene3d.quad
-- 緑の面
(Material.color ObjColor.green)
(Point3d.meters -1 -1 0)
(Point3d.meters 1 -1 0)
(Point3d.meters 1 1 0)
(Point3d.meters -1 1 0)
|> Scene3d.scaleAbout Point3d.origin (panel_size / 2)
|> Scene3d.translateBy (Vector3d.meters 0 0 (0.5 + small_gap))
-- y軸方向に90度回転させて手前にもってくる
|> rotateAround Axis3d.y (Angle.degrees 90)
, Scene3d.quad
-- 赤の面
(Material.color ObjColor.red)
(Point3d.meters -1 -1 0)
(Point3d.meters 1 -1 0)
(Point3d.meters 1 1 0)
(Point3d.meters -1 1 0)
|> Scene3d.scaleAbout Point3d.origin (panel_size / 2)
|> Scene3d.translateBy (Vector3d.meters 0 0 (0.5 + small_gap))
-- y軸方向に90度回転させて手前にもってきて、z軸方向に90度回転させて右にもってくる
|> (rotateAround Axis3d.y (Angle.degrees 90) >> rotateAround Axis3d.z (Angle.degrees 90))
]
|> Scene3d.group -- キューブと色のセットを一塊にする
ブロックに色付きの平面をくっつけて一つのキューブにする
現在のキューブのデータから「どの面のどの位置が何色か」を復元できるので、全てのキューブに対して Scene3d.block と Scene3d.quad で構成し適切な座標に配置します。
cubeView : Cube -> Entity coordinate
cubeView cube =
cube
|> toColorArray -- 「どの面のどの位置が何色」を表現する Array に変換
|> composeCube -- 色の配列からキューブを構成する
アプリケーションとして表示する
アプリケーションとして操作や表示ができるように、 Model や Msg を定義していきます。
Model はシンプルにキューブのデータだけです。初期化はデータの型と一緒に定義した initCube を使います。
type alias Model =
{ cube : Cube
}
init : () -> ( Model, Cmd Msg )
init _ =
( Model (initCube ())
, Cmd.none
)
Msg は、キューブを回転させる命令を表現できると良さそうです。 RotateCube は、キューブの回転させる面の情報を持ちます。これらの情報を使って、 Cube.rotateSide で model.cube を更新しています。
type Msg
-- キューブを回転させる命令
= RotateCube Side
update : Msg -> Model -> ( Model, Cmd Msg )
update msg model =
case msg of
RotateCube side ->
( { model | cube = Cube.rotateSide side model.cube }
, Cmd.none
)
view を実装します。
キューブのオブジェクトの描画は こちら を参考にしました。 entities には model.cube と cubeView を組み合わせてキューブの3Dオブジェクトとして渡しています。
回転の面と方向ごとにボタンを並べて、クリックすると対応する回転の Msg を送信し、 Model が更新されるようになっています。
view : Model -> Html Msg
view { cube } =
div []
[ Scene3d.unlit
{ dimensions = ( Pixels.pixels 600, Pixels.pixels 600 )
, camera =
Camera3d.perspective
{ viewpoint =
Viewpoint3d.lookAt
{ focalPoint = Point3d.origin
, eyePoint = Point3d.meters 9 0 0
, upDirection = Direction3d.positiveZ
}
, verticalFieldOfView = Angle.degrees 35
}
, clipDepth = Length.meters 3.4
, background = Scene3d.backgroundColor Color.grey
, entities =
cubeView cube
}
, table []
[ tr []
[ td [] [ button [ onClick (RotateCube Top ] [ text "Top" ] ]
, td [] [ button [ onClick (RotateCube Left ] [ text "Left" ] ]
, td [] [ button [ onClick (RotateCube Front ] [ text "Front" ] ]
, td [] [ button [ onClick (RotateCube Right ] [ text "Right" ] ]
, td [] [ button [ onClick (RotateCube Back ] [ text "Back" ] ]
, td [] [ button [ onClick (RotateCube Bottom ] [ text "Bottom" ] ]
]
]
]
これで「ボタンをクリックするとキューブを回転させる」挙動を実装することができました。
ボタンのクリックでキューブを回転させる様子
アニメーションの実装
回転のボタンをクリックしてデータがパッと更新されるのでは味気ないなと思い、アニメーションを追加しました。
Main のモデルに現在の回転状態を扱うデータを追加します。データの型は、回転している面を示す Side と回転量を表す Float (0以上1未満の実数) をあわせて、 Maybe でラップしています。（回転中は Just 、回転していないときは Nothing）
tyoe alias Model =
{ cube : Cube
+ , rotating : Maybe ( Side, Float )
}
init _ =
- ( Model (initCube ())
+ ( Model (initCube ()) Nothing
, Cmd.none
)
elm/Time を使ってキューブの回転を実現させます。以下のように Msg、subscriptions、update を実装することで、20ミリ秒に一度 Tick という Msg で update が実行されます。
type Msg
= Tick Time.Posix
subscriptions _ =
Sub.batch
[ Time.every tickPeriod Tick
]
update msg model =
case msg of
Tick _ ->
-- 20ミリ秒ごとに実行したい処理を書く
先の実装でキューブのデータを更新していた RotateCube を回転の開始のために使うことにします。回転を開始したときの回転量は0です。データの更新はまだ行いません。
Tick を受け取ったときに回転中なら、回転量が 1 を超えるまで rotateSize 分だけ回転量を加算していきます。回転量が1を超えたら回転を終了し（rotating = Nothing）、データの更新を行います（cube = Cube.rotateSide side model.cube）。
rotateSize = 1 / 50
update msg model =
case msg of
RotateCube side ->
( { model | rotating = Just ( side, 0 ) }
, Cmd.none
)
Tick _ ->
( case model.rotating of
Just ( side, ratio ) ->
if ratio >= 1 then
-- 回転量が1に達したときはじめて cube のデータが更新される
{ model | cube = Cube.rotateSide side model.cube, rotating = Nothing }
else
-- 20ミリ秒ごとに回転量が少しずつ加算されていく
{ model | rotating = Just ( side, ratio + rotateSize ) }
Nothing ->
model
, Cmd.none
)
Model に、キューブの回転している面と回転量の情報が追加されたので、キューブを表示する cubeView を適切に更新して回転状態を描画させられるようになりました。
キューブの配色からキューブのオブジェクトを生成する composeCube に回転の情報を与えます。「どの面が回転しているときにどのブロックが影響を受けるか」という情報を事前に組み込んでおくと、回転中のブロックとそれ以外のブロックを分離させることができます（groupByRotating）。回転中のブロックは、 Scene3d.rotateAround で回転量に応じて回転させます。これで指定した面が回転中のキューブを作ることができました。
composeCube : CubeColor -> Maybe ( Side, Float ) -> Entity coordinate
composeCube cubeColor rotating =
cubeColor
|> composeBlocksWithColor
|> groupByRotating rotating
|> (\( rotatingBlock, others ) ->
( case rotating of
Just ( side, ratio ) ->
Scene3d.rotateAround (axisOfSide side) (90 * ratio) rotatingBlock
Nothing ->
rotatingBlock
)
|> \blocks -> Scene3d.group [blocks, others]
)
rotating が Just ( Front, 0.4 )のときの回転の様子
回転のアニメーションを追加した様子
おわりに
その他やったこと
記事が大きくなりすぎて書けませんでしたが、ほかにやったことを上げておきます。気が向いたら書くかも
- 四元数を使ったキューブ全体の回転
- キューブの領域の検出
- 3D オブジェクトの位置から画面に表示される位置の計算
- convexhull algorithm と ray-casting algorithm を使った
- マウスカーソルでキューブを操作
やれなかったこと
テストはもう少し充実させたらよかったと後悔しています。もう少しテストを書いたほうが実装やリファクタリングしやすかったかもなあと思いました（適当に作って捨てるつもりだったので仕方ないとも思いつつ）。ルービックキューブの表示部分のテストはどうすればよかったのかわからなかったので、詳しい方がいれば教えていただきたいです。
次に実装を再開することがあれば、ちゃんとテストから作りたい。
あと触ってもらった人からは操作性が悪いことをよく指摘されました。この記事で触れてないですが、マウスを使ったキューブの回転操作がやりにくいらしいです。自分は実装中に操作に慣れすぎてしまったので難しさをわからなくなってしまいました。。。ゲーム作りとかそういうの多そうですね。
感想
実装してとても楽しかったです。実装のためにルービックキューブの特性をよく理解するきっかけになりました。 3D オブジェクトの扱いにもかなり慣れたと思います。
Discussion