Conway’s Game of Life

Ich habe mal wieder Spaß beim Programmieren gehabt. Bei der Entwicklung des Send More Money Programms hatte ich in der Vergangenheit auch schon mal Spaß gehabt. Programme, die kein Mensch braucht. 🙂

Schon lange einmal wollte ich mir das Game of Life des Mathematikers John Horton Conway vornehmen. Und inzwischen habe ich eine Version in PHP geschrieben.

Worum geht es im „Game of Life“?

Beim „Game of Life“ handelt es sich um die Simulation eines zellulären Automaten. Das ist ein Raum (oder eine Fläche als zweidimensionaler Raum), in dem sich voneinander getrennte Einheiten nach definierten Regeln entwickeln. In unserem Fall nehmen wir eine Art kariertes Blatt Papier. Da sind die Zellen quasi schon vorgegeben. Jede Zelle (jedes Quadrat auf dem Karoblatt) kann tot oder lebendig sein. Mehr nicht.

Wenn man jetzt zufällig (oder wohl überlegt) eine Reihe von Zellen ins Leben ruft, so ergibt sich ein Anfangszustand unserer kleinen Welt. Man kann zum Beispiel Reiskörner auf die Kästchen legen, wo sich eine lebende Zelle befinden soll.

Foto eines Karopapiers mit Reiskörnern

(Okay, so richtig viel kann man nicht erkennen. Ich hätte die Reiskörner einfärben sollen!)

Man könnte statt der Reiskörner auch ein paar Spielsteine nehmen.

Foto eines Karopapiers mit Spielsteinen

(Schon besser.)

Diese Ursuppe an Zellen bzw. Reiskörnern entwickelt sich nun nach genau vier einfachen Regeln weiter zu einer neuen Generation. Dabei wird jede Zelle einzeln auf ihre Nachbarn hin untersucht und dann entsprechend der Regeln in einen neuen Zustand überführt. Zellen können sterben, aber es können auch neue Zellen geboren werden.

Wie lauten die Regeln?

Für jede Zelle werden die Nachbarzellen betrachtet, also insgesamt 8 Zellen (diagonal zählt mit). Auf die Nachbarn selber haben die Regeln keine Auswirkung, sie werden also nicht beeinflusst. Es geht immer um genau dieses eine Kästchen. Deswegen werden bei den Beispielen auch keine Nachbarn mit in die nächste Generation übernommen. Wie es um sie steht, entscheidet sich erst bei der Untersuchung derer Nachbarn.

Neugeburt einer Zelle

Ausgangszustand für die Geburt einer neuen ZelleEine neue Zelle wurde geboren

In einem Kästchen, in dem sich noch keine Zelle bzw. kein Reiskorn/Spielstein befindet, kann neues Leben entstehen. Dazu braucht es zwei Eltern und eine Hebamme, also genau drei Nachbarn.

Überleben der Zelle

Eine Zelle mit zwei Nachbarn überlebtDer Zustand der Zelle hat sich nicht geändert
Eine Zelle mit drei Nachbarn überlebtDer Zustand der Zelle hat sich nicht geändert

Befindet sich in einem Kästchen ein Reiskorn/Spielstein, so kann die Zelle nur dann überleben, wenn sie genau zwei oder drei Nachbarn hat. DIe drei Nachbarzellen helfen also nicht nur bei der Geburt, sondern auch beim Überleben. Das nennt man wohl Familie.

Die Zelle stirbt an Einsamkeit

Eine Zelle ohne NachbarnDie einsame Zelle ist gestorben
Eine Zelle mit einem einzigen NachbarnDIe Zelle ist gestorben, die Nachbarzelle wird nicht beeinflusst.

Wenn die Zelle gar keine oder nur einen einzigen Nachbarn hat, dann geht es der Zelle sehr schlecht und sie stirbt leider an Einsamkeit.

Die Zelle stirbt an Überbevölkerung

Diese Zelle hat rundherum überall Nachbarn.Die Zelle ist an der Überbevölkerung gestorben.
Eine Zelle mit vier Nachbarzellen.Eine Zelle mit vier Nachbarn ist gestorben.

Bei vier oder mehr Nachbarn bekommt die Zelle einen Rappel und stirbt an Überbevölkerung, Man könnte auch sagen, dass einfach nicht genug Nahrung für alle da ist.

Vom Karopapier zum PHP-Programm

Keine Frage: das kann man super mit einem Blatt Papier spielen.

Ein wenig mühsam ist es aber schon.

Und deswegen gibt es auch zahlreiche Programme und Apps, mit denen man das ganz einfach spielerisch auf dem Handy oder dem PC ausprobieren kann.

Ich habe mir mein eigenes Programm geschrieben.

Wenn ihr wollt, könnt ihr das hier ausprobieren: http://sevke.net/php/gol/gol.php.

Interessante Objekte in Conway’s Game of Life

Wenn man mit dem Programm eine Zeit lang herumgespielt hat, stellt man schnell fest, dass es ein paar interessante Objekte gibt. Mitunter bleiben Zellklumpen erhalten und entwickeln sich nicht mehr weiter.

Zusammenstellung von statischen <Objekten in Conway's Game of Life
In dem Bild seht ihr die folgenden Objekte von links oben nach rechts unten: Pond (Teich), Block, Loaf (Laib), Beehive (Bienenstock), Tub (Wanne), Snake (Schlange), Boat (Boot), Largeboat (großes Boot), Ship (Schiff), Largeship (großes Schiff), Barge (Kahn), Largebarge (großer Kahn).
(Ich habe mir diese Bezeichnungen nicht ausgedacht.)

Manche Objekte wechseln immer zwischen mehreren Zuständen hin und her, bleiben aber ansonsten stabil.

Der Blinker
[selber ausprobieren]

Anfangszustand des BlinkersOszillierender Blinker

Die Uhr
[selber ausprobieren]

Anfangszustand der ClockOszillierende Clock

Der Bipol
[selber ausprobieren]

Anfangszustand des BipolsOszillierender Bipol

Der Tripol
[selber ausprobieren]

Anfangszustand des TripolsOszillierender Tripol

Die Kröte
[selber ausprobieren]

Anfangszustand des ToadsOszillierender Toad

Das Pentadecathlon
[selber ausprobieren]

Anfangszustand des PentadecathlonsOszillierendes Pentadecathlon

Der Pulsar
[selber ausprobieren]

Anfangszustand des PulsarsOszillierender Pulsar

Das Oktagon
[selber ausprobieren]

Anfangszustand des OktagonsOszillierendes Oktagon

Der Tümmler
[selber ausprobieren]

Anfangszustand des TumblersOszillierender Tumbler

Der Pulsar ist eins meiner Lieblingsobjekte. Er besitzt im Zentrumsbereich einige statische Zellen, um die herum das Gebilde pulsiert.

Darstellung der drei Phasen des Pulsars

Die 3 Phasen des Pulsars

Und dann gibt es manchmal sogar Gleiter und Raumschiffe, die sich über den Bildschirm bewegen, ihre Form dabei ändern, dann aber wieder zur Ursprungsform zurückfinden.

Der Glider in der ersten Generation

Glider

Das LWSS in der ersten Generation

LWSS

Das MWSS in der ersten Generation

MWSS

Das HWSS in der ersten Generation

HWSS

Der Gleiter bewegt sich diagonal über das Spielfeld.

Das sieht dann in etwa so aus:

Der Glider in der Bewegung

Hier bewegt sich der Gleiter diagonal nach rechts unten … auch wenn es komisch aussieht, als würde sich das Papier nach links oben bewegen. Alles ist eben relativ. 😉

Im Gegensatz zum Gleiter bewegen sich die Raumschiffe immer senkrecht oder waagerecht. Die drei verschiedenen Raumschiffe unterscheiden sich nur in ihrer Größe. Exemplarisch hier die Bewegung des LWSS (Light Weight Space Ship):

Das LWSS in der Bewegung

Eins der interessantesten Objekte ist die Gosper Gleiter Kanone. Dieser Zellenverbund wabert immer von rechts nach links und wieder nach rechts und stößt dabei nach unten in regelmäßigen Abständen Gleiter aus, die sich nach unten rechts wegbewegen. Das Ganze läuft in einer endlosen Schleife.

Die Gleiter Kanone sieht folgendermaßen aus:
Die Glidergun in der ersten Generation
Naja, okay, unter einer „Kanone“ stellt man sich überlichweise etwas anderes vor. Die Bezeichnung müsst ihr einfach akzeptieren. Jedes Ding braucht seinen Namen.

In Aktion werden – wie gesagt – regelmäßig kleine Gleiter ausgestoßen. Das wiederholt sich immer wieder.

Animierte Darstellung der Glidergun

Hinweise zu meiner Version des Game of Life

Normalerweise werden die Zellen immer als schwarze Objekte dargestellt. Ich habe das Ganze etwas farbenfroher gestaltet:

Farbige Darstellung des Tumblers in der neunten Generation

Der Tumbler

Grün: eine Zelle wurde neu geboren
Schwarz: die Zelle hat überlebt
Grau: die Zelle ist schon ziemlich alt
Rot: die Zelle stirbt gleich an Einsamkeit

Das Programm unterstützt (zur Zeit) nur Einzelschritte, aber keine (endlose) automatische Erzeugung der Generationen. Damit möchte ich verhindern, dass einige Spaßvögel den Webserver einem Stress-Test aussetzen.

Eine ganze Menge an stabilen statischen Objekten (Block, Tub, Snake, Beehive, Pond, Loaf, Boat, Largeboat, Ship, Largeship, Barge, Largebarge) und stablien oszillierenden Objekten (Blinker, Toad, Beacon, Tripole, Clock, Oktagon, Tumbler, Pulsar, Pentadecathlon) sowie natürlich verschieden Gleiter und Raumschiffe (Glider, LWSS, MWSS, HWSS) und natürlich die berühmte GliderGun könnt ihr euch anzeigen lassen, indem ihr an den URL den Parameter „?type=…“ anhängt. Die drei Punkte müsst ihr dabei durch den Namen des Objektes (alles in Kleinbuchstaben) ersetzen.

Alle oszillierenden Objekte werden mit jeweils 2 kompletten Zyklen angezeigt. Danach könnt ihr per Einzelschritt weitermachen.

Beispiel: http://sevke.net/php/gol/gol.php?type=glidergun.

Weitere Informationen im Internet

Kategorien: Allgemein  Tags: , ,

Du kannst die Kommentare als RSS 2.0-Feed abonnieren. Du kannst selber einen Kommentar schreiben, oder von deiner eigenen Website einen Trackback setzen.

Dein Kommentar