JavaScript: Web Workers und Conway's Game of Life in 3D

Inhaltsverzeichnis

Der vor über 40 Jahren von John Horton Conway entwickelte zelluläre Automat, bekannt als Conway's Game of Life, begeistert auch heute noch, wenn sich aus dem scheinbarem Chaos Schritt für Schritt Strukturen entwickeln. Selbst Stephen Hawking nutzt ihn in seinem Werk "Der große Entwurf" als stark abstrahierte Analogie zu unserem Universum.

"Gespielt" wird das Zero-Player-Spiel auf einem zweidimensionalen Spielfeld nach folgenden Regeln: Eine Zelle überlebt eine Spielrunde, wenn zwei oder drei Zellen in der Nachbarschaft (einem drei mal drei Pixel großem Quadrat) ebenfalls lebendig sind. Sind es mehr oder weniger gilt die Zelle als über- oder unterbevölkert und stirbt. Ist die Zelle tot und es grenzen genau drei lebendige Zellen an, so wird eine neue Zelle geboren.

Im vorliegenden Artikel soll das Spiel um eine dritte Dimension erweitert in JavaScript implementiert werden. Für die Visualisierung kommt ein WebGL-Partikel-Renderer zum Einsatz. An zwei Stellen lassen sich außerdem die sogenannten Web Worker für die Optimierung nutzen.

Den Web-Worker-Standard entwickelten das World Wide Web Consortium (W3C) und der Web Hypertext Application Technology Working Group (WHATWG), um JavaScript Code im Hintergrund, unabhängig vom User Interface, ausführen zu können. Damit stellt er die Funktion der bisher fehlenden Threads unter JavaScript zur Verfügung.

Im Beispiel lassen sich durch Web Worker zum einen die Berechnung der Spielrunden und die Visualisierung auf zwei separate Threads aufteilen, um das Userinterface nicht zu blockieren. Damit sich die Hardware von Mehrkernsystemen voll nutzen lässt, besteht zudem die Option, die Berechnung der Spielrunden auf mehrere Threads zu verteilen. Beide Maßnahmen können Entwickler auf einige andere Anwendungsfälle übertragen. Alle Codebeispiele lassen sich zusammengepackt hier (.RAR) herunterladen.

Implementierung ohne Worker

Als Grundlage für die Optimierung mit Web Workern dient die Single-Threaded-Version des Programms. Bei der Erweiterung um die dritte Dimension sind die Regeln leicht anzupassen. Die Anzahl der Nachbarn ergibt sich nun aus einem 3x3x3 Zellen großen Würfel. Die Mengen der Zellen für Über-, Unterbevölkerung und Geburt sind darüber hinaus anzupassen, um Stabilität in das Universum zu bringen.

Als erstes soll betrachtet werden, wie sich das Universum verwalten lässt. Jede Zelle kann als einzelnes Bit im Speicher abgelegt werden. Typed Arrays erlauben es, Letzteren effizient zu allokieren. Die kleinste Elementeinheit ist jedoch ein Byte. Je Arrayelement lassen sich folglich mindestens 8 Zellen ablegen. Ein direkter Zugriff über den Arrayindex ist deshalb nicht möglich. Um die Spiellogik überschaubar zu halten, kann man die Bitoperationen in eine Universum-Klasse auslagern. Neben den set- und get-Methoden sorgt die init-Methode für einen Big Bang und haucht, je nach übergebener fuelrate, zufällig gewählten Zellen Leben ein. Die zaehleNachbarn-Methode sorgt ebenfalls für überschaubaren Code in der Spielrundenlogik.

Für den Partikelrenderer wird ein Float32Array mit je vier Elementen pro Partikel/lebender Zelle benötigt, das in die Methode generierePositionsArray erstellt. Neben den Koordinaten ist als viertes Element ein Attribut zur Bestimmung der Größe und Farbe des Partikels zu übergeben. Die Anzahl der Nachbarn bietet sich hier an, um Cluster kenntlich zu machen (Code siehe Exkurs: "3D-Bit-Array inklusive Util-Methode").

Die Spiellogik ist in der GameOfLife3d-Klasse implementiert. Im Konstruktor werden zwei Universen (multiversum) erstellt, die abwechselnd als Quelle und Ziel dienen. Die Größe ist durch den Parameter optionen.groesse definiert. Nach dem Allokieren kann man dem ersten Universum Leben einhauchen, was die init- Methode der Universum-Klasse übernimmt. Das Attribut optionen.initaleFuellrate definiert das Verhältnis Gesamtanzahl aller Zellen zu lebendigen Zellen. Die Spielrunden werden in der Methode berechneNaechsteGeneration berechnet. Die Arrays optionen.leben und optionen.geburt enthalten das Regelwerk für das Überleben und die Geburt einer Zelle. Eine Regel trifft zu, wenn die Anzahl lebendiger Nachbarn als Element im Array enthalten ist. Die drei verschachtelten for-Schleifen, für jede Dimension eine, wenden dieses Regelwerk auf alle Zellen an.

//Dieser Code initialisiert das Universum und stellt eine 
//Methode zur Berechnung der nächste Generation bereit.

var GameOfLife3d = function(optionen) {
  this.multiversum = [
    new Universum(optionen.groesse),
    new Universum(optionen.groesse)];
  this.multiversum[0].init(optionen.initaleFuellrate);

  this.berechneNaechsteGeneration = function(quelle, ziel, callback) {
    var todOderLebendig = function(zelle, nachbarn) {
      if(zelle == 1) {
        if(optionen.leben.indexOf(nachbarn) != -1)
          return 1;
        else
          return 0;
      } else {
        if(optionen.geburt.indexOf(nachbarn) != -1)
          return 1;
        else
          return 0;
      }
    };

    for(var x=0; x<optionen.groesse; x++) {
      for(var y=0; y<optionen.groesse; y++) {
        for( var z=0; z<optionen.groesse; z++) {
          ziel.set(x, y, z, todOderLebendig(quelle.get(x, y, z),
            quelle.zaehleNachbarn(x, y, z)));
        }
      }
    }

    callback();
  };
};