この課題は「チャレンジャー向けのおまけ課題」なので,提出しなくても成績評価には基本的に影響しません.但し,ちゃんと取り組んでクリア出来た(と判断できた)人に対しては少しプラスアルファがあります.
但し,採点基準はかなり高く引き上げますので,コンパイル出来ないようなものや動作仕様を満たしていないようなものは評価対象にしません.尚,誰かの人まねだけで「なんとかプラスを....」という下心見え見えの行為をする人はいないと思いますが,万が一いた場合には「思いっきり痛い目」を見てもらいます.
そのため,挑戦したいと考える人は,自分の作成したソースプログラムをたとえ一部でも他人に見せないようにしましょう.他人に見せた結果,プログラムがそっくりになってしまって「人まねをしたと誤解される」危険性があります.
自然現象や社会現象などを数学モデル化し,コンピュ−タ上の数値計算を用いて,その現象の振る舞いや結果などを解析する手法を「コンピュ−タ・シミュレ−ション」と呼ぶ.
ライフゲ−ムとは,人工知能や生物学の研究過程から生まれた細菌増殖や人口増加にヒントを得たシミュレ−ションであり,そのル−ルは極めて単純である.
シミュレ−ションは2次元平面に展開され,その平面は格子状(碁盤目状)に区切られる.区切られた部分を「セル」と呼ぶ.
セルは2つの状態がある.一つは「死」,もう一つは「生」である.
各セルは以下のル−ルに従って一定時間後に状態を変化させる.セルの状態は全てのセルで一斉に次の状態へ変化するものとする.
ここで,ある一つのセルXに注目する.Xの次の状態はXを取り囲んで隣接する8個のセルの状態によって決まる.
上記の条件を簡単に図示すると以下のようになる.この図で赤は死状態のセル,青は生状態のセルを表し,中央のX記号のついたセルが次の状態でどの状態に変化するかが図の下に記されている.
但し,セル全体の領域を考えると最も外側に位置するセルに限っては隣接するセルが無いので困ってしまう.これら外周部のセルについては,その外側は死んだままのセルになっていると考えるものとする.
例えば,3行×3列のセルがあるとする.初期状態が以下の図の左端のような状態であったとしよう.この図で赤は死状態,青は生状態とする.
この場合,初期状態の次にはStep1のような生死状態となり,その次はStep2, さらにその次はStep3というように,各セルの状態は段階を追って変化してゆく.
ライフゲ−ムを実現するシミュレ−ションプログラムを作成せよ.
そのプログラムは次のような機能仕様を実現すること.
いきなり,完成したプログラムが頭の中から湧いてくる訳はない.プログラム中でどんな事を実現すれば良いか,その構成要素に分解して,それぞれを一つ一つ実現する事を考える.また,その構成要素が大きい(複雑)と思えば,それをさらに細かい(より単純な)構成要素に分解して考えるというのが,プログラムを設計する時の基本的な態度である.
その構成要素は,概ね以下のようになるだろう.
セルの生死は2つのどちらかである.コンピュータで「二つのどちらか」という情報を表現するのは,数値(整数)の0と1で表現すれば良さそうだ.また,セル領域はセルが二次元状に並んでいるものだから,整数が二次元状に並んだもの,つまり「二次元配列」を使って表現すれば良さそうだ.
各セルは自分の周りにあるセルの「前の状態から次の状態が決まる」ので,配列を2組用意しておいて,片方を「前の状態」,他方を「後の状態」を表すものとして使えば良いだろう.
前状態を表す配列の各要素は各セルの状態を表しているはずだから,それらを使って,次のセル状態を表す配列の要素が「次の状態ではどうなるか?」を考慮して,それぞれ計算していけば,「次状態のセル全体」を表す配列の内容を作り上げる事が出来る.
さらに次の状態変化を計算する時には,「次の状態」を表す配列の内容を「前の状態」を表す配列に,一旦,写してから改めて計算するか,或いは,2つの配列の「役割を入れ替える」ように考えれば良いだろう.
本課題のプログラムはどのような初期状態でも動作するように作成しておいて,起動した時点で外部から「セル全体の初期状態」を外部から与えるように作成しないと融通が利かないプログラムになってしまう.
ただし,C言語には動作に必要なデータをファイルから読み込むという機能(fscanf関数など)が用意されているが,もう少しC言語の学習を進めた後でないと,少し難しいだろう.(ちなみに,C言語の「ファイル読み込み」に用意されているfscanf関数などについては,秋学期に詳しく学習する.)
ここでは,既に学習したscanf関数を使って何とかする事を考える.
実はscanf関数は,非常に多彩な使い方が出来る機能を本来持っている.その一つに複数のデータを一行で読み取るというものがある.例えば,
int x, y, z; …… …… …… scanf("%d %d %d", &x, &y, &z);
とすると,変数x, y, zに対して,3つ整数を空白文字で区切った一行をキーボードから入力すると,一気に入力する事が出来たりする.
この機能を使ったサンプルプログラムが
/usr/local/cse/class/oomoto/program/lifegame/scanf_triple.c
として置いてあるから,各自コンパイルして動作確認してみよう.
また,3行×3列の二次元整数配列に対して,各要素の値を各要素毎に
縦要素番号[空白]横要素番号[空白]要素の値
という形式で作成したサンプルデータファイルとそれを読み込んで配列要素に格納するサンプルプログラム
/usr/local/cse/class/oomoto/program/lifegame/matrix.dat
/usr/local/cse/class/oomoto/program/lifegame/scanf_advance.c
が置いてあるからコンパイルして試してみよう.
このサンプルプログラムでは,9個分の配列要素の値をキーボードから入力しなければならず,そのままだと入力が面倒だったり,或いは,タイプミスで上手く動かないといった問題が起きてしまうが,この問題に対しては
./scanf_advance < matrix.dat
という具合に,コマンド操作での「入力リダイレクション」を使えば,プログラムを実行中にキーボード入力の代わりに予め用意しておいたデータファイルmatrix.datからデータを読み取らせる事が出来る.
セル全体について次状態(つまり配列要素の値)を計算する度に,各セル状態(0か1)を表す図形を「碁盤目状に上手く並べて描画」すれば良いだろう.また,各図形の状態(色や形など)を2つ考えて,それを各セルの状態に対応させれば上手くグラフィック表現出来そうだ.その図形としては円や正方形が一番簡単そうだが別にどのように図示しても構わない.
さらに,全セル状態は二次元配列で表されて,二次元配列の要素を特定するのは2つの整数による要素番号の対(0, 1)や(5, 4)などで出来るから.結局,配列の要素番号(i, j)から,その配列が表すセル状態に対応する図形を描く座標位置(x, y)を上手に計算して,その座標位置に何かの図形を描画すれば良い事になる.
また,セルの状態は生か死のどちらかなので,「それぞれの状態をどんな図形で表すか?」というのは,各自工夫してみよう.
ここで,各セルをグラフィック配置した時,
垂直方向(上から下)の配置順: 二次元配列の最初の添え字 水平方向(左から右)の配置順: 二次元配列の二番目の添え字
で表すとしておこう.
以上の考え方を図示すると次のようになる.以下の図で図形の描画間隔はHとWとする.
図中の直線の交点座標(x, y)と各セルを表す配列要素番号(i, j)の対応関係から,
x = jを使った式 y = iを使った式
と考えれば,iとjからxとyを計算出来る事になる.(尚,これらの式は高校数学の「等差数列」の概念を使って表現出来る.)
ちなみに,上記のxとyの式は線形代数の行列式として表現する事が出来るが,この考え方はコンピュータグラフィックス分野では,「アフィン変換」と呼ばれる最も基本的な概念の一つに繋がっている.コンピュータの知識だけではなく数学や物理の基本素養も色々なプログラミングには必要になってくる事があるので,しっかりと勉強しておきましょう.
尚,HandyGraphicを適当な時間だけ停止させるやり方は,アニメーション課題に取り組んだ時に手法を学んだはずです.
作成したソースプログラムは,以下のテスト用データで動作をした上でmoodle学習支援システムにて提出せよ.尚,提出する際にはテストデータ2に対して動作するものを提出すること.
テストデータ0: /usr/local/cse/class/oomoto/program/lifegame/small.dat (上記の「セル状態変化の例」の図における初期状態,セル領域サイズ3×3)
テストデータ1: /usr/local/cse/class/oomoto/program/lifegame/clock.dat (時計のようにくるくる回転するパターン,セル領域サイズ6×6)
テストデータ2: /usr/local/cse/class/oomoto/program/lifegame/glider.dat (グライダーのように領域を移動する,セル領域サイズ16×16)
テストデータ3: /usr/local/cse/class/oomoto/program/lifegame/pulser.dat(周期的に振動する,セル領域サイズ15×15)
テストデータ4: /usr/local/cse/class/oomoto/program/lifegame/glider_gun.dat(グライダー銃,無限にグライダーを生成し続ける,セル領域サイズ38×38)
ちなみに,clock.datのセル初期状態(6行6列)は,以下のようになる.(但し,○が死,◆が生に対応)
○○○○○○ ○○◆○○○ ○○○◆◆○ ○◆◆○○○ ○○○◆○○ ○○○○○○
レポ−ト名:program/lifegame
提出期限:8/4(日) 24:00
まず最初に一言.「インターネットを検索してはいけません!」
ライブゲームは非常に有名な問題で昔から各所でプログラミング課題として使われてきているので,もしかすると誰かが作成したプログラムが見つかるかも知れません.
しかし,インターネットは「教員も検索できる」のです.君が見つけたプログラムはこちらも簡単に見つける事が出来ます.また,そのプログラムは本課題として与えられた仕様を満たしてはいないはずで,恐らく満足にコンパイルも出来ないようなものでしょう.
この課題は,かなりハードルが高いのですが真剣に取り組む事が出来れば,身に付くものはとても大きいと思います.
意欲はあるが,あと一歩が及ばない......でも何とか頑張りたいと思うチャレンジャーは以下の電子メールアドレスへメールで相談してください.
そのようなチャレンジャーが何名か出現するようであれば,「相談会」とか「勉強会」など,授業とは無関係に何かの対応があると思います.