Conways Game of Life

Im Jahre 1970 entwickelte ein britischer Mathematiker einen "zellulären Automaten" der als "Spiel des Lebens" eine Zeitlang einen Hype auslöste.

Auf einem rechteckigen Spielbrett liegen "lebende" und "tote" Zellen. Jede Zelle hat insgesamt acht direkte Nachbarn. Es werden nacheinander beliebig viele Generationen erzeugt. Hat in einer Generation eine lebende Zelle weniger als zwei lebende Nachbarn, stirbt sie aus Vereinsamung. Hat sie zwei oder drei Nachbarn, überlebt sie. Hat Sie mehr als drei Nachbarn stirbt sie an Übervölkerung. Eine Zelle mit genau drei lebenden Nachbarn wird neu geboren.

Im Internet gibt es eine Vielzahl von Beiträgen: Die Googlesuche nach Conway game of life liefert über 20 Millionen Beiträge, die Suche nach Conway Spiel des Lebens immerhin noch 310.000.

 Es gibt außerdem eine Vielzahl von Computer-Programmen, die dieses Spiel zeigen. Rosetta Code
(https://rosettacode.org/wiki/Conway%27s_Game_of_Life) liefert mehr als 170 Lösungen in verschiedenen Programmiersprachen, darunter auch C for Arduino, aber natürlich keine für mBlock und auch keine für Scratch. Allerdings finden sich im Scratch Studio zwei Projekte, von denen eins gut funktioniert., jedoch nicht auf dem mBot.

Hier ein instruktives Beispiel:

https://www.biologie-seite.de/Biologie/Conways_Spiel_des_Lebens

oder auch:

https://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens

 Wie üblich sind dort auch weitere nützliche Informationen und Beispiele enthalten.

Ich vermutete, dass die Umsetzung nicht besonders schwierig wird. Dies war allerdings eine eklatante Fehleinschätzung.

Ich begann mit einem Spielfeld der Größe 16 x 13.

Soweit ich das sehe, gibt es zwei verschiedene Vorgehensweisen:

In einer ersten Matrix wird das Spielfeld selbst gespeichert. Der Einfachheit halber hat die Matrix zwei Zeilen und zwei Spalten mehr als das Spielfeld. Hierdurch kann das Zählen der Nachbarn mit einer einheitlichen Routine auch für die Ränder erfolgen.

Eine zweite Matrix dient der Verarbeitung. Sie enthält ein Abbild der Hauptmatrix. Bei der Verarbeitung werden alle überlebenden Zellen und die neu geborenen in diese zweite Matrix eingetragen. Vor der Anzeige der nächsten Generation wird die zweite Matrix in die erste zurück kopiert und geleert.

Bei der zweiten Vorgehensweise wird die Anzahl der Nachbarn in die zweite Matrix eingetragen. Hiermit wird dann die geleerte erste Matrix wieder gefüllt.

Es gibt eine kleine Falle: Das Zählen der Nachbarn erfolgt sinnvollerweise über zwei ineinander geschachtelte Schleifen. Dabei darf aber die zentrale Zelle, für die die Auswertung erfolgt, nicht mitgezählt werden.

Bei meinen ersten Versuchen traten unerklärliche Fehler auf. Als ich dann in der oberen rechten Ecke  die Anzahl der Genearationen anzeigte, stellte ich fest, dass nach der ersten Generation diese Anzeige entweder verschwand oder eigenartige Zeichen angezeigt wurden. Bei einer Übersetzung mit der Arduino-IDE wurde mir angezeigt, dass der Speicher knapp ist.

Globale Variablen verwenden 1.780 Bytes (86%) des dynamischen Speichers, 268 Bytes für lokale Variablen verbleiben. Das Maximum sind 2.048 Bytes.
Wenig Speicher verfügbar, es können Stabilitätsprobleme auftreten.

Die empirisch ermittelte kritische Grenze scheint bei 235 Bytes zu liegen. Ich habe dann systematisch gespart und außerdem die erste Matrix auf 12x12 gesetzt.

Eine weitere Schwierigkeit war, dass die Laufzeit für das Erzeugen einer Generation unerträglich lang war. Dies lag daran, dass ich das gesamte Spielfeld jeweils neu aufgebaut habe: Bei einer toten Zelle habe ich ein ausgefülltes Rechteck mit der Hintergrundfarbe ausgegeben, bei einer lebenden entsprechend ein ausgefülltes Rechteck mit der Farbe für lebende Zellen.

Diese Ausgabe erfolgte, egal, wie die Zelle vorher aussah. Da die meisten Zellen in der Regel tot sind, wurden hierdurch Zellen in einer Farbe ausgegeben, die sie ohnehin schon hatten.

Ich habe das Programm dann so geändert, dass vor Ausgabe geprüft wird, ob die Farbe der Zelle überhaupt geändert werden muß. Wenn dies nicht nötig ist, erfolgt auch keine Ausgabe. Da die Ausgabe auf dem TFT-Screen sehr langsam ist, erbrachte diese Änderung eine dramatische Erhöhung der Geschwindigkeit.

Ich habe insgesamt 10 feste Muster eingetragen, die bei Spielstart durch die nummerischen Tasten auf der IR-Fernbedienung gewählt werden können.

Folgende interessante Muster können abgerufen werden:

0: Ecken-Test
1: Blinker
2: Test
3: r-Pentomino
4: Gleiter
5: A for All
6: SpaceShip
7: Haus
8: Kickback
9: Oktagon

Dass der mBot auf eine Eingabe wartet, wird auch durch die grünen LEDs auf dem Board angezeigt.

Wenn ein Lauf abgebrochen werden soll, kann der Button auf dem Board so lange gedrückt werden, bis die LEDs kurz rot und dann grün leuchten.

Eigentlich wollte ich das Ausgangsmuster auch editierbar machen. Da ich keine Möglichkeit sehe, ein solches eigenes Muster auch irgendwie zu speichern, habe ich einen anderen Ansatz gewählt:

Die Extension   ⇒AdvancedArduino (bzw. AdvancedAdruino_Fork) bietet die Möglichkeit, eigene Funktionsdefinitionen auf der lokalen Platte des PCs abzuspeichern und diese dann über eine #include-Anweisung in das Programm zu integrieren. Neben der "normalen" Version(GOL.sb2 (80.1 KB))  habe ich eine weitere erzeugt (GOL_include.sb2 (79.7 KB)). Für diese muss es eine Funktion Daten enthalten, die mit einem Editor erzeugt werden kann und irgendwo auf der Platte abgespeichert wird. Im Programm muss dann im Block def der genaue Pfad zu der Datei GOL_Daten_1.inc (6.6 KB) eingetragen werden.