[C#] 1次元セルオートマトンの実装

1次元セルオートマトンとは

• セル・オートマトン – Wikipedia

ライフゲームに代表されるような2次元のセルオートマトンは、2次元平面上にセルを構成します。一方、1次元セルオートマトンでは1次元の線上セルを並べてセルを構成します。

セルは2つの状態(1 or 0)をとることができ、隣接するセルの状態と合わせて次世代の状態を決定します。

隣接するセルを含めた3つのセルをまとめて近傍といいます。2つの状態を持ちうるセル3つで近傍を構成するため、1つの近傍の取りうるパターンは次の8種類(2³=8)となります。

ルール30セル・オートマトン

現在の状態から次世代の状態を決定するルールを次の表のように定義します。このルールは「ルール30」と呼ばれるものです。あとでルールは改めて紹介します。

例えば、次のようにセルが並ぶとき、強調されたセルに注目すると、上の表から次世代の状態は 0 になります。

0 1 1 0 1 1 0 0 0 1 0

ある状態のセルから世代を経るごとに、どのような変遷をたどるのかを見て楽しみます。そのために1次元セルオートマトンを実装してみます。

ルールについて

「ルール30・ルール90・ルール110」が有名なようです。ルール名の意味は、次世代の状態を並べてできる2進数を10進数に変換した値に由来します。

例えばルール30は、次世代の状態を並べると、上の表から "00011110" となります。(000の次世代の状態が1桁目に来ます。)

ルール90、ルール110の次世代の状態は次の表のようになります。

ルール90

ルール110

C# で 1次元セルオートマトン

実装方針

C# を使って1次元セルオートマトンを実装します。セルの状態は真偽値(bool)で表現し、1次元なので配列ですべてのセルを保持します。

セルは無限に存在していると仮定しますが、実装上は有限にしないといけないので、両端は常に 0 となることとします。

ライフゲームだと世代ごとの変遷をアニメーションして楽しみますが、1次元の場合は上から下にずらっと描画します。

実装したコード

class CellularAutomaton
{
    public bool[] Cells { get; private set; }
    public bool[] NextCells { get; private set; }
    public int Size { get; private set; }
    public Rule Rule { get; private set; }
    public Dictionary<string, bool> RuleDictionary { get; private set; }

    public CellularAutomaton(int size, Rule rule)
    {
        this.Size = size;
        this.Rule = rule;

        // 次世代の状態を決定するルール
        this.RuleDictionary = CreateRuleDictionary(this.Rule);
    }

    // 開始(セルの状態を初期化)
    public void Start()
    {
        // 指定サイズ+2分のセル用配列を生成(全部false)
        // 両端の状態は常にfalseとする
        this.Cells = Enumerable.Repeat<bool>(false, this.Size + 2).ToArray();
        this.NextCells = Enumerable.Repeat<bool>(false, this.Size + 2).ToArray();

        // 中央のセルだけ true に初期化
        this.Cells[this.Size / 2] = true;
    }

    // セルを次世代に進める
    public void Next()
    {
        // 両端を無視してループ
        for (int i = 1; i < this.Cells.Length - 2; i++)
        {
            // 前のセルの値と次のセルの値を含めた近傍を文字列で作成
            var neighborhood = "";
            neighborhood += this.Cells[i - 1] ? "1" : "0";
            neighborhood += this.Cells[i    ] ? "1" : "0";
            neighborhood += this.Cells[i + 1] ? "1" : "0";

            // 次世代のセルの状態を判定し、格納
            var nextStatus = this.RuleDictionary[neighborhood];
            this.NextCells[i] = nextStatus;
        }

        // 全てのセルの次世代を判定し終えたので現世代配列にコピー
        this.NextCells.CopyTo(this.Cells, 0);
    }

    // ルールに対応した辞書を生成
    private Dictionary<string, bool> CreateRuleDictionary(Rule rule)
    {
        var dict = new Dictionary<string, bool>();
        switch (rule)
        {
            case Rule.Cell030:
                dict["000"] = false;
                dict["001"] = true;
                dict["010"] = true;
                dict["011"] = true;
                dict["100"] = true;
                dict["101"] = false;
                dict["110"] = false;
                dict["111"] = false;
                break;
            case Rule.Cell090:
                dict["000"] = false;
                dict["001"] = true;
                dict["010"] = false;
                dict["011"] = true;
                dict["100"] = true;
                dict["101"] = false;
                dict["110"] = true;
                dict["111"] = false;
                break;
            case Rule.Cell110:
                dict["000"] = false;
                dict["001"] = true;
                dict["010"] = true;
                dict["011"] = true;
                dict["100"] = false;
                dict["101"] = true;
                dict["110"] = true;
                dict["111"] = false;
                break;
        }
        return dict;
    }
}

enum Rule
{
    Cell030,
    Cell090,
    Cell110,
}

CellularAutomaton クラス

CellularAutomaton クラスは、すべてのセルの状態をbool型配列で保持します。現在のセルの状態と次世代の状態をそれぞれ別の配列で保持します。

コンストラクタで全セルの数と使うルールを初期化します。また、指定されたルールに基づき、次世代の状態を判定するための辞書を作成します。

CreateRuleDictionary メソッド

CreateRuleDictionary メソッドは、ルールに対応した辞書を生成します。辞書は近傍を文字列にしたものをキー、次世代の状態を値とします。近傍は8パターンあるので8つの要素を持つ辞書となります。

Start メソッド

Start メソッドは1世代目のセルの状態でセルの配列を初期化します。大きさは指定されたサイズ+2とします。これは両端を常にfalse固定として扱うためです。

全てのセルをfalseにすると何も発生しないので、中央のセルだけをtrueにしています。この1つのセルからどのように変遷していくかを見てみます。

Next メソッド

Next メソッドは、次世代に進める処理です。

現在のセルを両端を除いて走査し、両隣のセルを見て近傍の文字列(3文字)を作成します。作成した文字列をキーに次世代の状態を辞書から取得します。

現在のセル配列をそのまま更新すると、次のセルの判定に影響してしまうので、次世代用のセル配列の状態を更新します。最後のセルまで更新したら、次世代のセル配列の値を今世代のセル配列として値をコピーします。

コンソールに表示してみる

最後に、CellularAutomaton クラスを使って得られるシミュレーション結果を、コンソールに表示してみます。ルール90が規則的な並びになりわかりやすいです。

class Program
{
    static void Main(string[] args)
    {
        // セルの数を75とする
        var size = 75;

        // ルール90で初期化
        var ca = new CellularAutomaton(size, Rule.Cell090);
        ca.Start();

        // 30世代分のシミュレーションを行う
        var maxAge = 30;
        for (int i = 0; i < maxAge; i++)
        {
            var sb = new StringBuilder();
            foreach (var b in ca.Cells)
            {
                sb.Append(b ? "*" : " ");
            }
            Console.WriteLine(sb.ToString());

            // 次世代へ進む
            ca.Next();
        }
        Console.ReadLine();
    }
}

75個のセルで30世代分動かします。セルの状態が 1(True)の場合にはアスタリスク(*)で表示し、0(False)の場合には空文字を表示します。

結果は次のようになります。

                                     *
                                    * *
                                   *   *
                                  * * * *
                                 *       *
                                * *     * *
                               *   *   *   *
                              * * * * * * * *
                             *               *
                            * *             * *
                           *   *           *   *
                          * * * *         * * * *
                         *       *       *       *
                        * *     * *     * *     * *
                       *   *   *   *   *   *   *   *
                      * * * * * * * * * * * * * * * *
                     *                               *
                    * *                             * *
                   *   *                           *   *
                  * * * *                         * * * *
                 *       *                       *       *
                * *     * *                     * *     * *
               *   *   *   *                   *   *   *   *
              * * * * * * * *                 * * * * * * * *
             *               *               *               *
            * *             * *             * *             * *
           *   *           *   *           *   *           *   *
          * * * *         * * * *         * * * *         * * * *
         *       *       *       *       *       *       *       *
        * *     * *     * *     * *     * *     * *     * *     * *

きれいな図形が浮かび上がっているのが確認できます。不思議です。

頂点に当たるのが1世代目として初期化した真ん中のセルです。世代を経るごとに数を増減しながら模様を形成しているのわかります。

もっと数を増やすには表示させる方法を考える必要がありそうです。

以上。

参考URL

• セル・オートマトン – Wikipedia