Tetris comme imprimeur

En tournant, en réorganisant et en abaissant une séquence de formes prédéterminée, Tetris Printer Algorithm utilise la mécanique de Tetris pour générer des bitmaps arbitraires.

Description de l'algorithme

L'algorithme convertit les pixels de l'image source en carrés du champ Tetris ligne par ligne, se déplaçant de bas en haut. Pour générer un seul carré, l'algorithme assemble une structure composée d'une zone rectangulaire qui est complètement supportée par un carré en dessous. Une fois l'assemblage de la région rectangulaire terminé, ses lignes sont effacées, laissant un carré en dessous. Voici trois exemples de ce comportement.




Comme indiqué ci-dessous, l'algorithme peut également générer plusieurs carrés avec une seule structure.


Dans le processus de construction d'une ligne, tous les carrés ainsi créés doivent être basés sur quelque chose. Dans les images ci-dessus, les carrés générés sont sur le sol du terrain de jeu. Cependant, si une ligne arbitraire contient des trous, elle ne pourra pas fournir le support nécessaire pour construire une ligne au-dessus d'elle. L'algorithme résout ce problème en créant une plate-forme plate au-dessus de la chaîne avec des trous. Dans l'animation ci-dessous, une plate-forme construite au sommet d'une ligne se compose d'un carré rouge. Une plate-forme est une structure temporaire et l'insertion de la dernière forme la supprime.


La rangée de 5 carrés rouges illustrée ci-dessous est au-dessus de la rangée de 3 carrés rouges. Ceci est réalisé en construisant une plate-forme plate en haut de la ligne du bas. La plateforme fournit le support nécessaire pour générer 5 carrés rouges. À la fin, la plate-forme est supprimée en insérant la dernière forme et la nouvelle ligne se met en place. Notez que si l'algorithme doit générer des lignes dans l'ordre inverse (une ligne de 3 carrés rouges au-dessus d'une ligne de 5 carrés rouges), la plate-forme ne sera pas nécessaire.

Un motif carré

Pour référence, je donnerai les noms de 7 tetramino (pièces de jeu).


La version de Tetris Printer Algorithm présentée dans l'article est spécialement conçue pour le rendu des sprites d'anciens jeux vidéo. Ces jeux contiennent des graphiques en 8 × 8 tuiles, et 2 octets ont été alloués pour chaque pixel. Par conséquent, les sprites ne contenaient généralement que 3 couleurs plus des zones transparentes et avaient le plus souvent une taille de 16 × 16 ou 16 × 32 pixels.

L'animation ci-dessous montre tous les motifs utilisés pour créer des carrés individuels. Chaque motif utilise un tétramino interchangeable J, T et L, créant un seul carré en bas. L'algorithme attribue ce tétramino à l'une des 3 couleurs présentes dans le sprite. Le reste du tétramino se voit attribuer des couleurs arbitraires. Tout au long du gameplay, toutes les couleurs restent constantes.


En raison de la forme des trois tétraminos, il est impossible de créer un carré à partir des trois couleurs dans les deux premières et les deux dernières colonnes. Par conséquent, la largeur minimale du terrain de jeu pour le rendu d'un sprite d'une largeur de 16 pixels est de 2 + 16 + 2 = 20 carrés. Cependant, il s'est avéré que 20 est trop peu.

Comme indiqué ci-dessous, la zone au-dessus du carré inférieur unique ne peut pas être constituée d'une seule ligne, car les seules figures qui peuvent y entrer (tetramino I) n'ont aucun support.


Avec deux lignes, la seule façon d'étirer tout le terrain de jeu pour qu'il soit pris en charge est d'utiliser le tetramino S et Z. Mais dans ce cas, les trous resteront dans la ligne supérieure.


Le nombre minimum de lignes requises au-dessus du carré inférieur est de 3, et comme indiqué plusieurs fois ci-dessus, de tels modèles existent. 20 carrés est la largeur minimale requise pour placer un sprite d'une largeur de 16 pixels. Mais 20 × 3 + 1 = 61, et ce nombre n'est pas divisible par 4, ce qui signifie qu'il ne peut pas être construit à partir de tétramino. Cependant, une largeur de 21 nous donne 21 × 3 + 1 = 64, et il peut être construit à partir de 16 tetramino. En fait, cette largeur permet à l'algorithme de rendre les sprites jusqu'à 17 pixels de large.

Le terrain de jeu du Tetris original a une taille de 10 × 20 carrés (rapport 1: 2). Dans cette version de l'algorithme, ce rapport est préservé - le terrain de jeu a une taille de 21 × 42 carrés.

Étant donné que le tétramino J, T et L sont interchangeables lors de la création d'un carré, et que 3 carrés de ces tétramino sont impliqués dans la création d'une ligne au-dessus, il existe 21 - 3 = 18 motifs pour créer un seul carré. Cependant, en raison de la symétrie miroir, il n'y a en fait que 9. Il y a 3 lignes qui fonctionnent pour la plupart de ces 9. Cependant, une étude informatique approfondie a montré que les deux modèles avaient besoin de plus. La prochaine option possible est de 7 lignes, car 21 × 7 + 1 = 148, ce qui nécessite 37 tétraminos. Comme le montrent les images ci-dessous, de tels modèles existent.

Motifs carrés multiples

Les motifs de création de plusieurs carrés sont limités aux trois mêmes couleurs créées par les motifs d'un seul carré. Les carrés résultants sont créés à partir de tetramino J, T et L, chacun occupant 3 carrés sur une ligne au-dessus de la ligne de création. Le nombre maximum de carrés pouvant potentiellement être créés avec un seul motif est 21/3 = 7. Cependant, pour les sprites d'une largeur de 16 pixels, le tétramino le plus à droite ne peut pas créer un carré. Même dans le cas de sprites d'une largeur de 17 pixels, il peut créer un carré d'une seule couleur. Par conséquent, le modèle de création à partir de 7 carrés est rarement utilisé.


Le nombre de modèles pour créer un nombre arbitraire de carrés peut être déterminé en utilisant la combinatoire des énumérations. Considérez le modèle ci-dessous, représentant une rangée au-dessus d'une rangée de trois carrés. Chaque bloc de trois carrés blancs adjacents désigne une partie de tetramino; les carrés créés ne sont pas affichés.


Trois tétramino créent 4 vides. Il y a 21 - 3 × 3 = 12 carrés sombres qui peuvent être insérés arbitrairement dans ces vides pour former un motif spécifique. Le nombre de façons de distribuer ces carrés sombres peut être calculé en les plaçant sur une ligne dans laquelle les carrés blancs simples sont traités comme des séparateurs.


La tâche a donc été réduite au calcul de la valeur du coefficient du polynôme. En regardant ces carrés blancs, vous pouvez comprendre qu'il s'agit du nombre de façons de choisir 3 sur 15. = 455.

Dans le cas général, pour n il est égal à . Mais en raison de la symétrie miroir, en fait, ils sont deux fois moins; si la quantité est impaire, puis en divisant par deux, nous arrondissons à l'entier le plus proche pour inclure le modèle idéalement symétrique qui devrait exister dans cet ensemble, comme, par exemple, illustré ci-dessous pour le cas avec 455.


En appliquant cette formule à 7 tetramino, nous confirmons l'évidence: il n'y a qu'un seul motif pour créer 7 carrés.

Le modèle de création de 6 carrés peut être construit de deux manières: deux lignes pleines (2 × 21 + 6 = 48) et six lignes remplies (6 × 21 + 6 = 132), ce qui nécessite 12 et 33 tetramino. La formule ci-dessus montre qu'il existe 84 modèles pour créer 6 carrés, mais seulement 35 d'entre eux peuvent être construits à partir de 2 lignes complètes. 49 modèles nécessitent 6 lignes. Les nombres sont impairs en raison des motifs symétriques illustrés ci-dessous.



Il convient également de noter que 2 lignes sont possibles ici, car contrairement au modèle de création d'un carré qui nécessitait le tétramino S et Z, 6 chiffres sont utilisés dans ces modèles.

Le tableau ci-dessous indique le nombre de carrés créés par chaque type de motif, le nombre de lignes complètes, le nombre de tétramino utilisé et le nombre de motifs.


Exemples de modèles.

Plateformes

Avant de construire une ligne, l'algorithme examine la ligne en dessous. Si la rangée du bas ne peut pas prendre en charge tous les carrés au-dessus, alors une plate-forme temporaire est nécessaire. Lorsque la plate-forme est supprimée, une nouvelle ligne descend, et en raison de la façon dont la gravité est implémentée dans le Tetris d'origine, certains carrés restent suspendus dans l'air.

L'illustration ci-dessous montre 10 modèles de plate-forme. La construction de la plate-forme commence par abaisser le tétramino T au-dessus de l'un des carrés de la dernière ligne générée. Les tétraminos restants dépendent de ce premier T. Autrement dit, si la ligne générée précédente contient au moins 1 carré, comme le carré rouge dans l'image ci-dessous, nous pouvons créer une plate-forme plate au-dessus pour générer la ligne suivante.


Au milieu de la construction de la plate-forme, la ligne du bas est terminée et supprimée, laissant trois lignes au-dessus. Le dernier tétramino J ou L, qui supprimera ces lignes, n'est inséré que lorsque les modèles de création génèrent la ligne de sprite suivante au-dessus de la plate-forme. Cette dernière figure empêche la création de carrés dans les deux premières et dernières lignes. Mais, comme mentionné ci-dessus, en raison de la géométrie du tétramino J, T et L utilisé dans ce processus, les modèles de création de carrés sont limités à 17 colonnes internes.

De plus, sur 19 façons possibles de construire des plates-formes au-dessus de Tetramino T, il n'y en a que 10 ci-dessus.

Matrices emballées

Comme indiqué ci-dessus, un sous-ensemble des 6 modèles de création de carrés implique de ne supprimer que deux lignes. Tous les autres modèles nécessitent 6 lignes. Pour comprendre pourquoi c'est le cas, considérez le modèle ci-dessous.


Ces tetramino sont interchangeables avec tetramino J et L, et chacun d'eux ajoute 3 carrés adjacents à la rangée commune. Les lignes à compléter sont représentées par la matrice ci-dessous.


Maintenant, le tout consiste à emballer un espace vide avec du tetramino. En partant de la gauche, la seule option est d'utiliser la séquence tetramino I.


La seule façon de remplir l'espace restant est d'utiliser J et O ou I et L. Les deux options sont présentées ci-dessous.



Malheureusement, tetramino O et L ne sont pas pris en charge dans les matrices illustrées ci-dessus. Ce motif à 6 carrés nécessite une matrice plus grande.

Un problème similaire se pose dans deux modèles de création d'un carré. Considérez la matrice ci-dessous:


La seule façon de remplir la ligne du bas à droite est d'enchaîner la séquence Z.


De même, le seul moyen d'obtenir 3 cases vides en bas à gauche est le tetramino S.

Dans la ligne médiane, il y a un carré vide entre S et Z et la seule façon de le remplir est d'utiliser le tétramino J, T ou L, comme indiqué dans les figures ci-dessous.



L'insertion de l'une de ces formes divise l'espace vide. La zone vide à gauche contient respectivement 5, 6 et 7 vides. Puisqu'aucune de ces valeurs n'est divisible par 4, il est impossible de continuer. Une matrice plus grande est requise pour ce motif carré unique.

Il en va de même pour un autre motif de création d'un carré, illustré dans la matrice ci-dessous.


Après avoir utilisé tetramino S et Z pour remplir la majeure partie de la ligne du bas, il y a un espace vide entre eux sur la ligne médiane.


Comme indiqué dans les images ci-dessous, l'insert de trou divise l'espace vide et la zone vide à gauche contient 9, 10 ou 11 carrés, respectivement; aucun des nombres n'est divisible par 4.



Mais l'emballage de matrices n'est pas le seul moyen de générer un motif de carrés. Par exemple, jetez un œil au créateur de 4 carrés ci-dessous.


Ce qui suit est une tentative de rendre le modèle comme un ensemble de tétraminos emballés.


Le dernier L est ignoré, car un espace n'est formé qu'après l'achèvement et la suppression de la troisième ligne.

Mais après une recherche approfondie, il a été découvert que cette technique ne permet pas aux modèles à un carré susmentionnés de fonctionner avec seulement 3 lignes. De plus, il ne lui permet pas d'implémenter de nouveaux motifs de 6 carrés sur deux lignes. Il n'est pas nécessaire de rechercher les motifs restants en dehors des matrices emballées, car ils utilisent déjà la plus petite quantité possible de tétramino. Et en nous limitant aux matrices emballées, nous trouverons tous les modèles nécessaires beaucoup plus rapidement.

Recherche de motifs

Pour simplifier la sortie des données, l'algorithme d'imprimante Tetris se limite à créer du tétramino au point central supérieur du terrain de jeu, à le tourner, à le déplacer horizontalement et à l'abaisser. Il n'a jamais à déplacer la figure horizontalement après avoir passé une certaine distance. Cette restriction réduit considérablement l'espace de recherche, car elle ne permet pas la formation de lacunes sous les chiffres ajoutés à la matrice. À titre d'exemple, regardons la matrice des 3 carrés suivante.


Si nous jetons J au centre de la matrice, comme indiqué ci-dessus, nous obtenons alors un espace de 2 carrés vides, qui ne peuvent pas être remplis avec les chiffres suivants. Par conséquent, la recherche ne suivra pas ce chemin.


Étant donné que les espaces couverts ne sont pas autorisés, chaque colonne de la matrice peut être considérée comme une pile de carrés remplis et la hauteur de ces piles décrit pleinement le contenu de la matrice entière. Quel que soit le nombre de lignes, un tableau entier unidimensionnel à 21 éléments sera suffisant pour décrire une matrice bidimensionnelle.

Lorsqu'un chiffre tombe dans la matrice, les hauteurs des piles des colonnes correspondantes augmentent. Pour accélérer ce processus, toutes les tétramines sont analysées à l'avance. Il y a 19 tours tétramino, et la recherche considère chacun d'eux comme une figure unique.


Tetramino J dans le coin supérieur gauche de l'image occupe 3 colonnes. Lors de la descente sur la matrice, les hauteurs de 3 piles adjacentes augmentent respectivement de 1, 1 et 2 carrés. Mais avant que la figure puisse être abaissée, le profil inférieur de la figure doit correspondre au profil supérieur des piles respectives. Si ce J était allongé sur le sol du terrain de jeu, sous chacune de ces colonnes, il aurait dû y avoir des espaces de 1, 1 et 0 cases vides. Étant donné que les dégagements sont interdits, les hauteurs relatives de 3 piles devront correspondre parfaitement au modèle.

Une autre conséquence de l'absence de lacunes est que lorsque les chiffres tombent dans la matrice, les rangées sont remplies de bas en haut. Il n'est pas possible de remplir une ligne au milieu d'une matrice avant ou sans compléter toutes les lignes en dessous. Dans le processus de remplissage de la matrice, sa limite inférieure remonte en fait. Par conséquent, une pile de colonnes de matrice peut fournir un support uniquement si sa hauteur moins le nombre de lignes terminées est supérieure à 0. Lorsqu'une forme est ajoutée à la matrice, au moins une des colonnes correspondantes doit fournir un support.

La recherche stocke un deuxième tableau unidimensionnel contenant le nombre de carrés remplis dans chaque ligne. Le J ci-dessus contient dans les lignes correspondantes 3 et 1 un carré. Lorsque vous l'insérez dans la matrice, ces valeurs sont ajoutées aux éléments correspondants du tableau. Le nombre de lignes complétées est le nombre d'éléments avec une valeur de 21.

Comme indiqué dans la section précédente, si la figure ajoutée divise la matrice, les tailles des zones résultantes doivent être divisées par 4. Par exemple, dans l'image ci-dessous, l'ajout de I crée 2 zones, chacune contenant 46 carrés vides. Puisque 46 n'est pas divisible par 4, il n'y a plus de moyen de remplir le reste de la matrice.


La séparation apparaît lorsque la hauteur de la pile est égale à la hauteur de la matrice. Après avoir inséré la figure en incrémentant les hauteurs des piles respectives, les dimensions de toutes les zones divisées d'espace vide peuvent être déterminées en scannant le tableau de hauteurs et en ajoutant l'espace restant dans chaque pile. Ce nombre est vérifié et réinitialisé lorsqu'un fractionnement est détecté.

La recherche utilisée pour générer tous les modèles utilise une construction incrémentale randomisée, un algorithme de retour en arrière qui vérifie systématiquement toutes les combinaisons dans un ordre aléatoire. La construction incrémentale d'une solution en insérant des formes au hasard la fait grandir comme un cristal. L'aléatoire fournit une irrégularité contenant des faces brisées qui servent de base aux formes ajoutées par la suite. La plupart de la matrice est emballée au hasard très rapidement, et lorsque l'espace vide devient rare, le retour en arrière entre en jeu.

Avant d'effectuer la recherche, des permutations aléatoires de 371 façons d'ajouter un chiffre à la matrice sont effectuées. Le pseudo-code de la fonction de recherche est indiqué ci-dessous.

private Result search(Matrix matrix, int remaining) { if (remaining == 0) { return SOLUTION } attempts := attempts + 1 if (attempts >= MAX_ATTEMPTS) { return TIMEOUT } if (     S  Z) {        S  Z if (  ) { Result result := search(matrix, remaining - 1) if (result == SOLUTION) { return SOLUTION }       if (result == TIMEOUT) { return TIMEOUT } } }          for(   ,    ) {      if (   ) { Result result := search(matrix, remaining - 1) if (result == SOLUTION) { return SOLUTION }       if (result == TIMEOUT) { return TIMEOUT } } } return NO_SOLUTION } 

La matrice d'origine passée à la fonction de recherche est vide, à l'exception de la ligne du bas contenant des blocs de 3 carrés adjacents. Il est transmis avec le nombre de chiffres restants à ajouter. S'il remaining 0, la matrice contient la solution et la fonction retourne. Chaque appel récursif incrémente le nombre global de attempts . S'il dépasse MAX_ATTEMPTS , qui a une valeur de 1 000, la recherche recommence.

La troisième if essaie d'ajouter le tétramino S ou Z au bas de la matrice si l'espace le permet. Cela signifie éviter des situations comme celle illustrée ci-dessous, lorsque l'algorithme passe du temps à remplir une partie de la matrice, ne pouvant pas remplir le reste par manque de support.


Grâce à l' if elle forme rapidement une plateforme sur laquelle construire:


Pour tenter d'ajouter un chiffre à la matrice, les vérifications ci-dessus sont requises. L'algorithme vérifie si la figure aura un support, étant donné les lignes complétées. Il vérifie également s'il divise par 4 la taille de chaque espace vide individuel créé par l'insertion de la forme.

Conversion d'image

L'algorithme d'imprimante Tetris convertit chaque ligne du bitmap en une série de passes. En se déplaçant de gauche à droite, chaque passage de manière "gourmande" insère le tetramino J, T et L à l'endroit où il est placé. Par exemple, l'image ci-dessous montre une ligne de 16 pixels d'une image bitmap.


L'image ci-dessous montre les 5 passes nécessaires pour couvrir ces 16 pixels.






La séquence de formes que l'algorithme essaie d'insérer est déterminée par les couleurs des pixels. Pour que les formes ne se chevauchent pas, un tableau unidimensionnel de valeurs booléennes est utilisé. Pour insérer une figure, 3 éléments zéro doivent être présents dans le tableau. Une fois l'insertion de la figure 3 réussie, les éléments de tableau correspondants prennent la valeur 1.

Pour suivre les pixels terminés entre plusieurs passes, un deuxième tableau unidimensionnel de valeurs booléennes est utilisé. Lorsque chaque élément vaut 1, la ligne est terminée.

À la fin de chaque passage, le convertisseur d'image recherche dans le tableau tous les motifs pour créer un ou plusieurs carrés. À la sortie, il passe le motif correspondant avec le tetramino J, T et L inséré en bas. Par exemple, le premier passage montré ci-dessus est affiché comme le motif suivant pour créer 5 carrés:

Recherche en temps réel

Le convertisseur d'image décrit dans la section précédente est extrêmement rapide car il utilise une table constante contenant tous les motifs pour créer des carrés et ne les recherche pas en temps réel. Cependant, la recherche en temps réel peut utiliser des modèles qui ne figurent pas dans le tableau et, par conséquent, réduire considérablement la quantité de tétramino nécessaire pour générer l'image. Il utilise les carrés créés dans les passages précédents, les utilisant comme supports supplémentaires. Par exemple, comme mentionné ci-dessus, le modèle suivant pour créer un carré nécessite 7 lignes complètes.


Mais un carré rouge créé dans le passage précédent dans le coin inférieur gauche de l'image ci-dessous fournit un support supplémentaire, réduisant le nombre de lignes remplies à 3.


De plus, une recherche en temps réel peut couvrir 3 pixels adjacents de la même couleur en retournant le tetramino J, T ou L.


En fait, il peut combiner tétramino inversé et inversé, couvrant un grand nombre de pixels en une seule passe. Par exemple, les 5 passes ci-dessus nécessaires pour couvrir 16 pixels peuvent être réduites à la seule passe illustrée ci-dessous.


Pour obtenir ce motif, le convertisseur d'image commence par emballer avec enthousiasme le tétramino retourné J, T et L.


Ensuite, il essaie ardemment d'ajouter les versions non retournées, et dans ce cas, il parvient à ajouter un autre J.


En principe, une table de recherche pré-calculée peut également être utilisée dans ce processus, mais la taille même d'une telle table la rend inapplicable dans la pratique.

Dans cet exemple, 8 carrés consécutifs au-dessus de la ligne à créer sont ajoutés à la ligne inférieure de la matrice vide. Pour n carrés sur un terrain de 21 mètres carrés, la hauteur de la matrice h est le plus petit entier positif tel que 21h - n est divisible par 4. Dans ce cas, une matrice de hauteur 4 est requise.


La recherche en temps réel fonctionne exactement de la même manière que l'algorithme de recherche décrit ci-dessus, mais présente des améliorations mineures. Comme précédemment, la pile de colonnes de matrice fournit un support uniquement si la hauteur de colonne moins le nombre de lignes terminées est supérieure à zéro. Lorsque la différence est nulle, la pile de colonnes ne doit pas fournir de support. Cependant, dans cette version, s'il est égal à zéro, il vérifie les carrés de la ligne créée générés par les passes précédentes. En d'autres termes, tous les carrés de la ligne située sous la ligne inférieure de la matrice prennent en charge les colonnes vides.

De plus, la recherche étant effectuée en temps réel, il sera impossible de la rendre exhaustive. S'il n'a pas trouvé de solution après un certain nombre de tentatives, il ajoute 4 lignes supplémentaires en haut de la matrice, puis réessaye. Après cela, s'il ne pouvait toujours pas trouver de solution après un certain nombre de tentatives, alors dans le passage en cours, il revient à la méthode avec les tables de recherche précalculées et la conversion d'images décrites dans la section précédente de l'article.

Imprimer

Pour l'impression, vous devez suivre les instructions affichées par le convertisseur d'image sur le terrain de jeu de Tetris. L'imprimante crée un tétramino spécifique au point central supérieur du terrain de jeu dans une orientation standard. Ensuite, l'imprimante la fait pivoter, la déplace horizontalement et l'abaisse. Ce processus est illustré dans la vidéo:

Code source

Le code source du projet Java 7 est disponible ici .

Les algorithmes de recherche pour les tableaux pré-préparés et en temps réel sont dans les packages search.precomputed et search.realtime . Ils utilisent certaines classes communes situées dans le package de search . Les résultats d'une recherche précalculée sont stockés dans le package de patterns sous la forme d'une séquence de fichiers texte. Les fichiers texte stockent les matrices compressées sous forme de caractères ASCII, en commençant par A Par exemple, les 3 premières matrices dans emitters1.txt (l'ensemble de modèles pour créer un carré) ressemblent à ceci:


Comme indiqué à plusieurs reprises dans l'article, 3 symboles A adjacents dans les matrices ci-dessus peuvent être remplacés par tetramino J, T ou L.Les symboles B , C , D et ainsi de suite représentent la séquence de tetramino que vous devez créer.

La classe imageconverter.ImageConverter contient la méthode main , qui reçoit un seul argument de ligne de commande: le nom du fichier d'image-objet. Une image ne peut pas dépasser 17 × 32 pixels et ne peut pas contenir plus de 3 couleurs opaques. Tous les autres pixels doivent être transparents.

Fait intéressant, dans les anciens jeux vidéo, les développeurs utilisaient souvent l'arrière-plan pour obtenir des couleurs supplémentaires. Par exemple, les élèves et la bouche de Bubble de Bubble bobble, les élèves de Donkey Kong de Donkey Kong et le sourcil avec la taupe de Miss Pakman de Mme Pac-Man est en fait transparent. Le noir est obtenu à partir d'un fond uni.


Le fond du terrain de jeu de Tetris peut être utilisé de la même manière.

ImageConverter sortie d' ImageConverter ressemble à cet extrait:


Les 3 valeurs hexadécimales de la première ligne sont 3 couleurs opaques extraites du fichier image sprite. Ils correspondent aux couleurs du tétramino J, T et L. Les couleurs des autres tétramino n'affectent pas l'image. Les blocs restants sont des motifs emballés exécutés sur le terrain de jeu (pour les caractères après Z et jusqu'à a voir le tableau des caractères ASCII ). Les blocs jaunes surlignés composent la plateforme. Le premier bloc ajoute la plateforme, le second la supprime.

La classe printer.Printer reçoit un fichier texte dans ce format et génère un fichier image en lisant Tetris.

L'algorithme d'imprimante utilisé pour générer une vidéo ressemblant à la version NES de Tetris définit chaque type de tetramino dans chaque bloc d'un fichier texte. Ensuite, il se déplace dans l'ordre opposé du point de départ et de l'orientation initiale à l'angle de rotation et aux coordonnées de l'abaissement de la figure indiquée dans le fichier. Remarque: en raison de la vitesse extrêmement élevée des chiffres en baisse, il est impossible d'aller au-delà du niveau 30 dans la vraie version NES de Tetris. Il est supposé que l'imprimante transmet toutes ses commandes au terrain de jeu assez rapidement. pour compenser cela.

Pour régénérer des fichiers de search.precomputed.PatternSearcher , utilisez search.precomputed.PatternSearcher . Il peut être personnalisé en modifiant les constantes au début du fichier de code source.

 public static final int MATRIX_WIDTH = 21; public static final int MATRIX_HEIGHT = 4; public static final int EMITTED_SQUARES = 4; public static final int RANDOM_SETS = 100000; public static final int MAX_ATTEMPTS = 1000; 

RANDOM_SETS est le nombre de permutations aléatoires de 371 façons d'ajouter un chiffre à la matrice. Lorsqu'il est défini sur 100000 , il faut plusieurs secondes pour initialiser les permutations au démarrage. De plus, leur stockage nécessite plus d'un gigaoctet de mémoire.

MAX_ATTEMPTS contrôle le temps d'exécution de la recherche. Une valeur relativement petite de 1000 permet à la recherche de rejeter rapidement les débuts aléatoires qui ne se montrent pas bien. Cependant, afin de prouver que pour une taille de matrice spécifique et le nombre de carrés créés, il n'y a pas de solution, il est nécessaire d'explorer pleinement tout l'espace de recherche. Pour ce faire, vous pouvez définir MAX_ATTEMPTS sur Integer.MAX_VALUE .

Des constantes similaires se trouvent dans search.realtime.RealtimeSearcher , qui est utilisé par le convertisseur d'image. Comme mentionné ci-dessus, une grande valeur RANDOM_SETS nécessite une augmentation de la mémoire maximale et entraîne un démarrage plus long. MAX_RETRIES contrôle le nombre de tentatives, après quoi la recherche en temps réel se rend et revient à la recherche avec une table pré-calculée.

Gardez à l'esprit que les deux algorithmes de recherche utilisent 100% du processeur, créant de nombreux threads parallèles de taille égale au nombre de processeurs disponibles.