A l’occasion de mon récent anniversaire, on m’a offert un Rubik’s cube dit “miroir”. Ce dernier a exactement la même mécanique qu’un Rubik’s cube traditionnel. La seule différence, redoutable, est que désormais les cubes ont la même couleur (miroir). Ce qui identifie de façon unique leur position et leur orientation, c’est les dimensions des cubes (qui ne sont ainsi plus des cubes mais des pavés).

Je n’ai jamais vraiment manipulé de Rubik’s cube et l’exercice a été parsemé de fausses manip qui m’ont fait quasiment tout recommencer ! Il y a plein de sites en ligne qui expliquent comment résoudre ce genre de casse-tête. Avec un peu d’entraînement, on y arrive.

Ca a aussi été l’occasion pour moi de découvrir que la famille des Rubik’s cube est très diversifiée avec plein de déclinaisons différentes (dont un magnifique cube 1x1x1).

Mais ce que j’aime beaucoup dans celui qu’on m’a offert c’est qu’en le manipulant, on obtient des formes complexes que je trouve agréable à regarder.

Sauf qu’après l’avoir dérangé, il faut résoudre le puzzle !

Du coup, je me suis dit que j’allais développer un petit programme qui allait explorer à ma place et de façon aléatoire, les différentes configurations du cube.

Le cube

Voici le résultat, obtenu en p5.js. J’ai utilisé pour la première fois les primitives de rendu 3D du moteur (qui s’appuie sur WebGL).

On peut bouger la vue en cliquant/déplaçant la souris. Désolé si ça ne s’affiche pas bien sur smartphone, je n’ai pas géré le côté responsive du truc. On réinitialise le cube en appuyant sur r (en fait j’adore ce bouton, compte tenu du temps qu’il m’a fallu résoudre le cube dans la vraie vie).

Considérations sur l’implémentation

La principale difficulté de ce programme a résidé en deux points :

  1. Il faut tenir à jour un index de la position des différents cubes. En effet, souhaitant faire tourner la face supérieure selon l’axe vertical nécessite de connaître les 9 cubes qui composent cette face. J’ai décidé de stocker cette information dans une liste. D’une part pour des raisons de simplicité et d’autre part parce que je ne connais pas assez bien les autres solutions offertes par JavaScript. Le point qui fut délicat ici aura été de mettre correctement cette liste à jour après n’importe quel demi-tour.
  2. Un cube participant à une rotation élémentaire verra son orientation propre évoluer, il faut garder cela à jour également. J’ai décidé de partir sur une représentation classique de l’orientation par angles d’Euler, comme nous le verrons.

La bibliothèque p5.js nous offre trois primitives qui vont nous permettre de tourner les cubes, à savoir rotateX(), rotateY() et rotateZ().

La documentation indique :

Rotates the coordinate system about the x-axis in WebGL mode.

The parameter, angle, is the amount to rotate. For example, calling rotateX(1) rotates the coordinate system about the x-axis by 1 radian.

Alors déjà, les angles de rotation sont exprimés en radian ce qui est une bonne chose. Ensuite, on s’aperçoit que p5.js fait tourner le système de coordonnées et pas le cube ! C’est la fameuse ambiguité entre alias et alibi, il nous faudra donc considérer systématiquement les transposées des matrices de rotation (tourner le cube d’un angle $\theta$ selon un axe donné revient à tourner le repère d’un angle $-\theta$ selon ce même axe). En pratique, ça ne me semblait pas super gênant vu que le sens de rotation m’importait peu, c’est une convention. Une petite difficulté surgira pourtant lorsqu’il faudra identifier quels cubes ont tourné.

Quoiqu’il en soit, on comprend que la rotation totale se calcule par l’intermédiaire des angles d’Euler. Pour des rotations du système de coordonnées selon les axes X, Y et Z, cela revient à considérer les trois matrices suivantes :

\[R_X(\alpha) = \begin{pmatrix} 1 & 0 & 0\\ 0 & \cos \alpha & \sin \alpha \\ 0 & -\sin \alpha & \cos \alpha \end{pmatrix}\] \[R_Y(\beta) = \begin{pmatrix} \cos \beta & 0 & -\sin \beta\\ 0 & 1 & 0 \\ \sin \beta & 0 & \cos \beta \end{pmatrix}\] \[R_Z(\gamma) = \begin{pmatrix} \cos \gamma & \sin \gamma & 0\\ -\sin \gamma & \cos \gamma & 0 \\ 0 & 0 & 1 \end{pmatrix}\]

En pratique, les transformations élémentaires ne sont que des quarts de tour et donc $(\alpha, \beta, \gamma) \in \{-\pi/2, 0, +\pi/2\}^3$. Les matrices d’Euler sont donc très simple et consistent essentiellement en des permutations d’axe. Plus précisément :

Axe Sens X devient Y devient Z devient
X + +X -Z +Y
X - +X +Z -Y
Y + +Z +Y -X
Y - -Z +Y +X
Z + -Y +X +Z
Z - +Y -X +Z

La documentation indique également :

Note: The order the rotations are called is important, ie. if used together, it must be called in the order Z-X-Y or there might be unexpected behaviour.

On comprend donc que la rotation totale s’écrit :

\[R = R_Y \cdot R_X \cdot R_Z\]

Mes premiers développements se heurtaient à des comportements étranges. Je me suis alors rendu compte que le repère de référence de p5.js ne forme pas un trièdre direct… J’ai commencé à prendre cela en compte dans le programme mais en fait, les choses semblent se compenser (rappelons-nous que nous faisons tourner le repère, pas l’objet).

Parant d’un état donné du cube, j’ai décidé de ne pas tenir compte de l’avertissement de la documentation (qui, je pense, ne traduit que le fait que les rotations ne commutent pas. Une fois qu’on sait ça, il faut juste savoir ce qu’on fait) et j’ai allégremment mélangé les rotations.

Partant d’un cube orienté $YXZ = (\beta, \alpha, \gamma)$ si je rajoute, mettons, une rotation $D$ d’un demi-tour positif selon l’axe X, comment s’exprimera la nouvelle orientation ? Cela revient à trouver $(\alpha’, \beta’, \gamma’)$ qui satisfait :

\[R_Y(\beta)\cdot R_X(\alpha) \cdot R_Z(\gamma)\cdot D = R_Y(\beta')\cdot R_X(\alpha') \cdot R_Z(\gamma')\]

La solution n’est pas unique et il suffit de trouver un triplet qui fonctionne pour mettre correctement les informations à jour.

Hormis le cas trivial d’un demi-tour selon l’axe Z, la résolution de ce système dépendra de l’état actuel des rotations pour savoir quel axe se transformera en quel autre axe. Il faut alors propager les permutations d’axe de rotation en rotation jusqu’à revenir sur la première. Regardant par exemple $R_X(\alpha)$ qui me demande de tourner d’un angle $\alpha$ autour de X, si entre temps, mon axe X est devenu -Y, alors il faudra mettre à jour en indiquant une rotation d’angle $-\alpha$ autour de l’axe Y.