Puzzle Pong III - Irreversible Cube II

The Puzzle⌗

This is a continuation of Puzzle Pong - Irreversible Cube I. In the first part, Josh Mermelstein posed me a series of questions about the Irreversible Cube:

Oskar van Deventer {1} presents an Irreversible Cube in his 2013 video {2} which is an ordinary 2x2x2 Rubix Cube where you are only allowed to turn any face clockwise, and only once in a row.

By the end of part 1), I had a fairly poor approximation of an isometric projection, which was able to take a set of points and turn them into tilted tiles along one of three skew planes. This was pretty good for seeing what state the cube might be in at any given stage, but it was not a true 3D rendering, meaning that my higher goals of animating a real turn were next-to-impossible.

This inspired a separate Haskell library, Cornea for isometric 3D graphing and rendering, which I discuss here. Cornea has the benefit of being easily mapped to write out either a single image or a series of images, which can be stitched together into animations.

In this post, I’ll discuss wrapping the Irreversible Cube solver from part I into something which can render animations of the cube in the process of being solved.

Changes⌗

Recall our custom type definitions:

data Side        = F | B | U | D | L | R deriving (Eq, Bounded, Show, Enum, Ord)
data Axis        = X | Y | Z deriving (Eq, Show)
data Cardinality = Pos | Neg deriving (Eq, Show)
type Rotation    = (Coord -> Coord)
type Coord       = [Int]
type Tile        = Coord
type Cube        = [Tile]

The biggest change we must make from the old way of doing things is to rewrite mkRot :: Cardinality -> Axis -> Rotation to rely on a much more general rotate :: Float -> Axis -> [x,y,z] -> [x',y',z'] under the hood. That way, we can still do things like

given a turn on face  L 
-> run through sideToCardinalityAndAxis s2CA(L) = (Neg, Y) 
-> get cardinality Neg and axis Y
-> mkRot Neg Y -> (\[x,y,z] -> rotate (-90) Y [x,y,z])

Or, when we need to start calculating in-between frames (tweens) for our side rotation animation, we can do things like

rotateFace :: Float -> Axis -> Obj -> Obj
rotateFace <angle> <axis> (Face pts) = Face (map (rotate <angle> <axis>) pts)

Here’s the code that makes that happen.

mkRot :: Cardinality -> Axis -> Rotation
mkRot c a = map (\x -> round x :: Int) . rotate (toAngle c) a . map fromIntegral

s2Rot :: Side -> Rotation
s2Rot = uncurry mkRot . s2CA

s2CA :: Side -> (Cardinality, Axis)
s2CA F = (Pos, X); s2CA R = (Pos, Y); s2CA U = (Pos, Z); 
s2CA B = (Neg, X); s2CA L = (Neg, Y); s2CA D = (Neg, Z);

rotate :: Float -> Axis -> [Float] -> [Float]
rotate t X [x,y,z] = [ x                     , cos t * y - sin t * z ,  sin t * y + cos t * z]
rotate t Y [x,y,z] = [ cos t * x + sin t * z , y                     , -sin t * x + cos t * z]
rotate t Z [x,y,z] = [ cos t * x - sin t * y , sin t * x + cos t * y ,  z                    ]

rotateFace :: Float -> Axis -> Obj -> Obj
rotateFace t a (Face pts) = Face (map (rotate t a) pts)

toAngle :: Cardinality -> Float
toAngle Pos =  pi/2; toAngle Neg = -pi/2

Now we can just write twist as

twist :: Side -> Cube -> Cube
twist side = map (\x -> if side `sees` x then s2Rot side x else x)

sees :: Side -> (Coord -> Bool)
(sees) F = (>0) . (!!0); (sees) R = (>0) . (!!1); (sees) U = (>0) . (!!2);
(sees) B = (<0) . (!!0); (sees) L = (<0) . (!!1); (sees) D = (<0) . (!!2);

Seqeuence of Moves⌗

As for the algorithm, seed and kids stay the same; we end up producing the sequence of moves the same way with the same call.

moves = reverse $ snd $ head $ filter (solved.fst) $ concat 
      $ iterate (concatMap kids) seed

Rendering a Cube⌗

Things have changed a little bit; instead of projecting squares and skewing/translating them, we have to actually describe the four corner coordinates of a tile in able to render it in 3d space.

Recall that we store Tiles as 3-tuples describing the center of the tile in question; if a tile is on the top face of the cube, it will have coordinates $(\pm 1, \pm 1, +2)$, etc. Tiles don’t come bundled with normal vectors describing their face orientation, so there’s nothing to it here but to hard-code this logic.

toTile :: [Int] -> Obj
toTile [x,y,z] = p2t' [fromIntegral x, fromIntegral y, fromIntegral z]
  where p2t' [ x, y, 2] = Face [ [x+a, y+b,  n] | (a,b) <- rg ]
        p2t' [ x, y,-2] = Face [ [x+a, y+b, -n] | (a,b) <- rg ]
        p2t' [ x, 2, z] = Face [ [x+a,  n, z+b] | (a,b) <- rg ]
        p2t' [ x,-2, z] = Face [ [x+a, -n, z+b] | (a,b) <- rg ]
        p2t' [ 2, y, z] = Face [ [ n, y+a, z+b] | (a,b) <- rg ]
        p2t' [-2, y, z] = Face [ [-n, y+a, z+b] | (a,b) <- rg ]
        rg :: Num a => [(a,a)]
        rg = [(1,1),(1,-1),(-1,-1),(-1,1)] --range
        n = 5 --offset

We use n as a way to control how “exploded” the cube is; at the beginning I rendered cubes as n=2 to draw the cube realistically; later we can tune it up to explode the cube more and more.

Animation⌗

We have a couple of options here; let’s start simple and work our way up in complexity.

We can scanr and sequentially apply moves over a solvedCube to get a sequence of cubes in various staged of solved-ness.

If we write toImage <cube> <viewpoint> to return an Image px of the cube (zipped with our custom kolors color-sequence),

toImage :: [Obj] -> (Float, Float) -> Image PixelRGBA8
toImage cs v = render 500 500 40 $ world `seenFrom` v
  where world = map (second solid) $ zip cs kolors

Then we can write an animate function. In this case, because we want to do our styling in toImage, we only need an array of [Obj]s as our input. animate accepts a series of cubes, a series of viewpoints, and a series of filenames:

animate :: [[Obj]] -> [(Float,Float)] -> [String] -> IO ()
animate cs vs fs = mapM_ (\(c,v,f) -> writePng f $ toImage c v) $ zip3 cs vs fs

This is great. Let’s call something like:

main = do
  let frames    = map (map toTile) $ reverse $ scanr twist solvedCube moves
  let views     = repeat isometric
  let filenames = map (\i -> "/tmp/frame" ++ show i ++  ".png") [100000..]
  animate frames views filenames

We can see the turns a bit more clearly if we explode the cube by tuning up n, as noted above:

Animating Motion⌗

This is pretty good, but the whole point of a real isometric projection library is the ability to draw tiles in places other than along x-y, x-z, or y-z planes. Let’s try tweening frames.

Tweening is a concept from animation wherein, given a start and end position and a desired number of inbetween frames, we can generate those inbetween frames. This is a little like interpolation, but there are lots of different easing curves out there. For now we’ll stick with linear motion, though.

We want tween to take not a beginning- and end-state cube, but instead a beginning-state cube and a Side to turn (and a number of frames across which to turn it.

tween :: Int -> Side -> Cube -> [[Obj]]
tween num side cube = map (`swivel` cube) angles
  where (cardinality, axis) = s2CA side
        angles = map (* toAngle cardinality) $ init 
               $ map (/ fromIntegral num) [0..(fromIntegral num)]
        swivel :: Float -> Cube -> [Obj]
        swivel ang = map (\t -> if side `sees` t
                                  then rotateFace ang axis $ toTile t
                                  else toTile t
                         )

swivel is just a local implementation of twist above, with an inline renderer (toTile) which returns [Obj]s instead of Cubes. We generate a sequence of angles by using toAngle from above, and then simply return a series of cubes with more and more of the desired twist angle applied to it.

Now our frames looks like:

let frames r = concatMap (uncurry $ tween r) 
             $ zip (reverse moves) (reverse $ scanr twist solvedCube moves)

where r the framerate, sort of - the number of frames across each turn should occur.

If we write something like

main = do
   let frames    = concatMap (uncurry $ tween 20)
                 $ zip (reverse moves) (reverse $ scanr twist solvedCube moves)
   let views     = repeat isometric
   let filenames = map (\i -> "/tmp/frame" ++ show i ++ ".png") [100000..]
   animate frames views filenames

We might get something like

Roving Camera⌗

Just for fun, let’s create a series of views which, knowing the length of the frameset, does a complete yaw rotation. (Also we’re retuning n=3 here for a more exploded view.)

mkViews :: Int -> [(Float,Float)]
mkViews n = zip ps ys
  where ys  = take n [0, (360 / fromIntegral n).. ]
        ps  = [35,35..]

main = do
  ...
  let views = mkViews (length frames)
  animate frames views filenames

Conclusion⌗

These are all pretty fast to render, with the bulk of the difficulty being from running convert after a run to stitch the produced .pngs together into a gif. Presumably convert holds the frames in-memory, which gets expensive for longer animations; I found that using Codec.Picture to do the same thing in-Haskell was equally or more expensive.