ライフゲーム（Conway's Game of Life）の簡易実装例

**[ライフゲーム](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0)（[Conway's Game of Life](https://en.wikipedia.org/wiki/Conway%27s_Game_of_Life)）** は，学術的な側面以外にも，視覚的・パズル的に楽しめる要素が多いことから，一般的にもよく知られている **[セル・オートマトン](https://ja.wikipedia.org/wiki/%E3%82%BB%E3%83%AB%E3%83%BB%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3)** です．オリジナルのライフゲームは，次のルールに沿っています．

- 初期状態として，生死の二状態を表すセルが二次元状に並んでいる．
- あるセルの次のステップ（世代）の生死状態は，現在の周囲8セルの生死状態に従う．

|現在|次世代|
|:-:|:-:|
|死|周囲にちょうど3つの生のセルがあれば生に（誕生），それ以外は死のまま|
|生|周囲に2つか3つの生のセルがあれば生のまま（生存），それ以外は死（死滅）|

1970年の発表当初よりコンピュータのプログラムとして作成・実行され続けていますが，構成やルールが比較的単純だったり，興味深い初期パターンの発見の方が注視されていたりするせいか，**プログラムをどのように作るかといったことにはあまり言及されません**．

この記事では，文字端末での表示を想定してプログラムを簡略化することで，**どのような計算手順（アルゴリズム）で世代交代を処理するか**を中心としたコードについて述べています．表示については次の通りです．

・文字端末制御には，画面クリアのコマンド（UNIXシェルの`clear`，Windowsコマンドプロンプトの`cls`）のみを用いる．
・実装には（とりあえず）Pythonを用い，画面クリアは`os.system('コマンド名')`で行う．

このため，今回の記事から，**Python以外のプログラミング言語への書き直しや，グラフィック機能を用いた拡張も容易**かと思います．

【参考動画】（記事のプログラムコードとは異なります）

https://youtu.be/lOsjwsBxQJU

# セルの設定と基本操作

まず，二次元セルの大きさを設定します．このあたりは，実行時の引数や設定ファイルに従うこともあります．なお，プログラムコードの単純化のため，二次元セル空間を指す変数およびこの2変数については，大域変数としています[^1]．
[^1]: プログラミング言語によっては，この3変数をフィールド，その他の関数や処理をメソッドとした（オブジェクト指向の）クラス定義とした方がわかりやすいかもしれません．

```py
xsize, ysize = 20, 10
```

次に，二次元セルの初期化処理を定義します．実装環境によってどのように構成しても良いのですが，ここでは，一次元配列（リスト型）で構成することにします．また，後述の周囲判定の簡便化のため，生死は`0`と`1`の整数値で表現し，初期値は全て`0`（死）としています．

```py
def cinitialize():
    return [0] * (xsize * ysize)
```

その後，二次元セルの座標(x,y)（左上(0,0)，右下(`xsize`,`ysize`)）に値をセットしたり取り出したりする処理を定義します．なお，二次元セル空間を指す大域変数名は`cells`としています．

```py
def cset(x, y, value):
    cells[x + y * xsize] = value

def cget(x, y):
    return cells[x + y * xsize]
```

更に，二次元セルの中身を表示する処理を追加します．ここでは，生`1`ならば`*`を，死`0`ならば`_`を表示することとします．また，セルの表示の前に画面をクリアさせます（今回は，Windowsコマンドプロンプトの`cls`を呼び出しています）．

```py
from os import system

def cdisplay():
    system('cls')
    for y in range(ysize):
        for x in range(xsize):
            v = '*' if cget(x, y) else '_'
            print(v, end='')
        print()
```

ここまでできれば，二次元セルのテストが可能です．横20，縦10の二次元セルを生成し，座標(3,2)（左上から右に4番目，下に3番目）に生`1`をセットして表示させてみます．

```py
cells = cinitialize()
cset(3, 2, 1)
cdisplay()
```
```
____________________
____________________
___*________________
____________________
____________________
____________________
____________________
____________________
____________________
____________________
```

手動セットではなく，初期状態として生死をランダムにセットして確認してみます．ランダム値からの開始のみを想定するならば，二次元セルの初期化処理で行っても良いかもしれません．

```py
from random import randint

cells = cinitialize()
#cset(3, 2, 1)
for y in range(ysize):
    for x in range(xsize):
        cset(x, y, randint(0,1))
cdisplay()
```
```
_*_*_***__******___*
________*_*____*****
**___***___**_*_*___
_*_**********___*_*_
______***__**_*_*___
**___*__**____**____
***_*_****___**_*___
**_**___*_*_____***_
____**_*__*_***_***_
**_*******____*__*_*
```

ここまでの内容をまとめたコードは次の通りです．
```py:CGoL_1.0.py
from os import system
from random import randint

xsize, ysize = 20, 10

def cinitialize():
    return [0] * (xsize * ysize)

def cset(x, y, value):
    cells[x + y * xsize] = value

def cget(x, y):
    return cells[x + y * xsize]

def cdisplay():
    system('cls')
    for y in range(ysize):
        for x in range(xsize):
            v = '*' if cget(x, y) else '_'
            print(v, end='')
        print()

cells = cinitialize()
#cset(3, 2, 1)
for y in range(ysize):
    for x in range(xsize):
        cset(x, y, randint(0,1))

cdisplay()
```

# 周囲判定

今回の記事の中心である，周囲判定の処理を考えます．ある座標(x,y)にあるセルの周囲の生死状態を

|c00|c10|c20|
|:-:|:-:|:-:|
|**c01**|   |**c21**|
|**c02**|**c12**|**c22**|

とすると，今回は生死は`1`,`0`で表現していますので，周囲の生の数を求めるコードとして次が考えられます．

```py
def neighbor(x, y):
    c00, c10, c20 = cget(x-1, y-1), cget(x  , y-1), cget(x+1, y-1)
    c01,      c21 = cget(x-1, y  ),                 cget(x+1, y  )
    c02, c12, c22 = cget(x-1, y+1), cget(x  , y+1), cget(x+1, y+1)
    return c00 + c10 + c20 + c01 + c21 + c02 + c12 + c22
```

次のように確認すると，座標(1,1)（左上から右に2番目，下に2番目のセルの周囲の生の数）が得られているように見えます．

```py
cells = cinitialize()

for y in range(ysize):
    for x in range(xsize):
        cset(x, y, randint(0,1))

cdisplay()
print(neighbor(1, 1))
```
```
***___*_*__*_**___**
__*_*_*_**_*_***_***
**_***_***_******__*
**__*_*_***__*_*_*__
*___***_*_****___*_*
*__*_*******_***____
*_____**_*_*__*_***_
_**___*_*_*__**_*_**
__**__*_**___*_*****
_**_**__*******_*___
6
```

ですが，この周囲の生の数を求めるコードは次と同じです．

```py
def neighbor(x, y):
    c00, c10, c20 = cget(x-1, y-1), cget(x+0, y-1), cget(x+1, y-1)
    c01,      c21 = cget(x-1, y+0),                 cget(x+1, y+0)
    c02, c12, c22 = cget(x-1, y+1), cget(x+0, y+1), cget(x+1, y+1)
    return c00 + c10 + c20 + c01 + c21 + c02 + c12 + c22
```

すなわち，中央セルを除いた，x，yそれぞれに-1,0,1を加えた8通りの組合せでセルを参照し，その生の合計数を求めれば良いことになります．このため，繰り返し処理で次のように書き換えることができます．

```py
def neighbor(x, y):
    #c00, c10, c20 = cget(x-1, y-1), cget(x+0, y-1), cget(x+1, y-1)
    #c01,      c21 = cget(x-1, y+0),                 cget(x+1, y+0)
    #c02, c12, c22 = cget(x-1, y+1), cget(x+0, y+1), cget(x+1, y+1)
    #return c00 + c10 + c20 + c01 + c21 + c02 + c12 + c22
    w = 0
    for xd in [-1,0,1]:
        for yd in [-1,0,1]:
            w += 0 if (xd, yd) == (0, 0) else cget(x + xd, y + yd)
    return w
```

また，中央セルが二次元セルの境界にある場合，周囲セルの一部が二次元セルの外となってしまうため，上記では参照することができません．ここでは，**セル空間全体が上下左右でつながっている**とし，x,yがそれぞれ-1となるならばx,yのそれぞれ最大座標の値に，x,yがそれぞれ最大座標+1になるならば0となるようにします．これは，余りを求める`%`で計算可能です．
```py
def neighbor(x, y):
    w = 0
    for xd in [-1,0,1]:
        for yd in [-1,0,1]:
            xs, ys = (x + xd) % xsize, (y + yd) % ysize
            w += 0 if (xd, yd) == (0, 0) else cget(xs , ys)
    return w
```
※注：プログラミング言語によっては **`%`の定義がPythonと異なり**，たとえば，Pythonでは`-1 % 20`が`19`となる（$modulo$）ところ，別の言語では`-1`のまま（$remainder$）となります（後者のプログラミング言語には，CとJavaScriptがあります）．この場合は，上記コードでいう`xs`や`ys`について，二次元セルの大きさ`xsize`，`ysize`を更に加算して余り（$remainder$）を求める必要があります．

あらためて，座標(0,0)と座標(xの大きさ,yの大きさ)のそれぞれのセルの周囲の生の数を求めてみます．同じ値となることがわかります．
```py
cdisplay()
print(neighbor(0, 0))
print(neighbor(xsize, ysize))
```
```
*_*_***_*__**_******
__***_**__*_***___*_
___*_**___*****_*_*_
*__*_*_*******__****
***_*__**_***__****_
___*_*****___*__*___
___*___*_*__****__**
____***_*__*_****_*_
_____*_****_***_*_*_
*__*__***__**_****_*
3
3
```
周囲の生の数を求めることができるようになれば，次の世代を生成することができます．
```py
def ngenerate():
    r = []
    for y in range(ysize):
        for x in range(xsize):
            w = neighbor(x, y)
            if cget(x, y):
                r += [1 if w in [2,3] else 0]
            else:
                r += [1 if w == 3 else 0]
    return r
```
試しに表示部分を修正して，初期状態と次世代のみを表示させてみます．
```py
def cdisplay():
    #system('cls')
    print('==(cells)==')
    for y in range(ysize):
        for x in range(xsize):
            v = '*' if cget(x, y) else '_'
            print(v, end='')
        print()

cdisplay()
cells = ngenerate()
cdisplay()
```
```
==(cells)==
__**___***_*_**__*_*
*_**___*_____*****_*
*_*_**___*____*_*_*_
****__**_*****_****_
_*_*_*_*******_***__
**__**_*_______*__*_
__*_____**_*_*****_*
_***____***__*___*__
___*____****_*****__
*****_*_********__**
==(cells)==
______*____*_____*__
*_____**_**_*_______
____**_*_*_*________
*______*__________*_
___*_*_______*______
**_***_*__________**
____*__*____**_*_*_*
_*_*___*____________
_________________*_*
**__*______________*
```

ここまでの内容をまとめたコードは次の通りです．
```py:CGoL_2.0.py
from os import system
from random import randint

xsize, ysize = 20, 10

def cinitialize():
    return [0] * (xsize * ysize)

def cset( x, y, value):
    cells[x + y * xsize] = value

def cget(x, y):
    return cells[x + y * xsize]

def cdisplay():
    #system('cls')
    print('==(cells)==')
    for y in range(ysize):
        for x in range(xsize):
            v = '*' if cget(x, y) else '_'
            print(v, end='')
        print()

def neighbor(x, y):
    w = 0
    for xd in [-1,0,1]:
        for yd in [-1,0,1]:
            xs, ys = (x + xd) % xsize, (y + yd) % ysize
            w += 0 if (xd, yd) == (0, 0) else cget(xs , ys)
    return w

def ngenerate():
    r = []
    for y in range(ysize):
        for x in range(xsize):
            w = neighbor(x, y)
            if cget(x, y):
                r += [1 if w in [2,3] else 0]
            else:
                r += [1 if w == 3 else 0]
    return r

cells = cinitialize()

for y in range(ysize):
    for x in range(xsize):
        cset(x, y, randint(0,1))

cdisplay()
cells = ngenerate()
cdisplay()
```

# ループ処理

前節までできあがれば，あとは，一定もしくは無限のループで世代交代を繰り返せば良いことになります．ここでは，ランダムな初期状態から千回の世代交代を繰り返すものとして構成します．ただし，このままでは表示書き換えが速すぎるため，0.2秒ごとに世代交代を行うようにします．実行環境によっては，それでも書き換えが速くチラツキが大きくなるため，遅延時間をより大きくした方が良いかもしれません．
```py
from time import sleep

for _ in range(1000):
    cdisplay()
    cells = ngenerate()
    sleep(0.2)
```
![ezgif.com-gif-maker.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/672267/3ca068dc-7a72-e36e-196a-92a264349c7f.gif)
これで一応は完成です．最終版のコードを次に掲載します．
```py:CGoL_3.0.py
from os import system
from random import randint
from time import sleep

xsize, ysize = 20, 10

def cinitialize():
    return [0] * (xsize * ysize)

def cset(x, y, value):
    cells[x + y * xsize] = value

def cget(x, y):
    return cells[x + y * xsize]

def cdisplay():
    system('cls')
    for y in range(ysize):
        for x in range(xsize):
            v = '*' if cget(x, y) else '_'
            print(v, end='')
        print()

def neighbor(x, y):
    w = 0
    for xd in [-1,0,1]:
        for yd in [-1,0,1]:
            xs, ys = (x + xd) % xsize, (y + yd) % ysize
            w += 0 if (xd, yd) == (0, 0) else cget(xs , ys)
    return w

def ngenerate():
    r = []
    for y in range(ysize):
        for x in range(xsize):
            w = neighbor(x, y)
            if cget(x, y):
                r += [1 if w in [2,3] else 0]
            else:
                r += [1 if w == 3 else 0]
    return r

cells = cinitialize()

for y in range(ysize):
    for x in range(xsize):
        cset(x, y, randint(0,1))

for _ in range(1000):
    cdisplay()
    cells = ngenerate()
    sleep(0.2)
```

# 備考

## 記事に関する補足
- そのうち，[LifeWiki](https://conwaylife.com/wiki/Category:Patterns)でよく用いられている[RLE形式のパターンファイル](https://qiita.com/tadashi9e/items/b2ff031dd17172d5bb39#rle-rle)を初期状態とするコードを掲載するかもしれませんが，しないかもしれません．本業の進捗次第…．

## 更新履歴
- 2023-02-05：初版公開，`xsize`と`ysize`に加えて`cells`も大域変数に変更