Résolveur de rubik's cube

diabolos29 · Le 13/04/2014, à 20:41

Bonjour,

En marge du projet de jeu sur lequel je travaille (Action RPG type Zelda 3), j'ai aussi un autre projet un peu différent.
Il s'agit en fait de concevoir entièrement une machine capable de résoudre un rubik's cube de A à Z.
Les seules actions sont de poser le cube mélangé dans la machine et de cliquer sur un bouton pour lancer la résolution du cube.

Le soft est développé en C++ avec les libs Qt et OpenCV, sous GNU/Linux.
La machine est pilotées via un arduino.

Le développement a débuté en janvier 2013 (et s'est poursuivi par intermittences ensuite).
Voilà ce que ça donne maintenant que je l'ai quasi terminé :
http://youtu.be/Nl6sbZRm60s

Les sources (sous licence GPL) sont disponibles à l'adresse suivante : http://dev.sujets-libres.fr

Je n'ai pas encore terminé ce projet mais ça fonctionne.

[edit]
Et hop, nouvelle vidéo : http://youtu.be/XVA8TiN_8TE
La solution est générée ici par grâce à une appli externe que j'appelle depuis mon programme. Cette solution est quasi optimale.
[/edit]

Dernière modification par diabolos29 (Le 01/05/2014, à 12:57)

Madeba · Le 13/04/2014, à 20:53

Ça va, tu t'es bien amusé
Le plus pénible dans ce genre de projet, c'est l'usinage des pièces. Les pièces sont un peu trop grosses pour l'imprimante 3D.
Quel genre de moteurs utilises tu ? Tu utilises une webcam basique avec opencv?

diabolos29 · Le 13/04/2014, à 21:28

La machine est construite à partir de panneaux de médium (j'ai utilisé des chutes que j'avais chez moi). C'est assez facile à travailler, à la scie sauteuse ou avec de petites limes tout en étant suffisamment solide.
Une partie des pièces auraient pu être réalisées par une imprimante 3D je pense. Il n'est d'ailleurs pas impossible que j'en fasse refaire par ce biais plus tard.

Pour les moteurs, j'utilise deux servomoteurs basiques (HS311) et un moteur pas à pas 12V. C'est ce qui m'a coûté le plus cher en passant (60€ env pour les moteurs en tout).
Ils sont pilotés par un arduino et alimentés par une alim de PC.

J'ai d'abord utilisé une alim seule mais j'ai rencontré des comportements étranges (chutes de tension aléatoires). Deux hypothèses :
- Soit la charge sur l'alim était trop faible (environ 20W consommés théoriquement), ce qui fait que je ne devais pas me trouver dans la bonne plage de fonctionnement.
- Soit mon alim était foireuse à la base (possible car alim de récup et pas vraiment testée).

Bref, j'utilise temporairement un vieux PC sur lequel j'ai simplement déconnecté le disque dur. Je l'allume et je repique juste la 12V pour alimenter mon montage. Plus de comportements étranges depuis. Il faudra que je trouve une meilleure solution par la suite...

J'utilise une vieille webcam USB de recup. Du moment qu'elle est reconnue sous GNU/Linux, pas de soucis.

Dernière modification par diabolos29 (Le 13/04/2014, à 21:31)

moths-art · Le 14/04/2014, à 08:33

Chapeau l'artiste! vraiment sympa...

Pour la réponse à "Madeba" : c'est bien de l'openCV derrière : il suffisait de se plonger un peu dans les sources

MinecraftBreizh · Le 14/04/2014, à 08:51

Bravo à toi. Si j'ai bien compris, ça analyse les faces du cube puis ça exécute les mouvements nécessaires à la résolution ?

MinecraftBreizh · Le 14/04/2014, à 11:56

Une machine au même fonctionnement mais avec un langage et un matériau différent : http://youtu.be/wm9_RRYTpys

Sibe · Le 14/04/2014, à 13:48

Très bon travail diabolos29 !

moths-art · Le 14/04/2014, à 20:25

MinecraftBreizh : l'idée d'utiliser des lego technique est tout bonnement fabuleux!

diabolos29 · Le 14/04/2014, à 20:27

Merci ,

MinecraftBreizh a écrit :

Bravo à toi. Si j'ai bien compris, ça analyse les faces du cube puis ça exécute les mouvements nécessaires à la résolution ?

Oui, c'est bien ça.
A noter qu'entre l'analyse des faces du cube et sa résolution, il y a une grosse partie de recherche d'une solution. C'est cette partie là que je dois améliorer maintenant.

MinecraftBreizh a écrit :

Une machine au même fonctionnement mais avec un langage et un matériau différent : http://youtu.be/wm9_RRYTpys

En fait, on trouve pas mal de machines construites en Lego et/ou utilisant le boîtier Lego Mindstorm (il doit même y avoir des kit tout fait, à vérifier). Du coup, tout est déjà conçu et ça perd un peu de son intérêt je trouve (mais ce n'est que mon point de vue).
Certaines sont tout de même très intéressantes et valent le coup d’œil.

Dernière modification par diabolos29 (Le 14/04/2014, à 20:28)

MinecraftBreizh · Le 14/04/2014, à 20:33

En effet on en trouve beaucoup, et j'ai eu l'occasion d'en manipuler une au collège (pas perso, à 300€ c'est pas donné ces trucs là...), il n'y a pas de kit enfin un : il permet de construire 3 petits robots et ne contient que les bases. Après il faut payer des pièces supplémentaires (Technic et Mindstorms). Mais là je pars en hors-sujet...
De toute façon ton projet ne peut que s'améliorer, il fonctionne, maintenant il faut le perfectionner (enfin je serais perso incapable d'en arriver là déjà... )

diabolos29 · Le 26/04/2014, à 18:41

Et hop, nouvelle vidéo : http://youtu.be/XVA8TiN_8TE
Cette fois-ci, l'algo utilisé permet de trouver une solution optimale en 20 coups. On arrive plus rapidement à la solution du coup...

MinecraftBreizh · Le 28/04/2014, à 10:43

Ah oui en effet, une minute environ, c'est bien plus rapide.
Bien joué !

Tu pense qu'on peux faire encore mieux ou c'est déjà assez optimisé ?

diabolos29 · Le 28/04/2014, à 21:00

Merci.

Côté algo, il n'y a plus grand chose à améliorer puisqu'on est déjà quasiment à l'optimal.

Côté mécanique, j'ai encore réalisé quelques petite optimisations (ce qui me permet de grapiller quelques secondes sur le temps de résolution global tout en conservant une bonne précision) mais il va être difficile de faire mieux. A part remplacer les moteurs par des plus puissants, je ne vois pas.

MinecraftBreizh · Le 28/04/2014, à 23:30

Eh bien félicitations alors.
Reste plus qu'à commercialiser l'engin !

Caribou22 · Le 29/04/2014, à 00:00

Chapeau le fait maison !

Une vidéo du genre (surement déjà ultra connue), mais pas du tout avec les mêmes moyens ^^ http://youtu.be/X0pFZG7j5cE

moko138 · Le 29/04/2014, à 06:24

diabolos29 a écrit :

A noter qu'entre l'analyse des faces du cube et sa résolution, il y a une grosse partie de recherche d'une solution. C'est cette partie là que je dois améliorer maintenant.

Chapeau, de ma part aussi !

Dernière modification par moko138 (Le 29/04/2014, à 06:26)

cris22 · Le 29/04/2014, à 11:31

Beau travail, félicitations !

diabolos29 · Le 01/05/2014, à 13:07

MinecraftBreizh a écrit :

Eh bien félicitations alors.
Reste plus qu'à commercialiser l'engin !

Si quelqu'un veut s'amuser à le faire, mes sources sont dispo sous licence GPLv3 (je doute quand même un peu de l'intérêt de la chose).
Un bémol cependant, l'utilisation du paquet Java n'est autorisée par son auteur que dans le cadre d'une utilisation non commerciale. Seule la partie permettant de trouver une solution non optimale (ma partie quoi) peut éventuellement être intégré dans une solution commerciale (et si cette solution respecte les termes de la GPLv3).

Caribou22 a écrit :

Chapeau le fait maison !
Une vidéo du genre (surement déjà ultra connue), mais pas du tout avec les mêmes moyens ^^ http://youtu.be/X0pFZG7j5cE

Oui, c'est une vidéo qui tourne pas mal et c'est certain que je ne joue pas dans la même cour .

Dernière modification par diabolos29 (Le 01/05/2014, à 13:09)

moko138 · Le 01/05/2014, à 13:41

diabolos29 a écrit :

Une vidéo du genre (surement déjà ultra connue), mais pas du tout avec les mêmes moyens ^^ http://youtu.be/X0pFZG7j5cE
Oui, c'est une vidéo qui tourne pas mal et c'est certain que je ne joue pas dans la même cour .

Sauf que le cube est déjà en place dans le video d'AMR, donnant à penser que l'analyse et la solution ont eu lieu - ou ont pu avoir lieu - avant le top chrono.
Alors que dans ta video, on te voit modifier les faces et placer le cube dans ta bécane puis la démarrer.
De toute façon, ce qui est super c'est que tu aies fait toi-même les deux parties, logicielle et mécanique.

cracolinux · Le 07/05/2014, à 16:20

Putain c'est superbe comme projet !

Bravo, je suis vraiment sous le charme!

...allez, je la regarde encore une fois!

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 13/04/2014, à 20:41

Résolveur de rubik's cube

#2 Le 13/04/2014, à 20:53

Re : Résolveur de rubik's cube

#3 Le 13/04/2014, à 21:28

Re : Résolveur de rubik's cube

#4 Le 14/04/2014, à 08:33

Re : Résolveur de rubik's cube

#5 Le 14/04/2014, à 08:51

Re : Résolveur de rubik's cube

#6 Le 14/04/2014, à 11:56

Re : Résolveur de rubik's cube

#7 Le 14/04/2014, à 13:48

Re : Résolveur de rubik's cube

#8 Le 14/04/2014, à 20:25

Re : Résolveur de rubik's cube

#9 Le 14/04/2014, à 20:27

Re : Résolveur de rubik's cube

#10 Le 14/04/2014, à 20:33

Re : Résolveur de rubik's cube

#11 Le 26/04/2014, à 18:41

Re : Résolveur de rubik's cube

#12 Le 28/04/2014, à 10:43

Re : Résolveur de rubik's cube

#13 Le 28/04/2014, à 21:00

Re : Résolveur de rubik's cube

#14 Le 28/04/2014, à 23:30

Re : Résolveur de rubik's cube

#15 Le 29/04/2014, à 00:00

Re : Résolveur de rubik's cube

#16 Le 29/04/2014, à 06:24

Re : Résolveur de rubik's cube

#17 Le 29/04/2014, à 11:31

Re : Résolveur de rubik's cube

#18 Le 01/05/2014, à 13:07

Re : Résolveur de rubik's cube

#19 Le 01/05/2014, à 13:41

Re : Résolveur de rubik's cube

#20 Le 07/05/2014, à 16:20

Re : Résolveur de rubik's cube

Pied de page des forums