cfGol: The Game of Life

John H. Conway hat sich da 1970 ein cooles Regelwerk ausgedacht, das immer für ein schickes Progrämmchen gut ist. Das Game of Life besticht durch absolut einfache Regeln. Es lädt aber andererseits auch zum Herumprobieren ein und verfügt über ein paar Charakteristika, die es z.B. für Multi-Threading empfehlen. Spätestens da hatten wir angebissen und haben uns an die Arbeit gemacht.

Downloads

Ausführbares Programm (Version 0.0.2.121) 7zip, 15KB, .NET 4.0)

Sourcen (7zip, 1,4 MB, VS2010)

Vorbemerkungen

Das Programm, das wir hier diskutieren werden, hätte man auch ziemlich kompakt bauen können. Das habe ich mit Absicht nicht gemacht, denn ich möchte meinen Lesern immer möglichst aufzeigen, wie ich bestimmte Probleme im Business-Umfeld angehen würde. Das bedeutet, ich kommentiere, ich strukturiere ich nutze Schichten usw. Nicht immer wird ein Programm dadurch performanter oder leichtgewichtiger (eher selten) dafür erkauft man sich aber halt die altbekannten Vorteile sauberer Programmierung.

The Game of Life (GOL)

Es war niemand geringerer als Stephen Hawking, der mich in seinem Buch „The Grand Design“ auf das GOL aufmerksam machte. Die Idee dazu stammt wie gesagt von Conway. Letztlich entlehnt ist die Problemstellung der Automatentheorie. Es geht z.B. darum, aufzuzeigen, dass unter definierten Bedingungen unbegrenztes Wachstum nicht möglich ist. Jedes System, das gewissen Regeln unterliegt, wird irgendwann zum Stillstand kommen.

Doch eins nach dem anderen. Wie funktioniert GOL eigentlich? Ganz einfach. Wir denken uns eine Welt aus, die der Einfachheit halber einfach als Matrix (oder Tabelle, Array, wie auch immer) aus 2 Dimensionen besteht. Dann befüllen wir diese Welt zufällig mit einer gewissen Anzahl von „Lebewesen“. Ein Lebewesen ist in unserem vereinfachten Modell eine Zelle, die den Wert 1 hat. Eine tote oder leere Zelle hat den Wert 0.

Diese erste Befüllung nennen wir nun die 1. Generation. OK. Jetzt wenden wir ein paar Regeln auf jeden Punkt der Welt an:

  1. Wenn ein Lebewesen mehr als x1 Nachbarn hat, wird es in der nächsten Generation sterben.
  2. Wenn ein Lebewesen genau x2,x3… Nachbarn hat, wird es in der nächsten Generation weiterleben.
  3. Wenn ein toter Platz genau x4 Nachbarn hat, wird dort in der nächsten Generation ein Lebewesen geboren.

Das wars auch schon! Dieses Regelwerk wird einfach so lange auf jede Zelle der Welt angewandt, bis

  1. keine Lebewesen mehr in der Welt sind oder
  2. kein Wandel mehr erkennbar ist (es entstehen keine neuen Lebewesen und es sterben keine mehr) oder
  3. nur noch sog. oszillierende Objekte vorhanden sind (eine andere Art der Stagnation).

Die Entitäts-Typen

Das GOL erzeugt je nach initialem Regelsatz (x1, x2, x3, x4) unterschiedliche Welte, also sich unterschiedlich verhaltende Gruppen von Punkten. Ich nenne diese Gruppen Haufen (engl. bunches). Ein Haufen ist dabei eine Menge von Punkten, die in nachbarschaftlicher Beziehung zueinander stehen.

Es gibt einfache statische Haufenformen aber auch solche, die ihre Position bzw. Größe scheinbar ändern. Dann gibt es oszillierende Objekte und sog. Gleiter. Gerade letztere können entscheidend auf die Populations-Entwicklung der Welt einwirken, da sie scheinbar zufällig statische Objekte treffen und diese wieder zu nicht-statischen machen können.

Durch die zufällige Ausgangsbasis ist keine GOL-Welt wie die andere und es macht teilweise wirklich Spaß, einfach zu zuzusehen.

cfGol Allgemein

Das war nun die Geburtsstunde von cfGol. Ich habe das Programm zunächst als Proof of Concept entworfen und nachdem es dann rannte, habe ich es verfeinert und gebrauchsfähig gemacht. Die folgende Animation zeigt das Programm zur Laufzeit:

In der im Download angebotenen Version habe ich folgende Features im Einsatz:

  • Nutzung Task Parallel Library (TPL)
  • Nutzung von PLINQ
  • Optionen für die Game-Rules
  • Konsolen-Anwendung mit Argumenten
  • CSV-Export von Populations-Ergebnissen
  • Interface-basiertes Design von Klassen
  • Mustererkennung

Gerade der zuletzt genannte Punkt hat mich sehr interessiert, da ich auswerten wollte, wie häufig, welche Formen auftreten.

Das Projekt ist in 3 Teilprojekte untergliedert:

Abb 1.: Projektstruktur

Die App habe ich als Beispiel-Implementierung drin. Es spricht nichts dagegen, z.B. eine WPF-basierte GOL-App zu bauen und vielleicht mache ich das auch noch.

Genau wegen dieser Erweiterbarkeit ist cfGol.Shared entstanden. Hier habe ich Schnittstellen und andere in allen Schichten benötigten Einheiten untergebracht.

cfGol.Logic beinhaltet den Kern des Programms. Die Game-Klasse berechnet die einzelnen Generationen gesteuert durch die GameOption-Instanz. Eine Generation-Instanz behält die Ergebnisse einer einzelnen Generation im Blick. Die Game-Klasse arbeitet intern mit Arrays und bietet gewiss noch Raum für Optimierungen.

So richtig viel getüftelt habe ich an der „Mustererkennung“ für die Haufen. Die Game-Klasse hat eine Methode CollectBunches, die mit einigen Hilfsmethoden versucht, per PLINQ und TPL die Haufen zu identifizieren. Das verlangsamt das Programm momentan noch um einen Faktor bis zu 1.000! Hier ist also das größte Optimierungs-Potential. Mal schauen.

Ausblick

Ich werde jetzt mal abwarten, ob es Leute gibt, die vielleicht auch am Programm arbeiten möchten. Wenn ja, dann bitte einfach hier melden. Sollten mindestens 3 (mit mir) zusammen kommen, werde ich ein codeplex-Projekt daraus machen und mal weiter sehen. Ich mache aber auch allein weiter und informiere dann hier.

Wie gesagt: Es handelt sich hier nicht nur um eine Lösung für ein Problem. Es soll hier eine saubere, standardkonforme Lösung gezeigt werden. Quick&Dirty können alle (siehe wikipedia-Artikel am Ende).

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.

Diese Website verwendet Akismet, um Spam zu reduzieren. Erfahre mehr darüber, wie deine Kommentardaten verarbeitet werden.