Rolling Cubes and Group Theory

I love the “rolling cube” genre of puzzle games like Bloxorz, Cuboid, and Edge:

With Bloxorz and Cuboid, the orientation of the player (vertical versus horizontal) plays an important role in solving puzzles. For example, the end goal of each puzzle is a hole that can be passed through only when the player is vertically oriented.

In Edge (far right panel), the player is a cube with visually indistinguishable faces. The game is fast paced and mercifully does not have puzzles that take the cube’s orientation into account.

Some other rolling cube games that look interesting to me are Cubix Challenge, CubiX Fragment, and Cubiques.

Let’s think about a rolling cube game that does treat orientation in a significant way.

In the concept video below, the player controls a cube whose faces are textured with digits 1 through 6. It has a special “switch tile” that activates a bridge only when the cube rests on it with a certain orientation. I made this prototype using Filament.

Group Theory

Let’s talk a little about mathematical group theory, which provides a vocabulary that can be used to discuss symmetries of cubes and tiles.

Let G be a set bundled with a binary operation. We say that G is a group if all the following conditions are true:

1. The result of the operation is always in G, thus exhibiting closure.
2. The operation is associative such that \((a∘b)∘c = a∘(b∘c)\).
3. The set contains an identity element such that \(a∘I = I∘a = a\).
4. The operation is invertible such that \(a∘\textit{inv}(a) = \textit{inv}(a)∘a\).

The switch tile in the above game concept belongs to a group called D₄, also known as the dihedral group of order 8. The elements of this group are depicted in the animation below.

The cube has 48 symmetries, but only 24 can be realized using physical rotations. The other 24 could only be obtained via reflection. The rotation-only group for cubes is called S₄, and is sometimes known as the octahedral group. Octahedra and cubes are dual Platonic solids, so they belong to the same symmetry group.

To remember that a cube has 24 rotational symmetries, you can multiply the number of faces by the number of 90-degree rotations along the z-axis (6*4). Another strategy is to compute the number of permutations of the four body diagonals, which is 4!.

Labels for Orientations

One way to label each element in S₄ is to combine a single digit and letter. The digit is an integer in the range [1,6] and represents which face you can see. The letter is in {a, b, c, d} and represents a number of quarter-turn rotations along the viewing axis.

Yet another way of naming each of the 24 cube orientations is to use a quaternion that can rotate a base configuration to the desired orientation. Since these quaternions are composed of quarter-turn rotations, the individual components of each quaternion always belong to the following set. \[ \textstyle \left \{ 0, \pm 1, \pm \frac{1}{2}, \pm\frac{\sqrt{2}}{2} \right \} \]

This limited set of quaternions can easily be encoded into a 16-bit word. For example, by applying \(\left \lfloor{5 + \epsilon + 5q}\right \rfloor\) to each component \(q\) of the quaternion, every legal value maps to a non-negative integer that fits in 4 bits.

Some Helpful Code

Before writing code that performs the encoding described above, note that any quaternion is equivalent to the component-wise negation of itself. So, let’s standardize the incoming quaternion such that its first non-zero component is always positive. The following code snippet makes two small loops over the quaternion components: the first loop finds the first non-zero component, and the second loop performs the actual encoding.

uint16_t encode_quaternion(const double quat[4]) {
    double scale = 0.0;
    for (int i = 0; i < 4 && scale == 0.0; i++) {
        if (quat[i] > +0.1) scale = +5.0;
        else if (quat[i] < -0.1) scale = -5.0;
    }
    assert(scale != 0.0 && "Unexpected quaternion.");
    uint16_t result = 0;
    for (int i = 0; i < 4; i++) {
        const int c = 5.1 + scale * quat[i];
        result = (result >> 4) | (c << 12);
    }
    return result;
}

The following table lists the results of the above code snippet for all 24 rotational cube symmetries. This table also includes the “digit and letter” label mentioned earlier. Note that 6a is the base orientation that corresponds to the identity quaternion.

Another way of representing cube orientation uses a pair of enums. One enum tells you the face that is presently on top, and the other tells you the spin around the axis that’s perpendicular to the floor:

enum class CubeFace { LEFT, RIGHT, BOTTOM, TOP, BACK, FRONT };

enum class CubeSpin { d0, d90, d180, d270 };

struct CubeOrientation {
  CubeFace face; // The side that is facing the sky.
  CubeSpin spin; // Quarter turns around ground-to-sky axis.
};

Note that spin is ordered second in the structure to emphasize that it is applied after the face rotation is applied to the base configuration.

Next let’s think about some helpful utilities to accompany our little struct. We might need a function that applies a rolling movement, as well as conversion functions for quaternions:

enum class Direction { EAST, NORTH, WEST, SOUTH };

CubeOrientation apply_roll(CubeOrientation ori, Direction dir);

void cube_to_quaternion(CubeOrientation ori, float quat_out[4]);

CubeOrientation cube_from_quaternion(const float quat[4]);

The cube_to_quaternion function is fairly easy to implement. Just apply the face rotation around the X or Y axis, then apply the spin rotation around the Z axis. Something like the following should work.

void cube_to_quaternion(CubeOrientation orientation, float quat_out[4]) {
    float q0[4];
    switch (orientation.face) {
        case CubeFace::FRONT: quat_identity(q0); break;
        case CubeFace::BACK: quat_rotate_y(q0, M_PI); break;
        case CubeFace::TOP: quat_rotate_x(q0, M_PI / 2); break;
        case CubeFace::BOTTOM: quat_rotate_x(q0, -M_PI / 2); break;
        case CubeFace::LEFT: quat_rotate_y(q0, M_PI / 2); break;
        case CubeFace::RIGHT: quat_rotate_y(q0, -M_PI / 2); break;
    }
    float q1[4];
    quat_rotate_z(q1, float((int)orientation.spin) * -M_PI / 2);
    quat_multiply(quat_out, q0, q1);
}

Going the other away around is a bit more tricky. One way of implementing quaternion_to_cube is to leverage the 16-bit encoding from earlier in the post, and build a little table of quat encodings to CubeOrientation instances. The implementation might look a little like this:

CubeOrientation cube_from_quaternion(const float quat[4]) {
    const uint16_t* table = get_table_singleton();
    const uint16_t code = encode_quaternion(quat);
    for (int index = 0, face = 0; face < 6; face++) {
        for (int spin = 0; spin < 4; spin++, index++) {
            if (table[index] == code) {
                return CubeOrientation{(CubeFace)face, (CubeSpin)spin};
            }
        }
    }
    assert(false && "Unexpected quaternion.");
    return {};
}

Topology

Rolling a cube is not the only way to change its orientation. In the game concept depicted below (again, I used Filament to render these videos), the cube slides instead of rolls, but the player can still change its orientation by circumnavigating an interesting surface.

In the above game concept, non-orientable surfaces (like a Möbius strip) could be used to great effect, because they would allow the player to change orientation simply by sliding around on the surface.

By the way, if you’re interested in arranging tiles on a sphere (which is an orientable surface, but nevertheless tricky to deal with) please check out this excellent article at Red Blob Games.

Philip Rideout, 11 November 2020.