🅰️ 🙋🏿 👵🏻 Mettre le jeu "Snake" sur la planche à pain. Partie 1: machines d'état 🤵🏽 ✔️ 💱

À loisir, mon fils et moi étudions l'électronique numérique. Récemment, nous sommes arrivés au chapitre sur les machines à états finis. Cette rubrique regorge de tâches typiques, telles qu'un sémaphore ou un distributeur automatique. Mais ils sont tous ternes et trop simples, et certains sont généralement, franchement, farfelus. Après avoir étudié des exemples simples, je voulais faire quelque chose de plus intéressant et complexe. Le jeu classique «serpent» a attiré mon attention (mon fils l'a joué au téléphone), et j'ai suggéré de le faire sur des machines d'État. Après tout, l'état du jeu est assez final (surtout si vous vous limitez à un petit champ), et à partir des entrées, il n'y a que 4 boutons. Et c'est ce que nous avons obtenu.

Le jeu Snake (c'est un serpent, un python, un boa constrictor, etc.) est largement connu de tous. Elle vient des années 70 lointaines, mais je ne vais pas répéter son histoire, que vous pouvez lire sur Wikipedia ou de nombreux articles sur Habré. Le jeu a des règles assez simples et en même temps un gameplay addictif)) Grâce à cela, il est souvent utilisé pour des tutoriels ou des exemples de code . Dans les langages de programmation de haut niveau, faire un tel jeu est assez simple. Mais dans des conditions plus limitées, la plus intéressante commence, par exemple, une implémentation sur LabVIEW . Il existe également de nombreuses options sur FPGA: lien 1 , lien 2 , lien 3, Lien 4 . Mais il n'y a pas eu une seule option sur des puces TTL distinctes de série standard. C’est ce que nous allons faire.

Il semblerait que les solutions FPGA soient les plus proches pour nous, et vous pouvez emprunter beaucoup à partir de là? Mais dans toutes les options que j'ai examinées, elles sont facilement dispersées dans les registres gauche et droit. Par exemple, très souvent, un bit ou un numéro distinct est attribué à chaque cellule de champ. Nous ne pouvons pas le faire avec de la poudre libre, car chaque nouveau registre est un microcircuit séparé qui doit être placé quelque part, puis connecté. Par conséquent, nous rayons toute l'expérience accumulée par d'autres développeurs et ferons tout à partir de zéro. En bonus, nous collecterons tout sur les puces domestiques (et mieux - soviétiques) de la série k555 / kr1533, à l'exception des ROMs, qui devront être renouvelées.

Formulation du problème

Nous aurons de telles restrictions: un champ de taille 8 × 8 cellules ( matrice LED chinoise ), une longueur de queue de 8 cellules. Un serpent peut traverser les murs, mais nous ne traiterons pas l'intersection avec la queue dans un premier temps (afin de ne pas compliquer la conception, vous pouvez l'ajouter plus tard). Pour décrire l'état complet du jeu, nous avons besoin de:

Position de la tête (X = 0..7, Y = 0..7, 6 bits)
Sens de déplacement (↑ ↓ ← →, 2 bits)
Position Apple (X, Y, 6 bits)
Longueur de queue (0..7, 3 bits)
La position des cellules de la queue (de 0 à 7 morceaux de 6 bits chacun)

Au total, 65 bits sont obtenus, même si nous prenons des registres de 8 bits chacun, seuls 8 de ces microcircuits (et un déclencheur de plus) sont nécessaires pour stocker l'état, c'est beaucoup.

Mais la queue ne peut pas être située où elle veut, elle "pousse" de la tête. Par conséquent, nous pouvons stocker non pas les coordonnées complètes de chaque section de la queue, mais uniquement la direction dans laquelle la direction de la cellule (ou tête) précédente doit être dessinée. Ensuite, au lieu de 6 × 8 = 48 bits, nous avons besoin de 4 × 8 = 16 bits, ce qui représente une économie de quatre cas de registre!

Machines automatiques

Essayons de tout faire sur des machines similaires à Moore ou Miles. Pour implémenter un tel automate, il suffit d'avoir un peu de mémoire d'état (registre) et de logique combinatoire pour basculer entre eux.

Image de Wikipedia

Habituellement, une machine à états est décrite comme un graphique des états et des transitions entre eux. Parfois, il est plus pratique de créer un tableau de transitions vers un nouvel état, l'exemple le plus simple (de Wikipedia):

vous pouvez trouver plus d'informations et de belles images, par exemple, dans cet article sur Habré

Petite digression

, , . , ROM , ROM. ( , ).

, , .

, « » .

Un serpent de différents états (si vous ne tenez pas compte de la position de la pomme) peut avoir 2 ^ 8 + 2 ^ 10 + ... + 2 ^ 24 ≈ 32 millions. Il n'est pas possible de les écrire dans le tableau, et encore plus de dessiner un graphe de transition. Mais la plupart des transitions sont tout à fait les mêmes (la tête ne déplace qu'une seule cellule adjacente et la queue se déplace d'une section par tour). Dans ce cas, nous ne pouvons pas décrire chaque état individuel, mais formuler un nouvel état en fonction du précédent. De plus, on peut diviser l'ensemble du jeu en plusieurs automates parallèles: 1) une machine automatique de direction, 2) une machine automatique de position de la tête, 3) une machine automatique pour la queue. Et pour régler chacun d'eux comme il sera plus pratique:

1) ,  │  
  ────────────────────┼───────────────────
   ←        ←/↓/↑     │ ←
   ←          →       │ →
   ↑        ↑/←/→     │ ↑
   ↑          ↓       │ ↓
   ......          │

2) ,  │  
  ─────────────────────┼──────────────
   ←             (x,y) │ (x-1, y)
   →             (x,y) │ (x+1, y)
   ↑             (x,y) │ (x, y-1)
   ↓             (x,y) │ (x, y+1)

3) ,                       │  
  ─────────────────────────────────────────┼──────────────────────────
   ←            (t1,t2,t3,t4,t5,t6,t7,t8)  │ (←,t1,t2,t3,t4,t5,t6,t7)
   ......                               │

Direction

Commençons par la machine directionnelle. Si vous réfléchissez bien, vous pouvez l'assembler sur une logique distincte. Mais, comme la tâche dans son ensemble est déjà assez grande, j'ai décidé qu'il serait plus facile de créer une table de recherche à partir de l'EEPROM et d'écrire la table de transition manuellement. Il aura 6 entrées, ce qui signifie seulement 64 valeurs, que nous pouvons simplement insérer dans l'éditeur hexadécimal.

Tête

Pour une machine de position de tête, l'écriture d'une telle table sera beaucoup plus difficile. Mais il ne contient essentiellement que 2 opérations: +1 et -1. Ils peuvent être implémentés sur un additionneur 4 bits K155IM6. Pour +1, nous ajouterons nos coordonnées avec b'0001, et pour -1 avec b'1111 (qui est en fait -1 dans le code supplémentaire ). Nous aurons besoin de deux additionneurs (pour x et y), un peu de logique, et nous stockerons l'état dans le registre IR27 à 8 bits (nous en avons encore besoin de beaucoup):

Assemblons-le sur la carte, et pour vérification, nous connecterons immédiatement la matrice LED avec deux décodeurs. Le décodeur à sorties inverses est ID7, et pour le direct il serait possible de prendre K561ID1 (CD4028), mais je ne l’avais pas sous la main. Une autre option est de prendre 8 transistors comme clés, mais je ne voulais pas le faire, j'ai donc dû bêtement dépenser une autre EEPROM (y écrire seulement 8 cellules). La logique de la nouvelle position de la tête sur une carte séparée en haut Une autre digression

Prenons une courte pause et sauvons la planche à pain (et quelques cas de puces). Nous profiterons à nouveau du fait que tout circuit combiné peut être remplacé par une LUT en écrivant le tableau dans la ROM. Mais comment faire cela pour une si grande table? Nous allons utiliser une autre astuce - nous ferons le contraire: remplacer l'EEPROM par notre circuit logique et le mettre dans le programmateur. _{Les jambes inutilisées sont connectées à la terre via des résistances.}_{(Cela ne pourrait pas être fait si vous plongiez dans les paramètres du programmeur)} Maintenant, nous allons lire notre diagramme logique en tant que ROM et obtenir un tableau. Nous l'écrivons avec le même programmeur dans une véritable EEPROM, que nous mettons à la place d'un circuit d'éléments séparés.

Queue

La queue a une longueur (dans nos limites) de 2 à 8 cellules. Pour stocker cette longueur, vous pouvez utiliser un compteur conventionnel avec une entrée de résolution de compte. En fait, ce sera la même machine à états finis, dans laquelle le nouvel état S 'sera égal à S + 1 ou juste S (si le compte est interdit). La queue elle-même (ou plutôt, la direction où elle pousse), nous allons stocker dans deux registres de 8 bits. Théoriquement, on pouvait prendre des registres à décalage prêts à l'emploi (par exemple, IR8), mais ils n'étaient pas à portée de main, donc les mêmes IR27 ont été utilisés. À chaque étape, la direction actuelle du mouvement de la tête est écrite dans le premier bit du registre et la valeur de la précédente dans le second et le suivant. Pour obtenir la direction de la croissance de la queue, il suffit d'inverser un bit. Vous pouvez le faire tout de suite lors de l'enregistrement, mais j'ai décidé qu'il valait mieux laisser l'inverse pour le circuit restant.

Schème

Au total, notre machine du prochain mouvement prend cette forme: Cette image (comme tout le monde) est cliquable. Il s'agit d'une partie plutôt «pure» (d'un point de vue théorique) du schéma. Exemple presque parfait pour une machine Moore codée en sortie . U1 est responsable de la nouvelle direction, U2 de la position de la tête, qui sont stockées dans U5. U3 et U4 sont utilisés pour la queue, et sa longueur est stockée (et augmentée) dans U6. Ensuite, nous devrons afficher tout ce que nous avons à l'écran, et il y aura également un vaisseau spatial, uniquement sous une forme plus sale. Ainsi qu'un générateur de nombres aléatoires primitifs, une transition entre des circuits avec un signal d'horloge différent et d'autres hacks.

Total

J'espère que cet article vous a intéressé et j'essaierai de terminer rapidement la deuxième partie.

Et si vous êtes déjà déchiré par la bataille, rempli de maquettes, de microcircuits et d'écrans à points, un fichier avec le circuit ROM et le firmware est joint à cet article. Mini-spoiler: pour répéter la conception, vous aurez besoin d'environ 6 prototypes, 4 EEPROM 28C16 et un peu plus de deux douzaines d'autres puces.

Eh bien, comme il se doit: aimer, partager, retweets, s'inscrire, appuyer sur la cloche, etc ...)) Et pour aujourd'hui tout, merci de votre attention! À suivre…

Archive avec firmware ROM et schéma

UPD général : la deuxième partie est disponible ici .

Mettre le jeu "Snake" sur la planche à pain. Partie 1: machines d'état