Conway's Game of Life auf dem Busch Microtronic 2090
*Zeitraffer
Gleich vorweg: Du solltest irgendetwas haben, das die Signale an den Ausgängen des Microtronic 2090 sinnvoll interpretiert und darstellt. Und außerdem den Takt vorgibt, denn die Übermittlung der einzelnen Bit-Sequenzen ist zeitkritisch. Diese Aufgaben übernimmt das ESP2090-Studio - was du dazu wissen musst, findest du auf der entprechenden Github-Seite.
Wenn du das ESP2090-Studio noch nicht hast, dann empfehle ich, das erst einmal zusammenzubauen - es sei denn, du sagst: "Es reicht mir, algorithmische Schönheit in Gedanken zu bestaunen", dann auch gut. Aber zusammenlöten, anfassen und austesten macht mehr Spaß. Isso. Schreib mir, vielleicht hab ich noch ne Platine und Teile bei mir rumliegen.
Zum Nachlesen hier das - wie immer liebevoll dokumentierte - Programm Life2090. Und hier die MIC-Datei, die du mit geeigneten Mitteln auf deinen Microtronic bringen musst.
Life kennst du, oder? Nein? Dann bist du kein Nerd der 80er-Jahre. Oder gar kein Nerd. Aber was machst du dann auf dieser Seite? Geh weg... Nur Spaß. Bleib natürlich, wenn du magst. Aber lies erstmal in Ruhe, was es mit Life auf sich hat. Es ist ein sehr interessantes Stück Computer-Geschichte.
In den 80er-Jahren lief dieses Programm auf jedem Heimcomputer mindestens einmal in irgendeiner Variante. Wir erfreuten uns daran, wie der Computer immer neue Generationen ausrechnete und darstellte. Bewunderten vielleicht manchmal die Geschwindigkeit, in der sich das emsige Treiben auf dem Bildschirm abspielte. Und mancher - wir wollen keine Namen nennen - versuchte womöglich, die philosophischen Aspekte dieser Simulation zu ergründen... Woher kommen wir? Wohin gehen wir? Hat alles ein Ende? ... Ok, genug... Ich hab´s wieder im Griff :-)
Mein erster Computer, der Busch Microtronic 2090, konnte das leider nicht. Denn er hatte ja keinen Bildschirm... Bis jetzt!
Life ist ja eigentlich kein echtes Spiel. Du bestimmst die Anfangskonfiguration und schaust danach mehr oder weniger interessiert zu, welche neuen Figuren und Muster daraus entstehen. Insofern ist die Interaktion mit den Programm sehr trivial.
Die Zellen in der LED-Matrix sind wie der positive Quadrant eines kartesischen Koordinatensystems angeordnet. Spalten gehen von links nach rechts (x-Achse), Reihen gehen von unten nach oben (y-Achse). Die Register 0-F folgen dieser Anordnung, das niedrigstwertige Bit eines einzelnen Registers (LSB) ist ganz links, das höchstwertige (MSB) ganz rechts.
Als Beispiel ein paar Zellen im Life-Spielfeld:
| Reihe | Reg. | Bits LSB → MSB 1 2 3 4 |
Bits LSB → MSB 1 2 3 4 |
Reg. | |
|---|---|---|---|---|---|
| 8 | E | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | F | |
| 7 | C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | |
| 6 | A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | |
| 5 | 8 | ⚪ ⚪ ⚪ 🔴 | ⚪ ⚪ ⚪ ⚪ | 9 | |
| 4 | 6 | ⚪ ⚪ ⚪ ⚪ | 🔴 ⚪ ⚪ ⚪ | 7 | |
| 3 | 4 | ⚪ ⚪ 🔴 🔴 | 🔴 ⚪ ⚪ ⚪ | 5 | |
| 2 | 2 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 3 | |
| 1 | 0 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 1 | |
| Spalte | 1 2 3 4 | 5 6 7 8 |
- Die Zellen (3,4), (4,4) und (5,4) leben - im Register 4 steht daher der Wert C (Bits 3 und 4 gesetzt) und im Register 5 der Wert 1 (Bit 1 gesetzt).
- Die Zelle (5,6) lebt - im Register 7 steht der Wert 1 (Bit 1 gesetzt).
- Die Zelle (4,5) lebt - im Register 8 steht der Wert 8 (Bit 4 gesetzt).
- Alle anderen Zellen leben nicht, also steht der Wert 0 in den übrigen Registern.
Aus vorherigen Programmläufen können noch Werte in den Registern liegen, deshalb solltest du vor Programmstart einmal die grüne RESET-Taste drücken. Auf der Weboberfläche des ESP2090-Studios muss der Button LED Start gedrückt sein, sonst siehst du nix. Dann startest du das Programm mit HALT-NEXT-00-RUN und wählst aus, ob du die Werte schon eingegeben hast, ob du sie noch eingeben willst, oder ob du eine im Programm hinterlegte Figur zum Start laden willst.
- Taste 0 - die Werte wurden bereits über HALT-REG-x in die Register 0-E eingegeben (Register F ist immer 0)
- Taste 1 - Uhr
- Taste 2 - Kröte
- Taste 3 - Bipole
- Taste 4 - Gleiter
- Taste 5 - Segler
- Taste 6 - Pentomino
- Taste 7 - Suppe (ein zufälliges Startmuster)
- Taste F - die Werte werden anschließend erfasst, jedes Register von 0 bis F separat
Wenn du selbst ein Startmuster eingeben willst, dann hast du die Wahl.
Entweder füllst du alle nötigen Register schon vor Programmstart (mit HALT-REG-x), startest dann das Programm und wählst 0, um die Berechnung sofort anzuwerfen. Beachte aber, dass Register F bei dieser Auswahl bauartbedingt immer 0 sein wird.
Oder du startest das Programm und wählst F, um anschließend alle Register von 0 bis F der Reihe nach einzugeben. Ein Blick auf die Anordnung von Zellen und Registern in der Darstellung oben hilft dir dabei, die richtigen Register mit den richtigen Werten zu füllen. Probier einmal:
C, 3, 2, 4, 9, 9, 5, A, 1, 8, 5, A, 2, 4, C, 3
Wie üblich - der erste Gedanke war: Müsste doch vielleicht irgendwie gehen... Der zweite Gedanke: Nee, kann nicht klappen, zu viele Programmschritte, zu wenig Register.
Zunächst einmal haben wir - bedingt durch die LED-Matrix - eine 8x8-Welt mit 64 Zellen, das passt genau in die 16 Register einer Registerbank (Arbeits- oder Speicherregister). Die anderen Register könnte man dann doch zur Berechnung der Folgegeneration verwenden...
Den allerersten Ansatz habe ich nach kurzer Überlegung gar nicht weiter verfolgt: Jedes einzelne Register mit den jeweils fünf angrenzenden Registern vergleichen und die Bits dann entsprechend setzen. Um etwa Register 2 auszuwerten, müssten Vergleiche mit den Registern 0, 1, 3, 4 und 5 durchgeführt werden:
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| E | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | F | ||
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| 8 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 9 | ||
| 6 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 7 | ||
| 4 | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | 5 | ||
| 2 | 🟢 🟢 🟢 🟢 | 🔴 ⚪ ⚪ 🔴 | 3 | ||
| 0 | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | 1 |
Für Register 6 brauchen wir aber Vergleiche mit anderen Registern, nämlich 4, 5, 7, 8 und 9:
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| E | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | F | ||
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| 8 | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | 9 | ||
| 6 | 🟢 🟢 🟢 🟢 | 🔴 ⚪ ⚪ 🔴 | 7 | ||
| 4 | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | 5 | ||
| 2 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 3 | ||
| 0 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 1 |
Andere Register bedingen aber anderen Code. Denn leider können wir Register nicht indirekt adressieren (also elegant Register-Pointer auf die jeweils relevanten Register mitlaufen lassen) - dafür gibt es im Befehlssatz des Microtronic schlicht keine Instruktionen. Das bedeutet, jedes Register bekäme seinen eigenen Code-Teil im Programm. Also 16 mal irgendwie fast das gleiche, aber mit jeweils wechselnden Registern. Das hätte wahrscheinlich eine knappe Million Instruktionen erfordert.
Die nächste Idee: Auszuwertende Register aus der unteren Speicherhälfte werden nacheinander in ein Test-Register in der oberen Hälfte geschoben. Die bis zu fünf relevanten Nachbarregister werden ebenfalls nach oben geschoben. Dann wird die (stets identische) Auswertungsroutine für das Test-Register ausgeführt und das Ergebnis zurück an die Stelle des gerade ausgewerteten Registers geschrieben - diesmal aber in das Speicherregister als neue Generation.
Wenn z.B. das Register 4 ausgewertet werden soll:
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| TEST | E | 🟢 🟢 🟢 🟢 | 🔴 ⚪ ⚪ 🔴 | F | NEBEN |
| UNTEN | C | 🔴 🔴 🔴 🔴 | 🔴 🔴 🔴 🔴 | D | OBEN |
| NEBEN-U | A | 🔴 ⚪ ⚪ 🔴 | 🔴 ⚪ ⚪ 🔴 | B | NEBEN-O |
| 8 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 9 | ||
| OBEN ← | 6 | 🟠 🟠 🟠 🟠 | 🟠 ⚪ ⚪ 🟠 | 7 | → NEBEN-O |
| TEST ← | 4 | 🟡 🟡 🟡 🟡 | 🟠 ⚪ ⚪ 🟠 | 5 | → NEBEN |
| UNTEN ← | 2 | 🟠 🟠 🟠 🟠 | 🟠 ⚪ ⚪ 🟠 | 3 | → NEBEN-U |
| 0 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 1 |
Zwar gab es in diesem Ansatz nur noch einen einzigen, immer gleichen Code-Teil für die Auswertung, da stets die Register A-F ausgewertet werden. Aber die zahlreichen MOV-Operationen machten das Programm insgesamt trotzdem nicht kürzer, eher im Gegenteil.
Ich hatte mal drauflos programmiert... und der Programmspeicher war bereits voll, als ich noch nicht einmal die Hälfte der Register codiert hatte. Diese Idee passte also auch nicht in die verfügbaren 256 Programmschritte. Zudem wurde die Menge der noch übrigen Register knapp, im Prinzip standen nur noch die beiden Register 8 und 9 zur Verfügung. Bedenklich.
Die Idee, nur einen einzigen Code-Teil für die Auswertung zu haben, fühlte sich aber richtig an. Denn dann muss ich lediglich das immer gleiche Register mit den immer gleichen Nachbarregistern vergleichen, was den Code für die Auswertung deutlich verschlankt. Das Problem lag nur noch darin, dass für jedes Register zu viele und - schlimmer noch - jeweils andere Verschiebe-Operationen durchgeführt werden mussten, insbesondere das Verschieben der fünf Nachbarregister machte den Ansatz sehr teuer.
Wie wäre es denn, wenn wir - wie im zweiten Ansatz - nur ein einziges, immer gleiches Register in der unteren Hälfte des Arbeitsspeichers auswerten und durch einen clever durchdachten Verschiebebahnhof dafür sorgen, dass alle fünfzehn anderen Register nacheinander in diesem speziellen Register landen, um dort mit der immer gleichen Routine bearbeitet zu werden? Die Frage ist natürlich rhetorisch... es zeigte sich, dass das die Lösung war.
Dieses spezielle Register sollte fortan Register 0 sein:
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| UNTER-R0 | E | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | F | UNTER-R1 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| 8 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 9 | ||
| 6 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 7 | ||
| 4 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 5 | ||
| 2 | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | 3 | ||
| 0 | 🟢 🟢 🟢 🟢 | 🔴 ⚪ ⚪ 🔴 | 1 |
Die Berechnung der neuen Generation soll jeweils nur für eine Hälfte des Life-Feldes erfolgen: In den Arbeitsregistern 0-7 sind die auszuwertenden Register, in den Arbeitsregistern 8-F haben wir dann noch Platz für Schleife, Test-Register, Zähler usw. Nach der ersten Hälfte werden Oben und Unten getauscht - und so die zweite Hälfte berechnet.
Wenn Register 0 ab jetzt immer das auszuwertende Register ist, dann brauchen wir in einem toroidalen Spielfeld auch die Register "darunter", also E und F. Diese Register liegen aber eigentlich in den Speicherregistern, wir müssen die Register E und F daher in die Arbeitsregister "einblenden", damit sie in die Auswertung einbezogen werden. Gleichzeitig werden wir später auch die Register "oberhalb" von Register 6 benötigen, die deswegen ebenfalls in die Arbeitsregister einzublenden sind.
Also befinden sich Kopien der Speicherregister 8, 9, E und F in den entsprechenden Arbeitsregistern, es bleiben dann nur noch die vier Register A-D für Operationen des Programms übrig.
Mehr braucht der Algorithmus zur Auswertung aber auch nicht:
- KOPIE-Register: Kopie des jeweils auszuwertenden Registers, wird durch Bitoperationen "verbraucht"
- ANZAHL-Register: Zähler für die Gesamtzahl der lebenden Nachbarn einer Zelle
- ERGEBNIS-Register: Ergebnis der Auswertung, wird schrittweise mit den berechneten Bits gefüllt und rotiert, später in das Speicherregister geschrieben
- SCHLEIFE-Register: Schleifenzähler (Hinweis weiter unten)
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| UNTER-R0 | E | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | F | UNTER-R1 |
| KOPIE | C | ⚫ ⚫ ⚫ ⚫ | ⚫ ⚫ ⚫ ⚫ | D | SCHLEIFE |
| ANZAHL | A | ⚫ ⚫ ⚫ ⚫ | ⚫ ⚫ ⚫ ⚫ | B | ERGEBNIS |
| ÜBER-R6 | 8 | 🟠 🟠 🟠 🟠 | 🟠 ⚪ ⚪ 🟠 | 9 | ÜBER-R7 |
| 6 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 7 | ||
| 4 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 5 | ||
| 2 | 🔴 🔴 🔴 🔴 | 🔴 ⚪ ⚪ 🔴 | 3 | ||
| 0 | 🟢 🟢 🟢 🟢 | 🔴 ⚪ ⚪ 🔴 | 1 |
Wir erinnern uns: Das aktuelle Life-Spielfeld liegt in den Speicherregistern 0-F. Nur zur Anzeige mit dem Unterprogramm Frame werden die Speicher- mit den Arbeitsregistern getauscht (EXRL und EXRM) und schnell hintereinander auf die Ausgänge gelegt (DOT).
Für die Auswertung der neuen Generation schieben wir die untere Hälfte der Speicherregister-Bank durch EXRL in die Arbeitsregister 0-7. Außerdem blenden wir die angrenzenden vier Register UNTER-R0, UNTER-R1 sowie ÜBER-R6 und ÜBER-R7 in die Arbeitsregister 8, 9, E und F ein. Damit sind alle nötigen Arbeitsregister befüllt, um die untere Hälfte des Feldes vollständig zu berechnen.
Wir werten stets nur das Register 0 aus, also müssen die Inhalte aller Register nacheinander in dieses Register geschoben werden. Nachdem die erste Auswertung durchgeführt wurde, werden alle relevanten Register ring-getauscht, damit die Zellen des nächsten Registers zur Auswertung im Test-Register 0 landen. Register 2 kommt in Register 0, Register 4 in 2, Register 6 in 4, ÜBER-R6 in 4, UNTER-R0 in 8 und schließlich Register 0 in UNTER-R0. Das gleiche passiert auch mit allen Registern auf der "rechten Seite", also mit Register 1, 3, 5 und 7 sowie ÜBER-R7 und UNTER-R1.
| Inhalt soll... | Reg. | Bits | Bits | Reg. | Inhalt soll... |
|---|---|---|---|---|---|
| ↓ | E | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | F | ↓ |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| ↓ | 8 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 9 | ↓ |
| ↓ | 6 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 7 | ↓ |
| ↓ | 4 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 5 | ↓ |
| ↓ | 2 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 3 | ↓ |
| ↻ | 0 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 1 | ↺ |
Die Zellen von Register 0 wandern mit jedem Ringtausch ein Register weiter. Nach dem Tausch sehen die Arbeitsregister dann so aus:
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| aus R0 | E | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | F | aus R1 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| aus UNTER-R0 | 8 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 9 | aus UNTER-R1 |
| aus ÜBER-R6 | 6 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 7 | aus ÜBER-R7 |
| aus R6 | 4 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 5 | aus R7 |
| aus R4 | 2 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 3 | aus R5 |
| aus R2 | 0 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 1 | aus R3 |
Die Zellen von Register 2 sind jetzt im Test-Register 0 gelandet. Alle relevanten Nachbarregister von R2 - also Register 0, 1, 3, 4 und 5 - sind ebenfalls an die richtigen Stellen geschoben. Daher kann jetzt die Auswertung für Register 2 mit dem gleichen Code wie zuvor durchgeführt werden.
Nach vier Durchläufen ist die linke Seite der unteren Hälfte des Spielfeldes (also Register 0, 2, 4 und 6) komplett berechnet:
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| aus R6 | E | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | F | aus R7 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| aus R4 | 8 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 9 | aus R5 |
| aus R2 | 6 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 7 | aus R3 |
| aus R0 | 4 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 5 | aus R1 |
| aus UNTER-R0 | 2 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 3 | aus UNTER-R1 |
| aus ÜBER-R6 | 0 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 1 | aus ÜBER-R7 |
Nach zwei weitere Ringtauschen (ohne Auswertung) sind die ursprünglich in Register 0 befindlichen Zellen wieder wie zuvor in Register 0, und alle anderen Zellen sind auch wieder an den ursprünglichen Plätzen. Optisch hat sich nichts verändert, lediglich die Ergebnisse der Auswertung (also die neue Generation) von Register 0, 2, 4 und 6 befinden sich jetzt in den entsprechenden (verborgenen) Speicherregistern.
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| UNTER-R0 | E | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | F | UNTER-R1 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| ÜBER-R6 | 8 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 9 | ÜBER-R7 |
| R6 | 6 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 7 | R7 |
| R4 | 4 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 5 | R5 |
| R2 | 2 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 3 | R3 |
| R0 | 0 | 🟢 🟢 🟢 🟢 | 🟠 🟠 🟠 🟠 | 1 | R1 |
Die innere Schleife kann jetzt verlassen werden, um Links mit Rechts zu tauschen (Register 0-7 sowie die zughörigen UNTER- und ÜBER-Register):
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| aus UNTER-R1 | E | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | F | aus UNTER-R0 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| aus ÜBER-R7 | 8 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 9 | aus ÜBER-R6 |
| aus R7 | 6 | 🟠 🟠 🟠 🟠 | 🟢 🟢 🟢 🟢 | 7 | aus R6 |
| aus R5 | 4 | 🟠 🟠 🟠 🟠 | 🟢 🟢 🟢 🟢 | 5 | aus R4 |
| aus R3 | 2 | 🟠 🟠 🟠 🟠 | 🟢 🟢 🟢 🟢 | 3 | aus R2 |
| aus R1 | 0 | 🟠 🟠 🟠 🟠 | 🟢 🟢 🟢 🟢 | 1 | aus R0 |
Nach dem LR-Tausch werden für die Register 0, 2, 4 und 6 wieder die gleichen vier Auswertungen wie zuvor durchgeführt - mit dem Unterschied, dass dieses Mal tatsächlich die Zellen der Register 1, 3, 5 und 7, also die rechte Seite, ausgewertet werden.
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| aus R7 | E | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | F | aus R6 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| aus R5 | 8 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 9 | aus R4 |
| aus R3 | 6 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 7 | aus R2 |
| aus R1 | 4 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 5 | aus R0 |
| aus UNTER-R1 | 2 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 3 | aus UNTER-R0 |
| aus ÜBER-R7 | 0 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 1 | aus ÜBER-R6 |
Nach zwei weiteren Ringtauschen und einem anschließenden LR-Tausch zur Positionskorrektur sind alle Zellen wieder am richtigen Ort. Die Register 0-7 sind damit vollständig ausgewertet, also die untere Hälfte des Life-Spielfeldes komplett.
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| UNTER-R0 | E | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | F | UNTER-R1 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| ÜBER-R6 | 8 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 9 | ÜBER-R7 |
| R6 | 6 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 7 | R7 |
| R4 | 4 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 5 | R5 |
| R2 | 2 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 3 | R3 |
| R0 | 0 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 1 | R1 |
Zum Schluss soll die zweite, also obere Hälfte des Life-Spielfeldes berechnet werden. Damit wir wieder den gleichen Code zur Auswertung nutzen können, müssen die Zellen in den Registern 8-F in die Register 0-7 geschoben werden - was mit dem Befehl EXRA ja elegant zu lösen ist. Zuvor müssen allerdings einige Registerbänke hin- und hergeschoben und der Zähler "gerettet" werden, um am Ende den Oben-Unten-Tausch durchzuführen:
| Inhalt soll... | Reg. | Bits | Bits | Reg. | Inhalt soll... |
|---|---|---|---|---|---|
| ↓ | E | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | F | ↓ |
| ↓ | C | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | D | ↓ |
| ↓ | A | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | B | ↓ |
| ↓ | 8 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 9 | ↓ |
| ↑ | 6 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 7 | ↑ |
| ↑ | 4 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 5 | ↑ |
| ↑ | 2 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 3 | ↑ |
| ↑ | 0 | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | 1 | ↑ |
Nach dem OU-Tausch:
| Inhalt ist... | Reg. | Bits | Bits | Reg. | Inhalt ist... |
|---|---|---|---|---|---|
| aus R6 | E | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | F | aus R7 |
| aus R4 | C | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | D | aus R5 |
| aus R2 | A | 🟢 🟢 🟢 🟢 | 🟢 🟢 🟢 🟢 | B | aus R3 |
| aus R0 | 8 | 🟡 🟡 🟡 🟡 | 🟡 🟡 🟡 🟡 | 9 | aus R1 |
| aus RE | 6 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 7 | aus RF |
| aus RC | 4 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 5 | aus RD |
| aus RA | 2 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 3 | aus RB |
| aus R8 | 0 | 🟠 🟠 🟠 🟠 | 🟠 🟠 🟠 🟠 | 1 | aus R9 |
Auch die angrenzenden Register UNTER und ÜBER sind durch den OU-Tausch bereits mit den richtigen Inhalten belegt: R6 ist unter R8, R7 unter R9, R0 über RD und R1 über RF.
Die Zellen der oberen Hälfte des Feldes werden jetzt wieder mit der gleichen Routine ausgewertet: Erst die ursprünglich aus Register 8, A, C und E stammenden Zellen, dann LR-Tausch, dann die aus Register 9, B, D und F. Nochmal LR-Tausch, nochmal OU-Tausch und... die komplette Folgegeneration liegt fertig ausgewertet in den Speicherregistern und kann angezeigt werden. Tadaa.
Wir haben einen Mechanismus entwickelt, durch den nacheinander alle Register in das Test-Register 0 zur Auswertung gelangen. Die eigentliche Auswertung erfolgt dann Zelle für Zelle, Bit für Bit in immer diesem Register.
Zum Beispiel werden für das vierte Bit (MSB) alle lebenden Nachbarzellen gezählt:
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| UNTER-R0 | E | ⚪ ⚪ 🔴 🔴 | 🔴 ⚪ ⚪ ⚪ | F | UNTER-R1 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| 8 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 9 | ||
| 6 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 7 | ||
| 4 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 5 | ||
| 2 | ⚪ ⚪ 🔴 🔴 | 🔴 ⚪ ⚪ ⚪ | 3 | ||
| 0 | ⚪ ⚪ 🔴 🟢 | 🔴 ⚪ ⚪ ⚪ | 1 |
Alle Nachbarregister sowie das Test-Register 0 landen nacheinander im Register KOPIE. Um nur die unmittelbaren Nachbarn zu zählen, werden die betreffenden Bits mit SHL und SHR aus dem Register KOPIE "herausgeschüttelt" und mit ADC zur ANZAHL der lebenden Nachbarzellen addiert.
MOV UNTER-R1,KOPIE rechter Rand unten in KOPIE
CALL CountR1 zählt Bit 1
MOV r1,KOPIE rechter Rand mitte in KOPIE
CALL CountR1 zählt Bit 1
MOV r3,KOPIE rechter Rand oben in KOPIE
CALL CountR1 zählt Bit 1
MOV UNTER-R0,KOPIE unterer Rand in KOPIE
CALL CountL2 zählt Bits 3 und 4
MOV r0,KOPIE Selbst in KOPIE
SHL KOPIE schiebt Bit 4 heraus (ohne zu zählen)
CALL CountL1 zählt also nur Bit 3
MOV r2,KOPIE oberer Rand in KOPIE
CALL CountL2 zählt Bits 3 und 4
CALL ConwayRules ermittelt neuen Zustand der Zelle
Die anderen Zellen des Test-Registers 0 werden ebenfalls entsprechend ausgewertet. Ergebnis-Bits werden in das Register ERGEBNIS geschrieben.
Für die mittleren Zellen (Bits 2 und 3) ist die Ermittlung übrigens weniger aufwändig, da nur drei Register (die beiden Register oberhalb und unterhalb sowie das Test-Register selbst) berücksichtigt werden müssen - die Nachbarzellen rechts und links befinden sich bereits im Test-Register 0:
| Reg. | Bits | Bits | Reg. | ||
|---|---|---|---|---|---|
| UNTEN-R0 | E | ⚪ 🔴 🔴 🔴 | ⚪ ⚪ ⚪ ⚪ | F | UNTEN-R1 |
| C | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | D | ||
| A | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | B | ||
| 8 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 9 | ||
| 6 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 7 | ||
| 4 | ⚪ ⚪ ⚪ ⚪ | ⚪ ⚪ ⚪ ⚪ | 5 | ||
| 2 | ⚪ 🔴 🔴 🔴 | ⚪ ⚪ ⚪ ⚪ | 3 | ||
| 0 | ⚪ 🔴 🟢 🔴 | ⚪ ⚪ ⚪ ⚪ | 1 |
Da nur die Nachbarzellen, nicht aber die zu testende Zelle selbst addiert werden sollen, wird das zugehörige Bit im Register KOPIE vorher mit ANDI gelöscht (Bit-maskiert).
MOV UNTER-R0,KOPIE unterer Rand in KOPIE
CALL CountL3 zählt Bit 2, 3 und 4
MOV r0,KOPIE Selbst in KOPIE
ANDI #A,KOPIE maskiert Bit 3
CALL CountL3 zählt also nur Bit 2 und 4
MOV r2,KOPIE oberer Rand in KOPIE
CALL CountL3 zählt Bit 2, 3 und 4
CALL ConwayRules ermittelt neuen Zustand der Zelle
...
Das Programm ist ziemlich rechenintensiv. Die Operationen selbst sind nicht komplex, innerhalb der Schleife werden eigentlich nur ein paar Bits hin- und hergeschoben, ein paar Register getauscht, ein bisschen addiert und verglichen. Aber die Menge macht's...
Um die neue Generation eines einzelnen Registers zu berechnen, müssen etwa 174 Instruktionen abgearbeitet werden. Da der Microtronic mehr als doppelt so schnell rechnet, wenn das Display ausgeschaltet bleibt, ist DISOUT praktisch ein Muss. Dann braucht ein Befehl immer noch 9 ms, also sind 174 Befehle in 1,5 Sekunden durchlaufen.
Alle 16 Register werden somit theoretisch innerhalb von etwa 25 Sekunden ausgewertet. Nach jeweils vier Registern kommen allerdings noch (relativ aufwändige) Register-Tauschereien dazu, so dass am Ende etwa 31 Sekunden für Berechnung und Anzeige der kompletten folgenden Generation herausspringen. Ein ziemlich gemütlicher Bildschirmschoner.
Testweise habe ich eine Version geschrieben, die auf den Tausch von Rechts und Links verzichtet und stattdessen Register 0 und Register 1 gemeinsam in der inneren Schleife auswertet. Das spart eine Schleifenebene, macht den Programmcode aber deutlich länger, da nun acht statt vier Bits auszuwerten sind. Gemessen habe ich dann xx Sekunden für die Berechnung einer Generation, also xx% Geschwindigkeitssteigerung. Ordentlich, aber zieht jetzt auch nicht die Wurst vom Teller. Ich wollte lieber mehr Platz für ein paar Testfiguren zur Auswahl haben.
Schachteln und Schleifen erinnern ja eigentlich an Geburtstagsgeschenke. Und ein bisschen wie ein Geschenk ist auch diese Konstruktion...
Um alle Register auszuwerten, müssen wir sie nacheinander in das Test-Register 0 befördern. Dazu dient die folgende Schleifenanordnung:
- Innere Schleife: Nach jedem Durchlauf sind alle vier Bits des Registers 0 ausgewertet, Register 2 wird über Ringtausch in das Register 0 geschoben und die anderen Register entsprechend.
- LR-Schleife: Nach jedem vierten Durchlauf tauschen die linken Register (0, 2, 4, 6) mit den rechten Registern (1, 3, 5, 7).
- OU-Schleife: Nach jedem achten Durchlauf tauschen die oberen Register 8-F mit den unteren Registern 0-7.
- Äußere Schleife: Nach jedem 16. Durchlauf werden die Register auf der LED-Matrix dargestellt.
Ohne groß nachzudenken, würde man dafür in einer Hochsprache einfach drei FOR-Schleifen mit drei unterschiedlichen Index-Variablen ineinander legen (= verschachteln). Register sind beim Microtronic aber kostbar und in diesem Fall schon fast alle belegt. Ich musste mit nur einem Index-Register SCHLEIFE für alle drei Schleifen gemeinsam auskommen.
Das geht aber verhältnismäßig einfach und elegant, wenn man das Bitmuster des Schleifenregisters auswertet. Denn bei jedem vierten Durchlauf (und nur dann) sind die Bits 1 und 2 des Schleifenregisters gesetzt, bei jedem achten Durchlauf die Bits 1, 2 und 3 und bei jedem 16. Durchlauf alle 4 Bits. Mit ANDI blenden wir die anderen Bits aus und können dann entscheiden, ob die Schleife in die nächsthöhere Ebene verlassen werden soll.
Exemplarisch für die innere Schleife:
MOV SCHLEIFE,TEMP
ANDI #3,TEMP Nur Bits 1 und 2 berücksichtigen
CMPI #3,TEMP Fertig mit innerer Schleife?
BRZ RLRotate ja, dann Schleife verlassen (bei 3, 7, B und F)
GOTO Loop
RLRotate ...
Bitweise Rotation funktioniert besser mit SHL (Verdoppeln), weil das höchstwertige Bit (MSB) herausgeschoben wird und direkt als Carry wieder addiert werden kann:
Rotate SHL ERGEBNIS
ADC ERGEBNIS
Mit SHR (Halbieren) würde das niedrigstwertige Bit (LSB) herausfliegen, dieses müsste als Wert 8 wieder zum Register addiert werden. Man müsste also schreiben
Rotate SHR ERGEBNIS
BRC Add8
GOTO Ende
Add8 ADDI #8,ERGEBNIS
Ende ...
Daher beginnt die Bit-Auswertung in der inneren Schleife mit dem Most Significant Bit (MSB), also mit Bit 4. Das kehrt zwar die intuitive Reihenfolge um, spart aber zwei Befehle.
Den ADC-Befehl können wir auch zur Auswertung der links bei Bit 1 angrenzenden Register vorteilhaft nutzen.
Normalerweise wird das Register, dessen Bits wir zählen wollen, in KOPIE geschoben. Dort werden die Bits, die in die Summe einfließen sollen, mit SHL, SHR und ADC gezählt (Unterprogramme CountLx und CountRx).
Bei Bit 1 geht das aber deutlich einfacher. Wir vergleichen nur, ob das angrenzende Register (der linke Nachbar von Bit 1) größer als 7 ist. Denn dann ist das vierte Bit gesetzt, also lebt der Nachbar und wird direkt mit ADC zur Summe addiert.
CMPI #7,UNTEN-R Bit 4 in linkem Nachbarregister gesetzt?
ADC ANZAHL Dann +1 in Anzahl Nachbarn
Bei Bit 4 geht das nicht, denn mit CMPI können wir nicht einfach die Existenz von Bit 1 im angrenzenden rechten Register prüfen. Daher nutzen wir hier die bekannte Zähl-Routine CountR1.
… ist nicht zu unterschätzen.
Zunächst gab es nur ein Unterprogramm Count für die Zählung aller vier Bits im Register KOPIE. Alle nicht zu zählenden Bits wurden in der inneren Schleife zuvor über ANDI gelöscht. Das funktionierte.
Foto: Barry Stock / CC BY-SA 2.0
Als ich dann dokumentieren wollte, wie lange eine Generation braucht, um berechnet zu werden, musste ich messen. Und genau dabei kam dann die Überlegung auf: Wie kriege ich das ein bisschen schneller hin? Die Zähl-Routine Count iterierte ja immer über alle vier Bits, also oft über Bits, die ich gerade vorher mit ANDI maskiert hatte. Unnötig eigentlich.
Also stellte ich zwei Zähl-Routinen mit mehreren Einsprung-Adressen zur Verfügung - eine zählt x-mal nach links, eine zählt x-mal nach rechts: CountLx und CountRx. Dadurch wurden dann immer nur noch so viele Bits wie nötig gezählt. Das funktionierte gut (minus 2 Sekunden).
Und beim Kommentieren stellte ich dann irgendwann fest, dass die ANDI-Operationen zur Maskierung nicht zu zählender Bits immer noch in der inneren Schleife waren. Das war zwar sehr ordentlich, aber inzwischen gar nicht mehr nötig. Weg damit. Das funktionierte noch besser (minus 2 Sekunden).
Hätte ich keine Notwendigkeit gehabt, alle Schritte nachvollziehbar zu kommentieren, wären diese überflüssigen Operationen sicher in der Schleife verblieben - und die Berechnung einer neuen Generation hätte jeweils 4 Sekunden länger gedauert.