ブログ

2次元セルオートマトン”ライフゲーム”を作る

「ライフゲーム」と呼ばれるものを作ってみます。これ自体を作る事は難しくはないです。

ライフゲーム(Wikipedia)
https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0
以下の説明は、このWikipediaの記事と殆ど同じなので、こっちのページを読んでる人は飛ばしてください。

ライフゲームとは

ライフゲーム (Conway’s Game of Life) は1970年にイギリスの数学者ジョン・ホートン・コンウェイ (John Horton Conway) が考案した生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームである。単純なルールでその模様の変化を楽しめるため、パズルの要素を持っている。生物集団においては、過疎でも過密でも個体の生存に適さないという個体群生態学的な側面を背景に持つ。セル・オートマトンのもっともよく知られた例でもある。

ライフゲームのルール
ライフゲームでは初期状態のみでその後の状態が決定される。碁盤のような格子があり、一つの格子はセル(細胞)と呼ばれる。各セルには8つの近傍のセルがある (ムーア近傍) 。各セルには「生」と「死」の2つの状態があり、あるセルの次のステップ(世代)の状態は周囲の8つのセルの今の世代における状態により決定される。

誕生
 死んでいるセルに隣接する生きたセルがちょうど3つあれば、次の世代が誕生する。
生存
 生きているセルに隣接する生きたセルが2つか3つならば、次の世代でも生存する。
過疎
 生きているセルに隣接する生きたセルが1つ以下ならば、過疎により死滅する。
過密
 生きているセルに隣接する生きたセルが4つ以上ならば、過密により死滅する。

誕生生存(維持)死(過疎)死(過密)

セルの変化の仕方によって、多くのパターンが存在します。
パターン

固定物体世代が進んでも同じ場所で形が変わらない。
振動子ある周期で同じ図形に戻る。
移動物体一定のパターンを繰り返しながら移動していく。
繁殖型マス目が無限であれば無限に増え続ける。

固定物体

ブロック蜂の巣ボート

振動子

ブリンカーヒキガエルビーコン時計

移動物体

グライダー軽量級宇宙船中量級宇宙船重量級宇宙船

繁殖型
グライダー銃

グライダー銃の動く様子(Bill Gosper’s Glider Gun in action—a variation of Conway’s Game of Life. This image was made by using Life32 v2.15 beta, by Johan G. Bontes.)


と言う事で、様々なパターンがあります。Wikipediaにもありますが、ライフゲームはチューリング完全なので、論理回路を作り、計算機を作ったりできます。


では、ライフゲームを作っていきます。わざわざ書く必要は無いかもしれませんが、
前述のライフゲームのルールをまとめると、

\(n回変化した時の碁盤上の位置(i,j)の値を{(x_{i,j})}_nとする。これは1(生)と0(死)の値を取るとする。\)
\(また、周囲8マスの値の和をf(x_{i,j})=x_{i-1,j-1} + x_{i,j-1} + x_{i+1,j-1} + x_{i-1,j} + x_{i+1,j} + x_{i-1,j+1} + x_{i,j+1} + x_{i+1,j+1}とする。\)
\((i){(x_{i,j})}_n=0の時\)
\( f((x_{i,j})_n) = 3の 時、{(x_{i,j})}_{n+1}=1\)
\( f((x_{i,j})_n) \neq 3の時、{(x_{i,j})}_{n+1}=0 \)

\((ii){(x_{i,j})}_n=1の時\)
\( f((x_{i,j})_n) = 2または3の時、(x_{i,j})_{n+1} = 1 \)
\( f((x_{i,j})_n) \leq 1 または 4 \leq f((x_{i,j})_n) の時、(x_{i,j})_{n+1} = 0 \)

となります。


【備考】
ウディタでライフゲームの簡易版を制作したものをウディコンに出しました。
よかったら遊んでみてください。

リンク:https://www.silversecond.com/WolfRPGEditor/Contest/entry.shtml
エントリー番号23です。

最後に参考になりそうな資料を置いておきます。
ライフゲームでチューリングマシン
https://www.ics.uci.edu/~welling/teaching/271fall09/Turing-Machine-Life.pdf
http://rendell-attic.org/gol/tm.htm
ライフゲームのソフトGolly
http://golly.sourceforge.net/
ライフゲームWiki
https://www.conwaylife.com/wiki/Main_Page

物体の斜方投射[空気抵抗]+α[ゲーム]


なるべく分かりやすく書くので、既習の方は飛ばしながら見てください。
\(重さm[kg]の物体がある。重力加速度をg[m/s^{2}]とする。\)
\( tの関数として、物体にかかるx軸方向の力をF_x(t)[N]、y軸方向の力をF_y(t)[N]とする。 \)
\( あくまでtの関数としたが、実装したい変数を含むものにすればいい? \)
\(物体の運動方程式は\)\[\ ma_x(t)=F_x(t) \] \[\ ma_y(t)=F_y(t) \]である。ゆえに、 \[\ a_x(t)=\frac{F_x(t)}{m} \] \[\ a_y(t)=\frac{F_y(t)}{m} \]
\(時刻tの速度v_x、v_yを求める(積分定数をCとする)。\)
\[ v_x=\int a_{x}(t)dt + C_x= \frac{1}{m}\int F_x(t)dt + C_x \]
\(t=0の時の物体のX軸方向の速度をv_{0x}とすると、\)
\[ v_{0x} = C_x \] \[ v_x = \frac{1}{m}\int F_x(t)dt + v_{0x} \]

\[ v_y=\int a_{y}(t)dt + C= \frac{1}{m}\int F_y(t)dt + C_y \]
\(同様に、t=0の時の物体のY軸方向の速度をv_{0y}とすると、\)
\[ v_{0y} = C_y \] \[ v_y = \frac{1}{m}\int F_y(t)dt + v_{0y} \]

\(次に時刻tの位置x,yを求める。\)
\[ x=\int v_{x}dt = \frac{1}{m}\int(\int F_x(t)dt)dt + v_{0x}t + C_x’\]
\[ y=\int v_{y}dt = \frac{1}{m}\int(\int F_y(t)dt)dt + v_{0y}t + C_y’\]
\( t=0の時の物体のX軸方向の座標をx_0とすると、 \)
\[ x_0 = C_x’ \] \[ x=\int v_{x}dt = \frac{1}{m}\int(\int F_x(t)dt)dt + v_{0x}t + x_0\]
\(同様に、t=0の時の物体のY軸方向の座標をy_0とすると、\)
\[ y= \frac{1}{m}\int(\int F_y(t)dt)dt + v_{0y}t + y_0\]

\(tに関わらず、F_x(t)=F_x,F_y(t)=F_yという一定の力が加わり続けた場合、\)
\[\ v_x= \frac{F_{x}t}{m} + v_{0x}\]
\[\ v_y= \frac{F_{y}t}{m} + v_{0y}\]

\[ x = \frac{F_{x}t^2}{2m} + v_{0x}t + x_0 \]
\[ y = \frac{F_{y}t^2}{2m} + v_{0y}t + y_0 \]

\(この物体をx軸方向に対して角度θの方向に投げる。\)
【空気抵抗がない場合】
\(物体は空中にあり、重力のみが加わる。また、空気抵抗が存在しないので、F_x=0,F_y=-mgである。上述の式に代入すると、\)
\[ a_x=0 \hspace{10pt} v_x = v_{0x} \hspace{10pt} x = v_{0x}t + x_0 \]
\[ a_y=-g \hspace{10pt} v_y = v_{0y} – gt \hspace{10pt} y = -\frac{gt^2}{2} + v_{0y}t + y_0 \]

【空気抵抗がある場合】
\(空気抵抗係数をkとすると、物体の運動方程式は、\)
\[ ma_x = -mkv_x \]
\[ ma_y = -mg – mkv_y \]
\[ a_x = \frac{dv_x}{dt} = -kv_x \]
\[ a_y = \frac{dv_y}{dt} = -g -kv_y \]
\[ \int \frac{1}{v_x}dv_x = -k\int dt + C \]
\[ \int \frac{1}{ v_y + \frac{g}{k}}dv_y= -k\int dt + C \]
\[ \log{v_x} = -kt + C \]
\[ \log({v_y + \frac{g}{k}}) = -kt + C \]
\( A,Bを定数として \)
\[ v_x=Ae^{-kt} \]
\[ v_y = Be^{-kt} -\frac{g}{k} \]
\( t=0の時,v_x=v_{0x},v_y=v_{0y}とすると \)
\[ v_{0x}=A \]
\[ v_{0y}=B-\frac{g}{k} \]
\[ v_x = v_{0x}e^{-kt} \]
\[ v_y = (v_{0y}+\frac{g}{k})e^{-kt}-\frac{g}{k}\]
\[ x = \int v_x dt + C = -k v_{0x}e^{-kt} + C \]
\[ x_0 = -kv_{0x} + C\] \[ C = x_0 + kv_{0x} \] \[ x = kv_{0x}(1-e^{-kt}) + x_0 \]
\[ y = \int v_y dt + C = -k(v_{0y} + \frac{g}{k})e^{-kt} – \frac{gt}{k} + C \]
\[ y_0 = -k(v_{0y} + \frac{g}{k}) + C \] \[ C = y_0 + k(v_{0y} + \frac{g}{k}) \]
\[ y = k(v_{0y} + \frac{g}{k})(1-e^{-kt}) – \frac{gt}{k} + y_0 \]
以上より、空気抵抗の有無の解析解が求められた。

【ゲーム】
次に、ゲームで物体を斜方投射する事について考える。
実際にゲームで物体を斜方投射するには、
【発射時に力を加えて、初速を決定する。または、単に初速を決定する。】
【初速は決まっていて、発射地点からマウスカーソルがある方向に発射する】
【発射後に予測される弾道のある点を、マウスカーソル等の位置として、初速度を決定する】
などが挙げられる。これらはゲームに合わせて実装するのが良いと思う。
ゲームによっては、これら以外で斜方投射をするものもあるはずなので、それはその都度実装する。

挙げた例に関して説明する。
【発射時に力を加えて、初速を決定する。または、単に初速を決定する。】
\(発射する角度θが与えられている場合は、角度θに加える力Fに対して、F_{0x}=F_0cosθ,F_{0y}=F_0sinθ\)
\(発射する角度θが与えられていない場合は、F_{0x},F_{0y}を決める。\)
\(単に、速度VからV_{0x}=V_0cosθ,V_0sinθを決定するか、V_{0x},V_{0y}を決定する。\)

【初速は決まっていて、発射地点からマウスカーソルがある方向に発射する】
初速の決め方は適当にしてもらって、マウスカーソルと発射地点の座標から初速度の角度を算出する。
\(例えば、物体を投げ出す起点(x_0,y_0)とマウス位置(X,Y)から、\) \[tanθ=\frac{Y-y_0}{X-x_0}\]
\[ θ=\arctan{\frac{Y-y_0}{X-x_0}} \]

【発射後に予測される弾道のある点を、マウスカーソル等の位置として、初速度を決定する】
これは、空気抵抗が無い場合にのみ書く。弾道は既に述べたように、
\[ x = v_{0x}t + x_0 \]
\[ y = -\frac{gt^2}{2} + v_{0y}t + y_0 \]
と表せられる。
速さは、
\[ v_x = v_{0x} \]
\[ v_y = v_{0y} – gt \]
である。
例えば、
\(マウスカーソルの位置をX,Yとする。v_xは一定だから、物体のy軸方向の速さがv_y=V_yとなる時 、\)
\(物体がマウスカーソルの位置(X,Y)に来るとすると、\)
【空気抵抗がない場合】
\[ V_y = v_{0y} – gt \]
\[ X = v_{0x}t + x \]
\[ Y = -\frac{gt^2}{2} + v_{0y}t + y_0 \]
\(求めたい変数がv_{0x},v_{0y},tの3つだから、3つの式から計算できます。\)
\[ t =\frac{\sqrt{V_y^2+2g(Y-y_0)}-V_y}{g}\]
\[ v_{0x} = \frac{g(X-x_0)}{\sqrt{V_y^2+2g(Y-y_0)}-V_y} \]
\[ v_{0y} = \sqrt{V_y^2 + 2g(Y-y_0)} \]

放物線の軌道はこんな感じですよね。

\(例えば、マウスカーソルの位置(X,Y)が、軌道の一番上に来る時、すなわち位置(X,Y)でV_y=0の時、\)
\[ t= \frac{\sqrt{2g(Y-y_0)}}{g} \]
\[ v_0x = \frac{g(X-x_0)}{\sqrt{2g(Y-y_0)}} \]
\[ v_{0y} = \sqrt{2g(Y-y_0)} \]
と表す事が出来る。
\( この例ではV_y = 0としましたが、それに限らず、例えばV_y = – V_{0y}とおくと、 \)
\( 物体が上方に飛んで、最初に発射した時と同じ高さに落ちた時の位置をマウスカーソルの位置とする事が出来る。 \)
\( 作りたいものに合わせてください。 \)
\( これで、v_{0x},v_{0y}が求まったので、軌道が求まりました。 \)
\( 予測軌道を描画するなり、好きな力を加えるなり、物体を飛ばす力に制限を付けて特徴の分かれた砲台でも作るなりしてください。 \)
\( 微分方程式の数値計算は別で書きます。 \)

ニュートン法(例:平方根の近似)

\(連続で1回微分可能なある関数f(x)について、x_0をf(x)=0の解に十分に近くに選ぶ。\)
点\((x_0,f(x_0))\)を通る接線の方程式は\[\ g(x)=f'(x_0)(x-x_0)+f(x_0) \]と表せる。
\(g(x)=0\)となる点\[\ x_1=x_0-\frac{f(x_0)}{f'(x_0)}\]
同様に\[\ x_{n+1}=x_n-\frac{f(x_n)}{f'(x_n)}\]
これを繰り返す事で、f(x)=0の近似解を得る。

\(例: \sqrt{a}の近似値を求める。\)
\(f(x)=x^2-a=0の解は、x=\pm\sqrt{a} \)
\[ f'(x)=2x \]
\[ x_{n+1} = x_n – \frac{f(x_n)}{f'(x_n)} = x_n – \frac{x_n^2 + a}{2x_n} = \frac{x_n^2 + a}{2x_n} \]
\(である。初期値x_0の値を、-\sqrt{a}に近い値にすると-\sqrt{a}に、\sqrt{a}に近い値にすると\sqrt{a}に収束する。 \)