Conway

John Conway^[1]

John Horton Conway war ein englischer Mathematiker, bekannt für seinen Zellulären Automaten «Game of Life». Es handelt sich dabei um eine Art «fiktive Simulation»: Auf einem Gitter lebende Zellen vermehren sich oder sterben ab.

Seit der Veröffentlichung 1970 im Scientific American, wurde das Spiel zig-fach programmiert, in vielen Programmmiersprachen, auf allen möglichen Plattformen und auch in abgewandelten Varianten.

Idee

Zellen leben auf einer unendlichen Gitter-Welt. Dabei wird generationsweise berechnet welche Zellen weiterleben, welche absterben und wo neue Zellen geboren werden. Conway wählte die Regeln für die Berechnung der nächsten Generation so, dass sie nicht sehr kompliziert sind, aber das trotzdem sehr interessante Muster entstehen können.

Regeln

Die Regeln für einen Gitterpunkt in der nächsten Generation lauten wie folgt:

• hat es dort eine lebendige Zelle, dann
  • stirbt sie, wenn sie weniger als zwei Nachbarn hat. (Unterbevölkerung)
  • lebt sie weiter, wenn sie genau zwei oder drei Nachbarn hat.
  • stirbt sie, wenn sie mehr als drei Nachbarn hat. (Überbevölkerung)
• hat es dort keine Zelle (resp. eine gestorbene Zelle), dann
  • wird eine neue Zelle geboren, wenn der Gitterpunkt genau 3 Nachbarn hat. (Fortpflanzung)

Als Nachbarn einer Zelle zählen alle Zellen, welche die Zelle berühren, wenn auch nur in einer Ecke. Eine Zelle kann also maximal 8 Nachbarn haben.

Beispiel

00000
00xx0
0xx00
00x00
00000

1. Generation

00000
0xxx0
0x000
0xx00
00000

2. Generation

00x00
0xx00
x00x0
0xx00
00000

3. Generation

1. zu 2. Generation
Oben links und unten rechts entstehen neue Zellen.
Die Zelle in der Mitte stirbt.

2. zu 3. Generation
Oben und links, sowie in der Mitte rechts entstehen neue Zellen.
Die Zelle links in der Mitte stirbt.

Implementation

Wir versuchen, Conway’s Game of Life mit dem uns bekannten Pygame Zero zu implementieren.

Welt

Am Besten verwendet man für die Gitter-Welt wohl eine zweidimensionale Liste, z.B. von Wahrheitswerten bool:

• True steht für: «Hier lebt eine Zelle»
• False steht für: «Hier lebt keine Zelle»

Laut Conway sollte die Welt unendlich gross sein. Das kann man natürlich nicht so umsetzen, man könnte aber die Welt als Torus darstellen, indem man den oberen und den unteren, sowie den linken und den rechten Rand verbindet. Einfacher ist es, den Rand einfach bestehend als toten Zellen anzunehmen.

Alternativ könnte man auf jeden Gitterpunkt einen Actor setzen. Dann könnte man den Zellen in Form von PNG-Dateien eine Gestalt geben. Allerdings bräuchte das wesentlich mehr Resourcen. Zudem stellt sich die Frage, ob man bei Entstehen einer Zelle einen Actor erzeugen möchte und beim Tod einer Zelle diesen wieder löscht, oder ob man immer überall einen Actor hat und Leben und Tod durch zwei unterschiedliche Bild-Dateien darstellt.

Startzustand

Am Einfachsten wählt man einige zufällige Zellen aus, z.B. jede dritte Zelle lebt. Man könnte natürlich auch vordefinierte Zustände laden oder fest programmieren (zum Beispiel ein r-Pentomino), dann ist aber der Ablauf immer der selbe.

Darstellung

Wir brauchen eine zweidimensionale Darstellungsart:

• zu Testzwecken könnte man die aktuelle Welt als Text in der Shell ausgeben
• schöner wäre eine grafische Darstellung, z.B. mit Pygame Zero. Man könnte lebende Zellen als Rechtecke screen.draw.filled_rect() oder mit Hilfe von Actors zeichnen

Generationen berechnen

Die neue Generation sollte man in einem Unterprogramm berechnen, das man z.B. jede Sekunde einmal aufruft (clock.schedule_interval("next_generation", 1). Dabei gilt es einiges zu beachten:

• Um die Nachbarn zu zählen, braucht man die Koordinaten. Auch muss man aufpassen wenn man am Rand ist!
• beim Berechnen der nächsten Generation muss man die Welt doppelt haben – man darf ja beim Zählen der Nachbarn nicht schon auf die neue Generation zugreifen

Interessante Elemente

0000
0xxx
xxx0
0000

Oszillator – verändert sich zyklisch

0x0
00x
xxx

Gleiter – bewegt sich

0xx
xx0
0x0

r-Pentomino – wächst über mehrere Generationen

Mögliches Vorgehen

einfaches Game of Life

• Zellen als zweidimensionales Array definieren
• zufällige lebende Zellen einbauen
• Welt in draw() grafisch darstellen
• Unterprogramm zur Berechnung der nächsten Generation implementieren
• Unterprogramm mit clock.schedule_interval() regelmässig ausführen lassen

gewünschte Erweiterungen

• einfache Möglichkeit Grösse der Welt und Frequenz der Generationsberechnung einzustellen (als Konstante in Programm oder als Input beim Programmstart)
• Welt «wrappen» und als Torus darstellen

weitere Erweiterungen

• GUI mit Steuermöglichkeiten (nächste Generation, Pause, Abspielen, …)
• Möglichkeit Zellen zu setzen/zu entfernen (mit der Maus)
• Laden von speziellen Objekten aus dem Code (Glider, Oszillator, …)
• Laden und Speichern von Welten aus einer Datei

---

1. Thane Plambeck via Wikimedia Commons (opens new window) ↩︎