Mobilfunkautomaten im Browser

Ein zellularer Automat ist ein System, das aus Zellen mit numerischen Werten in einem Raster sowie Regeln besteht, die das Verhalten dieser Zellen bestimmen. Wenn man die Regel wiederholt parallel zur Visualisierung des Gitters auf jede Gitterzelle anwendet, kann man häufig die Wirkung eines bestimmten sich entwickelnden Organismus mit komplexem und komplexem Verhalten erzielen, selbst wenn die Regeln relativ einfach sind.

Zelluläre Automaten haben verschiedene Formen, Typen und Abmessungen. Der wohl bekannteste zellulare Automat ist das Conway's Game of Life (GOL). Es besteht aus einem zweidimensionalen Gitter, in dem jede Zelle einen Binärwert enthält (lebend oder tot). Die begleitenden Regeln, basierend auf dem Zustand benachbarter Zellen, bestimmen, ob die Zelle tot oder lebendig sein soll. Die Regeln besagen, dass eine lebende Zelle an Einsamkeit stirbt, wenn sich weniger als 2 lebende Zellen um sie herum befinden. Wenn mehr als drei benachbarte Zellen am Leben sind, stirbt sie an Überbevölkerung. Mit anderen Worten, eine Zelle "überlebt", wenn genau zwei oder drei benachbarte Zellen um sie herum leben. Damit eine tote Zelle zum Leben erweckt wird, müssen genau drei benachbarte Zellen leben, ansonsten bleibt sie tot. Ein Beispiel für eine GoL-Maschine, die mehrere Status durchläuft, ist unten dargestellt.


Eine andere berühmte Version des zellularen Automaten ist eindimensional; Es heißt Elementary Cellular Automaton (ECA). Dies setzen wir in diesem Beitrag um.

Jeder Zustand dieses Automaten wird als eindimensionales Array von Booleschen Werten gespeichert, und während zur Visualisierung des GOL-Zustands zwei Dimensionen erforderlich sind, reicht für diesen Automaten ein Werteautomat aus. Aus diesem Grund können wir die gesamte Geschichte der Zustände dieses Automaten zweidimensional (anstatt animiert) darstellen. Wie im Fall von GOL ist der Status der Zelle in dieser Maschine 0 oder 1, aber im Gegensatz zu der GOL-Zelle, die abhängig von ihren 8 Nachbarn aktualisiert wird, wird die ECA-Zelle basierend auf dem Status des linken Nachbarn, des rechten Nachbarn und sich selbst aktualisiert!

Beispiele für Regeln sind im Folgenden aufgeführt: Die oberen drei Zellen sind die Eingabe der Regel, und die untere ist die Ausgabe, wobei Schwarz 1 und Weiß 0 ist. Außerdem können wir die von jedem von ihnen erzeugten Muster sehen, wenn der Anfangszustand alle 0 außer 1 ist in der mittleren Zelle.


Sie fragen sich vielleicht: Warum werden die oben aufgeführten Regeln durch Zahlen angezeigt? Da jede Zahl im Bereich von 0 bis 255 direkt der ECA-Regel entspricht, werden diese Zahlen als Namen der Regeln verwendet. Diese Entsprechung wird unten gezeigt:


Von der Zahl zur Regel

Jede Zahl im Bereich von 0 bis 255 kann binär mit nur 8 Stellen dargestellt werden (erster Pfeil oben). Darüber hinaus können wir jeder dieser Zahlen einen Index geben, der auf ihrer Position basiert (zweiter Pfeil). Selbstverständlich liegen diese Indizes im Bereich von 0 bis 7, dh sie können mit nur 3 Stellen binär dargestellt werden (dritter Pfeil). Wenn wir diese 3 Ziffern als Eingabe interpretieren und die entsprechende Ziffer der ursprünglichen Zahl als Ausgabe, erhalten wir die benötigte ternäre Funktion (vierter Pfeil).

Regelerstellung

Implementieren wir die obige Interpretation als übergeordnete Funktion get_rule , die eine Zahl von 0 bis 255 als Eingabe empfängt und eine dieser Zahl entsprechende ECA-Regel zurückgibt.

Wir müssen so etwas erstellen:

 const rule30 = get_rule(30); const output110 = rule30(1, 1, 0); 

In dem obigen Beispiel kombiniert das Starten von rule30(1,1,0) alle drei Binärwerte zu einer Zahl (110 = 6) und gibt an dieser Stelle (6) in der Binärdarstellung 30 ein Bit zurück. Die Zahl 30 in der Binärdarstellung ist 00011110. Daher gibt die Funktion 0 zurück (wir zählen rechts und beginnen die Zählung bei 0).

Da wir wissen, dass die drei binären Eingangsvariablen zu einer Zahl zusammengefasst werden, implementieren wir zunächst eine solche combine .

 const combine = (b1, b2, b3) => (b1 << 2) + (b2 << 1) + (b3 << 0); 

Nachdem wir die Argumente nach links verschoben und dann die drei verschobenen Zahlen addiert haben, erhalten wir die gewünschte Kombination.

Der zweite wichtige Teil der Funktion get_rule besteht darin, den get_rule an einer bestimmten Position in einer Zahl zu bestimmen. Erstellen get_bit(num, pos) daher eine Funktion get_bit(num, pos) , die einen get_bit(num, pos) an einer bestimmten Position pos an einer bestimmten Nummer num . Die Zahl 141 in binärer Form lautet beispielsweise 10001101, daher sollte get_bit(2, 141) 1 und get_bit(5, 141) 0 .

Die Funktion get_bit(num,pos) kann implementiert werden, indem zuerst eine Bitverschiebung der Zahl um pos nach rechts durchgeführt wird und dann die bitweise Operation „AND“ mit der Zahl 1 ausgeführt wird.

 const get_bit = (num, pos) => (num >> pos) & 1; 

Jetzt müssen wir nur noch diese beiden Funktionen kombinieren:

 const get_rule = num => (b1, b2, b3) => get_bit(num, combine(b1, b2, b3)); 

Großartig! Wir haben also eine Funktion, die uns für jede Zahl innerhalb unseres Intervalls eine eindeutige ECA-Regel gibt, mit der wir alles tun können. Der nächste Schritt ist das Rendern im Browser.

Regelvisualisierung

Zum Rendern von Automaten im Browser verwenden wir das canvas Element. Das canvas kann wie folgt erstellt und dem HTML-Körper hinzugefügt werden:

 window.onload = function() { const canvas = document.createElement('canvas'); canvas.width = 800; canvas.height = 800; document.body.appendChild(canvas); }; 

Um mit canvas interagieren zu können, brauchen wir Kontext . Der Kontext ermöglicht es uns, Formen und Linien zu zeichnen, Objekte einzufärben und allgemein auf der canvas navigieren. Sie wird uns über die getContext Methode unserer getContext bereitgestellt.

 const context = canvas.getContext('2d'); 

Der Parameter '2d' bezieht sich auf den Kontexttyp, den wir in diesem Beispiel verwenden werden.

Als Nächstes erstellen wir eine Funktion, die den Kontext, die ECA-Regel sowie einige Informationen über den Maßstab und die Anzahl der Zellen enthält und die Regel auf canvas zeichnet. Die Idee ist, ein Gitter Linie für Linie zu erzeugen und zu zeichnen. Der Hauptteil des Codes sieht ungefähr so ​​aus:

 function draw_rule(ctx, rule, scale, width, height) { let row = initial_row(width); for (let i = 0; i < height; i++) { draw_row(ctx, row, scale); row = next_row(row, rule); } } 

Wir beginnen mit einer Art anfänglichem Satz von Zellen, der aktuellen Zeile. Diese Zeile enthält, wie in den obigen Beispielen, normalerweise alle Nullen, mit Ausnahme einer Einheit in der mittleren Zelle. Sie kann jedoch auch eine vollständig zufällige Reihe von 1 und 0 enthalten. Wir zeichnen diese Reihe von Zellen und verwenden dann die Regel, um die nächste Wertereihe basierend auf zu berechnen aktuelle Zeile. Dann wiederholen wir einfach die Zeichnung und berechnen die neuen Schritte, bis wir feststellen, dass das Gitter hoch genug ist.

Für das obige Code-Snippet müssen drei Funktionen implementiert werden: initial_row , draw_row und next_row .

initial_row ist eine einfache Funktion. Es erstellt ein Array von Nullen und ändert das Element in der Mitte des Arrays um eins.

 function initial_row(length) { const initial_row = Array(length).fill(0); initial_row[Math.floor(length / 2)] = 1; return initial_row; } 

Da wir bereits eine Regelfunktion haben, kann die next_row Funktion aus einer Zeile bestehen. Der Wert jeder Zelle in einer neuen Zeile ergibt sich aus der Anwendung der Regel mit den Werten der nächsten Zellen, und die alte Zeile wird als Eingabe verwendet.

 const next_row = (row, rule) => row.map((_, i) => rule(row[i - 1], row[i], row[i + 1])); 

Haben Sie bemerkt, dass wir diese Linie betrogen haben? Jede Zelle in einer neuen Zeile erfordert die Eingabe von drei anderen Zellen, aber zwei Zellen an den Rändern der Zeile empfangen Daten von nur zwei. Beispielsweise versucht next_row[0] , den next_row[0] aus row[-1] next_row[0] . Dies funktioniert immer noch, da beim Versuch, auf Werte über Indizes zuzugreifen, die nicht im Array enthalten sind, Javascript undefined zurückgibt, und es daher vorkommt, dass (undefined >> [ ]) (aus der combine ) immer 0 zurückgibt. Dies bedeutet dass wir in Wirklichkeit jeden Wert außerhalb des Arrays als 0 verarbeiten.

Ich weiß, dass das hässlich ist, aber bald werden wir etwas Schönes auf dem Bildschirm erschaffen, damit uns vergeben werden kann.

Als nächstes kommt die draw_row Funktion; Sie ist es, die das Rendering durchführt!

 function draw_row(ctx, row, scale) { ctx.save(); row.forEach(cell => { ctx.fillStyle = cell === 1 ? '#000' : '#fff'; ctx.fillRect(0, 0, scale, scale); ctx.translate(scale, 0); }); ctx.restore(); ctx.translate(0, scale); } 

Hier sind wir sehr abhängig von dem Kontextobjekt und verwenden mindestens 5 davon verschiedene Methoden. Hier ist eine kurze Auflistung und wie man sie benutzt.

• fillStyle gibt an, wie die Formen gefüllt werden sollen. "#f55" kann eine Farbe sein, zum Beispiel "#f55" , sowie ein Farbverlauf oder ein Muster. Wir verwenden diese Methode, um Zellen 0 visuell von Zellen 1 zu trennen.
• fillRect(x, y, w, h) zeichnet ein Rechteck aus einem Punkt (x, y) mit der Breite w und Höhe h, gefüllt gemäß fillStyle . Unsere Rechtecke sind einfache Quadrate, aber Sie werden überrascht sein, dass der Ausgangspunkt aller Rechtecke am Ursprung liegt. Es ist passiert, weil wir diese Methode in Kombination mit translate .
• translate(x, y) können Sie das gesamte Koordinatensystem verschieben. Die Position wird gespeichert, daher ist die Methode eine hervorragende Alternative zum Verfolgen verschiedener Positionen von Elementen. Anstatt zum Beispiel die Position jeder einzelnen Gitterzelle zu berechnen, können wir einfach eine Zelle zeichnen, nach rechts gehen, eine neue Zelle zeichnen und so weiter.
• save() und restore() werden in Verbindung mit translate und anderen Koordinatenkonvertierungsmethoden verwendet. Wir verwenden sie, um das aktuelle Koordinatensystem an einem bestimmten Punkt zu speichern , damit wir später darauf zurückgreifen können (mithilfe von Wiederherstellen ). In diesem Fall speichern wir das Koordinatensystem vor dem Rendern der Linie und verschieben es nach rechts. Wenn wir mit dem Zeichnen der Linie fertig sind und ganz nach rechts gegangen sind, werden die Koordinaten wiederhergestellt und wir kehren zum ursprünglichen Zustand zurück. Dann gehen wir nach unten, um uns darauf vorzubereiten, die nächste Linie zu zeichnen.

Jetzt haben wir alle Teile, die für die Funktion draw_rule erforderlich sind. Wir verwenden diese Funktion in window.onload nachdem wir den canvas vorbereitet haben. Wir werden auch die Parameter bestimmen, die wir brauchen.

 window.onload = function() { const width = 1000; // Width of the canvas const height = 500; // Height of the canvas const cells_across = 200; // Number of cells horizontally in the grid const cell_scale = width / cells_across; // Size of each cell const cells_down = height / cell_scale; // Number of cells vertically in the grid const rule = get_rule(30); // The rule to display const canvas = document.createElement('canvas'); canvas.width = width; canvas.height = height; document.body.appendChild(canvas); const context = canvas.getContext('2d'); draw_rule(context, rule, cell_scale, cells_across, cells_down); }; 

Wir extrahieren die canvas als separate Variablen zusammen mit der Anzahl der Zellen horizontal. Dann berechnen wir cell_scale und 'cells_down' so, dass das Raster die gesamte Zeichenfläche ausfüllt, während die Zellen quadratisch bleiben. Dank dessen können wir leicht die "Auflösung" des Gitters ändern, die innerhalb der canvas verbleibt.


Das ist alles! Das vollständige Codebeispiel ist auf Github und auf Codepen :

Weitermachen

Dank dieses Systems können wir nacheinander alle 256 Regeln überprüfen, entweder iterativ, indem wir den Code ändern oder bei jedem Seitenaufruf eine zufällige Regelnummer auswählen. Wie dem auch sei, es ist sehr aufregend, all diese unvorhersehbaren Ergebnisse in unserer kontrollierten Umgebung zu untersuchen.

Sie können auch den Anfangszustand der Zellen des Automaten zufällig bestimmen, anstatt der statischen „durchgezogenen Nullen und einer Einheit“. So erhalten wir noch unvorhersehbarere Ergebnisse. Diese Version der Funktion initial_row kann folgendermaßen geschrieben werden:

 function random_initial_row(width) { return Array.from(Array(width), _ => Math.floor(Math.random() * 2)); } 

Unten sehen Sie, wie sehr diese Änderung der Ausgabezeile einen großen Einfluss auf die Ausgabe hat.


Zufällige Quellzeichenfolge

Und dies ist nur ein Aspekt, den Sie ändern können! Warum beschränken Sie sich nur auf zwei Bedingungen? (Der Übergang von 2 zu 3 Staaten erhöht die Anzahl der Regeln von 256 auf 7 625 597 484 987!) Warum auf Quadrate beschränken? Warum nur 2 Dimensionen? Warum immer nur eine Regel?

Beispiele für Visualisierungen, die auf ECA basieren, sind unten aufgeführt, jedoch mit einer alternativen Funktion draw_rule , draw_rule Linien nicht mit Quadraten, sondern mit einem isometrischen Muster zeichnet und anschließend die durch diese Linien definierten Bereiche mit Farben füllt. Sie müssen nicht einmal Trennlinien anzeigen und nur Farben anzeigen.


Wenn Sie noch weiter gehen, können Sie Symmetrien hinzufügen, sowohl axial (mittlere Reihe) als auch gespiegelt (untere Reihe).


Wenn Ihnen diese Visualisierungen interessant erschienen, studieren Sie diese interaktive Sandbox , oder noch besser, beginnen Sie mit dem Code, den wir erstellt haben, und versuchen Sie, Ihre eigenen zellularen Automaten zu entwickeln!

Viel glück