Générateur de chiffres "pixels"

Version imprimable

13/09/2012, 16h53
Maxow

Générateur de chiffres "pixels"

Bonjour à tous,

Désolé si mon sujet n'est pas dans la bonne catégorie, j'ai beaucoup hésite en le créant !

J'ai pour projet de créer une "horloge tetris" en me basant sur la vidéo suivante :
[ame="http://www.youtube.com/watch?v=nIu74xDp2Ek"]Tetris Alarm Clock - YouTube[/ame]

Coté électronique j'utilise Arduino seulement je commence à régléchir à l'algo me permettant de "générer" les chiffres. Je pense que j'ai deux méthodes pour générer les chiffres :

- Système fixe (avec des variantes possible) mais c'est moi qui définit à l'avance comment bougent les blocs

- Système aléatoire qui trouve automatiquement les blocs et leurs positions.

Concernant la première solution il n'y a pas de soucis, seulement si je souhaite mettre en place la deuxième c'est plus compliqué. Auriez vous dans un premier temps une idée logique permettant de mettre en place cette solution ?

En me basant comme sur l'exemple de chiffres en 6x10 pixels je pourrais commencer le tableau suivant (60 bits) pour le chiffre 0 :
111111
111111
110011
110011
110011
110011
111111
111111

Je peut ensuite sélectionner un "bloc" aléatoire parmis la liste de ceux de tétris. Mais je doit ensuite tester :
- si il passe (en partant par exemple du point le plus bas)
- si il ne dépasse pas
- si il ne bloc pas
- si je peut mettre un autre bloc à la suite

Voilà c'est les premieres infos que j'ai réfléchit, je ne sait pas trop comment m'orienter après ! Si vous avez une idée ce serait top :)

Bonne après midi à tous !
13/09/2012, 19h54
pseudocode

Citation:

Envoyé par Maxow

1. Système fixe (avec des variantes possible) mais c'est moi qui définit à l'avance comment bougent les blocs

2. Système aléatoire qui trouve automatiquement les blocs et leurs positions.

3. Système fixe, mais c'est un algorithme qui a trouvé à l'avance les solutions possibles (Sur un PC externe, sans contrainte de temps).

Pour trouver les solutions, un algo de type "backtracing" explorera toutes les combinaisons réalisables.
14/09/2012, 16h45
Maxow

Merci pour ta réponse et ces précisions. Je vais regardé du coté de backtracing dans un premier temps.
20/02/2013, 11h27
Maxow

Bonjour à tous,

Je me permet de relancer cette discution car je me suis récement relancé dans ce code pour mon projet. Si je reviens sur le forum c'est que je galère pas mal, j'ai beau tourner et touner dans tous les sens je n'avance pas vraiment.

Je suis resté sur la base de tableaux, par exemple pour le chiffre 1 : (6x10)
000011
000011
000011
000011
000011
000011
000011
000011
000011
000011

Et pour les blocs, j'ai fait des tableaux de 4x4. Le "L" :
0000
1000
1000
1100

J'ai tenté de faire des vérifications par ligne, par colonnes mais rien n'y fait je ne parviens pas à mes fins !

Voici deux version de code en PHP, j'ai décidé de re-créer un second fichier car les premiers tests dataient de plusieurs mois, la seconde étant basé sur la première il y a des fonctions qui ne servent plus :
"V1" : http://pastebin.com/znnmvT4g
"V2" : http://pastebin.com/D9h51Xw3

J'ai essayé plusieurs techniques, des vérifications et des tests.

Dans le principe :
J'ai un tableau qui corrrespond à mon caractère numérique composé de nombre de 0 à 2. 0 est un espace à ne pas remplir, 1 un espace à remplir et 2 dans l'idéal un espace rempli. (donc validé)
Ensuite j'ai des tableaux correspondant aux blocs tetris que je souhaite placer sur les 1 de mon premier tableau. J'ai bien noté le système de backtracking mais avant tout il faut placer le premier bloc :p

Avez-vous quelques conseils sur la procédure à suivre pour effectuer mes tests et placer mes blocs ?

Sinon une autre petite question, avez vous une idée pour effectuer une "rotation" d'un tableau ? Par exemple de :
1 1 1 1
0 0 0 0
0 0 0 0
0 0 0 0

à

1 0 0 0
1 0 0 0
1 0 0 0
1 0 0 0

Ou encore :
0 0 0 0
1 0 0 0
1 1 0 0
1 0 0 0

à

0 0 0 0
0 0 0 0
1 1 1 0
0 1 0 0

Merci d'avance pour votre aide et vos conseils !
21/02/2013, 11h24
souviron34
Citation:

Envoyé par Maxow

- Système aléatoire qui trouve automatiquement les blocs et leurs positions.

Une petite précision : ce n'est pas aléatoire :P
- Le découpage de la forme est dans le sens vertical : on empile du bas vers le haut..
- Les éléments sont à +/- 2 pixels : soit des éléments horizontaux, soit des éléments verticaux, soit des éléments dans un sens avec +/- 1 pixel dans l'autre
- Ils arrivent tous centrés par rapport au milieu et se décalent de +/- 2 en horizontal
ça donne suffisamment de contraintes pour ne pas être aléatoire ;)
22/02/2013, 13h01
Maxow
@souviron34 : En effet il y a pas mal de conditions, c'est d'ailleurs "un problème" pour mon niveau d'algorithimie ;)

J'ai pas mal avancé grâce à une bonne idée (pas de moi !), du coup j'arrive maintenant à générer des nombre, malheureusement avec pas mal de refresh pour arriver à mon but.

Dans un premier temps mon code : http://pastebin.com/rsEpBWvc

Un exemple d'output avec le nombre 0 : http://pastehtml.com/view/ctcmuo5zj.html (39 passages, pas trop mal !)

Un exemple d'output avec le nombre 1 : http://pastehtml.com/view/ctcmx66q7.html (4 passages, pas mal ! Mais plus simple !)

Un exemple d'output avec le nombre 2 : http://pastehtml.com/view/ctcmzwztr.html (31 passages, bien !)

Je ne vais pas vous faire toute la liste (je suis allé jusqu'a 3 :p) mais pour avoir ces résultats j'ai du faire pas mal de refresh !

Il y a plusieurs points à améliorer parmis :
1. Système de vérification plus poussé (méthode Tetris->check()) pour par exemple prendre en compte le cas suivant :
  0 0 0 0 0 0
  3 3 3 1 1 1
  1 1 3 1 1 1
  qui est impossible à résoudre et que je doit pouvoir détecter. (2 points isolé dans ce cas)
2. Certains blocs ne peuvent pas être utilisé dans ma technique, le bloc utilisé dans l'exemble précédent par exemple (J à - 90°) Peut-être en effectuant des mouvement de 1 ou 2 "px" pour chaqun des blocs ?
3. Système de backtracking, dans certains cas il boucle et se retrouve dans la même situation que précédement. Je n'ai pas trop d'idée "propre" pour éviter ces cas, ma variable "ignore" n'est pas adéquate pour tous les cas.
Pour information dans un premier temps je compte trouver une suite pour remplir mes nombres, ensuite avec cette suite je devrait trouver une autre suite logique pour placer mes blocs (éviter de placer un bloc en dessous d'un autre, c'est pas la logique de tetris ^^) puis plus tard partir d'un bloc dans une position, et être capable d'effectuer des rotations de blocs (ce serait parfait !)

Donc je suis toujours dans la première étape, je souhaite pouvoir remplir me nombre avec un peu plus de précisions que 15 refresh de mon algo en PHP !

Auriez vous des conseils à me donner pour améliorer mon code et arriver un peu plus souvent à atteindre mon but ?

Merci de votre lecture !
22/02/2013, 13h46
souviron34

Citation:

Envoyé par Maxow

@souviron34 : En effet il y a pas mal de conditions, c'est d'ailleurs "un problème" pour mon niveau d'algorithimie ;)

Vu la taille de 6*10, il n'y a que peu de découpages possibles de paquets de 3 ou 4... avec lec conditions empilement vertical + entre 1 et 5 pix en ligne vertical + entre 1 et 5 pixel en ligne horizontal, non ??
22/02/2013, 14h03
Maxow

Citation:

Envoyé par souviron34

Vu la taille de 6*10, il n'y a que peu de découpages possibles de paquets de 3 ou 4... avec lec conditions empilement vertical + entre 1 et 5 pix en ligne vertical + entre 1 et 5 pixel en ligne horizontal, non ??

Oui je suis d'accord sur le nombre de solutions ;) (au fait je voulais dire contraintes, "pas mal de contraintes")

Après il ya de nombreuses solutions et malheureusement mon script actuel arrive à ne pas en trouver après 500 passage ! Mais c'est plus un soucis de logique et de débuggage ;)