HOME

Python

download

Set を用いたライフゲームの実装

1. 初めに

• 誕生: 死んでいるセルに３つの生きたセルが隣接していれば、そのセルは次の世代で生きる。
• 生存: 生きているセルに２つあるいは３つの生きたセルが隣接していれば、そのセルは次の世代でも生きる。
• その他：その他は次の世代で死ぬ。

ライフゲームプログラムは、以前、はじめての Python のサンプルプログラムとして書いたのですが、 いまいちだったので、いつか改良版を書こうと思っていました。 Clojure Programming に集合を用いた実装が載っていたので、 それを参考にして、今回のスクリプトを書きました。

今回のは、生きているセルとその近傍だけを計算対象にするので、無駄な計算を省いています。 (ライフゲームのセルは通常 2/3 以上が死んでいるのと、次の世代で生きる可能性があるのは現在生きているセルとその近傍にあるセルだけなので、 生きているセルとその近傍についてのみ次世代での状態を計算したほうが能率的です。) また、計算時間がボードのサイズに依存しないので、大きなボード上で描画することができますし、 表示とセルが分離しているので縁の処理も自然になっています。

2. ライフゲーム計算スクリプト

[code 1]

001:   #!python
002:   '''life game console virsion'''
003:   
004:   from collections import namedtuple
005:   
006:   Cell = namedtuple('Cell', 'x y')
007:   
008:   def neighbors(c):
009:       '''return a set of adjacent cells to c'''
010:       return {Cell(c.x+dx, c.y+dy) for dx in (-1,0,1) for dy in (-1,0,1) if (dx,dy)!=(0,0)}
011:   
012:   
013:   def survive(c,cs):
014:       '''see if the cell will survive in the next generation'''
015:       nadj=len(neighbors(c) & cs)
016:       return nadj==3 or (c in cs and nadj==2)
017:   
018:   
019:   def include_neighbors(cs):
020:       '''return union of cs and the neighbors'''
021:       cs1=cs.copy()
022:       for c in cs:
023:           cs1.update(neighbors(c))
024:       return cs1
025:   
026:   
027:   def generate(cs, f=lambda c:True):
028:       '''return the set of living cells in the  next generation, f is an additional constraint'''
029:       return { c for c in include_neighbors(cs) if survive(c,cs) and f(c) }
030:   
031:   
032:   def play(cs, board_size=5, n_rep=5):
033:       '''console version of life game'''
034:       def show(_cs):
035:           for y in range(-board_size, board_size):
036:               print( ''.join('*' if Cell(x,y) in _cs else ' ' for x in range(-board_size, board_size)))
037:   
038:       def _iter(n, _cs):
039:           show(_cs)
040:           if n<n_rep:
041:               _iter(n+1, generate(_cs))
042:   
043:       _iter(0, cs)
044:   
045:   
046:   if __name__=='__main__':
047:       play({Cell(-1,0), Cell(0,0),Cell(1,0)})

Cell (6 行目)

セルは、tuple で表してもいいのですが、namedtuple で表すことにします。こうすると cell.x, cell.y などと書けるので スクリプトが読みやすくなります。また、セルの状態は、セルが、生きたセルの集合に属するかどうかで判定します。従て、セルには生死の状態を持たせていません。

neighbors(c) (8--11 行目)

セル c に隣接するセルの集合を返す関数です。x 座標あるいは y 座標の差が ± 1 のセルの集合を返します。

survive(c, cs) (13--16 行目)

セル c が次の世代で誕生するか生き残るかを判定します。ここで cs は生きているセルの集合です。
セル c の周りの生きているセルの個数 (nadj) は、15 行目にあるようにセル c に隣接するセルの集合と生きているセルの集合の積の要素数であらわされます。 nadj が 3のときは、無条件で生き、nadj が 2 のときは、自分が生きている (自分が生きているセルの集合の要素である) とき、次の世代でも生きます。

include_neighbors(cs) (19--24 行目)

生きているセルと、それに隣接するセル、すなわち次世代に生きている可能性のあるセルの集合です。

generate(cs, f=lambda c:True)

生きているセルの集合 cs の次の世代の生きているセルの集合を返します。 基本的には、include_neighbors(cs) のセルについて、survive(c) が True を返すものの集合を返します。 追加の制約 f(c) は盤から外れたセルの計算を打ち切るためなどに使います。

play(cs, board_size=5, n_rep=5) (32--43 行目)

コマンドライン版のライフゲームです。

1. 生きているセルとその近傍だけを計算するので、処理速度が速くなります。
2. 計算と表示とを分離しやすくなり、盤の端の影響を小さくすることができます。
3. 計算する部分 (Cell, neighbors, survive, include_neighbors, generate) は 25 行で実装することができます。

3. GUI

[code 2]

001:   #!python3
002:   
003:   '''
004:   Life game tkinter version.
005:   
006:   Usage:
007:   mouse click: toggle a cell, living<->dead (reset state only)
008:   space: to start, stop, and reset
009:   l    : load a set of living cells from a file (reset state only)
010:   s    : save the set of living cells to a file (reset state only)
011:   c    : clear, there are no living cells  after this command (reset state only)
012:   '''
013:   
014:   import tkinter as tk
015:   from tkinter.filedialog import askopenfile, asksaveasfile
016:   import pickle
017:   
018:   import life
019:   
020:   def in_range(c,min_,max_):
021:       '''check if the cell c is in the square specified by min_ and max_'''
022:       return all(min_<=z<=max_ for z in (c.x,c.y))
023:   
024:   
025:   class Board (tk.Canvas):
026:       '''The board where cells are on.'''
027:   
028:       SIZE=800                  # board size in pixel
029:       CELL_SIZE=8               # cell size in pixel
030:       B_SIZE=SIZE//CELL_SIZE    # number of cells in each side
031:       MARGIN=10                 # the width of the band outside of the board, where lives are still living
032:       RESET,START,STOP=0,1,2    # cyclic states
033:       TAG_FORMAT='{}.{}'           # format of tag
034:       SLEEP=250                 # in ms
035:   
036:       def __init__(self, master=None):
037:           '''create board, bind methods to keys'''
038:           tk.Canvas.__init__(self, master, bg='white', width=self.SIZE, height=self.SIZE)
039:           self.master.title('Life Game')
040:           self.livings=set()  # the set of living cells
041:           self.state=self.RESET # the state
042:           self.bind('<1>', self.toggle)
043:           for k, a in [('<space>','proceed'),
044:                        ('<KeyPress-l>','load'),
045:                        ('<KeyPress-s>','save'),
046:                        ('<KeyPress-c>','clear')]:
047:               self.master.bind(k, getattr(self,a))
048:           self.pack()
049:   
050:       def proceed(self, e):
051:           '''proceed the state'''
052:           self.state=(self.state+1) % 3
053:           if self.state==self.START:
054:               self.play(self.livings)
055:           elif self.state==self.RESET:
056:               self.show_lives(self.livings)
057:   
058:       def show_each(self, x, y):
059:           '''draw a black square'''
060:           self.create_rectangle( *[z*self.CELL_SIZE for z in (x,y,x+1,y+1)],
061:                                   fill='black', tags=self.TAG_FORMAT.format(x,y))
062:   
063:       def show_lives(self, cs):
064:           '''show living cells'''
065:           self.delete(tk.ALL)
066:           for c in cs:
067:               if in_range(c, 0, self.B_SIZE):
068:                   self.show_each(c.x, c.y)
069:   
070:       def toggle(self,e):
071:           '''living<->dead'''
072:           if self.state == self.RESET:
073:               c=life.Cell(e.x//self.CELL_SIZE, e.y//self.CELL_SIZE)
074:               if c in self.livings:
075:                   self.livings.remove(c)
076:                   self.delete(self.TAG_FORMAT.format(c.x,c.y))
077:               else:
078:                   self.livings.add(c)
079:                   self.show_each(c.x,c.y)
080:   
081:       def play(self, cs):
082:           '''play life game'''
083:   
084:           def keep_watching(_c):
085:               return in_range(_c,-self.MARGIN, self.B_SIZE+self.MARGIN)
086:   
087:           self.show_lives(cs)
088:           if self.state==self.START:
089:               self.after(self.SLEEP, lambda : self.play(life.generate(cs, keep_watching)))
090:   
091:   
092:   
093:       def load(self,_e):
094:           '''load saved cells'''
095:           if self.state == self.RESET:
096:               with askopenfile(mode='rb') as f:
097:                   self.livings=pickle.load(f)
098:               self.show_lives(self.livings)
099:   
100:       def save(self,_e):
101:           '''save cells'''
102:           if self.state == self.RESET:
103:               with asksaveasfile(mode='wb') as f:
104:                   pickle.dump(self.livings, f)
105:   
106:       def clear(self,_e):
107:           '''clear the board'''
108:           if self.state == self.RESET:
109:               self.delete(tk.ALL)
110:               self.livings.clear()
111:   
112:   
113:   if __name__=='__main__':
114:       b=Board()
115:       b.mainloop()

3.1. 使い方

ライフの初期状態 (図2) が決まったら、スペースキーを押下するとシュミレーションが始まります (図3)。スペースキーを押下すると、開始、終了、初期状態、が循環します。

まとめると、使えるコマンドは以下のようになります。

コマンド	挙動
マウスクリック	盤面のセルの生死の切り替え
スペースキー	開始、終了、リセット の切り替え。これらの3つの状態は循環する。
l キー	ライフの配置をファイルからロードする。
s キー	盤面上のライフの配置をファイルに保存する。
c キー	盤面をクリアする。

図 1: スクリプトを起動したところ。真っ白なキャンバスが表示される。

図 2: 生きているセルを配置したところ。マウスクリックでセルの生死を切り替える。

図 3: シミュレーションを行っているところ。

3.2. 簡単な説明

in_range(c,min_,max_) (20--22 行目)

セル c の c.x, x.y がともに min_, max_ の範囲にあるか調べます。

Board (25--110 行目)

セルを配置する盤面のクラスです。tkinter.Canvas のサブクラスです。以下の定数を持ちます。

SIZE

ピクセル単位でのボードの大きさです。

CELL_SIZE

ピクセル単位でのセルの大きさです。

B_SIZE

ボードの一辺にあるセルの個数です。

MARGIN

表示する範囲は B_SIZE の正方形だが、計算は 一辺が B_SIZE+2*MARGIN の範囲で行う。

RESET, START, STOP

ボードの３つの状態です。循環します。

TAG_FORMAT

生きたセル (黒い正方形) に着けるタグの書式です。

SLEEP

(ms) この時間待って次の世代を計算します。

__init__(self, master=None) (36--48 行目)

以下のことを行います。

• tkinter.Canvas として初期化します。
• 盤の状態 (self.state) を初期状態 (self.RESET) にします。
• 生きたセルの集合 (self.lives) を空集合にします。
• イベントとメソッドをバインドします。

proceed(self, e) (50--56行目)

スペースキーにバインドされています。ボードの状態を1つ進めます。 ボードの状態が self.START になれば、シュミレーションを開始します。また、 ボードの状態が self.RESET になれば、元のライフの配置を表示します。

show_each(self, x, y) (58--61 行目)

個々の生きているセルを黒い正方形として表示します。

show_lives(self, cs) (63--68 行目)

盤上にある生きているセルすべてを表示します。

toggle(self,e) (70--79 行目)

セルの生死を切り替えます。マウスクリックにバインドされています。

play(self, cs) (81--89 行目)

シュミレーションを行います。cs は生きているセルの集合です。 ボードが実行状態にあるときは self.SLEEP ミリ秒待機して、次の世代を計算して表示します。 図 4 に示すようにボードに表示されないセルも MARGIN の幅にあるものは計算を続けます。

load(self,_e) (93--98 行目)

生きたセルの集合をファイルからロードします。

save(self,_e) (100--104 行目)

盤上にある生きたセルの集合をファイルにセーブします。

clear(self,_e) (106--110 行目)

盤上のセルをクリアします。

図 4: シュミレーションを行う範囲。表示する範囲は内側の正方形だが、シミュレーションは外側の正方形の内側で行う。

4. 終わりに

HOME

Python

download