Get best of the week

Das Spiel "Snake" auf das Steckbrett legen. Teil 1: Zustandsautomaten

In meiner Freizeit studieren mein Sohn und ich digitale Elektronik. KĂŒrzlich sind wir zum Kapitel ĂŒber endliche Zustandsmaschinen gekommen. Dieses Thema ist voll von typischen Aufgaben wie einem Semaphor oder einem Verkaufsautomaten. Aber sie sind alle langweilig und zu einfach, und einige sind im Allgemeinen, ehrlich gesagt, weit hergeholt. Nachdem ich einfache Beispiele studiert hatte, wollte ich etwas interessanteres und komplexeres machen. Das klassische Spiel „Schlange“ fiel mir auf (mein Sohn spielte es am Telefon) und ich schlug vor, es auf Zustandsautomaten zu machen. Immerhin ist der Status des Spiels ziemlich endgĂŒltig (besonders wenn Sie sich auf ein kleines Feld beschrĂ€nken), und von den Eingaben gibt es nur 4 Tasten. Und das haben wir bekommen.


Das Spiel Snake (sie ist eine Schlange, Python, Boa Constrictor usw.) ist allen bekannt. Sie stammt aus den fernen 70ern, aber ich werde ihre Geschichte, die Sie auf Wikipedia oder in vielen Artikeln ĂŒber HabrĂ© lesen können, nicht wiederholen . Das Spiel hat ziemlich einfache Regeln und zugleich fesselndes Gameplay)) Dank dieser Tatsache wird es oft verwendet fĂŒr Tutorien oder Code Proben . In höheren Programmiersprachen ist es einfach genug, ein solches Spiel zu erstellen. Unter eingeschrĂ€nkteren Bedingungen beginnt das Interessanteste beispielsweise mit einer Implementierung in LabVIEW . Es gibt auch viele Optionen auf FPGA: Link 1 , Link 2 , Link 3, Link 4 . Es gab jedoch keine einzige Option fĂŒr separate TTL-Chips der Standardreihe. Das werden wir also tun.

Es scheint, dass FPGA-Lösungen fĂŒr uns am nĂ€chsten sind und Sie von dort viel ausleihen können? Aber in allen Optionen, die ich mir angesehen habe, sind sie leicht in den Registern links und rechts verstreut. Beispielsweise wird sehr oft jeder Feldzelle ein separates Bit oder eine separate Nummer zugewiesen. Wir können dies nicht mit losem Pulver tun, da jedes neue Register eine separate Mikroschaltung ist, die irgendwo platziert und dann angeschlossen werden muss. Daher streichen wir alle Erfahrungen anderer Entwickler durch und werden alles von Grund auf neu machen. Als Bonus sammeln wir alles auf inlĂ€ndischen (und besser sowjetischen) Chips der Serie k555 / kr1533, mit Ausnahme von ROMs, die frisch genommen werden mĂŒssen.

Formulierung des Problems


Wir werden solche EinschrĂ€nkungen haben: ein Feld mit einer GrĂ¶ĂŸe von 8 × 8 Zellen (chinesische LED-Matrix ), eine SchwanzlĂ€nge von 8 Zellen. Eine Schlange kann durch WĂ€nde gehen, aber wir werden den Schnittpunkt mit dem Schwanz zunĂ€chst nicht verarbeiten (um das Design nicht zu komplizieren, können Sie dies spĂ€ter hinzufĂŒgen). Um den gesamten Status des Spiels zu beschreiben, benötigen wir:

  1. Kopfposition (X = 0..7, Y = 0..7, 6 Bits)
  2. Bewegungsrichtung (↑ ↓ ← →, 2 Bit)
  3. Apple Position (X, Y, 6 Bit)
  4. SchwanzlÀnge (0..7, 3 Bit)
  5. Die Position der Schwanzzellen (von 0 bis 7 StĂŒck Ă  6 Bit)

Insgesamt werden 65 Bits erhalten, selbst wenn wir Register mit jeweils 8 Bits verwenden, werden nur 8 solcher Mikroschaltungen (und ein weiterer Trigger) benötigt, um den Zustand zu speichern. Dies ist ziemlich viel.

Aber der Schwanz kann nicht lokalisiert werden, wo er will, er "wĂ€chst" aus dem Kopf. Daher können wir nicht die vollstĂ€ndigen Koordinaten jedes Abschnitts des Schwanzes speichern, sondern nur die Richtung, in die Richtung von der vorherigen Zelle (oder dem Kopf) gezeichnet werden muss. Dann benötigen wir anstelle von 6 × 8 = 48 Bit 4 × 8 = 16 Bit, und dies spart bis zu vier RegisterfĂ€lle!

Automatische Maschinen


Versuchen wir, alles auf Maschinen zu machen, die Moore oder Miles Àhnlich sind. Um einen solchen Automaten zu implementieren, reicht es aus, ein bisschen Zustandsspeicher (Register) und kombinatorische Logik zu haben, um zwischen ihnen zu wechseln. Wikipedia-


Bild

Normalerweise wird eine Zustandsmaschine als Diagramm von ZustĂ€nden und ÜbergĂ€ngen zwischen ihnen beschrieben. Manchmal ist es bequemer, eine Tabelle mit ÜbergĂ€ngen in einen neuen Zustand zu erstellen, das einfachste Beispiel (aus Wikipedia):

Weitere Informationen und schöne Bilder finden Sie beispielsweise in diesem Artikel ĂŒber HabrĂ©

Kleiner Exkurs
, , . , ROM , ROM. ( , ).

, , .


, « » .


Eine Schlange verschiedener ZustĂ€nde (wenn Sie die Position des Apfels nicht berĂŒcksichtigen) kann 2 ^ 8 + 2 ^ 10 + ... + 2 ^ 24 ≈ 32 Millionen haben. Es ist nicht möglich, sie in die Tabelle zu schreiben, und noch mehr, ein Übergangsdiagramm zu zeichnen. Die meisten ÜbergĂ€nge sind jedoch ziemlich gleich (der Kopf bewegt nur eine benachbarte Zelle und der Schwanz bewegt einen Abschnitt pro Umdrehung). In diesem Fall können wir nicht jeden einzelnen Zustand beschreiben, sondern einen neuen Zustand als Funktion des vorherigen formulieren. DarĂŒber hinaus können wir das ganze Spiel in mehrere parallele Automaten unterteilen: 1) eine automatische Richtungsmaschine, 2) eine automatische Positionierungsmaschine des Kopfes, 3) eine automatische Maschine fĂŒr den Schwanz. Und um jeden von ihnen so einzustellen, wie es bequemer ist:

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)
   ......                               │


Richtung


Beginnen wir mit der Richtungsmaschine. Wenn Sie sorgfĂ€ltig ĂŒberlegen, können Sie es auf einer separaten Logik zusammenstellen. Da die Aufgabe insgesamt jedoch bereits ziemlich umfangreich ist, habe ich beschlossen, dass es einfacher ist, eine Nachschlagetabelle aus dem EEPROM zu erstellen und die Übergangstabelle manuell zu schreiben. Es wird 6 EingĂ€nge haben, was nur 64 Werte bedeutet, die wir einfach in den Hex-Editor fahren können.



Kopf


FĂŒr eine Kopfpositionsmaschine ist das Schreiben einer solchen Tabelle viel schwieriger. Es enthĂ€lt jedoch im Wesentlichen nur zwei Operationen: +1 und -1. Sie können auf einem 4-Bit-Addierer K155IM6 implementiert werden. FĂŒr +1 addieren wir unsere Koordinate mit b'0001 und fĂŒr -1 mit b'1111 (was im zusĂ€tzlichen Code tatsĂ€chlich -1 ist ). Wir brauchen zwei Addierer (fĂŒr x und y), ein bisschen Logik, und wir werden den Zustand im 8-Bit-Register IR27 speichern (wir brauchen noch viele davon):



Lassen Sie es uns auf der Platine zusammenbauen, und zur ÜberprĂŒfung werden wir die LED-Matrix sofort mit zwei Decodern verbinden. Der Decoder mit inversen AusgĂ€ngen ist ID7, und fĂŒr den direkten wĂ€re es möglich, K561ID1 (CD4028) zu nehmen, aber ich hatte ihn nicht zur Hand. Eine andere Möglichkeit besteht darin, 8 Transistoren als SchlĂŒssel zu verwenden, aber ich wollte dies nicht tun, also musste ich dumm ein anderes EEPROM ausgeben (nur 8 Zellen dort schreiben). Die Logik der neuen Kopfposition auf einer separaten Platine oben Ein weiterer Exkurs





Machen wir eine kurze Pause und bewahren das Steckbrett (und einige Chip-HĂŒllen) auf. Wir werden wieder die Tatsache ausnutzen, dass jede Kombinationsschaltung durch eine LUT ersetzt werden kann, indem die Tabelle in den ROM geschrieben wird. Aber wie geht das fĂŒr einen so großen Tisch? Wir werden einen anderen Trick anwenden - wir werden das Gegenteil tun: Ersetzen Sie das EEPROM durch unsere Logikschaltung und setzen Sie es in den Programmierer ein. Nicht benutzte Beine sind ĂŒber WiderstĂ€nde mit der Erde verbunden. (Dies wĂ€re nicht möglich, wenn Sie sich mit den Einstellungen des ProgrammiergerĂ€ts befassen.) Nun lesen wir unser Logikdiagramm als ROM und erhalten eine Tabelle. Wir schreiben es mit demselben Programmierer in ein echtes EEPROM, das wir anstelle einer Schaltung aus separaten Elementen einsetzen.







Schwanz


Der Schwanz hat eine LĂ€nge (in unseren EinschrĂ€nkungen) von 2 bis 8 Zellen. Um diese LĂ€nge zu speichern, können Sie einen herkömmlichen ZĂ€hler mit einer Eingabe fĂŒr die Kontoauflösung verwenden. TatsĂ€chlich wird es dieselbe endliche Zustandsmaschine sein, in der der neue Zustand S 'gleich S + 1 oder nur S ist (wenn das Konto verboten ist). Den Schwanz selbst (oder besser gesagt die Richtung, in der er wĂ€chst) werden in zwei Registern mit 8 Bits gespeichert. Theoretisch könnte man vorgefertigte Schieberegister (zum Beispiel IR8) nehmen, aber sie waren nicht zur Hand, so dass genau das gleiche IR27 verwendet wurde. Bei jedem Schritt wird die aktuelle Kopfbewegungsrichtung in das erste Bit des Registers und der Wert des vorherigen in das zweite und das nĂ€chste geschrieben. Um die Richtung des Schwanzwachstums daraus zu ermitteln, mĂŒssen wir nur ein Bit umkehren. Sie können dies sofort bei der Aufnahme tun, aber ich entschied, dass es besser ist, die Umkehrung fĂŒr die verbleibende Schaltung zu belassen.

Planen


Insgesamt hat unsere Next-Move-Maschine folgende Form: Dieses Bild ist (wie alle anderen auch) anklickbar. Dies ist ein eher „reiner“ (aus theoretischer Sicht) Teil des Schemas. Fast perfektes Beispiel fĂŒr eine ausgabecodierte Moore-Maschine . U1 ist verantwortlich fĂŒr die neue Richtung, U2 fĂŒr die Position des Kopfes, die in U5 gespeichert sind. U3 und U4 werden fĂŒr den Schwanz verwendet, und seine LĂ€nge wird in U6 gespeichert (und erhöht). Als nĂ€chstes mĂŒssen wir alles anzeigen, was wir auf dem Bildschirm haben, und es wird auch ein Raumschiff geben, nur in einer schmutzigeren Form. Neben einem primitiven Zufallszahlengenerator ein Übergang zwischen Schaltungen mit einem anderen Taktsignal und anderen Hacks.







Zwischensumme


Ich hoffe, dass dieser Artikel Sie interessiert hat und ich werde versuchen, den zweiten Teil schnell abzuschließen.

Und wenn Sie bereits in die Schlacht gerissen sind und mit Steckbrettern, Mikroschaltungen und Punktbildschirmen bestĂŒckt sind, ist diesem Artikel eine Datei mit der ROM-Schaltung und der Firmware beigefĂŒgt. Mini-Spoiler: Um das Design zu wiederholen, benötigen Sie ungefĂ€hr 6 Prototypen, 4 EEPROM 28C16 und etwas mehr als zwei Dutzend andere Chips.

Nun, wie es sein sollte: wie, teilen, retweeten, sich anmelden, die Glocke drĂŒcken usw. ...)) Und fĂŒr heute alles, danke fĂŒr Ihre Aufmerksamkeit! Fortsetzung folgt



Archiv mit ROM-Firmware und dem allgemeinen

UPD- Schema : Der zweite Teil ist hier verfĂŒgbar .

More articles:


All Articles