Compact Binary Cube State + Moves

[lgarron]

A draft from 2 months ago:

Encoding

Note: the order of this encoding is a bit unnatural, but it minimizes information that is split across 8-bit, 16-bit, 32-bit, or 64-bit segments (since this will be the natural int lengths that most languages will be aple to read this from).

Component	# Bits	Interpretation
edge permutation	29	12-element permutation, Reid order
puzzle orientation	3 + 2 bits	3 bits for face on U, 2 bits for face on F (ULFRBD order as 0 to 5) 0x11111 if not supported
center orientation support	1	0x1 if center orientation is encoded, else 0x0
corner orientation	5 + 8	Reid order, radix 3 (higher order digits first), 1 is CW, 2 is CCW, first 3 corners + last 5 corners
corner permutation	16	Reid order
edge orientation	12	bit mask, Reid order, <U, R, L, D> keeps orientation
center orientation	12	ULFRBD order, # of quarter turns clockwise. All 0 if center orientation is not encoded (in order to make encoding deterministic)
Total	88

Design Goals

1. Compact. This is designed for Bluetooth Low Energy (BLE), which only has space for 20 bytes per packet.
2. Easy to write correct code to encode and decode in language.
3. Easy to encode and decode efficiently:
   • Fast algorithms to encode/decode, with low memory overhead (no large lookup tables!).
   • Byte-aligned values where possible, for simple masking/shifting.
4. Deterministic encoding.
5. Support "illegal" cube states. This serves as a checksum for normal use cases, and can support future use cases (e.g. puzzles that can detect corner twists)
6. Place all important data in a single type of message for a BLE characteristic.
   • Using multiple characteristics might be more "natural", but using a simple one is foolproof:
     • easy to implement
     • easy to test all functionality
     • easy to proxy or store values from a single stream

Draft

Component	# Bits	Interpretation
Timestamp	16	centiseconds mod 2^16 (just under 11 minutes)
Current moves	5 + 5 + 5?	TODO
Recent moves	9 + 9?	2 moves, TODO
Orientation	8?	Refinement of rough puzzle orientation from able (TODO: Quaternion? angles from rough ori?)
Move count	8	# of moves mod 256
Message Type	4 bits	see below
Mode	4 bits	see below
minutes until sleep?	6
Low battery?	1 bit	0x1: over 10%, 0x0: 10% or lower

Message Types and Modes

Code	Message Type
0x0	QUERY_RESPONSE
0x1	MOVE
0x2	STREAM_START
0x3	STREAM_UPDATE
0x4	STREAM_PAUSE

A threshold angle of X is defined as either of the following:

• face turned X since last message or
• top of puzzle orientation has moved ≈X from vertical

Continuous streaming with a given START_THRESHOLD (fraction of a quarter turn), PAUSE_THRESHOLD (fraction of a quarter turn), TIMEOUT (milliseconds) turn a minimum FREQUENCY (Hz):

• Every time the puzzle passes START_THRESHOLD:
  • Send a STREAM_START message, and start continuous streaming.
• During continuous streaming:
  • Every time any value changes at all:
    • If no message was sent in the last 1/H second: Send a STREAM_UPDATE message if puzzle orientation or current move fraction has changed at all.
    • If a message was sent in the last 1/H second: if not already scheduled, schedule a STREAM_UPDATE message to be sent no more than 1/H second after the last message was sent, with the latest data at that time.
  • If the total movement of the puzzle has not passed PAUSE_THRESHOLD since in the last TIMEOUT milliseconds, send a STREAM_PAUSE message and stop continuous streaming.

Modes

In every mode, send a MOVE message as soon as a move happens (passed 45 degrees, closer to new state than the previous MOVE message).

Code	Name	MOVE Messages	Continuous Streaming	START_ THRESHOLD	PAUSE_ THRESHOLD	TIMEOUT	FREQUENCY
0x0	MOVES	✅	❌	-	-	-	-
0x1	EFFICIENT	✅	✅	¼	¼	250 ms	10 Hz
0x2	PERFORMANCE	✅	✅	¼	⅛	1000 ms	60 Hz
0x3	EXTREME	✅	✅	any amount	-	-	120 Hz

Note that most modern displays (and the web platform) run at 60Hz. Some high-performance monitors run at 144 Hz, and iPad Pro runs at 120Hz

TODO:

• experiment and tweak values
• separate thresholds and message types for orientation and partial moves?
• support separate characteristics to minimize the amount of data that is sent?
• Allow the client to request custom modes with custom values for the parameters?

Drawing Board

• Characteristic to query state or functionality
• recent turns
• current turns?
  • physical 3x3x3s have 3 axes, 3 possible bit masks of turning faces per axis (and also "no turning"). Makes 3 + 3 + 3 + 1 = 13 possibilities. With direction info (e.g. R / R' / L / L' / R L' / R L / R' L / R' L'), 8 + 8 + 8 + 1 = 25. Plus maybe one value for unsupported?
  • speed of turn???
  • support block turn detection? Or should that be purely client-side?
  • should we support up to 6 simultaneous turns?
• synchronization info
  • timestamp (looping centiseconds, mod 256?)
  • move count (4 bits?)
  • time since previous turn?
• detailed orientation info (TODO: figure out how to reuse higher-order bits from above). This should maybe go in a separate (optional) characteristic. Synchronization info should help!
  • center orientation (partial turn info)
  • puzzle orientation
• performance status
  • battery? (Bluetooth already supports this)
  • seconds until sleep?
• Commands:
  • turn off orientation updates
  • performance level (orientation update frequency)
• metadata
  • format version? (can use spec URL in the characteristic descriptor, though)
  • message type (e.g. special message for initial data?)
  • Number of connected devices?
• UUIDs: 0xc00be001 (Or 0xc00b?), etc."

TODO

• Angular unit: fractions vs. degrees/radians vs. arcminutes vs. latitude/longitude
• Do multiple connections affect any design decisions?