knp.de

– Archiv: Zelluläre Automaten simulieren

Archiv: Zelluläre Automaten simulieren

03/31/2014

Archiv-Einträge haben sich aus älteren Posts ergeben. Sie erscheinen hier in einem neuen Layout.

Einer meiner ältesten Posts beschäftigt sich mit zellulären Automaten. Eine Zeile aus Bits (mit den Werten 0 oder 1) sind gegeben. Das Bit an einer beliebigen Position in der nächsten Zeile ist durch das Bit aus der vorherigen Zeile und seine Nachbarn bestimmt.

Das folgende Programm in C++ simuliert einen solchen Automaten.

cellular.c++:

#include <iostream>
#include <vector>
#include <getopt.h>

#pragma mark - configuration

static int automata_nr = 30;
static int display_rows = 60;
static int display_column_begin = -39;
static int display_column_end = 40;

void handle_options(int argc, char **argv) {
    static struct option long_options[] = {
        { "nr", required_argument, 0, 'n' },
        { "rows", required_argument, 0, 'r' },
        { "begin", required_argument, 0, 'b' },
        { "end", required_argument, 0, 'e' },
        { 0 }
    };

    for (;;) {
        int choice = getopt_long(
            argc, argv,
            "n:r:b:e:",
            long_options, NULL
        );

        if (choice == -1) break;
        switch (choice) {
            case 'n':
                automata_nr = atoi(optarg);
                break;
            case 'r':
                display_rows = atoi(optarg);
                break;
            case 'b':
                display_column_begin = atoi(optarg);
                break;
            case 'e':
                display_column_end = atoi(optarg);
        }
    }
}

#pragma mark - handling bits in one line

class Line {
public:
    Line(bool placeholder, int begin);

    bool placeholder() const { return _placeholder; }
    int begin() const { return _begin; }
    int end() const { return _begin + _data.size(); }
    int default_mask() const;

    bool operator[](int index) const;
    void push_back(bool value);

    std::ostream &print(std::ostream &out) const;

private:
    Line();
  
    bool _placeholder;
    int _begin;
    std::vector<bool> _data;
};

inline Line::Line(bool placeholder, int begin):
    _placeholder(placeholder), _begin(begin), _data()
{}

inline int Line::default_mask() const {
    return _placeholder ? 0b111 : 0b000;
}

inline bool Line::operator[](int i) const {
    if (i < begin() || i >= end()) return _placeholder;
    return _data[i - begin()];
}

inline void Line::push_back(bool value) {
    _data.push_back(value);
}

std::ostream &Line::print(std::ostream &out) const {
    for (
        int i = display_column_begin;
        i < display_column_end;
        ++i
    ) {
        out << (*this)[i];
    }
    return out;
}

std::ostream &operator<<(std::ostream &out, const Line &line) {
    return line.print(out);
}

#pragma mark - run simulation

int main(int argc, char **argv) {
    handle_options(argc, argv);
  
    const bool resulting_bit[8] = {
        (automata_nr & 0b00000001), (automata_nr & 0b00000010),
        (automata_nr & 0b00000100), (automata_nr & 0b00001000),
        (automata_nr & 0b00010000), (automata_nr & 0b00100000),
        (automata_nr & 0b01000000), (automata_nr & 0b10000000)
    };

    Line previous(false, 0);
    previous.push_back(true);
    std::cout << previous << std::endl;

    for (int i = 0; i < display_rows; ++i) {
        Line current(
            resulting_bit[previous.default_mask()],
            previous.begin() - 1
        );
        
        int gliding = previous.default_mask();
        for (
            int j = previous.begin();
            j <= previous.end() + 1;
            ++j
        ) {
            gliding = ((gliding << 1) + previous[j]) & 0b111;
            current.push_back(resulting_bit[gliding]);
        }

        std::cout << current << std::endl;
        previous = current;
    }
}

Der Code wurde etwas aufpoliert. Der voreingestellte Automat eignet sich wunderbar, um Zufallszahlen zu generieren.

Konfiguration

Über Kommandozeilen Optionen kann das Verhalten und die Ausgabe des Programms verändert werden.

Verhalten

Der Parameter -n oder --nr gibt an, welcher Automat simuliert werden soll. Die Ausgaben aller Automaten sind in alle einfachen Automaten abgebildet.

Die Nummer ergibt sich aus den Ausgaben des Automaten für alle möglichen Eingaben, etwa:

000 → 0 ⇒ 0 * 1
001 → 1 ⇒ 1 * 2
010 → 0 ⇒ 0 * 4
011 → 0 ⇒ 0 * 8
100 → 1 ⇒ 1 * 16
101 → 0 ⇒ 0 * 32
110 → 0 ⇒ 0 * 64
111 → 0 ⇒ 0 * 128

Die Summe der rechten Spalte ergibt 2 + 16 == 18 als Nummer für den Automaten.

Das Eingabemuster der ersten Zeile ist ein einzelnes gesetztes Pixel in der Spalte 0.

Ausgabe

Die Anzahl der ausgegebenen Spalten wird über den Parameter -r oder --rows angegeben. Wenn dieser Parameter nicht angegeben wird, dann werden 30 Zeilen ausgegeben.

Die erste auszugebende Spalte kann mit -b oder --begin angegeben werden. Die erste Spalte, die nicht mehr ausgegeben wird, kann mit -e oder --end angegeben werden. Die Semantik ist analog zu Containern in der C++ STL.

Insgesamt werden

--end - --begin

viele Spalten ausgegeben. Wenn die Parameter nicht angegeben werden, dann wird -39 für --begin und 40 für --end verwendet.

Für jedes gesetzte Bit wird eine 1 und für jedes gelöschte Bit eine 0 ausgegeben. Jede Zeile wird mit einem Zeilenvorschub terminiert.

Folgender Aufruf gibt zum Beispiel die mittlere Spalte als Binärzahl zurück (der tr-Aufruf entfernt die Zeilenumbrüche):

cellular --rows=400 --begin=0 --end=1 | tr -d "\\n"

Liefert das Ergebnis

110111001100010110010011101011100111010101100001100101011010
101111110000111100010101110000010010110001110001101101101000
000010001111101110100111000111010111000001100100011001111001
111110000001111111011001011011100000101100011011000110001110
110110010101111111011010110110111101110010111011000100000000
001101110010110010111100100110000111110000001011011001111001
00001001111100000110100101100100101110101

Damit können sich schöne Zufallszahlen generieren lassen.

Sierpinski

Der Automat 16 erinnert an das berühmte Fraktal:

000000000000000000000000000000010000000000000000000000000000000
000000000000000000000000000000101000000000000000000000000000000
000000000000000000000000000001000100000000000000000000000000000
000000000000000000000000000010101010000000000000000000000000000
000000000000000000000000000100000001000000000000000000000000000
000000000000000000000000001010000010100000000000000000000000000
000000000000000000000000010001000100010000000000000000000000000
000000000000000000000000101010101010101000000000000000000000000
000000000000000000000001000000000000000100000000000000000000000
000000000000000000000010100000000000001010000000000000000000000
000000000000000000000100010000000000010001000000000000000000000
000000000000000000001010101000000000101010100000000000000000000
000000000000000000010000000100000001000000010000000000000000000
000000000000000000101000001010000010100000101000000000000000000
000000000000000001000100010001000100010001000100000000000000000
000000000000000010101010101010101010101010101010000000000000000
000000000000000100000000000000000000000000000001000000000000000
000000000000001010000000000000000000000000000010100000000000000
000000000000010001000000000000000000000000000100010000000000000
000000000000101010100000000000000000000000001010101000000000000
000000000001000000010000000000000000000000010000000100000000000
000000000010100000101000000000000000000000101000001010000000000
000000000100010001000100000000000000000001000100010001000000000
000000001010101010101010000000000000000010101010101010100000000
000000010000000000000001000000000000000100000000000000010000000
000000101000000000000010100000000000001010000000000000101000000
000001000100000000000100010000000000010001000000000001000100000
000010101010000000001010101000000000101010100000000010101010000
000100000001000000010000000100000001000000010000000100000001000
001010000010100000101000001010000010100000101000001010000010100
010001000100010001000100010001000100010001000100010001000100010
101010101010101010101010101010101010101010101010101010101010101

Dies wurde mit dem Aufruf

cellular --nr 18 --rows 31 --begin -31 --end 32

erzeugt.

Weitere Informationen zu zellulären Automaten finden sich zum Beispiel in A New Kind of Science.


Comments

Would you like to correct, expand or correct an entry? Please send an e-mail to timm@knp.de. I will gladly publish interesting contributions on this site.