Bonjour,

Je cherche un algorithme de placement a la tetris

Je m'explique, je possède une grille de 12 cases de large et possiblement infinie en longueur, représenter par une matrice

J'ai des bloc rectangulaires de tailles 4x2, 8x4 2x6...

J'aimerais un algorithme qui me place ces différents blocs de haut en bas sur cette grille, de manière a ce qu'il y ai le moins possible de trou en haut, de manière homogène (un peu de chaque bloc partout, et pas tout les même blocs rassembler au même endroit)

Existe t'il un algorithme pour faire ça ?

Merci d'avance

-
Edité par Graille 22 juillet 2016 à 15:12:12

Bonjour,

La famille de problèmes dont les solutions algorithmiques pourraient convenir est celle des problèmes du sac à dos multi dimensionnel. Ensuite il y a pleins d'inconnues dans ton explication :

• «à la tétris», j'imagine que cela signifie qu'il y a de la gravité est que «les blocs» doivent s'appuyer sur des «blocs situés en dessous»
• «possiblement infini», si c'est infini que signifient «pas de trou en haut», «remplir de haut en bas» ?
• tu as des blocs rectangulaires, soit. Mais les connais-tu avant, arrivent-ils au fur et à mesure, en as-tu un nombre limité de chaque ?

Suivant les réponses à ces interrogations tu pourras adapter un des algorithmes.

Tu dis à la tetris... ça veut dire qu'il y a de la gravité. Ca veut dire aussi que les blocs doivent être placés au fr et à mesure qu'ils arrivent...

Autrement dit, i mon 1er bloc est un carré 1X1, je le place obligatoirement sur la 1ère ligne,  dans la colonne de mon choix, par exemple dans la colonne 1.  Et si le 2ème bloc est un carré 12 *12, j'ai une seule place possible, et les 11 places inoccupées de la ligne 1 sont définitivement perdues. Même si le 3ème bloc est un rectangle 1x11 que serait rentré à merveille sur la première ligne.

Et dans ce cas, Quelle est la visibilité ? Je m'explique : Dans Tétris,si je me souviens bien, on voyait l'objet à placer, et aussi l'objet suivant. Ca permettait d'établir une certaine stratégie. Ici, on a la même visibilité ? Ou on connait à l'avance tous les rectangles qui vont arriver par la suite, et dans quel ordre ?

Dans un cas , on est dans un scénario 'probabiliste' ; dans l'autre, on a tous les éléments pour décider.   Et bien évidemment, le cas 'probabiliste' est beaucoup plus complexe.

Autre formulation qui est imprécise dans ton énoncé. Tu dis qu'il ne faudrait pas trop de trou, pas toutes les pièces semblables ensemble ..  Ces mots là, ce ne sont pas des mots mathématiques. Si j'ai 3 blocs 4*4 cote à cote, c'est éliminatoire? C'est un malus... mais acceptable ?  Il faut que tu définisses des règles précises. 

Je me suis hyper mal exprimer, "a la teris" voulait surtout dire qu'il n'y avait pas de trou, toute les lignes doivent etre completer.

Tous mes blocs sont connu avant de commencer, j'ai par exemple n rectangle de toute tailles, et je veux les placer sur ma grille de haut en bas (et non de bas en haut)

Que tu remplisses ta grille de haut en bas ou de bas en haut ne change pas beaucoup le fond du problème…

Quelle est la liste exacte de tous les rectangles que tu dois placer ? Sont-ils par ailleurs tous équiprobables ou certains sont-ils plus fréquents que d'autres ?

Je n'ai pas de liste exacte, en fait ça change a chaque chargement du programme.

Au début, j'ai un algo qui créer les blocs, leur attribut des caractéristique et ainsi de suite. Puis quand tout les blocs son configurer, ils faut les afficher. AU lieu de les afficher les un en dessous des autres, j'aimerais avoir quelque chose de stylisé en essayant de remplir le maximum d'espace en mode puzzle :).

-
Edité par Graille 24 juillet 2016 à 4:06:04

C'est un problème de recherche opérationnelle. Tu cherches la longueur minimale pour ranger tes blocs. Si tu ordonnes tous tes blocs, ça en devient une permutation de blocs (ou d'entiers) pour représenter la solution. Un voisin d'une solution peut être l'inversion de 2 entiers de la permutation. Tu as ainsi les algorithmes de recherche locale, génétiques,... pour résoudre ce problème.

Il ne te reste qu'à trouver la fonction pour calculer la longueur d'une solution donnée.

EDIT : la solution écrite comme ça ne tient pas compte de l'orientation du bloc. On pourrait ainsi ajouter un vecteur de n entiers de 1 à 4 pour donner l'orientation du bloc. Un voisin pourrait être une inversion des données dans la permutation et ce vecteur ou le changement de l'orientation d'un des blocs.

C'est un problème complexe. Il est impossible de parcourir toutes les solutions en temps polynomial. (sauf si l'on démontre que P=NP)

-
Edité par anolya 24 juillet 2016 à 12:10:40

Je pense que notre ami n'est pas très concerné par la question P=NP ou non.

Pour un rectangle, il n'y a pas 4 orientations, mais seulement 2.

Ceci étant, le mot qui me fait le plus peur dans ton message, c'est le mot 'Stylisé'. Tu avais déjà donné des indications dans ce sens. Il faut traduire ce mot en termes mathématiques, et seul toi peut faire ça.